Click here to Skip to main content
15,395,877 members
Please Sign up or sign in to vote.
4.00/5 (1 vote)
Hello guys.

I know, the header is not clear enough. Let me explain the situation in detail.

I've a server which takes messages from clients, then check if the message type matches any of the existing types via if - else if(there are more than 30 else if statements)

Thinking having these many else ifs would be bad for performance, I've decided to use an std::map. Specifically this one:

std::map<std::string,boost::function<void(std::string)>


Then I've decided to compare these 2 techniques' performances.

What I have tried:

Test code for if-else takes 17 milliseconds.

 std::string s = "test3";
 for (int i = 0; i < 1000000; i++) {


    if (s == "test1") test1("asd");
    else if (s == "test2") test2("asd");
    else if (s=="test3") test3("asd");

}



Test code for std::map takes 30 milliseconds.
std::map<std::string, boost::function<void(std::string)>> testmap
{
    {"test1",boost::bind(&TcpServer::test1, this, _1) },
    {"test2",boost::bind(&TcpServer::test2, this, _1) },
    {"test3",boost::bind(&TcpServer::test3, this, _1) }
};

std::string s="test3";

for (int i = 0; i < 1000000; i++) {
    testmap[s]("asd");
}




Why is using std::map inefficient compared to 1 if and 2 else ifs. Especially considering I don't even check if map has the key I'm searching for, which increases the value to 49 milliseconds.
Posted
Updated 19-Oct-21 12:16pm
v3
Comments
Rick York 20-Oct-21 3:41am
   
It could make for an interesting experiment to see where the break-even point is between using a map and a linear search. I would probably use a different set of strings than the three you have. I found a list of over 460K words and I would probably use a random set of them for a test like this. I might just do this if I get some time soon.
Shao Voon Wong 20-Oct-21 6:50am
   
You can try std::unordered_map which is a hashed table.
Weird Japanese Shows 20-Oct-21 7:10am
   
it's faster if I don't check if the unordered_map has the key or not but slower if I check it. But it surely is alot better than std::map
Shao Voon Wong 21-Oct-21 3:47am
   
You can follow my tip on unordered_map: https://www.codeproject.com/Tips/5255442/Cplusplus14-20-Heterogeneous-Lookup-Benchmark to avoid the std::string instantiation during find. In my experience of a switch statement with a few hundred of cases because I have that many message types to process, unordered_map can be faster because there are many branching in this massive switch-case. Of course, your mileage may vary. When you only have a few if-else, I'll say don't bother.

1 solution

At a guess: the strings "test1", "test2", "test3" are all very short and maybe the compiler is smart enough to use a "small string optimization", and ends up comparing 64bit ints rather than doing a string compare.
You also have a very small test set. I expect that the overhead to calculate the string hash outweighs the efficiencies of a hash lookup for only 3 items. The hash lookup might get better performance in a larger test case, since it will be able to do a binary search over the map to find the right key, whereas the multiple ifs will search linearly. Now, the linear search might also be an improvement over a map if you know that say 60% of the message types would be "type7" and 30% are "type2", since you can test for those two message types first, and then proceed with the others.
Bottom line: try testing with a larger test set - e.g "test1" ... "test10" and see if the overhead for calculating the hash is the culprit here.
   
Comments
k5054 19-Oct-21 18:15pm
   
Checking gcc-11 and clang at the compiler explorer (https://godbolt.org/), the small string optimizations don't come into play - even at -O3 both compilers make a call to std::string.compare(). Just FYI.
Weird Japanese Shows 19-Oct-21 18:18pm
   
Checked with 14 values :
if-else takes 30ms.
std::map takes 56ms.
std::map with checking if the value exists in the map takes 99ms.
Weird Japanese Shows 19-Oct-21 18:29pm
   
When I randomize the picked key each iteration, map is faster than if-else if I don't check weather map contains the key or not. I assume compiler keeps track of most selected else-if statements.
Greg Utas 19-Oct-21 19:15pm
   
I would have answered in much the same way as k5054. Whether a std::map or a sequence of if/else-if statements is faster will greatly depend on the number of strings, their distribution, and the order of the else-if statements.

When you say you assume that the "compiler keeps track of most selected else-if statements", do you mean that it arranges the else-if statements in order of how often they are reached? If so, that couldn't be true in a compiled language, and it's very unlikely in an interpreted language (because if performance was that important, the code would be compiled to start with).

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900