[ccache] Questions about two hot functions in ccache

Michael Niedermayer michaelni at gmx.at
Wed Oct 20 09:40:34 MDT 2010


On Wed, Oct 20, 2010 at 05:03:02PM +0200, Michael Niedermayer wrote:
[...]
> yet another way to get a fast 128bit hash function is to use a LFG
> heres an example:
> 
> tmp[i] = input[i] + tmp[i-7] + tmp[i-10]
> with input and tmp being uint64_t
> this can be implemented extreemly efficient by putting all 10 tmp values in
> registers requireing only 1 64bit read and 2 64bit additions for each 8 bytes
> of input if the loop is unrolled
> the output of that hash function would be 10*64bit and could either be used
> directly or passed through a second hash to get 128bit out of it
> other values instead of 7 and 10 can be used to improve the strength of this
> but then they wont fit in the 16 available registers on x86_64 anymore

Replying to my own mail ...
one way to make above stronger without completely loosing the register
optimization is to use
tmp[i] = input[i] + tmp[i-6] + tmp[i-31]
that way the tmp[i-6] case can still be read from register while tmp[i-31]
would need actual memory so this would need 1 write and 1 read more than
the case above

without the register optimization something like 
tmp[i] = input[i] + tmp[i-24] + tmp[i-55] can be used

One weakness of these hash functions is that theres a periodicy of 2^n in the
highest bit, that is moving the MSB of a 64bit input by 1024 64bit words
shouldnt change the hash of the 7,10 function. with the others this problem
is moved up to 2^31 and 2^55 which should be a non issue. How much this is of
relevance to ccache i dont know ...


[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

The bravest are surely those who have the clearest vision
of what is before them, glory and danger alike, and yet
notwithstanding go out to meet it. -- Thucydides
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://lists.samba.org/pipermail/ccache/attachments/20101020/88a67f3d/attachment.pgp>


More information about the ccache mailing list