efficiently initialize unordered_map with large dataset of integer pairs

Question

I have a huge array (say, ParticleId[]) of unique integers (representing particle IDs) stored in random order in memory. I need to build a hash table to map each ID to its location inside the array, i.e., from ID to index. The IDs are not necessarily continuous integers so a simple look-up array is not a good solution.

I am currently using the unordered_map container of c++11 to achieve this. The map is initialized with a loop:

unordered_map <ParticleId_t, ParticleIndex_t> ParticleHash;
ParticleHash.rehash(NumberOfParticles);
ParticleHash.reserve(NumberOfParticles);
for(ParticleIndex_t i=0;i<NumberOfParticles;i++)
  ParticleHash[ParticleId[i]]=i;

The ParticleId_t and ParticleIndex_t are simply typedef-ed integers. NumberOfParticles can be huge (e.g., 1e9). ParticleId[] array and NumberOfParticles are const as far as the hash table is concerned.

Currently it takes quite a lot of time to build the unordered_map as above. My questions are:

1. Is unordered_map the optimal choice for this problem?
   • would map be faster to initialize, although it may not be as efficient in the look-up?
2. Is it possible to speed up the initialization?
   • Is it much faster to use ParticleHash.insert() than ParticleHash[]=? or any other functions?
   • Given that my keys are known to be unique integers, is there a way to optimize the map as well as the insertion?

I am considering the intel concurrent_unordered_map to parallelize it. However, that would introduce a dependence on the intel TBB library, which I would like to avoid if possible. Is there an easy solution using the native STL containers?

Update:

Now I've reverted to a plain sorted index table and rely on bsearch for lookup. At least the initialization of the table is now 20 times faster and can be easily parallelized.

Answer 1

It seems the application building the look up table is memory bound, not cpu bound. This can probably be verified by profiling a prototype of the application. The rest of this answer assumes this to be true.

The process building the look up table is taking a global view of the input data and this may be contributing to lot of swapping in/out of memory to/from disk.

If that is the case, the solution is an alternative algorithm that deals with smaller chunks of memory at a time. Suppose there are 1 million integers. The current process may be inserting into the low end of hash table closer to 1 at this moment and in the next moment it may be inserting into the high end closer to 1 million. This leads to lot of swapping.

An alternative approach would avoid the swapping by dealing with smaller chunks of the data set at a time. We could borrow ideas from bucket/radix sort. In this approach, the step of building a look up table would be replaced by a sorting step. Bucket/Radix sort are supposed to run in linear time. The fact that all the integers in the data set are unique is another reason to use these sorting algorithms. If linear time sorting and minimization of swapping could be combined, that may improve performance.

Answer 2

I don't think there's a lot you can do with this, but here's a few things to try.

First, since you're calling realloc you don't need to call rehash.

insert is potentially faster than operator[] since operator[] will call insert to add an element to the map with the default value, then assign your value to the newly inserted element, but the optimizer may be able to eliminate the extra work.

Just because the keys are unique, the hashed value of those keys may not be as I don't think the language spec requires that an integer hash returns that integer (the section that describes the hash template doesn't say it, anyway).

'map' would probably be slower to initialize, since it would have to keep rebalancing the tree as you inserted things, and the lookups would be slower. One alternative to map you could use if your ParticleID vector could be rearranged would be to sort your vector, then do a binary_search to find where the ID is and compute the index. But it would have similar performance to map and require the rearranging of the vector.

If you decide to try concurrent_unordered_map you probably won't see much improvement after 3 or 4 threads because of all the memory contention between threads.

Answer 3

Given "huge array of unique integers stored in random order" - is there anything already depending on that random order? If not, just sort the array of unique integers in-place, and to map from unique integer to index, you do a std::lower_bound in the array.

If there is a need to preserve the pre-exsting order of the huge array, but you're building an index as a one-off step after that array's been populated (as your illustrative code does), you can create a similarly huge array of ParticleId* and std::sort them based on the pointed-to elements (you'll need a custom < comparison of the pointed-to values); afterwards you can use std::lower_bound with the same < comparison to quickly find the index in huge array of a specific ParticleId.

The above contiguous array approaches benefits hugely in performance and memory use from the use of contiguous memory in a cache-friendly fashion.

Only if you have a large number of new ParticleIds coming in or being removed during the time you need to be able to search would you need to consider std::unordered_map.