<deque>: Needs a major performance overhaul

[StephanTLavavej]

deque has long-standing performance problems, including but not limited to its choice of a very small block size. Unlike all other containers, deque::iterator always uses the proxy object, further adding to its complexity. When we can break binary compatibility in the vNext release, we need to eliminate deque's proxy (as we've already done for all other containers in debug mode, except vector<bool>), retune the block size, and generally rethink deque from scratch.

Also tracked by Microsoft-internal VSO-102760 / AB#102760.

vNext note: Resolving this issue will require breaking binary compatibility. We won't be able to accept pull requests for this issue until the vNext branch is available. See #169 for more information.

[bubnikv]

The current block size is tragically small: For more than two int32 values or for a single int64 the deque degenerates to a vector of pointers. Thus for all practical purposes, on MSVC deque IS a vector of pointers, which defeats its purpose of reducing allocator load and memory fragmentation.

https://github.com/microsoft/STL/blob/main/stl/inc/deque#L561

while GCC 4.6.3 allocates blocks of 512 bytes:

#define _GLIBCXX_DEQUE_BUF_SIZE 512
inline size_t
  __deque_buf_size(size_t __size)
 { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
     ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }

https://gcc.gnu.org/onlinedocs/gcc-4.6.3/libstdc++/api/a01049_source.html

boost::deque uses a similar logic and block size as the glibc implementation above.

[frederick-vs-ja]

Currently, both checked and unchecked iterators of MSVC STL's deque add one more layer of indirection. It seems that we can add simpler iterator types that hold the _Mapptr and the offset before vNext and use them internally. I don't know whether we can directly change unchecked iterators now.

[Seneral]

The tiny block size of MSVC's implementation is just utterly baffling.
Whoever made that choice actively contributed to make the world that much harder for devs, and should be ashamed.
Please fix this - in my limited knowledge I don't see how this could possibly be an ABI breaking change, but you had plenty choice to fix this even if it was, and you didn't.
For now, I gotta keep using my own implementation, or just accept that windows users get a less optimised experience.

[AmmoniumX]

Is this still not fixed as of VS 2026? I think this issue is more serious than what people realize, it makes any code that relies heavily on std::deque have significantly worse performance on MSVC, leading developers away from using the simple STL provided container and having to instead replace itwith alternatives such as Boost deque project-wide, purely because of the significant performance penalty on MSVC

[StephanTLavavej]

No, this is definitely 100% blocked on breaking ABI, and the MSVC Build Tools 14.5x in VS 2026 18.x remain ABI-compatible with the v14 release series. We've found clever ways to fix issues that were previously thought to be ABI-sensitive, but deque's representation is by definition part of the ABI and there's no clever way to get around that. Sorry. (If starting vNext were up to me, I would do it in a flash.)

[AmmoniumX]

No, this is definitely 100% blocked on breaking ABI, and the MSVC Build Tools 14.5x in VS 2026 18.x remain ABI-compatible with the v14 release series. We've found clever ways to fix issues that were previously thought to be ABI-sensitive, but deque's representation is by definition part of the ABI and there's no clever way to get around that. Sorry. (If starting vNext were up to me, I would do it in a flash.)

Thanks for the info. As long as people are aware that this is an issue and there are still plans to fix it eventually, that's understandable. I'd just hate this to be one of those problems that have existed for so long, people just accept it for what it is and don't even bother trying to fix it, and 2 years of silence on the issue post wasn't very reassuring 🫠