STL multi_map entry size?

[rzhu]

Hi, there

I'm a beginer of STL and I have a question about the size of each map
entry. I'm using STL on Linux for string search and reverse search.
I'm using a multi_map for regular search (to handle the case of
multiple values per key) and a map for reverse search. For both maps,
the key and value types are 'string'. What I found out was that for
something as simple as a 2 character key and value size, my memory
usage is increasing at the rate of about 40 bytes per entry in the
multi_map and about 1000 bytes per entry in the map. I'm sure
something's not right but don't know where to start looking. Can
anyone point me to the right direction?

BTW, I'm using gcc 3.3.1 on linux for this program. Any suggestion is
greatly appreciated.


R. Zhu

 

[tom_usenet]

Hi, there

I'm a beginer of STL and I have a question about the size of each map
entry. I'm using STL on Linux for string search and reverse search.
I'm using a multi_map for regular search (to handle the case of
multiple values per key) and a map for reverse search. For both maps,
the key and value types are 'string'. What I found out was that for
something as simple as a 2 character key and value size, my memory
usage is increasing at the rate of about 40 bytes per entry in the
multi_map and about 1000 bytes per entry in the map. I'm sure
something's not right but don't know where to start looking. Can
anyone point me to the right direction?

BTW, I'm using gcc 3.3.1 on linux for this program. Any suggestion is
greatly appreciated.

On a typical red-black tree based implementation of map, the overhead
per node is typically: 3 pointers (to the parent and left and right
children) and a boolean indicating colour (red or black, although a
clever implementation might steal an unused bit from one of the
pointers), say 16 bytes. Additionally each node might include a
std::allocator or three (another 3-12 bytes), if the implementation
isn't optimal.

sizeof(string) is typically 12 to 48 (depending on presence of SSO,
etc.), before you add the character memory (2 bytes for your thing).

Finally, every memory allocation using :perator new has perhaps 16
bytes of book-keeping associated with it, though this is very
implementation dependent.

The 1000 bytes per map entry seems high - but lets examine it:

The sizeof the map node will be 32? + sizeof(pair<string, string>) or,
say, 96 bytes. With allocation overhead, say 112 bytes.

The two strings add about 20 bytes each, giving a total of 150 bytes.
Are you sure about the 1000? How are you measuring?

multimap is a bit different in that you get a node for a particular
key, and then additional values for the same key incur overhead in the
same way as a linked list of pair<key, value>. Hence it does a bit
better on memory usage.

I suspect I've missed some bits of overhead, but you get the general
idea.

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html