STL Map of Pointers vs Map Containing the Data

[nukerdoggie]

My application consists of the following requirements:

1. The map container will be created in full at the start of the app and no insertions or deletions will occur throughout the life of the object.

2. Updates to data elements inside the map occur frequently.

3. Access to map "records" will need to be by key at times and at other times access will be sequential, starting from the first "record" and continuing thru to the last "record".

4. The container is large - in excess of 1gb, with many "records", whose data elements add up to about 65 bytes, with the key element about 24 bytes in length.

My question is whether there is a significant performance difference between the two models, one model being having the key and data all contained literally inside the map object versus the other model of constructing a map of pointers to a list or array that contains the data?

Also, in the application I have put forward, if anyone has a better solution than the STL map, perhaps a hybrid solution of some sort, I am open to suggestions.

Thanks,

Nukerdoggie

[RRick]

The pointer approach will add an extra 4 or 8 bytes for each record of the data. This is an increase of either 6% or 12% to your program data size. You also have the extra work of newing and deleting the data.

Storing the data internally is fine except for modifications to the data. In this case you must copy the data to and from the map. At 65 bytes, its not too bad, but that is 8 or 16 times longer than copying a pointer.

Which is best? I don't see any clear winner here.


As for using an STL map, that's pretty much a given from your description. When you say key, element, and infer random access; that defines a map. My only caution is that maps can get slow when they get big, especially with insertions. Watch the creation of the map and see if it slows down with more and more additions. When insertions start to slow down, it only gets worst. It looks like you have a million entries and that could cause problems. Big, sloooowwww problems.

If you need other structures, then a vector will work. Concatenate the key with the data, insert at the end, and sort on the key value. This allows you to search sequentially and also do a binary search on the key. I believe the STL has algorithms that will sort and search for you.

[nukerdoggie]

Thanks for the quick reply - your insights are very helpful, RRick.

[RRick]

Feel free to reply to this posting when you get some results.

We all would be interested in knowing if there are performance issues to STL maps with a million inserts.

Good Luck

[nukerdoggie]

Will do..... The app runs on a fast Linux server and should be quite speedy by comparison to Windows.

[nukerdoggie]

Here are the results of our testing:

We created a STD::STL test map with a 64-byte key and a 256-byte data section, with all data consolidated into the map (it was not a map of pointers to the data).

Our first run created a map of just over 800,000 records and the total elapsed time to create the map was about 8 seconds.

Our second run created the same map structure, but this time with 1.8 million records. The total elapsed time to create the map was about 18 seconds.

This test is very encouraging and demonstrates for us that the creation of the map (insert perfomance) is very fast, well within the framework of required perfomance, even when the number of inserts gets very large.

The development server we ran the test on is an x86 4-processor Sun server with AMD chips running at 2.4GHZ each, Linux opsys, with about 60 developer-tester/users logged on at the time we ran the test.

[RRick]

Thanks for the info.

Your measurements are linear that's about as good as can be expected. Also, its good to know that maps can handle a million plus entries without issues.

Good Luck.