Why doesn't std::deque allow specifying the bucket size?

Question

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.

Answer 1

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.