3 ms·

> 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 collecti

> 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.

joshuamorton 6y ago
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.
- slavik81 6y ago
  Specifically, the bucket interface: https://en.cppreference.com/w/cpp/container/unordered_map#Bucket_interface https://en.cppreference.com/w/cpp/container/unordered_map#Bu...
frutiger 6y ago
Yes, the address of any element of an std::map is valid until that element is erased.
leetcrew 6y ago
> 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.
- jstimpfle 6y ago
  I thought that was impossible because it breaks references when moving strings.
  - leetcrew 6y ago
    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.
    - jstimpfle 6y ago
      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.

joshuamorton 6y ago

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.

slavik81 6y ago
Specifically, the bucket interface: https://en.cppreference.com/w/cpp/container/unordered_map#Bucket_interface https://en.cppreference.com/w/cpp/container/unordered_map#Bu...

frutiger 6y ago

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

leetcrew 6y ago

> 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.

jstimpfle 6y ago
I thought that was impossible because it breaks references when moving strings.
- leetcrew 6y ago
  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.
  - jstimpfle 6y ago
    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.