Re: [boost] [MultiIndex] Measuring the overhead of a multi_index_container?

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2007-09-17 10:14:20

Douglas Gregor ha escrito:

> Hello,
>
> I'm working on a project where we're watching memory usage very closely.
> We have several multi_index_containers around (they are *very* useful),
> and we would like to measure the memory overhead of these containers. Is
> there a way to determine the per-item overhead of a
> multi_index_container?

Hi Doug, I'm glad you're finding the lib useful. Memory consumption of
multi_index_containers is briefly explained at

http://boost.org/libs/multi_index/doc/performance.html#spatial_efficiency

while the program

http://boost.org/libs/multi_index/perf/test_perf.cpp

performs some actual calculations on 1- to 3-index containers (look for
multi_index_node_size.)

Basically, a node of an N-index multi_index_container holds the value_type
object plus N headers, one for each index, whose contents are as follows:

  * Ordered indices: three pointers when http://tinyurl.com/yp8h29 applies,
  three pointers plus a 2-valued enum otherwise.
  * Hashed indices: a pointer.
  * Sequenced indices: two pointers.
  * Random access indices: one pointer.

Aditionally, some types of indices maintain their own bookkeeping data
structures which add to the memory consumption of the container:

  * Hashed indices: A bucket table containing bucket_count() pointers.
  * Random access indices: An internal array of capacity() pointers.

So, the per-item overhead of each index of a multi_index_container with
n elements is (in sizeof(pointer) units):

  * Ordered: 3
  * Hashed: 1+1,33/max_load_factor() (assuming the typical occupation
  of a hash table is 0.5(1+1/GF) where GF is the table growth factor, in our
  case ~2)
  * Sequenced: 2
  * Random access: 1+0,83 (again assuming an occupation with respect
  to capacity of 0.5(1+1/GF), but thes indices use GF=1.5)

In real life, you could in principle have padding adding to the size of a
multi_index_container node, though I haven't seen them myself as all the
members involved are pointers with the same alignment requirements.
You can measure yourself the way multi_index_node_size --referred to
above-- does.

HTH,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo