Article: Increasing the D Compiler Speed by Over 75%

Dmitry Olshansky dmitry.olsh at gmail.com
Wed Jul 31 08:04:46 PDT 2013


31-Jul-2013 13:17, Walter Bright пишет:
> On 7/31/2013 1:49 AM, Dmitry Olshansky wrote:
>> Here key is 32 bits. Surely 2 strings can hash to the exact same 32
>> bit value.
>
> No, they cannot. The "hash value" is a pointer to the string. The
> strings are already inserted into another hash table,

The StringTable ? Then I have to look somewhere else entirely.

> so all strings
> that are the same are combined. Therefore, all unique strings "hash" to
> unique values.

Now that sets things straight ... if they ain't hashes then it isn't a 
hash table in the general sense :)

At least that means that contrary to my naive guess calcHash has no 
effect whatsoever on the distribution of keys in this AA. The "real hash 
function" could be rather biased. I've got to dig a bit deeper into the 
code then.

>
>> This resolves only slot collision. It doesn't resolve full hash
>> collision.
>
> If it was broken the compiler wouldn't work at all :-)

I had a feeling that it can't be that bad :)

-- 
Dmitry Olshansky


More information about the Digitalmars-d-announce mailing list