apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Branko ─îibej <br...@xbc.nu>
Subject Re: Hash?
Date Wed, 03 Jan 2001 20:53:18 GMT
rbb@covalent.net wrote:

>> This was suggested by Carlos Hasan mailto:chasan@acm.org but as I'm not
>> overly familiar with the hashing code I'm putting it forward rather than
>> committing it :)
> 
>>       */
>>      hash = 0;
>>      for (p = key, i = klen; i; i--, p++)
>> -       hash = hash * 33 + *p;
>> +        hash += (hash << 5) + *p;
>> +
>>      /* scan linked list */
>>      for (hep = &ht->array[hash & ht->max], he = *hep;
>>          he;
> 
> 
> Ummmm,  those aren't equal.

Of course they are.  (hash * 33) == (hash + hash * 32) == (hash += (hash 
<< 5)).

However, I'd let the compiler work that out, or the processor microcode, 
or whatever. The days when using shifts and adds was faster than using 
multiplies (in the code) are long gone; compilers have become a bit 
smarter in the last 20 years.

Besides, on some architectures the shift + add may actually be slower 
than the multiply. Let's not commit this unless he can come up with 
corroborating evidence (i.e., performance measurements) from at least 
five popular, but wildly different architectures, using the same compiler.



(Note: A couple of months ago I changed a hash function in Subversion to 
multiply with 127 ((x << 7) - x) instead of 47 ((x << 5) + (x << 4) - 
x), and guess what, it was /way/ faster. But I measured the performance 
change on four different platforms first.)


-- 
Brane ─îibej
    home:   <brane@xbc.nu>             http://www.xbc.nu/brane/
    work:   <branko.cibej@hermes.si>   http://www.hermes-softlab.com/
     ACM:   <brane@acm.org>            http://www.acm.org/



Mime
View raw message