Here is a working version of compile time string hashing in C++,
pretty tedious to make this so perhaps I’ll save someone some time.
You cannot currently do this with templates, at least not without
resorting to specifying one character at a time or using multi-byte for
4 at a time, so it massages the compiler into optimizing the string hash
out of existence.
Another way of doing it is with pure macros.
It was written with VS2010, so results may not be the same on other compilers
(though I’d expect GCC and Intel should be able to pull it off). In debug(without
optimizations on), it will not be optimized out so you may want to force it to use
the const char* path in debug.
Also the __forceinline calls are necessary, without them once the compiler starts
seeing more than one string literal of the same length it switches to calling a function.
Tested it with string literals up to 64 characters in length, and the resulting
assembly is just a single assignment.
Usage is like this:
size_t id = ptl::string_id(“hello what is my hash?”);
You can also pass a const char* or a std::string, but this will result in a run
time hash(using same hash function so results should be the same).
Additionally you can use it with std::unordered_map/set like so
std::unordered_map < ptl::string_id, int, ptl::string_id::hash > PreHashed;
And a lookup like this:
auto it = PreHashed.find(“hello”);
Won’t actually hash anything, it will just use the compile-time calculated hash value.
The hash function used is called One-at-a-Time, see here for description.
Of course– it probably isn’t a good idea to actually use something like this without throughly testing
to verify that the compiler generates the correct code in all situations, which is pretty difficult
to do
November 4th, 2010 at 1:23 pm
I tested the code with VS 2008 SP1, and it made no compile time hash.
Or does I have to change some compiler settings?
I think I found a mistake, did you really wanted to say this:
” but this will result in a compile time hash” I think you might want to say, “will result in a runtime hash”
right?
November 4th, 2010 at 1:47 pm
I found the problem:
in line 312 you wrote “_forceinline” but you need to write “__forceinline”
I also got a problem when using runtime generated hashes.
When I have a space between two words only the first word got hashed.
November 5th, 2010 at 12:46 pm
Thanks, I had that jumbled up– edited it so it is correct now
November 5th, 2010 at 12:55 pm
Thanks for the _forceinline catch, I’ve fixed that now
By space between two words do you mean trying to hash something like this?
“hello there”
and
“hello”
Are you seeing these generate the same hash?
I tested this and it was not the case for me, the “hello world” was hashed with both runtime & compile time hashing to the same result, which was not the same as the shorter “hello” hash. Was there a specific phrase you used that caused this?
Thanks
I
November 7th, 2010 at 3:59 am
I found out, that was my problem.
When you input a std::string with space, he stores only the first word in the string, strange…
btw. I think you can implement this hashing algo simply with template meta programming.
Then you don’t need any macros, these macro magic was really difficult to understand for me