On Tue, Oct 19, 2010 at 11:18:06PM -0200, Ramiro Polla wrote: > Hi, > > On Tue, Oct 19, 2010 at 7:15 PM, Joel Rosdahl <j...@rosdahl.net> wrote: > > On 2010-10-18 03:44, Justin Lebar wrote: > >> So it appears that 13% of my CPU time is spent computing md4 hashes, > >> while another 25% is spent in hash_source_code_string but outside the > >> MD4 code. > >> > >> To someone new to the code like me, it appears that there's some room > >> for optimization here. > > > > Indeed. (This was by the way mentioned on the list a couple of weeks > > ago: http://www.mail-archive.com/ccache@lists.samba.org/msg00532.html) > [...] > >> * Why does ccache still use MD4? Surely there's a better / faster hash > >> out there. I noticed that ccache includes murmurhash, but it doesn't > >> seem like it's used in too many places. There's probably a good reason > >> for this, but it's not too apparent to me. > >> [...] > > > > I added murmurhash to get a good hash function for some hash tables I > > introduced when implementing the direct mode, which is a relatively late > > invention. I'm far from an expert on hash functions, but surely > > murmurhash and similar functions (that are designed to be good hash > > functions for a hash table) aren't suitable to use for identifying > > (without verification) arbitrary content like a cryptograhic hash > > function is. Even the 64-bit version of murmurhash has way too high > > collision rate. > > > > MD4 has been there from the start and neither Tridge or I have seen any > > reason to switch it. MD5, SHA1 and other even more modern cryptograhic > > hash functions are indeed stronger but also slower, and the increased > > resistance against various crypto attacks doesn't seem necessary in a > > tool like ccache. That said, I'm sure there nowadays may exist hash > > functions that are both better (i.e., with lower collision rate) AND > > faster than MD4. Do you (or anyone else) know of any with properties > > that would be a good fit for ccache? > > I'm CC'ing a couple of gurus from FFmpeg in the hope that they can help us.
Iam not really a hash function expert but i know enough math and random number stuff that i think iam able to comment ... I assume crypto strength isnt needed and about 64bit collision protection should be there. That would require at least a 128bit hash. The first obvious choice is a 128bit CRC this requires a table lookup per byte though and some 128bit xor and is likely not the fastest but there should be no doubt about it being good enough The next idea i have is something along the lines of adler32 first we would use 32bit instead of 8bit input (makes it 4 times faster and requires a 32bit prime) at this point we would have a 64bit checksum, luckily adler32 can easily be extended by adding 2 higher order stages the result would look like this: #define BASE 0x10000000F // 32bit prime adler128(const uint32_t *input, int len){ uint64_t a,b,c,d while (len>0) { while(len>0 && d<CONSTANT_TO_PREVENT_OVERFLOW){ uint32_t in=*input++; len--; d+=c; c+=b; b+=a; a+=in } a %= BASE; b %= BASE; c %= BASE; d %= BASE; } return "a,b,c,d" } The above checksum should have the property that any 2 inputs that produce the same checksum must either be equal or differ in at least 4 32bit words and it should be stronger than adler32 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 -- Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB Awnsering whenever a program halts or runs forever is On a turing machine, in general impossible (turings halting problem). On any real computer, always possible as a real computer has a finite number of states N, and will either halt in less than N cycles or never halt.
signature.asc
Description: Digital signature
_______________________________________________ ccache mailing list ccache@lists.samba.org https://lists.samba.org/mailman/listinfo/ccache