[codelobe]

My first thing is usually:

    #0: Replace the custom/proprietary Hashmap implementation with the STL version.

Once upon a time, C++ academics brow beat the lot of us into accepting Red-Black-Tree as the only Map implementation, arguing (in good faith yet from ignorance) that the "Big O" (an orgasm joke, besides others) worst case scenario (Oops, pregnancy) categorized Hash Map as O(n) on insert, etc. due to naieve implementations frequently placing hash colliding keys in a bucket via linked list or elsewise iterating to other "adjacent" buckets. Point being: The One True Objective Standard of "benchmark or die" was not considered, i.e., the average case is obviously the best deciding factor -- or, as Spock simply logic'd it, "The needs of the many outweigh the needs of the few".

Thus, it came to pass that STL was missing its Hashmap implementation; And since it is typically trivial (or a non issue) to avoid "worst case scenario" (of Waat? A Preggers Table Bucket?), e.g., use of iterative re-mapping of the hashmap. So it was that many "legacy" codebases built their own Hashmap implementations to get at that (academically forbidden) effective/average case insert/access/etc. sweet spot of constant time "O(1)" [emphasis on the scare quotes: benchmark it and see -- there is no real measure of the algo otherwise, riiight?]. Therefore, the affore-prophesied fracturing of the collections APIs via the STL's failure to fill the niche that a Hashmap would inevitably have to occupy came to pass -- Who could have forseen this?!

What is done is done. The upshot is: One can typically familiarize oneself with a legacy codebase whilst paying lip service to "future maintainability" by (albeit usually needless) replacing of custom Hashmap implementations with the one that the C++ standards body eventually accepted into the codebase despite the initial "academic" protesting too much via "Big O" notation (which is demonstrably a sex-humor-based system meant to be of little use in practical/average case world that we live in). Yes, once again the apprentice has been made the butt of the joke.

[sgerenser]

It’s unfortunate that the hashmap picked by the standards comittee (std::unordered_map) is both awkwardly named and not very performant. Still probably better than whatever was hacked up in 1998, but nowadays you can do much better for any case where performance actually mattered. Note, still don’t roll your own, but there’s plenty of options from e.g. Abseil or Facebook’s Folly.

I worked on a project a few years ago where all data was stored in hashmaps. Just swapping out std::unordered map for an optimized implementation of a robin hood hash map increased performance by something like 2x and cut memory usage in half on many larger test cases.

[bluGill]

In the mid 1990s when C++ was getting std::map and the other containers CPU caches were not a big deal. Average case was the correct thing to optimize for. These days CPU caches are a big deal and so your average case is typically dominated by CPU cache miss pipeline stalls. This means for most work you need different data structures. The world is still catching up to what this means.

[codelobe]

Well, Red-Black algos are supposed to be better at cache-locality, but I have an AVL-tree impl (ugg jokes, again: AVUL (ALV) is the "evil" tree of "forbidden" {carnal?} wisdom from The Garden of Eden, associated with Yggdrasil/Odin [a "pagan" God of Balance & Pleasure]) that has improved cache locality since its data nodes can be made to contain AvlTreeNode structure(s), and avoid copying any data, as users are made to provide node alloc/free function pointers to this C lib's Tree "constructor". This means, for real example, I have a command line option interpreter with const structures for each option, each node added to two AVL trees (to find by unicode codepoint and find by length prefixed unicode string name). C++ STL Map implementations can not conditionally generate code for const types and thus do needless coppies, whereas my C collections API causes 0 calls to malloc (vs STL's 2 mallocs per node insert). NodeAlloc is just pointer math to get at the apt AvlNode, NodeFree is NoOp.

Benchmarking the STL vs my AVL approach results in millions of times quicker cmd line opt interpretaion (for my gnu getopt replacement lib) due to reduction of pointer chasing...

And if I want to do something similar in C++ (overloading operator new), I have to instantiate multiple copies of the Tree code, one per each "class". What if I want to use my Sortable class with various allocators: OBJ cache, dynamic GC'd, static (no alloc, its in the .data section already)...? Well then I get N copies of EXACT SAME template code for no real reason, only differing in delete and new [con|de]structors. The cache-misses galore this causes isn't even fair to bench against the C w/ fn() ptr approach.

[bluGill]

Try benchmarking on something from 1995, like a 80486. Cache misses won't matter much.

[samatman]

> that the "Big O" (an orgasm joke, besides others)

> worst case scenario (Oops, pregnancy)

> (of Waat? A Preggers Table Bucket?)

> "Big O" notation (which is demonstrably a sex-humor-based system

This post reeks of obesity, desperation, poor life choices, and old-fashioned body odor.