Article: Increasing the D Compiler Speed by Over 75%

[Dmitry Olshansky]

30-Jul-2013 22:22, Walter Bright пишет:
> On 7/30/2013 11:02 AM, Dmitry Olshansky wrote:

>>
>> 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.

Yes but it does so using full _hash_ alone.
Basically Key is size_t, if we store strings in this AA and they hash to 
exactly the same size_t "key" then you'll never find one of them.


>> 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];

***   ^^^ obviously key is only a hash value ***

>>          while (e)
>>          {
>>              if (key == e->key)
>>                  return e->value;
>>              e = e->next;
>
> **** ^^^ collision resolution code ^^^ *****


Here key is 32 bits. Surely 2 strings can hash to the exact same 32 bit 
value. This resolves only slot collision. It doesn't resolve full hash 
collision.

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


-- 
Dmitry Olshansky