https://github.com/D-Programming-Language/dmd/blob/master/src/root/stringtable.c#L21

Profiling shows the calcHash function is a significant contributor to compilation time (3.25% of total time). So making it faster is a win. Even making dmd 1% faster would be a nice win - all those little drops add up.

There are many, many string hash functions findable through google. Anyone want to spend the effort to make a faster one? Remember, ya gotta prove it's faster!

A nice timing test would be the time expending compiling Phobos. I would suggest that the 64 bit build of dmd be used for timing tests.

Also, be careful, many of those hash functions on the intarnets have a license that makes it unusable for dmd.

On 06/23/2013 11:22 PM, Walter Bright wrote:
> https://github.com/D-Programming-Language/dmd/blob/master/src/root/stringtable.c#L21
>
>
> Profiling shows the calcHash function is a significant contributor to
> compilation time (3.25% of total time). So making it faster is a win.
> Even making dmd 1% faster would be a nice win - all those little drops
> add up.
>
> There are many, many string hash functions findable through google.
> Anyone want to spend the effort to make a faster one? Remember, ya gotta
> prove it's faster!
> ...

It seems to be easy to make it faster without changing the algorithm significantly. There should be only one switch executed, not one per 4 characters. If the length is short enough from the start, there is no point in doing any arithmetic.

On 06/23/2013 06:22 PM, Walter Bright wrote:
> https://github.com/D-Programming-Language/dmd/blob/master/src/root/stringtable.c#L21
> 
> Profiling shows the calcHash function is a significant contributor to compilation time (3.25% of total time). So making it faster is a win. Even making dmd 1% faster would be a nice win - all those little drops add up.
> 
> There are many, many string hash functions findable through google. Anyone want to spend the effort to make a faster one? Remember, ya gotta prove it's faster!
> 
> A nice timing test would be the time expending compiling Phobos. I would suggest that the 64 bit build of dmd be used for timing tests.
> 
> Also, be careful, many of those hash functions on the intarnets have a license that makes it unusable for dmd.


I performed a quick test, and I don't think that the original function can be improved for speed (though it might be improved for less collisions):

    https://gist.github.com/jmcabo/5847036

I used words and lines from the complete works of Shakespeare. I tested separating the loop from the switch, as was suggested in Timon Gehr post. It didn't improve the speed when compiled with "g++ -O3", though it improved it a bit without -O3.

I also tested removing the multiplication by 37. It didn't improve the speed. With "g++ -O3" they are all the same.

So, unless I'm measuring it wrong, the algorithm is as fast
as can be (as fast as just adding chars).

--jm

On 06/23/2013 11:22 PM, Walter Bright wrote:
> Profiling shows the calcHash function is a significant contributor to
> compilation time (3.25% of total time). So making it faster is a win.
> Even making dmd 1% faster would be a nice win - all those little drops
> add up.
>

You'll find a benchmark at the end of the post.
http://forum.dlang.org/thread/op.v2yky9pdsqugbd@dawg-freebsd.lan


Obviously the switch in a for loop is a branch prediction killer.
This should work much better.

for (size_t i = 0; i < len / 4; ++i)
{
    hash *= 37;
    hash += *(const uint32_t *)str;
    str += 4;
}
switch (len & 3)
{
case 0:
    break;
case 1:
    hash *= 37;
    hash += *(const uint8_t *)str;
    break;
case 2:
    hash *= 37;
    hash += *(const uint16_t *)str;
    break;
case 3:
    hash *= 37;
    hash += (*(const uint16_t *)str << 8) +
             ((const uint8_t *)str)[2];
    break;
default:
    assert(0);
}
return hash;

Finding a faster hash algorithm isn't simple because prime multiplication is so simple. At least we're not diving the hash result by 37 any longer.
I think using the Hsieh hash is a good choice because it has quite an OK distribution so it leads to fewer collisions. It's also pretty fast for short strings and we already use it in druntime.

On 06/23/2013 09:20 PM, Juan Manuel Cabo wrote:
> On 06/23/2013 06:22 PM, Walter Bright wrote:
>> https://github.com/D-Programming-Language/dmd/blob/master/src/root/stringtable.c#L21
>>
>> Profiling shows the calcHash function is a significant contributor to compilation time (3.25% of total time). So making it faster is a win. Even making dmd 1% faster would be a nice win - all those little drops add up.
>>
>> There are many, many string hash functions findable through google. Anyone want to spend the effort to make a faster one? Remember, ya gotta prove it's faster!
>>
>> A nice timing test would be the time expending compiling Phobos. I would suggest that the 64 bit build of dmd be used for timing tests.
>>
>> Also, be careful, many of those hash functions on the intarnets have a license that makes it unusable for dmd.
> 
> 
> I performed a quick test, and I don't think that the original function can be improved for speed (though it might be improved for less collisions):
> 
>     https://gist.github.com/jmcabo/5847036
> 
> I used words and lines from the complete works of Shakespeare. I tested separating the loop from the switch, as was suggested in Timon Gehr post. It didn't improve the speed when compiled with "g++ -O3", though it improved it a bit without -O3.
> 
> I also tested removing the multiplication by 37. It didn't improve the speed. With "g++ -O3" they are all the same.
> 
> So, unless I'm measuring it wrong, the algorithm is as fast
> as can be (as fast as just adding chars).
> 
> --jm
> 
> 

Oh, it might be improved by loading 128bits at a time instead of 32bits... but that would benefit strings of more than 16 bytes. Google's CitiHash seems tuned for large strings.

--jm

On Sun, Jun 23, 2013 at 2:22 PM, Walter Bright <newshound2@digitalmars.com>wrote:

> https://github.com/D-**Programming-Language/dmd/blob/** master/src/root/stringtable.c#**L21<https://github.com/D-Programming-Language/dmd/blob/master/src/root/stringtable.c#L21>
>
> Profiling shows the calcHash function is a significant contributor to compilation time (3.25% of total time). So making it faster is a win. Even making dmd 1% faster would be a nice win - all those little drops add up.
>
> There are many, many string hash functions findable through google. Anyone want to spend the effort to make a faster one? Remember, ya gotta prove it's faster!
>
> A nice timing test would be the time expending compiling Phobos. I would suggest that the 64 bit build of dmd be used for timing tests.
>
> Also, be careful, many of those hash functions on the intarnets have a license that makes it unusable for dmd.
>

implementing this "proposal: lazy compilation model for compiling binaries" http://forum.dlang.org/post/mailman.1357.1371876331.13711.digitalmars-d@puremagic.com would have much larger impact on compile time performance.

https://code.google.com/p/xxhash/
BSD 2-Clause License

On Sunday, 23 June 2013 at 21:22:40 UTC, Walter Bright wrote:
> https://github.com/D-Programming-Language/dmd/blob/master/src/root/stringtable.c#L21
>
> Profiling shows the calcHash function is a significant contributor to compilation time (3.25% of total time). So making it faster is a win. Even making dmd 1% faster would be a nice win - all those little drops add up.
>
> There are many, many string hash functions findable through google. Anyone want to spend the effort to make a faster one? Remember, ya gotta prove it's faster!
>
> A nice timing test would be the time expending compiling Phobos. I would suggest that the 64 bit build of dmd be used for timing tests.
>
> Also, be careful, many of those hash functions on the intarnets have a license that makes it unusable for dmd.

My first idea was to look at Python, since it requires a lot of hash calculation dynamically and probably is one of the most tuned implementations. Interesting how naive it is:

http://hg.python.org/cpython/file/7aab60b70f90/Objects/object.c#l759

Just a simple for loop over chars. No switch.

Wikipedia: "Python Software Foundation License (PSFL) is a BSD-style permissive free software license"

On 06/24/2013 03:43 AM, Juan Manuel Cabo wrote:
>> I used words and lines from the complete works of Shakespeare.
>> I tested separating the loop from the switch, as was suggested
>> in Timon Gehr post. It didn't improve the speed when compiled
>> with "g++ -O3", though it improved it a bit without -O3.
>>
This is limited by the memory bandwidth so your testing the wrong thing.

On Sunday, 23 June 2013 at 21:22:40 UTC, Walter Bright wrote:
> https://github.com/D-Programming-Language/dmd/blob/master/src/root/stringtable.c#L21
>
> Profiling shows the calcHash function is a significant contributor to compilation time (3.25% of total time). So making it faster is a win. Even making dmd 1% faster would be a nice win - all those little drops add up.

To make dmd 1% faster, calcHash must be reduced to 69% run time. Does not look possible.

Also, why is it implemented twice -- in src/root/stringtable.c and in src/root/root.c?

Improving AAs by changing the data structure seems to be more worthwhile. They use a linked list internally, which is not exactly cache-friendly. From your gprof run the potential is mostly 5.19% _aaGetRvalue + 1.30% _aaGet.