Article: Increasing the D Compiler Speed by Over 75%

[Walter Bright]

On 7/30/2013 11:02 AM, Dmitry Olshansky wrote:
> 26-Jul-2013 23:17, Walter Bright пишет:
>> How about a pull request so we can try it out?
>
> Preliminary pull is here:
> https://github.com/D-Programming-Language/dmd/pull/2436
>
> So far it looses a bit.

:-) That's often been my experience.


> I'm still playing with it, looking at load factor,
> distribution of sizes, profiling.
>
> So far observations are that SpookyHash is slower then the one that was there
> thus stealing a few percents of speed. That is then hardly regained by a faster
> lookup of a slot:
> almost all of "large" tables were 31 in size and you have special case for that
> anyway.
>
> What bothers me is that while I've been hacking at this I couldn't shake off the
> feeling that AA code assumes NO FULL HASH COLLISIONS at all?

I don't know what you mean, as it has a collision resolution system. See 
embedded code below.


> Isn't that betting on luck (and a crude hash) a little too much (esp in 32 bit
> mode)?
>
> That is e.g. in code pasted from aav.c Key is only a hash and there is no way
> whatsoever to discern a full hash collision.
>
> Value _aaGetRvalue(AA* aa, Key key)
> {
>      //printf("_aaGetRvalue(key = %p)\n", key);
>      if (aa)
>      {
>          size_t i;
>          size_t len = aa->b_length;
>          if (len == 4)
>              i = (size_t)key & 3;
>          else if (len == 31)
>              i = (size_t)key % 31;
>          else
>              i = (size_t)key % len;
>          aaA* e = aa->b[i];
>          while (e)
>          {
>              if (key == e->key)
>                  return e->value;
>              e = e->next;

**** ^^^ collision resolution code ^^^ *****

>          }
>      }
>      return NULL;    // not found
> }