Why is the efficiency of std::deque so poor?

Question

I wanted to use std::deque, but the overhead memory consumed seems too excessive. Am I doing something incorrectly?

#include "windows.h"
#include "psapi.h"

#include <iostream>
#include <vector>
#include <queue>

int main (int, char* [])
{
    PROCESS_MEMORY_COUNTERS pm;
    GetProcessMemoryInfo(GetCurrentProcess(), &pm, sizeof(pm));
    size_t mem1 = pm.WorkingSetSize;

    std::vector<int> v( 10000000 );

    GetProcessMemoryInfo(GetCurrentProcess(), &pm, sizeof(pm));
    size_t mem2 = pm.WorkingSetSize;

    std::deque<int> q( 10000000 );
    GetProcessMemoryInfo(GetCurrentProcess(), &pm, sizeof(pm));
    size_t mem3 = pm.WorkingSetSize;

    std::cout << mem2 - mem1 << std::endl;
    std::cout << mem3 - mem2 << std::endl;

    return 0;
}

Output (on a 32-bit Windows system):

40087552
72564736

Bonus question: Why is mem2 - mem1 not exactly 40000000?

@KonradRudolph: Well, Microsoft owns the code now, Dinkumware wrote it first. `deque` is using "blocks" of 16 bytes compared to GCC's 512. For very small sets it's a lot less overhead. For medium or large sets... — Mooing Duck, May 24 '13 at 21:07
@MooingDuck [I know that.](http://stackoverflow.com/a/6292437/1968) I meant, as an answer. — Konrad Rudolph, May 24 '13 at 21:08
oh, that makes sense. I think the answers and aschepler's link are sufficient that I don't have to stop being lazy. — Mooing Duck, May 24 '13 at 21:09
Hmmm, Herb Sutter says [In Most Cases, Prefer Using deque vs. vector (Controversial)](http://www.gotw.ca/gotw/054.htm). But it's sounding like the use of `std::deque` isn't such a good idea on Windows. — DavidRR, May 24 '13 at 21:54
@DavidRR In its book **More Exceptional C++**, Herb Sutter says to prefer `vector` and the book was done later. — Phil1970, Jul 23 '17 at 00:18

score 4 · Answer 1 · edited May 24 '13 at 20:54

I don't think deques are allocated in continuous memory blocks. From (http://www.cplusplus.com/reference/deque/deque/):

Both vectors and deques provide a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors use a single array that needs to be occasionally reallocated for growth, the elements of a deque can be scattered in different chunks of storage, with the container keeping the necessary information internally to provide direct access to any of its elements in constant time and with a uniform sequential interface. Therefore, deques are a little more complex internally than vectors, but this allows them to grow more efficiently under certain circumstances, especially with very long sequences, where reallocations become more expensive.

score 2 · Answer 2 · edited May 23 '17 at 10:25

As has been mentioned previously a deque is not allocated in contiguous blocks of memory. It has to keep data to track where the blocks of memory are. The specifics are implementation dependent, but some details can be found in STL internals: deque implementation

Working set is the amount of physical memory being used. From the working set documentation.

The working set of a process is the set of pages in the virtual address space of the process that are currently resident in physical memory.

Chances are that some memory has been paged out to disk, which adds to the discrepency.

There are a few reasons mem2 - mem1 does not equal 40000000. Simply the std::vector object probably has additional member variables. It may keep track of size variables and begin and end iterators. Another reason is that the Windows heap will also need to keep track of its memory and this requires memory to do that.

From Managing Heap Memory

In reality, though, the heap manager requires additional memory for managing the memory in the heap. So instead of allocating only 100 bytes as requested, it also allocates some space for managing each particular chunk of memory. The type of memory and the size of the allocation determine the size of this additional memory.

You can try this, by replacing the std::vector<int> with int* v = new int[10000000]; and you'll see that the memory difference is over 40000000 bytes.

Actually a linked list can't be used, since a `deque` is required to have random-access iterators. — Ben Voigt, May 24 '13 at 21:16
@BenVoigt thanks for the correction, I've corrected my answer. — Steve, May 24 '13 at 21:19
@MooingDuck that's taken into account by measuring `mem1` immediately before creating the `vector` and then measuring `mem2` straight after. I don't think the memory used by either of those components would have changed in that time. Unless I've missed something? — Steve, May 24 '13 at 21:52

Why is the efficiency of std::deque so poor?

2 Answers2