Skip to content

Instantly share code, notes, and snippets.

@holocronweaver

holocronweaver/string_switch.cpp

Created January 12, 2017 23:11
Show Gist options
  • Save holocronweaver/c6f212d7fb9414b0cc88ca33217bb117 to your computer and use it in GitHub Desktop.
Save holocronweaver/c6f212d7fb9414b0cc88ca33217bb117 to your computer and use it in GitHub Desktop.
Download ZIP
In C++, using string hashes in switches is faster than if-else string comparisons on average.
Raw
string_switch.cpp
#include <cstdlib>
#include <iostream>
#include <string>
#include <boost/timer/timer.hpp>
#define NUM_CALLS 1000000
template <size_t N, size_t I = 0>
struct hash_calc
{
static constexpr size_t apply(const char (&s)[N])
{
return (hash_calc<N, I + 1>::apply(s) ^ s[I]) * 16777619u;
};
};
template <size_t N>
struct hash_calc<N, N>
{
static constexpr size_t apply(const char (&s)[N])
{
return 2166136261u;
};
};
/** Generate compile-time string hashes.
Useful for creating string switches and static "type IDs" based on
class name strings (i.e., size_t id = hash("MyClassName")).
Source: http://stackoverflow.com/a/5019604
*/
template <size_t N>
constexpr size_t hash(const char (&s)[N])
{
return hash_calc<N>::apply(s);
}
/// A non-static version.
size_t hash(const std::string& s)
{
size_t num = 2166136261u;
for (int i = s.size(); i >= 0; i--)
{
num = (num ^ s[i]) * 16777619u;
}
return num;
}
int main()
{
std::string wood = "wood";
std::cout << hash(wood) << " " << hash("wood") << std::endl;
boost::timer::cpu_timer timer;
std::cout << "long table, worst case" << std::endl;
timer.start();
for (int i = 0; i < NUM_CALLS; i++)
{
if (wood == "reed")
{
}
else if (wood == "lead")
{
}
else if (wood == "need")
{
}
else if (wood == "feed")
{
}
else if (wood == "seed")
{
}
else if (wood == "mead")
{
}
else if (wood == "bead")
{
}
else if (wood == "weed")
{
}
else if (wood == "ward")
{
}
else if (wood == "ford")
{
}
else if (wood == "gord")
{
}
else if (wood == "lord")
{
}
else if (wood == "word")
{
}
else if (wood == "bird")
{
}
else if (wood == "wood")
{
}
}
timer.stop();
std::cout << timer.format() << std::endl;
timer.start();
for (int i = 0; i < NUM_CALLS; i++)
{
switch (hash(wood))
{
case hash("reed"):
break;
case hash("lead"):
break;
case hash("need"):
break;
case hash("feed"):
break;
case hash("seed"):
break;
case hash("mead"):
break;
case hash("bead"):
break;
case hash("weed"):
break;
case hash("ward"):
break;
case hash("ford"):
break;
case hash("gord"):
break;
case hash("lord"):
break;
case hash("word"):
break;
case hash("bird"):
break;
case hash("wood"):
break;
}
}
timer.stop();
std::cout << timer.format() << std::endl;
std::cout << "long table, best case" << std::endl;
timer.start();
for (int i = 0; i < NUM_CALLS; i++)
{
if (wood == "wood")
{
}
else if (wood == "reed")
{
}
else if (wood == "lead")
{
}
else if (wood == "need")
{
}
else if (wood == "feed")
{
}
else if (wood == "seed")
{
}
else if (wood == "mead")
{
}
else if (wood == "bead")
{
}
else if (wood == "weed")
{
}
else if (wood == "ward")
{
}
else if (wood == "ford")
{
}
else if (wood == "gord")
{
}
else if (wood == "lord")
{
}
else if (wood == "word")
{
}
else if (wood == "bird")
{
}
}
timer.stop();
std::cout << timer.format() << std::endl;
timer.start();
for (int i = 0; i < NUM_CALLS; i++)
{
switch (hash(wood))
{
case hash("wood"):
break;
case hash("reed"):
break;
case hash("lead"):
break;
case hash("need"):
break;
case hash("feed"):
break;
case hash("seed"):
break;
case hash("mead"):
break;
case hash("bead"):
break;
case hash("weed"):
break;
case hash("ward"):
break;
case hash("ford"):
break;
case hash("gord"):
break;
case hash("lord"):
break;
case hash("word"):
break;
case hash("bird"):
break;
}
}
timer.stop();
std::cout << timer.format() << std::endl;
std::cout << "short table, best case" << std::endl;
timer.start();
for (int i = 0; i < NUM_CALLS; i++)
{
if (wood == "wood")
{
}
else if (wood == "lord")
{
}
else if (wood == "word")
{
}
else if (wood == "bird")
{
}
}
timer.stop();
std::cout << timer.format() << std::endl;
timer.start();
for (int i = 0; i < NUM_CALLS; i++)
{
switch (hash(wood))
{
case hash("wood"):
break;
case hash("lord"):
break;
case hash("word"):
break;
case hash("bird"):
break;
}
}
timer.stop();
std::cout << timer.format() << std::endl;
std::cout << "short table, worst case" << std::endl;
timer.start();
for (int i = 0; i < NUM_CALLS; i++)
{
if (wood == "lord")
{
}
else if (wood == "word")
{
}
else if (wood == "bird")
{
}
else if (wood == "wood")
{
}
}
timer.stop();
std::cout << timer.format() << std::endl;
timer.start();
for (int i = 0; i < NUM_CALLS; i++)
{
switch (hash(wood))
{
case hash("lord"):
break;
case hash("word"):
break;
case hash("bird"):
break;
case hash("wood"):
break;
}
}
timer.stop();
std::cout << timer.format() << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment