2

Simplified question with a working example: I want to reuse a std::unordered_map (let's call it umap) multiple times, similar to the following dummy code (which does not do anything meaningful). How can I make this code run faster?

#include <iostream>
#include <unordered_map>
#include <time.h>

unsigned size = 1000000;

void foo(){
    std::unordered_map<int, double> umap;
    umap.reserve(size);
    for (int i = 0; i < size; i++) {
        // in my real program: umap gets filled with meaningful data here
        umap.emplace(i, i * 0.1);
    }
    // ... some code here which does something meaningful with umap
}

int main() {

    clock_t t = clock();

    for(int i = 0; i < 50; i++){
        foo();
    }

    t = clock() - t;
    printf ("%f s\n",((float)t)/CLOCKS_PER_SEC);

    return 0;
}

In my original code, I want to store matrix entries in umap. In each call to foo, the key values start from 0 up to N, and N can be different in each call to foo, but there is an upper limit of 10M for indices. Also, values can be different (contrary to the dummy code here which is always i*0.1).

I tried to make umap a non-local variable, for avoiding the repeated memory allocation of umap.reserve() in each call. This requires to call umap.clear() at the end of foo, but that turned out to be actually slower than using a local variable (I measured it).

  • 1
    What is your goal? Please provide more context. In particular its unclear from your question if map could be reused. – Basilevs Jan 24 at 3:43
  • @Basilevs I want to speed up the code. – Abaris Jan 24 at 3:47
  • But you show us no code. Is there anything to speed up? I suggest to at least explain an algorithm you are trying to implement. – Basilevs Jan 24 at 3:56
  • What are the types of your keys and values? Clearing or removing N items will take O(N) if your keys and/or values are non-trivial, which requires doing cleanup on N items. When there are millions of items the cleanup time will add up. – rwong Jan 24 at 5:12
  • @Basilevs I added a piece of code to make it clear. – Abaris Jan 24 at 6:47
3

This depends heavily on how umap is used inside, but

  • if you have a fixed known upper limit for the size,

  • the umap items are really just pairs of ints and doubles (or of similar simplicity)

  • the access pattern for umap is really that simple (just adding, content retrieving, and clearing "all at once")

  • you have perfomance requirements which justify this effort

then you could implement your own simplified hash table, based on an array or vector of int/double pairs of large-enough size. That is actually not too hard, and it will give you much better control over the memory allocation strategy (like "allocate all at once, "free all at once"), something you don't have when you pick a general-purpose container.

An unordered map from the standard lib is intended to serve multiple purposes (like deleting arbitrary elements again, or not allocating too much memory beforehand). That is why its internal implementation might be more complex than necessary for your specific case. In such a situation sometimes hand-optimized data structures can be the faster choice. However, they come for the price of increased implementation and debugging effort, and they are typically less extensible. So better check carefully if you really have those performance requirements which are worth the additional effort.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.