{"thread":{"id":"38222","subject":"XDL_FAST_HASH can be very slow","startedAt":"2014-12-22T04:19:45Z","lastAt":"2014-12-23T02:51:05Z","messageCount":4,"participants":["Jeff King","Patrick Reynolds","Thomas Rast","demerphq"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"253914","messageId":"20141222041944.GA441@peff.net","threadId":"38222","inReplyTo":null,"subject":"XDL_FAST_HASH can be very slow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-12-22T04:19:45Z","receivedAt":"2014-12-22T04:19:45Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"I ran across an interesting case that diffs very slowly with modern git.\nAnd it's even public. You can clone:\n\n git://github.com/outpunk/evil-icons\n\nand try:\n\n git show fc4efe426d5b4e6aa8d5a4dc14babeada7c5f899\n\n(which is also the tip of master as of this writing).\n\nThe interesting file there is a 10MB Illustrator file, \"assets/ei.ai\".\nGit treats it as text, as the early part doesn't have any NULs, but it\nis mostly non-human-readable. It has a large number of lines, and some\nof the lines themselves are quite large.\n\nOn my machine, \"git show\" takes ~77 seconds using v2.2.1. But if I build\nthe same version with \"make XDL_FAST_HASH=\", it completes in about 0.4s.\nBoth produce the same output.\n\nI'm not really sure what's going on. A few points of interest:\n\n - You can replicate this with the very first commit that added\n XDL_FAST_HASH, 6942efc (xdiff: load full words in the inner loop of\n xdl_hash_record, 2012-04-06). So it was always bad on this case, and\n it's not part of any more recent changes.\n\n - We actually _don't_ spend most of our time in xdl_hash_record, the\n function modified by 6942efc. Instead, it all goes to\n xdl_classify_record, which is looping over the set of hash records.\n It's not clear to me if more or different hash records is part of the\n design of XDL_FAST_HASH, or if this is actually a bug.\n\nI haven't dug much further than that.\n\n-Peff\n"},{"id":"253916","messageId":"CAJrMUs_fM8+=2j1e5hYiaRjQq1QF87X6qOLN847q-B7Nu-wniw@mail.gmail.com","threadId":"38222","inReplyTo":"20141222041944.GA441@peff.net","subject":"Re: XDL_FAST_HASH can be very slow","fromName":"Patrick Reynolds","fromEmail":"piki@github.com","sentAt":"2014-12-22T09:08:12Z","receivedAt":"2014-12-22T09:08:12Z","isPatch":false,"sender":{"key":"piki@github.com","avatar":null},"body":"I have been working with Peff on this and have more results to share.\n\nFor background, xdl_hash_record is a hashing function, producing an\nunsigned long from an input string terminated by either a newline or\nthe end of the mmap'd file.\n\nThe original xdl_hash_record is essentially DJB hash, which does a\nmultiplication, load, and xor for each byte of the input. Commit\n6942efc introduces an \"XDL_FAST_HASH\" version of the same function\nthat is clearly inspired by the DJB hash, but it does only one\nmultiplication, load, and xor for each 8 bytes of input -- i.e., fewer\nloads, but also a lot less bit mixing. Less mixing means far more\ncollisions, leading to the performance problems with evil-icons. It's\nnot clear to me if the XDL_FAST_HASH version intended to match the\noutput of the DJB hash function, but it doesn't at all.\n\nPeff has been experimenting with using two modern hash functions, FNV\nand Murmur3. In theory, these should produce fewer collisions than\nDJB, but in his measurements, they didn't run diff any faster than\nplain DJB. They do fix the evil-icons problem.\n\nI have implemented two simpler possibilities, both of which fix the\nproblems diffing the evil-icons repository:\n\n1. An XDL_FAST_HASH implementation that matches the output of the DJB\nhash exactly. Its performance is basically the same as DJB, because\nthe only thing is does differently is load 8 bytes at a time instead\nof 1. It does all the same ALU operations as DJB.\n\n2. Using (hash % prime_number) instead of (hash & ((1< writes:\n\n> The original xdl_hash_record is essentially DJB hash, which does a\n> multiplication, load, and xor for each byte of the input. Commit\n> 6942efc introduces an \"XDL_FAST_HASH\" version of the same function\n> that is clearly inspired by the DJB hash, but it does only one\n> multiplication, load, and xor for each 8 bytes of input -- i.e., fewer\n> loads, but also a lot less bit mixing. Less mixing means far more\n> collisions, leading to the performance problems with evil-icons. It's\n> not clear to me if the XDL_FAST_HASH version intended to match the\n> output of the DJB hash function, but it doesn't at all.\n\nNote that XDL_FAST_HASH is just a ripoff of the hashing scheme that\nLinus socially engineered on G+ around that time. I didn't do any of\nthe hash genealogy that you did here, and it now shows. The orginal\npatches are linked from 6942efc (xdiff: load full words in the inner loop of\nxdl_hash_record, 2012-04-06):\n\n https://lkml.org/lkml/2012/3/2/452\n https://lkml.org/lkml/2012/3/5/6\n\nThe code still exists:\n\n https://github.com/torvalds/linux/blob/master/fs/namei.c#L1678\n\n> I have implemented two simpler possibilities, both of which fix the\n> problems diffing the evil-icons repository:\n\nI think it would be best to separate three goals here:\n\n1. hash function throughput\n2. quality of the hash values\n3. avoiding collision attacks\n\nXDL_FAST_HASH was strictly an attempt to improve throughput, and fairly\nsuccessful at that (6942efc (xdiff: load full words in the inner loop of\nxdl_hash_record, 2012-04-06) quotes an 8% improvement on 'git log -p').\n\nYou are now addressing quality.\n\nI have no idea how you ran into this, but if you are reworking things\nalready, I think it would be good to also randomize whatever hash you\nput in so as to give some measure of protection against collision\nattacks.\n\n> 1. An XDL_FAST_HASH implementation that matches the output of the DJB\n> hash exactly. Its performance is basically the same as DJB, because\n> the only thing is does differently is load 8 bytes at a time instead\n> of 1. It does all the same ALU operations as DJB.\n\nI don't think there's a point in having such a function, since it would\nmean a lot of code for no throughput gain. Let's just remove\nXDL_FAST_HASH and the original hashing scheme in favor of a better hash\nfunction.\n\n-- \nThomas Rast\ntr@thomasrast.ch\n"},{"id":"253986","messageId":"CANgJU+X1XvM7zMiBV5Auo+bi2Dup8z7GohGY=SJwWNDxMzB+zg@mail.gmail.com","threadId":"38222","inReplyTo":"87r3vsrmdc.fsf@thomasrast.ch","subject":"Re: XDL_FAST_HASH can be very slow","fromName":"demerphq","fromEmail":"demerphq@gmail.com","sentAt":"2014-12-23T02:51:05Z","receivedAt":"2014-12-23T02:51:05Z","isPatch":false,"sender":{"key":"demerphq@gmail.com","avatar":null},"body":"(sorry for the repost, I use gmail and it send html mails by default).\nOn 22 December 2014 at 11:48, Thomas Rast wrote:\n>\n> 1. hash function throughput\n> 2. quality of the hash values\n> 3. avoiding collision attacks\n>\n> XDL_FAST_HASH was strictly an attempt to improve throughput, and fairly\n> successful at that (6942efc (xdiff: load full words in the inner loop of\n> xdl_hash_record, 2012-04-06) quotes an 8% improvement on 'git log -p').\n>\n> You are now addressing quality.\n>\n> I have no idea how you ran into this, but if you are reworking things\n> already, I think it would be good to also randomize whatever hash you\n> put in so as to give some measure of protection against collision\n> attacks.\n\nI assume you mean DJB2 when you say DJB, and if so I will just note\nthat it is a pretty terrible hash function for arbitrary data. (I\nunderstand it does better with raw text.) It does not pass either\nstrict-avalanche-criteria[1], nor does it pass the\nbit-independence-criteria[2]. I have images which show how badly DJB2\nfails these tests if anyone is interested.\n\nMurmur3 is better, in that it does pass SAC and BIC, but before you\ndecide to use Murmur3 you should review https://131002.net/siphash/and\nrelated resources which demonstrate multi-collision attacks on Murmur3\nwhich are independent of the seed chosen. The paper also introduces a\nnew hash function with good performance properties, and claims that it\nhas cyptographic strength. (I say claims because I am not qualified to\njudge if it is or not.) Eg:\nhttps://131002.net/siphash/murmur3collisions-20120827.tar.gz\n\nI think if you want performance and robustness against collision\nattacks Siphash is a good candidate, as is perhaps the AES derived\nhash used by the Go folks, but the performance of that algorithm is\nstrongly dependent on the CPU supporting AES primitives.\n\nAnyway, the point is that simply adding a random seed to a hash\nfunction like DJB2 or Murmur3 is not sufficient to prevent collision\nattacks.\n\nYves\n[1] A change in a single bit of the seed or the key should result in\n50% of the output bits of the hash changing.\n[2] output bits j and k should change independently when any single\ninput bit i is inverted, for all i, j and k.\n"}]}