> In my opinion, hash tables, btrees and the like in the standard library should probably swap to flat lists internally when the number of items in the collection is small. I'm surprised more libraries don't do that.

If I recall correctly, the STL provides guarantees that prevents it from taking advantage of flat lists. I think some containers (not arrays) guarantee that they don't move the address of whatever they're containing, even if you insert or remove elements. Even if they switched to flat lists, it would be a flat list of pointers, with all the incurred overhead.

Likewise, I believe I have heard of small string optimisation being impossible with std::string for similar reasons.

> Likewise, I believe I have heard of small string optimisation being impossible with std::string for similar reasons.

not impossible, SSO is implemented to some extent in most mainstream c++ compilers.

I thought that was impossible because it breaks references when moving strings.

I don't see why this would happen. what problems are you envisioning? moves should leave the original object in a valid but unspecified state. that is, a move should not break a reference to the original object itself, but there are no guarantees as to what data it contains afterwards. in the case of a dynamically allocated string, the moved-from object would probably be empty. with SSO, a move is necessarily a copy, so the moved-from string could either be empty or just contain stale data.

are you maybe thinking of iterators? you have to assume iterators are invalid after a move.

No, I think the requirement is that a reference to the actual string buffer must be kept valid when the string is moved. And that property breaks with SSO data, which is not placed in the dynamically allocated buffer - it is placed directly in the object struct (it's an optimization after all), which can't be moved.

EDIT: seems I was wrong, and SSO is allowed for std::string. A similar optimization is illegal for std::vector, though, for the reasons I gave above.

I seem to recall some of this related to absl's flat_hash_map and co. They can't be stdlib compatible because there are api concerns that the std implementations provide (but that in practice no one uses) that result in real world performance being left on the table.

Specifically, the bucket interface: https://en.cppreference.com/w/cpp/container/unordered_map#Bu...

Yes, the address of any element of an std::map is valid until that element is erased.

Thank you, I tried the rope, and I ran a benchmark that creates a rope of length 1G by repeatedly inserting 1023 bytes at random positions. Some notes:

When I changed the hardcoded node size from 136 to 1024 bytes, time went down from 3.6 secs to 2.6 secs on my laptop. It kind of plateaued at 1024 bytes. I didn't do more extensive testing.

What's the rationale for the choice of 136? A cache line is usually 64, so the CPU will always end up loading a multiple of that in any case.

When I did a rope implementation myself (I don't know how it compares in terms of performance) I think I ended up with nodes of 4096 or 8192 bytes size. That was based on a Red-black tree. When I load ~1Gig of data, even with a node size of 4096, there will still be 2^18 nodes, meaning each access requires sth. like 17 child traversals, which seems a lot to me. So I can't see myself going down to 200 bytes or less.

Oh interesting! What CPU was that on? 136 the optimal number I found benchmarking on an old intel based laptop I was using a few years ago. I wonder if modern CPUs (with much larger caches) have changed the ideal array size.

This was on a Sandybridge Laptop from 2011: Intel(R) Core(TM) i5-2520M CPU @ 2.50GHz. If I read right, it has 256KB and 3MB L1 and L2 caches

Here's an article about how NSArray on MacOS does something similar:

https://ridiculousfish.com/blog/posts/array.html

In the sense of swapping the underlying implementation as the number of items in the collection increases.