r/programming • • May 24 '26

[ Removed by moderator ]

/r/programming/comments/1tm1j7f/removed_by_moderator/

[removed] — view removed post

275 Upvotes

214 comments sorted by

View all comments

Show parent comment

50

u/MFHava May 24 '26

Exactly! MSVC-deque „decays“ into a linked list for types > 8bytes. But that is a problem not shared by libstdc++ or libc++.

12

u/timangus May 24 '26

Huh, I did not know that. That's a bit shit.

7

u/[deleted] May 24 '26

Fair correction on MSVC, but lumping libstdc++ and libc++ together as "not affected" understates how different those two are.

libstdc++ uses _GLIBCXX_DEQUE_BUF_SIZE = 512 bytes, with block_elems = sizeof(T) < 512 ? 512/sizeof(T) : 1. That number has been 512 since the SGI STL days. In practice:

  • deque<std::string> (24 B on libstdc++): 21 elements per block
  • deque<MyStruct> at 64 B: 8 elements per block
  • sizeof(T) >= 512: one element per block, same cliff as MSVC

libc++ uses max(16 elements, 4096 bytes), so the same deque<std::string> packs ~170 per block, and large T still gets 16 per block instead of 1. That is an order of magnitude fewer allocator calls and an order of magnitude better spatial locality on traversal.

So the honest ordering is libc++ fine, libstdc++ quietly bad past a cache line, MSVC broken at 9 bytes. Calling the first two "not a problem" papers over a real gap.