[Exceptional C++ Style] Item 21: Containers in Memory, Part 2: How Big Is It Really?

[Ric Parkin]

From: Kevlin Henney <kevlin at curbralan.com>
> >- deque<T> is like a list of vectors -- elements live on 'pages' 
> >(supposedly) several at a time, and those pages are linked.  The amount 
> >of overhead will depend on the item count for a page, and can be as 
> >small as 1/32 bit per element.
> 
> Actually, a deque is more like a vector of equal-sized arrays than a 
> list of vectors. It is an important assumption for the implementation 
> and interface of a deque that the pages are the same size.

Checking the book, it doesn't actually say a list of vectors, but actually "...thought of as a vector<T> whose internal storage is broken up into chunks".



And further to my comment about vector's extra overhead for expansion, I can see that deque has the extra unused space in a chunk, which on average will be half a chunk.


However, thinking about it, these extra spaces probably shouldn't count as 'per element' overhead. Perhaps "spare capacity" overhead?

Also, the item's second question just focuses on per-element container requirements. 

There's potentially plenty more sources of overhead - spare capacity; per allocation request in the container's allocator, new/malloc, and the OS. This is all hinted at by part 1's discussion of the layers of memory management, but part 2 didn't really consider all of these other bits, but concentrated on the container.

I also tend to think of container overheads in terms of allocation per element - list/map etc can be much slower and have more overheads than vector and deque because of the individual allocations for each element instead of getting a bulk discount.

The final guideline is well said though - these details need to be known if you want to know what you're actually getting.

Ric






-----------------------------------------
Email provided by http://www.ntlhome.com/