|
Boost : |
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk