qznc:

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

I think the main problem to solve is to reduce the amount of memory used during the compilation.

Bye,
bearophile

On Monday, 24 June 2013 at 14:36:03 UTC, bearophile wrote:
> qznc:
>
>> To make dmd 1% faster, calcHash must be reduced to 69% run time. Does not look possible.
>
> I think the main problem to solve is to reduce the amount of memory used during the compilation.
>


Yes, my profiling show that were I spend the most time is swapping. This have the effect of making every single part of DMD slower, and have potential for a 10x speedup (easy !).

On Monday, 24 June 2013 at 15:29:55 UTC, deadalnix wrote:
> On Monday, 24 June 2013 at 14:36:03 UTC, bearophile wrote:
>> qznc:
>>
>>> To make dmd 1% faster, calcHash must be reduced to 69% run time. Does not look possible.
>>
>> I think the main problem to solve is to reduce the amount of memory used during the compilation.
>>
>
> Yes, my profiling show that were I spend the most time is swapping. This have the effect of making every single part of DMD slower, and have potential for a 10x speedup (easy !).

That, and it means dmd has better chances of finishing its compile before crashing (*cough*algorithm.d -unittest*cough*)

On Monday, 24 June 2013 at 11:11:42 UTC, qznc wrote:
> 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"

Python is one of the slower interpreted languages. It would be more interesting to look at luajit which actually does something clever.
If the string is at least 4 chars long it only hashes the first 4 bytes, the last 4, the 4 starting at floor(len/2)-2 and the 4 starting at floor(len/4)-1. Any of these may overlap of course but that isn't a problem.

The code is MIT licensed and can be found here:
http://repo.or.cz/w/luajit-2.0.git/blob/053041a9f47e3d341f98682ea1e4907a578e4920:/src/lj_str.c#l104

As others have mentioned it will be hard to improve the speed enough to get dmd 1% faster - but if anything can it's dirty tricks.

On 6/24/2013 1:08 PM, Anders Halager wrote:
> Python is one of the slower interpreted languages. It would be more interesting
> to look at luajit which actually does something clever.
> If the string is at least 4 chars long it only hashes the first 4 bytes, the
> last 4, the 4 starting at floor(len/2)-2 and the 4 starting at floor(len/4)-1.
> Any of these may overlap of course but that isn't a problem.

I used that method back in the 1980's, it was well known then, but perhaps has drifted into obscurity. In fact, I still use it for hashing identifiers in DMC++.

On Monday, 24 June 2013 at 20:19:31 UTC, Walter Bright wrote:
> On 6/24/2013 1:08 PM, Anders Halager wrote:
>> Python is one of the slower interpreted languages. It would be more interesting
>> to look at luajit which actually does something clever.
>> If the string is at least 4 chars long it only hashes the first 4 bytes, the
>> last 4, the 4 starting at floor(len/2)-2 and the 4 starting at floor(len/4)-1.
>> Any of these may overlap of course but that isn't a problem.
>
> I used that method back in the 1980's, it was well known then, but perhaps has drifted into obscurity. In fact, I still use it for hashing identifiers in DMC++.

I can't imagine all the clever (even if outdated) tricks that have disappeared with retired old-timers :)

I haven't set up anything for testing but if someone wants to try I've made a quick patch here: http://dpaste.com/hold/1268958/

On 6/24/13 5:56 PM, Anders Halager wrote:
> On Monday, 24 June 2013 at 20:19:31 UTC, Walter Bright wrote:
>> On 6/24/2013 1:08 PM, Anders Halager wrote:
>>> Python is one of the slower interpreted languages. It would be more
>>> interesting
>>> to look at luajit which actually does something clever.
>>> If the string is at least 4 chars long it only hashes the first 4
>>> bytes, the
>>> last 4, the 4 starting at floor(len/2)-2 and the 4 starting at
>>> floor(len/4)-1.
>>> Any of these may overlap of course but that isn't a problem.
>>
>> I used that method back in the 1980's, it was well known then, but
>> perhaps has drifted into obscurity. In fact, I still use it for
>> hashing identifiers in DMC++.
>
> I can't imagine all the clever (even if outdated) tricks that have
> disappeared with retired old-timers :)
>
> I haven't set up anything for testing but if someone wants to try I've
> made a quick patch here: http://dpaste.com/hold/1268958/

This is significantly faster than anything submitted thus far. Compiled alongside Juan Manuel Cabo's submission, the results are as follows:

Times hashing words:

	Unchanged : 1386 ms
	One switch: 1338 ms
	Only add : 1354 ms
	Anders Haliger : 933 ms

Times hashing entire lines:
	
	Unchanged : 335 ms
	One switch: 332 ms
	Only add : 331 ms
	Anders Haliger : 125 ms

Wonder how much faster can it get?

-- 

Andrew Edwards
--------------------
http://www.akeron.co
auto getAddress() {
    string location = "@", period = ".";
    return ("info" ~ location ~ "afidem" ~ period ~ "org");
}

In the case of high memory usage the input string is unlikely to be in cache, so may be it's better to optimize cache misses instead of computation speed.