27

std::deque stores elements in "buckets" (arrays) of fixed size. Different compilers use different bucket sizes:

  • MSVC: 16 bytes or element size if it's bigger
  • GCC: 512 bytes or element size if it's bigger
  • Clang: element_size < 256 ? 4096 : element_size * 16

For MSVC (especially) and GCC, if the deque element size is bigger than the hardcoded size, std::deque turns into a convoluted std::list with performance penalties in the majority of cases.

Clang does better in my opinion, no matter what the size of the deque element, the bucket will be at least 16 elements. Though the minimal bucket size of 4096 bytes can be sub-optimal in some cases for small elements.

Why doesn't std::deque have an additional template parameter for bucket size with the default value of what the vendor thinks is reasonable? This wouldn't break backward compatibility but would allow performance optimisation.

Boann
  • 48,794
  • 16
  • 117
  • 146
Andriy Tylychko
  • 15,967
  • 6
  • 64
  • 112
  • @L.F. fair point. though “buckets” are the most popular approach and the only one I’ve seen so far. A different data structure (unluckily) could ignore “bucket size”. – Andriy Tylychko Jul 14 '19 at 23:53
  • 2
    I'd always figured deque should be a middle-ground between vector and list (with some benefits of both), but benchmarks always shown it performed more poorly than I would've guessed (so I never used it), but now I wonder if thats just due to poor sizing behavior :/ – kmdreko Jul 15 '19 at 00:16
  • 3
    *std::deque turns into a convoluted std::list* I find that weird. A `dequeue` is [usually implemented as a vector of vectors](https://stackoverflow.com/a/6292401/10957435). Granted, it isn't guarenteed, but the consensus is that it's usually the best way to implement it. –  Jul 15 '19 at 04:09
  • libstdc++ (GNU) is 8 times object size. For deque less than 8 elements allocation starts in the middle of a map so it can grow both directions. (this is not related to std::map). Not sure where the 512 comes from, other than 8*8*8. https://en.cppreference.com/w/cpp/container/deque – Max Power Jun 10 '22 at 02:23

1 Answers1

15

deque is like a black box. It isn't specified how it is implemented. The implementation is free to use any technique it likes to conform to the performance requirements. Therefore, it can't take the bucket size as a template parameter.

Of course, such a data structure is useful. The standard can have chosen to provide it (under the name deque or as a new container), but they didn't. In contrast, the unordered_* containers are guaranteed to use buckets. Per [unord.req]/9:

The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket. The number of buckets is automatically increased as elements are added to an unordered associative container, so that the average number of elements per bucket is kept below a bound. Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements. For unordered_­multiset and unordered_­multimap, rehashing preserves the relative ordering of equivalent elements.

deque does not have similar wording.

L. F.
  • 19,445
  • 8
  • 48
  • 82
  • 1
    Like I understand OP's question is who benefits from a std::deque that always performs more poorly than one of std::vector, std::list, std::list of std::arrays or Boost.Circular Buffer; plus that poorness additionally differs from compiler to compiler. – Öö Tiib Jul 15 '19 at 00:39
  • 2
    So, in other words, because `std::deque` was not written at a time when cache coherency was the overwhelmingly largest factor in real-world performance. :( – s3cur3 Jul 15 '19 at 02:32
  • 1
    @ÖöTiib not exactly. there's a narrow (very narrow for MSVC) range of cases when `std::deque` can outperform `std::vector` and `std::list` at the same time. While Standard Library vendors can (and do) make default bucket size depend on element size, they don't know how many elements will be stored (order of magnitude). More elements usually ask for bigger buckets. So default size will be sub-optimal too often. An ability to specify bucket size would solve this issue. – Andriy Tylychko Jul 15 '19 at 08:55
  • @L.F. +1 as I tend to believe this was the original reason – Andriy Tylychko Jul 15 '19 at 09:02