{"id":108587,"date":"2023-08-10T07:00:00","date_gmt":"2023-08-10T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=108587"},"modified":"2023-08-10T11:47:22","modified_gmt":"2023-08-10T18:47:22","slug":"20230810-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20230810-00\/?p=108587","title":{"rendered":"Inside STL: The deque, implementation"},"content":{"rendered":"

Now that we understand the design behind the common STL dequeue implementations<\/a>, we can peek into the implementation details.<\/p>\n

All three of the major implementations of the standard library maintain an array of pointers to blocks, which they confusingly call a “map” even though it is unrelated to std::map<\/code>. (Even more confusingly, gcc internally uses the term “node” instead of “block”.) Initially, all the pointers in the map are nullptr<\/code>, and the blocks are allocated only on demand.<\/p>\n

We will say that a block is spare<\/i> if it contains only spare elements.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
\u00a0<\/th>\ngcc<\/th>\nclang<\/th>\nmsvc<\/th>\n<\/tr>\n
Block size<\/td>\nas many as fit in 512 bytes but at least 1 element<\/td>\nas many as fit in 4096 bytes but at least 16 elements<\/td>\npower of 2 that fits in 16 bytes but at least 1 element<\/td>\n<\/tr>\n
Initial map size<\/td>\n8<\/td>\n2<\/td>\n8<\/td>\n<\/tr>\n
Map growth<\/td>\n2\u00d7<\/td>\n2\u00d7<\/td>\n2\u00d7<\/td>\n<\/tr>\n
Map shrinkage<\/td>\nOn request<\/td>\nOn request<\/td>\nOn request<\/td>\n<\/tr>\n
Initial first\/last<\/td>\nCenter<\/td>\nStart<\/td>\nStart<\/td>\n<\/tr>\n
Members<\/td>\nblock** map;<\/p>\n

\nsize_t map_size;
\niterator first;
\niterator last;<\/tt><\/td>\n

block** map;
\nblock** first_block;
\nblock** last_block;
\nblock** end_block;
\nsize_t first;
\nsize_t size;<\/tt><\/td>\n		block** map;<\/p>\n

\nsize_t map_size;
\nsize_t first;
\nsize_t size;<\/tt><\/td>\n<\/tr>\n

Map layout<\/td>\ncounted array<\/td>\nsimple_deque<\/tt><\/td>\ncounted array<\/td>\n<\/tr>\n
Valid range<\/td>\nPair of iterators<\/td>\nStart and count<\/td>\nStart and count<\/td>\n<\/tr>\n
Iterator<\/td>\nT* current;
\nT* current_block_begin;
\nT* current_block_end;
\nblock** current_block;<\/tt><\/td>\n		T* current;<\/p>\n

\nblock** current_block;<\/td>\n

deque* parent;
\nsize_t index;<\/tt><\/td>\n<\/tr>\n
begin()<\/code> \/
\nend()<\/code><\/td>\n		Copy first<\/code> and last<\/code>.<\/td>\nBreak first<\/code> and first + size<\/code> into block index and offset.<\/td>\nBreak first<\/code> and first + size<\/code> into block index and offset.<\/td>\n<\/tr>\n
Spare blocks<\/td>\nAggressively pruned<\/td>\nKeep one on each end<\/td>\nKeep all<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

The Microsoft Visual C++ implementation has a tiny block size. I suspect this decision was made a long time ago, and the Visual C++ folks are anxious to bump up the block size at the next ABI break.<\/p>\n

The gcc implementation doesn’t believe in spare blocks; it frees blocks as soon as they become empty. The clang and Visual C++ implementations hold onto spare blocks in anticipation that they will be needed again soon. The clang implementation retains one spare block at each end, whereas the Visual C++ implementation retains all spare blocks. (I suspect this is another old design decision that the Visual C++ team wants to change at the next ABI break.)<\/p>\n

If the clang implementation needs to allocate a new block at one end, it first checks to see if there is a spare block at the other end. If so, then it moves that block from one end to the other instead of allocating a new block.<\/p>\n

The Microsoft Visual C++ implementation treats the map as a circular<\/i> array of blocks. This means that once the map is filled with blocks, no further allocations or element movement is needed to satisfy any further deque operations, assuming the size of the dequeue never exceeds the capacity.<\/p>\n

None of the three implementations shrinks the map automatically. You have to call shrink_to_fit()<\/code> to get the map to shrink.<\/p>\n

All three implementations keep track of the blocks differently. The gcc and Visual C++ implementations use a simple counted array. If the gcc implementation runs out of map entries at one end, it slides the in-use blocks so that they are centered in the block map. The Visual C++ implementation uses a circular buffer, so the only time it runs out of map entries is when the entire map needs to be expanded. The clang implementation gets fancy and uses the equivalent of our simple_deque<\/code> for its map. This allows it to use the “slide” trick to shift an empty slot from one end to the other.<\/p>\n

All three implementations choose different formats for their iterators. The gcc and clang implementations use a pointer to the current element and a pointer to the current block. When incrementing or decrementing off the end of the block, they increment or decrement the current_block<\/code> to find the next block. The gcc implementation carries extra values current_block_begin<\/code> and current_block_end<\/code>, which are technically redundant, since you can derive<\/p>\n

    \n
  • current_block_begin = *current_block;<\/code><\/li>\n
  • current_block_end = current_block_begin + block_size;<\/code><\/li>\n<\/ul>\n

    Not only are these iterators bulky (presumably for performance?), but the gcc implementation stores these bulky iterators in its deque<\/code>, whereas clang and Visual C++ use an index and length. Accessing an element by index involves dividing by the block size. This means that clang’s begin()<\/code> and end()<\/code> incur a runtime division to calculate which block the element is in and using the remainder to get the offset within the block. Visual C++ forces block sizes to be powers of two, so it can use bitwise operations to break the index into a block and offset.<\/p>\n

    Here’s a visualization of what the three deque<\/code> implementations look like if you alternately pop from the front and push to the back:<\/p>\n

    First, here’s what gcc’s implementation does.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    map[0]<\/td>\n <\/td>\nmap[1]<\/td>\n <\/td>\nmap[2]<\/td>\n <\/td>\nmap[3]<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\nA<\/td>\n <\/td>\nB<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n1<\/td>\n <\/td>\n2<\/td>\n3<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    pop 1 from the front: Free block A<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\nB<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n2<\/td>\n3<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    push 4 to the back: Allocate block C<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\nB<\/td>\n <\/td>\nC<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\n2<\/td>\n3<\/td>\n <\/td>\n4<\/td>\n\u00a0<\/td>\n<\/tr>\n
    pop 2 from the front<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\nB<\/td>\n <\/td>\nC<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n3<\/td>\n <\/td>\n4<\/td>\n\u00a0<\/td>\n<\/tr>\n
    push 5 to the back<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\nB<\/td>\n <\/td>\nC<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n3<\/td>\n <\/td>\n4<\/td>\n5<\/td>\n<\/tr>\n
    pop 3 from the front: Free block B<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\nB<\/td>\n <\/td>\nC<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n4<\/td>\n5<\/td>\n<\/tr>\n
    push 6 to the back: Allocate block D and slide<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\nC<\/td>\n <\/td>\nD<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n4<\/td>\n5<\/td>\n <\/td>\n6<\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    The eager pruning of empty blocks in gcc means that we free a block, only to immediately allocate a new one.<\/p>\n

    Here’s what clang does when you alternate pops and pushes:<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    map[0]<\/td>\n <\/td>\nmap[1]<\/td>\n <\/td>\nmap[2]<\/td>\n <\/td>\nmap[3]<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\nA<\/td>\n <\/td>\nB<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n1<\/td>\n <\/td>\n2<\/td>\n3<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    pop 1 from the front: Block A becomes spare<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\nA<\/td>\n <\/td>\nB<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n2<\/td>\n3<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    push 4 to the back: Steal block A<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\nB<\/td>\n <\/td>\nA<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\n2<\/td>\n3<\/td>\n <\/td>\n4<\/td>\n\u00a0<\/td>\n<\/tr>\n
    pop 2 from the front<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\nB<\/td>\n <\/td>\nA<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n3<\/td>\n <\/td>\n4<\/td>\n\u00a0<\/td>\n<\/tr>\n
    push 5 to the back<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\nB<\/td>\n <\/td>\nA<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n3<\/td>\n <\/td>\n4<\/td>\n5<\/td>\n<\/tr>\n
    pop 3 from the front: Block B becomes spare<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\nB<\/td>\n <\/td>\nA<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n4<\/td>\n5<\/td>\n<\/tr>\n
    push 6 to the back: Steal block B and slide<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\nA<\/td>\n <\/td>\nB<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    \u00a0<\/td>\n <\/td>\n4<\/td>\n5<\/td>\n <\/td>\n6<\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    Since clang keeps a one-block spare, the growth on the back can be satisfied by stealing the spare block from the front. No new memory allocations are performed; just block sliding.<\/p>\n

    And here’s what Visual C++ does. Note that Visual C++ always pushes starting at the start of the map, so getting to the initial state means that we have already popped three elements from the front, leaving a spare block A.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
    map[0]<\/td>\n <\/td>\nmap[1]<\/td>\n <\/td>\nmap[2]<\/td>\n <\/td>\nmap[3]<\/td>\n<\/tr>\n
    A<\/td>\n <\/td>\nB<\/td>\n <\/td>\nC<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    \u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n1<\/td>\n <\/td>\n2<\/td>\n3<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    pop 1 from the front: Block B becomes spare<\/td>\n<\/tr>\n
    A<\/td>\n <\/td>\nB<\/td>\n <\/td>\nC<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    \u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n2<\/td>\n3<\/td>\n <\/td>\n\u00a0<\/td>\n<\/tr>\n
    push 4 to the back: Allocate block D<\/td>\n<\/tr>\n
    A<\/td>\n <\/td>\nB<\/td>\n <\/td>\nC<\/td>\n <\/td>\nD<\/td>\n<\/tr>\n
    \u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n2<\/td>\n3<\/td>\n <\/td>\n4<\/td>\n\u00a0<\/td>\n<\/tr>\n
    pop 2 from the front<\/td>\n<\/tr>\n
    A<\/td>\n <\/td>\nB<\/td>\n <\/td>\nC<\/td>\n <\/td>\nD<\/td>\n<\/tr>\n
    \u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n3<\/td>\n <\/td>\n4<\/td>\n\u00a0<\/td>\n<\/tr>\n
    push 5 to the back<\/td>\n<\/tr>\n
    A<\/td>\n <\/td>\nB<\/td>\n <\/td>\nC<\/td>\n <\/td>\nD<\/td>\n<\/tr>\n
    \u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n3<\/td>\n <\/td>\n4<\/td>\n5<\/td>\n<\/tr>\n
    pop 3 from the front: Block C becomes spare<\/td>\n<\/tr>\n
    A<\/td>\n <\/td>\nB<\/td>\n <\/td>\nC<\/td>\n <\/td>\nD<\/td>\n<\/tr>\n
    \u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n4<\/td>\n5<\/td>\n<\/tr>\n
    push 6 to the back: Wrap around to block A<\/td>\n<\/tr>\n
    A<\/td>\n <\/td>\nB<\/td>\n <\/td>\nC<\/td>\n <\/td>\nD<\/td>\n<\/tr>\n
    6<\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n\u00a0<\/td>\n\u00a0<\/td>\n <\/td>\n4<\/td>\n5<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    Once you reach the steady state where all the map entries have blocks, further deque operations can be performed without any memory allocation or rearranging.<\/p>\n

    Here’s what the Microsoft Visual C++ deque looks like in the debugger with the visualizer:<\/p>\n

    d : { size = 0x2 }\r\n    [0x0] = 1 [Type: __int64]\r\n    [0x1] = 2 [Type: __int64]\r\n<\/pre>\n
    The raw view reveals the soft underbelly of the implementation.<\/p>\n
    0:000> ?? d\r\nclass std::deque<__int64,std::allocator<__int64> >\r\n   +0x000 _Mypair          : std::_Compressed_pair<std::allocator<__int64>,std::_Deque_val<std::_Deque_simple_types<__int64> >,1>\r\n0:000> ?? d._Mypair\r\nclass std::_Compressed_pair<std::allocator<__int64>,std::_Deque_val<std::_Deque_simple_types<__int64> >,1>\r\n   +0x000 _Myval2          : std::_Deque_val<std::_Deque_simple_types<__int64> >\r\n0:000> ?? d._Mypair._Myval2\r\nclass std::_Deque_val<std::_Deque_simple_types<__int64> >\r\n   +0x000 _Myproxy         : 0x000001c9`ee615540 std::_Container_proxy\r\n   +0x008 _Map             : 0x000001c9`ee6178b0  -> 0x000001c9`ee615000  -> 0n42\r\n   +0x010 _Mapsize         : 8\r\n   +0x018 _Myoff           : 3\r\n   +0x020 _Mysize          : 2\r\n0:000> dps 0x000001c9`ee6178b0 L 8\r\n000001c9`ee6178b0  000001c9`ee615000\r\n000001c9`ee6178b8  000001c9`ee615160\r\n000001c9`ee6178c0  000001c9`ee615380\r\n000001c9`ee6178c8  000001c9`ee6153c0\r\n000001c9`ee6178d0  000001c9`ee615720\r\n000001c9`ee6178d8  000001c9`ee6155e0\r\n000001c9`ee6178e0  000001c9`ee615240\r\n000001c9`ee6178e8  000001c9`ee615020\r\n0:000> dps 000001c9`ee615160 L2\r\n000001c9`ee615160  00000000`0000002a\r\n000001c9`ee615168  00000000`00000001\r\n0:000> dps 000001c9`ee615380 L2\r\n000001c9`ee615380  00000000`00000002\r\n000001c9`ee615388  00000000`00000099\r\n<\/pre>\n
    Since this is a dequeue of __int64<\/code> (8 bytes), there will be two values per 16-byte block. From the raw dump, the _Map<\/code> tells us where the block pointers are, and the _Mapsize<\/code> tells us how many. We dump the block pointers, and the _Myoff<\/code> tells us that the first valid entry is at offset 3, and the _Mysize<\/code> tells us that there are two valid entries. Therefore, the first valid entry is at offset 1 in block 1, and the second valid entry is at offset 0 in block 2.<\/p>\n
    We dump the block at index 1 and see that the value at offset 1 is 00000000`00000001<\/code>. And then we dump the block at index 2 and see that the value at offset 0 is 00000000`00000002<\/code>. We also see that the other (unused) elements in the block hold values that had previously been pushed and then popped from the deque.<\/p>\n
    Bonus chatter<\/b>: As I noted at the start of the series, the primary purpose of these articles is to explain how to extract the contents of these collection classes when you encounter them in a crash dump. I’m taking the designs as given and showing how to use them to find the data.<\/p>\n","protected":false},"excerpt":{"rendered":"
    An array of (pointers to) arrays.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-108587","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
    An array of (pointers to) arrays.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/108587","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=108587"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/108587\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=108587"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=108587"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=108587"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}