CODEWITHSUNDEEP
c++boostunordered-maplookup-tables
Aly
Aly

Reputation: 16255

using boost::unordered_map as a look up table appears to be extremely slow

I have the following look up table defined:

boost::unordered_map<std::string, STFRandomTreeFunctor*> functor_look_up_table;

the idea is to use it to call the functor, however this appears to be running very slow. At first I thought it was because the function that the functor calls may be taking a long time to run, I replaced the code as follows (i.e. removed the call to functor()):

my_function(){
    while(...){
        STFRandomFunctor* f = functor_look_up_table.at(some_string);
        ...<do some other stuff>
    }
}

and it still runs slow, the removal of the line STFRandomFunctor* f = functor_look_up_table.at(some_string); speeds up the code immensely. Am I using the wrong kind of data structure for my look up table here? If so, what is preferable?

Upvotes: 0

Views: 916

Answers (2)

Matthieu M.
Matthieu M.

Reputation: 299890

@aleguna strings are id's for functions, some examples are "single_channel_subtract_abs", "multi_channel_random_add", "multi_channel_random_subtract_abs". There are 5 keys in total

Then you should not be using a string, nor a unordered_map:

// Function.hpp

enum FunctorName {
    single_channel_subtract_abs,
    multi_channel_random_add,
    multi_channel_random_substract_abs,
    ...
};

STFRandomTreeFunctor const& get(FunctorName name);

// Function.cpp
static STFRandomTreeFunctor const Functors[] = {
    ...
};

STFRandomTreeFunctor const& get(FunctorName name) {
    size_t const index = name;

    assert(index < sizeof(Functors) && "Need to update Functors");

    return Functors[index];
} // get

You may drop the const& in get altogether if STFRandomTreeFunctor is a typedef for a function type and not a full blown functor.

Upvotes: 4

BigBoss
BigBoss

Reputation: 6914

unordered_map are extremely fast at lookup, but if you have a good hashing function, every time that you look at your map, hash of your key will be computed, so if computing hash take long time, then your performance is poor, on the other hand if hash function generate similar hash values may all(or a lot of) items fall in one bucket and then your search become linear, for first part your string must be really huge to default hash of the boost take a long time, but for second part, try changing bucket size and check performance again.

Upvotes: 0

Related Questions