Optimizing Open Addressing

I'm not convinced there are "a lot" of these real and common structures.

They certainly do arise, and particularly if you're also doing concurrency linked lists are attractive because a compare-exchange type mechanism is ideally suited for such structures and that has been implemented cheaply in hardware. But this article was about the default, and we don't want defaults tailored to niche uses. The default T-shirt size shouldn't be big enough for The Rock. The default ceiling height in new buildings shouldn't be 1.5 metres. The default beverage offered at your restaurant shouldn't be Mountain Dew Code Red. It's OK that these things are options, that somebody who wants them can have them, but they're bad defaults.

I'd want to see some measurements from real world projects to believe chainig should be the default. If I take, say, the Chromium codebase, and the LibreOffice codebase, and I look at places they use any type of hash table, how often are they going to be for stuff that'd be "better suited" to chaining? Am I going to consistently find 50% ? 10% ? 1% ?

Perhaps we need to start talking with actual code? Here's just a simple idea that's in my brain right now.

    template 
    struct HashNode{
        // Probably should be shared_ptr>, but that's 
        // now adding even more inefficiencies like a ref_count per element
        struct HashNode* nextPointerChain;
        Data d; // Maybe Data* d if you're sharing it with other data-structures?
    };

    template 
    struct ChainHashTable{
        HashNode theTable[size]; 
    };

    template 
    struct LinearProbingHashTable{
        Data theTable[size];
        vector occupied; // set to "size", 0 means empty and 1 means occupied
    };

nextPointerChain takes up 8 bytes, even if its nullptr. No other data-structure needs to have the nextPointerChain. If we use shared_ptr> as per typical modern C++, there's even more inefficiencies that I forgot about. EDIT: You probably can get away with unique_ptr, now that I think of it.

----------

Pointers aren't free btw. If you're sharing the pointer with many different parts of your program, that's definitely one of those things you'll want to start getting rid of. Not only does a pointer cost 8 bytes, but its also _SIGNIFICANTLY_ slower and cache-unfriendly in practice.

L1 cache works by reading data in-and-around anything you access. If you're only using 8-bytes of a cache line for pointer-indirection (8/64), you're wasting 56-bytes of your fetch.

Linear Probing is extremely fast because it tends to blitz through L1 cache thanks to locality of data. Simple Linear Probing (or Robin-hood augmented probing) is probably the fastest, and simplest, approach for modern CPUs.

Pretty much 95% of all hybrid data structures.

Now hybrid data structures are only used in systems programming, because they require to be particularly careful about object lifetime and such.

You still fail to understand what being part of multiple data structures means.

Shared pointers, separate container to check occupancy, suggesting making a container of pointers, all these things suggest you have no idea how to do hybrid data structures.

The nodes contain the data along with multiple pointers in them to chain them to various data structures they are part of (trees, lists, hash tables etc.). The object in question contains state that is several cache lines long.

You cannot just put the nodes inside your buckets as you don't get to control where the nodes are and cannot invalidate the other data structures. Though I suppose it's a possibility if you know ahead of time how many nodes you're going to need, but then in that case you may be able to go for perfect hashing to begin with (unless you're building some kind of fixed-size cache).

A given object for example can be part of several hash maps, based on the various pieces of state it is useful to index by.

In practice you'd use a pool to allocate all your nodes in blocks. There is no per-node overhead for this allocation strategy.