CODEWITHSUNDEEP
c++boostdictionary
user2100910
user2100910

Reputation: 327

How about storing the array indices in a map

my program is using boost::unordered_map a lot, and the map has about 40 million entries. This program doesn't do insertion or deletion very often. It just randomly accesses entries using keys.

I'm wondering will it improve the performance (in terms of the speed of accessing entries) if I store my entry values (about 1 KB each) in a flat array (maybe an std::vector), and I use boost::unordered_map to store the mapping of keys to the indices to this array.

Thanks, Cui

Upvotes: 2

Views: 345

Answers (2)

sehe
sehe

Reputation: 393134

Yes, that could seriously speed up things. In fact, that's what Boost flat_map is for :)

The docs relate: Non-standard containers

Using sorted vectors instead of tree-based associative containers is a well-known technique in C++ world. Matt Austern's classic article Why You Shouldn't Use set, and What You Should Use Instead (C++ Report 12:4, April 2000, PDF) was enlightening:

...

This gives you more than you asked for because you don't even need the extraneous index. This gives you more locality of reference and a lower memory footprint. Most importantly, it gives you lower complexity (-> fewer bugs) and a drop-in replacement for std::[unordered_]map in terms of interface.

Upvotes: 2

DaBrain
DaBrain

Reputation: 3185

Storing the values in contiguous memory like std::vector provides, will increase cache locality. This can make a pretty big difference in performance but it depends on the access pattern.

If your hunting performance, remember the golden rule: always measure!

Upvotes: 0

Related Questions