Faster map operations in C++

Question

In my code I'm storing parameters sets for interactions between different groups in a map. Currently at startup I add each structure (testvals in the code below) with the key created from joining the two group names into a single string.

string nKey = key1;
nKey += JOIN_STRING;
nKey += key2;

map< string, struct> mymap_string; 
mymap_string.insert( make_pair(nKey, testval ));

When it comes to looking up the data for two groups, I'm again creating that string and then using find on the map to retrieve my data.

string nKey = key1;
nKey += JOIN_STRING;
nKey += key2;

auto it = mymap_string.find( nKey );
if ( it != mymap_string.end() )
{
    struct vals= it->second;
}

In my code I'm creating the map once at startup but doing the lookup part millions of times. I'm wondering if there's a better way of doing this as string concatenation seems to be relatively expensive and find may not be the fastest way to search and compare strings?

My testing seems to show that strings are faster than using std::pair<string1, string2> as the key for the map. I've looked at map vs unordered_map but there doesn't seem to be much of a difference. unordered_map may be slightly faster when the number of keys is large.

Does anyone have any suggestion on what might be a better, quicker approach? Given the number of calls made to this, if I can make it significantly quicker I can save a lot of time. I don't mind if the insertion or setup isn't blindingly fast since it only happens once, but lookup is important. It would be better to use something standard that works on Windows and Linux.

Update:

OK so from the questions it seems that more background information is required.

testvals is a structure of doubles for the input parameters for the current model being used and the number of variables provided in it will vary with the model. But typically this is between 4-10 values. A typical set is show here:

typedef struct
{
    double m_temp_min;
    double m_temp_max;
    double m_liquid_content;
    double m_growth_rate;
    double m_alpha;
    double m_beta;
} testvals;

Key1 and Key2 are always strings that are passed from the programs core module, but the strings are user-defined, meaning they could be anything from "a" to "my_big_yellow_submarine_3".

The number of keys in the map will depend on the number of groups in the data. If there are only two groups for which interactions parameters need to be provided, then the map would only have 4 unique string keys: group1~~group1, group1~~group2, group2~~group1 and group2~~group2. Normally there are 3 or 4 group types in the map so the number of keys is usually in the number of tens. This size may be why I don't see much of a difference in map and unordered_map performance.

One of the comments mentioned std::pair<std::string,std::string> and as I originally said, the cost of calling make_pair() seems much higher than the cost of making the string and was more than 50% slower when I tested it. But I didn't try the combination of std::pair with unordered_map. I assumed that if std::pair is slower with map, it is also going to be slower with unordered_map. Is there a reason to expect it to be very different?

I hope this helps clarify some of the things.

Answer 1

You have only a limited number of keys which makes calculating the hash expensive compared to the real lookup. That's why std::map and std::unordered_map aren't much different in your case. Besides JOIN_STRING also introduces unnecessary operations while computing hash or comparing strings

I suggest you to avoid those group names altogether and use group IDs instead. With N group types you only have N² different types of interactions. Then the IDs will belong to a range of [0, N). If N is known at compile time you can even make it an array. So instead of

string nKey = key1;
nKey += JOIN_STRING;
nKey += key2;

you'll use

std::vector<testvals> vals(N*N);    // vector with N² elements

uint32_t nKey = key1*N + key2;      // index of the <key1, key2> mapping
const auto &val = vals[nKey];       // get the mapped value

You should use & to get a reference instead of a copy. You can also use a map instead of a vector. It's still much slower than a vector but still much faster than a map of string. You can calculate the mapped key like above, or use some mappings like nKey = (key1 << 16) ^ key2 or nKey = ((uint64_t)key1 << 32) | key2

Group names are only used when you convert the names to ID at the beginning, or when you want to print them out. You can use some struct like this to store the name

struct GroupInfo
{
    std::string groupName;
    uint32_t groupID;
}

No need to use typedef for structs in C++ like in your code. You can also use std::vector<std::string> or std::map<uint32_t, std::string> to map from ID to name. The ID can be a smaller type like uint8_t or uint16_t