Martin Leitner-AnkerlJan 4, 2023

Working on an alternative std::vector implementation that's not contiguous and can be the base for my ankerl::unordered_dense::map. https://github.com/martinus/unordered_dense

The big advantage is it doesn't have allocation spikes. Surprisingly, insertion is faster because no elements have to be moved around #cpp

GitHub - martinus/unordered_dense: A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion

A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion - martinus/unordered_dense

GitHub
Show threadDarrellJan 4, 2023
@martinus How does it compare to something like boost::deque/devector or libcxx's std::deque. Seems to be an alternative to that instead of vector who's defining characteristic is contiguous
Show threadMartin Leitner-AnkerlJan 5, 2023

@beached_whale I originally tried to use std::deque but its operator[] performance is a lot slower. It seems deque is optimized at push/poping on both ends, but I need very fast indexing performance.

With my container indexing is only ~5% slower than with std::vector or so in my benchmarks

Show threadMartin Leitner-AnkerlJan 5, 2023
@beached_whale See here for assembler generated for indexing: https://godbolt.org/z/vz4fvbxGd
Compiler Explorer - C++

int const& index_vector(std::vector<int> const& v, size_t idx) { return v[idx]; } int const& index_deque(std::deque<int> const& v, size_t idx) { return v[idx]; } int const& index_segmented_vector(ankerl::segmented_vector<int> const& v, size_t idx) { return v[idx]; }

Show threadDarrellJan 6, 2023
@martinus This is why I said libcxx's deque, it's using 4k blocks, not 512byte, or 64byte as libstdc++ and MS STL do. The asm is much better https://godbolt.org/z/r5af88hEf
Compiler Explorer - C++

int const& index_vector(std::vector<int> const& v, size_t idx) { return v[idx]; } int const& index_deque(std::deque<int> const& v, size_t idx) { return v[idx]; } int const& index_segmented_vector(ankerl::segmented_vector<int> const& v, size_t idx) { return v[idx]; }

Show threadMartin Leitner-AnkerlJan 6, 2023
@beached_whale Ah, nice. Unfortunately I can't use libc++ everywhere, it still misses lots of stuff.
Show threadMartin Leitner-Ankerl

@beached_whale Also, it seems the generated code is worse when using e.g. std::string as the type, then std::deque is not using power of 2 which would be faster. Although the size of the allocated blocks won't that close to 4k any more

https://godbolt.org/z/PsG1zjx1s

Compiler Explorer - C++

using T = std::string; //using T = int; T const& index_vector(std::vector<T> const& v, size_t idx) { return v[idx]; } T const& index_deque(std::deque<T> const& v, size_t idx) { return v[idx]; } T const& index_segmented_vector(ankerl::segmented_vector<T> const& v, size_t idx) { return v[idx]; } auto size_of_t() { return sizeof(T); }

Jan 6, 2023 at 11:22amWeb
Show threadDarrellJan 6, 2023

@martinus If I remember correctly it's something like 4096/sizeof(T), not 4k items. Yeah. libcxx is just better than the other std implementations for cost of allocation(assuming that push_front/pop_front are not dominant).

I wonder what boost is using for their new flat map

---
Just realized I was thinking out loud and not really making a point