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
}
