3 ms·
I don't see why I would use it over `std::deque`. It has all the same complexity properties, but better tested, included in stdlib, and supports complex objects
by theamk 2y ago
I don't see why I would use it over `std::deque`. It has all the same complexity properties, but better tested, included in stdlib, and supports complex objects. It even has OK cache locality, given it allocates data in large-ish blocks.
You should really include this in you summary table, because it'd have all the same values compared to shift-to-middle array.
And your benchmark confirm this: figure 3 does not show the raw data, but it looks like std::queue may be 8-10% slower on smaller data sizes, and 1-2% slower on larger data sizes. Such small and inconsistent differences do not indicate different O()-complexity, and likely very dependent on specific benchmark design.
Related: std::deque implementation details for various compilers: https://devblogs.microsoft.com/oldnewthing/20230810-00/?p=108587 https://devblogs.microsoft.com/oldnewthing/20230810-00/?p=10...
- jzwinck 2y agoYou say deque uses large-ish blocks but you provide documentation that it uses 512 byte blocks on GCC and MSVC is even worse. So if you're on Windows the blocks are so small the container degenerates into something like a std::list, and on non-Windows it only works well if your objects are a few bytes each.
- theamk 2y agoThe gcc's 512 byte block is actually not that bad. For cache locality, you want block size that is bigger that cache line size - and those are 64 to 128 byte range. And as for overhead, it seems like 1 pointer per block, or 1.5% for deque of pointers/integers - not a very big value. So yeah, while linked lists are bad, gcc's deque is pretty OK. For MSVC, I agree, their std::deque is pretty bad. But the title of the post isn't "a faster deque MSVC", it makes no distinction between OSes.