{"thread":{"id":"56294","subject":"Bad behavior in xhistogram.c in the face of hash collisions?","startedAt":"2021-08-16T12:43:00Z","lastAt":"2022-08-26T15:53:55Z","messageCount":2,"participants":["Greg Hurrell"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"432796","messageId":"4e0eff48-4a3e-4f0e-9ed2-d01ec38442a5@www.fastmail.com","threadId":"56294","inReplyTo":null,"subject":"Bad behavior in xhistogram.c in the face of hash collisions?","fromName":"Greg Hurrell","fromEmail":"greg@hurrell.net","sentAt":"2021-08-16T12:40:27Z","receivedAt":"2021-08-16T12:43:00Z","isPatch":false,"sender":{"key":"greg@hurrell.net","avatar":"https://avatars.githubusercontent.com/u/7074?v=4"},"body":"Hi,\n\nI think I may have found a bug in the histogram diff algorithm that\nmanifests when there is a hash collision.  This behavior seems to exist\nin the JGit implimentation (https://git.io/J0Ud8) too, and was brought\nacross with the port-to-C in 8c912eea94a2.\n\nIn the following, any line numbers refer to xdiff/xhistogram.c as it\nexists in 5d213e46bb (2.33-rc2), as seen here: https://git.io/J0UHS\n\nThere are two phases in the algorithm which look up slots in the\nhistogram hash table based on the value of a hash function:\n\n1. During the backwards scan in `scanA`, each line in the old sequence\n   is considered and hashes are used to assign items to histogram\n   buckets.\n2. During the forwards scan of the new sequence we call `try_lcs` with\n   each line in turn and look up the corresponding histogram bucket.\n\nNow, the original JGit code comments suggests the intended behavior and\npurpose of the buckets is as follows:\n\n> To prevent the algorithm from having an O(N^2) running time, an upper\n> limit on the number of unique elements in a histogram bucket is\n> configured by `setMaxChainLength(int)`. If sequence A has more than\n> this many elements that hash into the same hash bucket, the algorithm\n> passes the region to `setFallbackAlgorithm(DiffAlgorithm)`. If no\n> fallback algorithm is configured, the region is emitted as a replace\n> edit.\n\nBut when I look at both the JGit and Git implementations, this is what I\nactually see:\n\nDuring the backwards scan we select a hash table bucket (at line 115)\nbased on the value of the item:\n\n    tbl_idx = TABLE_HASH(index, 1, ptr);\n\nIf there is a chain in the corresponding bucket and the values match\n(ie. hash to the same hash code and are equal) we prepend to the front\nof the chain (lines 121-133).\n\nIn the event of a hash collision, we proceed to the next item in the\nchain (line 135):\n\n    rec = rec->next;\n\nand check for a match. By definition, this check is always going\nto fail, because only identical elements ever get prepended onto\nchains. So this chain traversal serves only to measure the count of\nitems in the chain, something that we could have done in constant time\nby looking up `rec->cnt` anyway.\n\nAfter reaching the end of the chain and exiting the loop, provided we\ndidn't exceed the maximum chain length, we now create a new chain,\noverwriting the original occupant of the slot:\n\n    *rec_chain = rec;\n\nSo, during `scanA` we'll effectively destroy chains whenever there is a\nhash collision, which doesn't seem to be the intent of the original\nalgorithm.\n\nIn the second half of the algorithm, `try_lcs`, we have the inverse\nproblem. On line 165 we again look up the hash table slot:\n\n    struct record *rec = index->records[TABLE_HASH(index, 2, b_ptr)];\n\nOn line 169 we start a loop that will consider each record in the chain:\n\n    for (; rec; rec = rec->next) {\n\nDue to the construction of `scanA`, we know that every item in this\nchain must be identical, which in turn means that in the event of a hash\ncollision we are doomed to traverse the entire chain without finding a\nmatch:\n\n    if (!CMP(index, 1, as, 2, b_ptr))\n           continue;\n\nThat is at best unnecessary work, but also means that whenever we have\ncollisions we will have a set of \"orphaned\" records that aren't actually\nreachable from any chain in a hash table slot that we will look up, and\nthat doesn't seem to match the intended behavior of the algorithm, if I\nunderstand it correctly.\n\nIs this a big deal in practice? I suspect the reason we haven't noticed\nit is that:\n\n1.  Hash collisions are sufficiently rare (although, via the birthday\n    paradox, not _that_ rare, especially because we use the next power\n    of two to determine the number of slots in our hash table; ie. a\n    200-line file would have a 256-slot hash-table associated with it);\n    and:\n2.  Their consequences tend not to produce obviously broken diffs,\n    because the algorithm is just used to select split points around\n    which to apply itself recursively; we still produce a valid diff\n    even if we don't select the \"optimal\" split point.\n\nAnyway, I just wanted to gut-check this analysis with the list to see\nwhether it sounds right or not. The bug is pretty benign as far as I can\ntell, but still probably worth fixing, if it is a bug.\n\nCheers,\nGreg\n"},{"id":"461997","messageId":"70e68b28-73fa-4d16-a135-cbb03ea09d35@betaapp.fastmail.com","threadId":"56294","inReplyTo":"4e0eff48-4a3e-4f0e-9ed2-d01ec38442a5@www.fastmail.com","subject":"Re: Bad behavior in xhistogram.c in the face of hash collisions?","fromName":"Greg Hurrell","fromEmail":"greg@hurrell.net","sentAt":"2022-08-26T15:53:28Z","receivedAt":"2022-08-26T15:53:55Z","isPatch":false,"sender":{"key":"greg@hurrell.net","avatar":"https://avatars.githubusercontent.com/u/7074?v=4"},"body":"On Mon, Aug 16, 2021, at 2:40 PM, Greg Hurrell wrote:\n> \n> I think I may have found a bug in the histogram diff algorithm that\n> manifests when there is a hash collision.  This behavior seems to exist\n> in the JGit implimentation (https://git.io/J0Ud8) too, and was brought\n> across with the port-to-C in 8c912eea94a2.\n\nThought I had better bump the thread as I did a fire-and-forget on it\na year ago and never followed up because I wasn't super confident\nabout my findings.\n\nI'd be interested in corroboration of my analysis, to see whether there\nreally is a bug there. Not quoting my entire email here so as to keep\nthings brief, but the original can be seen at:\n\nhttps://public-inbox.org/git/4e0eff48-4a3e-4f0e-9ed2-d01ec38442a5@www.fastmail.com/\n\n(Phillip, CC'ing you for an opinion because I see you have made a few\nchanges to xdiff/xhistogram.c relatively recently.)\n\nBest wishes,\nGreg\n"}]}