{"thread":{"id":"34703","subject":"[PATCH] lookup_object: split up displacement penalty for hash collisions","startedAt":"2013-08-15T19:35:06Z","lastAt":"2013-08-16T13:49:52Z","messageCount":6,"participants":["Stefan Beller","Thomas Rast","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"225278","messageId":"1376595306-6335-1-git-send-email-stefanbeller@googlemail.com","threadId":"34703","inReplyTo":null,"subject":"[PATCH] lookup_object: split up displacement penalty for hash collisions","fromName":"Stefan Beller","fromEmail":"stefanbeller@googlemail.com","sentAt":"2013-08-15T19:35:06Z","receivedAt":"2013-08-15T19:35:06Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"A little background on hash tables first:\nConsider you want to have the object X, which you'd expect at position\ni, but because that place was already taken by B, it is not found at\nposition i, you start looking right of position i to find X until you\nfind it.\n\n index | i-1 | i | i+1 | i+2 | i+3 | i+4 |\n --------------------------------------------\n entry ... | A | B | C | D | E | X | ...\n --------------------------------------------\n\nOnce you have found X at i+4, the commit 9a414486d9f0 (2013-05-01,\nlookup_object: prioritize recently found objects) did an optimization\nand swapped the object B with X, so the placement looks like\n\n index | i-1 | i | i+1 | i+2 | i+3 | i+4 |\n --------------------------------------------\n entry ... | A | X | C | D | E | B | ...\n --------------------------------------------\n\nThis would improve the lookup times, because you'd likely be looking up X\nagain soon. However we are putting a heavy penalty on B for the collision.\nAlso suppose we'd look up B now, which is expected to be at i or even left\nfrom there (i-n). So it is a long way to go until B is found.\nSo if B were expected at the same place as X, we'd end up as before the\nswap, now penalizing the lookup of X again.\n\nJeff stated in the referenced commit, that another solution, an LRU\nscheduling would be to shift all of the objects. So when looking for X\nin the first diagram, once we found X, we'd shift all the objects and put\nX to position i:\n\n index | i-1 | i | i+1 | i+2 | i+3 | i+4 |\n --------------------------------------------\n entry ... | A | X | B | C | D | E | ...\n --------------------------------------------\n\nBut that strategy would need to go through all the positions, hence taking\neven longer.\n\n\nThis patch proposes another strategy: We split the penalty into parts and\nadd the penalty to different objects. To keep the overhead small, we're\nsplitting up the penalty to only 2 portions and assign it to the object B\nand an arbitrary object in the range between B and X.\n\nThe reason why moving that arbitrary object in between is analogous to the\nexplanation of moving the first object. See 9a414486d9f0 (2013-05-01,\nlookup_object: prioritize recently found objects) for a detailed explanation.\n\nBut which of the objects to choose from in between? At first I naively choose\nthe exact mid between those 2 objects, so here is the diagram from the beginning\nagain:\n\n index | i-1 | i | i+1 | i+2 | i+3 | i+4 |\n --------------------------------------------\n entry ... | A | B | C | D | E | X | ...\n --------------------------------------------\n\nIf we now want to find X and X is expected at i, we put X to\nthe position i and B to the middle position between B and X at D\nand D will go to the old position of X:\n\n index | i-1 | i | i+1 | i+2 | i+3 | i+4 |\n --------------------------------------------\n entry ... | A | X | C | B | E | D | ...\n --------------------------------------------\n\nSo let's test how it works out:\n\t# running the current git.git master (c1ebd90c832e), repeat 25 times:\n\tperf stat -r 25 -- ./git-rev-list --all --objects >/dev/null\n\t...\n\t5.294512141 seconds time elapsed ( +- 7.88% )\n\t# Now running with this patch applied:\n\t5.111576725 seconds time elapsed ( +- 8.17% )\n\nThis is an average 5 percent performance gain, though the measure times\nare varying itself by that amount (7.88 and 8.17 percent)\n\nThis approach is faster than before, because it still doesn't touch too\nmany object for resorting, but also doesn't put the penalty to one\noutlier. The lookup penalty is split up between two objects, which\nprobably have nothing to do with each other.\n\nBut is the mid object really the right thing to do? We could\nsplit the lookup penalty not into 2 halfs, but in a huge and a\nsmall amount. So instead of the mid object, we are free to\nchoose any other arbitrary object in between B and X. Let's try\nto use the nearest object (C) and farest object(E), because there\nwe may have better cache effects (near the objects we're accessing anyway)\nand the calculation is easier:\n\nIf using C as the mid object, we'd end up with\n\n index | i-1 | i | i+1 | i+2 | i+3 | i+4 |\n --------------------------------------------\n entry ... | A | X | B | D | E | C | ...\n --------------------------------------------\n\nor if taking the E object we'd end up with\n\n index | i-1 | i | i+1 | i+2 | i+3 | i+4 |\n --------------------------------------------\n entry ... | A | X | C | D | B | E | ...\n --------------------------------------------\n\n\t# Test with C as mid object (25 repetitions as well):\n\t# 5.35 seconds time elapsed ( +- 7.09% )\n\t# Test with E as mid object (25 repetitions as well):\n\t# 5.42 seconds time elapsed ( +- 6.50% )\n\nSo that was not successful, hence the initial idea to take the mid\nobject is in this patch. A second run of the original state and\nthis patch yieled a 5 percent performance gain again, so I am quite\nconfident now this patch is good.\n\nHowever please do check if this patch brings the promised performance\non your own, as you're likely using different hardware and another\nsoftware setup. Feel free to share your performance differences.\n\nSigned-off-by: Stefan Beller \n---\n object.c | 22 ++++++++++++++++++++--\n 1 file changed, 20 insertions(+), 2 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex d8a4b1f..014290d 100644\n--- a/object.c\n+++ b/object.c\n@@ -71,7 +71,7 @@ static unsigned int hashtable_index(const unsigned char *sha1)\n \n struct object *lookup_object(const unsigned char *sha1)\n {\n-\tunsigned int i, first;\n+\tunsigned int i, first, middle;\n \tstruct object *obj;\n \n \tif (!obj_hash)\n@@ -90,9 +90,27 @@ struct object *lookup_object(const unsigned char *sha1)\n \t\t * Move object to where we started to look for it so\n \t\t * that we do not need to walk the hash table the next\n \t\t * time we look for it.\n+\t\t * However, we don't want to penalize the the object being\n+\t\t * moved from the first position, so divide the penalty to\n+\t\t * two different objects.\n \t\t */\n+\n+\t\t/*\n+\t\t * First make sure i > first, so the middle is really\n+\t\t * in between the i and first object\n+\t\t */\n+\t\tif (i < first)\n+\t\t\ti += obj_hash_size;\n+\n+\t\tmiddle = (i + first) / 2;\n+\t\tif (i >= obj_hash_size)\n+\t\t\ti -= obj_hash_size;\n+\t\tif (middle >= obj_hash_size)\n+\t\t\tmiddle -= obj_hash_size;\n+\n \t\tstruct object *tmp = obj_hash[i];\n-\t\tobj_hash[i] = obj_hash[first];\n+\t\tobj_hash[i] = obj_hash[middle];\n+\t\tobj_hash[middle] = obj_hash[first];\n \t\tobj_hash[first] = tmp;\n \t}\n \treturn obj;\n-- \n1.8.4.rc3.498.g5af1768\n"},{"id":"225316","messageId":"87haeqdop3.fsf@linux-k42r.v.cablecom.net","threadId":"34703","inReplyTo":"1376595306-6335-1-git-send-email-stefanbeller@googlemail.com","subject":"Re: [PATCH] lookup_object: split up displacement penalty for hash collisions","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-08-16T08:28:40Z","receivedAt":"2013-08-16T08:28:40Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Stefan Beller writes:\n\n> A little background on hash tables first:\n> Consider you want to have the object X, which you'd expect at position\n> i, but because that place was already taken by B, it is not found at\n> position i, you start looking right of position i to find X until you\n> find it.\n>\n> index | i-1 | i | i+1 | i+2 | i+3 | i+4 |\n> --------------------------------------------\n> entry ... | A | B | C | D | E | X | ...\n> --------------------------------------------\n>\n> Once you have found X at i+4, the commit 9a414486d9f0 (2013-05-01,\n> lookup_object: prioritize recently found objects) did an optimization\n> and swapped the object B with X, so the placement looks like\n>\n> index | i-1 | i | i+1 | i+2 | i+3 | i+4 |\n> --------------------------------------------\n> entry ... | A | X | C | D | E | B | ...\n> --------------------------------------------\n[...]\n> If we now want to find X and X is expected at i, we put X to\n> the position i and B to the middle position between B and X at D\n> and D will go to the old position of X:\n>\n> index | i-1 | i | i+1 | i+2 | i+3 | i+4 |\n> --------------------------------------------\n> entry ... | A | X | C | B | E | D | ...\n> --------------------------------------------\n>\n> So let's test how it works out:\n> \t# running the current git.git master (c1ebd90c832e), repeat 25 times:\n> \tperf stat -r 25 -- ./git-rev-list --all --objects >/dev/null\n> \t...\n> \t5.294512141 seconds time elapsed ( +- 7.88% )\n> \t# Now running with this patch applied:\n> \t5.111576725 seconds time elapsed ( +- 8.17% )\n[...]\n> However please do check if this patch brings the promised performance\n> on your own, as you're likely using different hardware and another\n> software setup. Feel free to share your performance differences.\n\nI get this on an i7-M620 laptop from t/perf/p0001-rev-list.sh:\n\n Test HEAD next \n -------------------------------------------------------------------------------\n 0001.1: rev-list --all 6.29(6.03+0.22) 6.33(6.06+0.24) +0.6% \n 0001.2: rev-list --all --objects 53.22(52.48+0.54) 54.90(54.15+0.55) +3.2%*\n -------------------------------------------------------------------------------\n Significance hints: '.' 0.1 '*' 0.05 '**' 0.01 '***' 0.001\n\nAnd this on a newer i7-3930K workstation:\n\n Test HEAD next \n -------------------------------------------------------------------------------\n 0001.1: rev-list --all 3.86(3.71+0.14) 3.89(3.74+0.14) +0.7%* \n 0001.2: rev-list --all --objects 30.23(29.91+0.29) 30.35(30.04+0.29) +0.4%.\n -------------------------------------------------------------------------------\n Significance hints: '.' 0.1 '*' 0.05 '**' 0.01 '***' 0.001\n\nThat's using linux.git as a test repository, I figured the numbers were\ntoo small with git.git.\n\nI trust the laptop numbers less because it has far more thermal (and\nthus throttling) issues, but the runs do show a significant difference,\nthough less than you claimed.\n\n> @@ -90,9 +90,27 @@ struct object *lookup_object(const unsigned char *sha1)\n> \t\t * Move object to where we started to look for it so\n> \t\t * that we do not need to walk the hash table the next\n> \t\t * time we look for it.\n> +\t\t * However, we don't want to penalize the the object being\n> +\t\t * moved from the first position, so divide the penalty to\n> +\t\t * two different objects.\n> \t\t */\n> +\n> +\t\t/*\n> +\t\t * First make sure i > first, so the middle is really\n> +\t\t * in between the i and first object\n> +\t\t */\n> +\t\tif (i < first)\n> +\t\t\ti += obj_hash_size;\n> +\n> +\t\tmiddle = (i + first) / 2;\n> +\t\tif (i >= obj_hash_size)\n> +\t\t\ti -= obj_hash_size;\n> +\t\tif (middle >= obj_hash_size)\n> +\t\t\tmiddle -= obj_hash_size;\n> +\n> \t\tstruct object *tmp = obj_hash[i];\n\nAdding all the code above means that this declaration is now in the\nmiddle of things, which is not valid C90. Please move the declaration\nto the beginning of the block, and compile with\n-Wdeclaration-after-statement to notice this issue.\n\n> -\t\tobj_hash[i] = obj_hash[first];\n> +\t\tobj_hash[i] = obj_hash[middle];\n> +\t\tobj_hash[middle] = obj_hash[first];\n> \t\tobj_hash[first] = tmp;\n> \t}\n> \treturn obj;\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"225319","messageId":"8761v6dm0r.fsf@linux-k42r.v.cablecom.net","threadId":"34703","inReplyTo":"87haeqdop3.fsf@linux-k42r.v.cablecom.net","subject":"Re: [PATCH] lookup_object: split up displacement penalty for hash collisions","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-08-16T09:26:28Z","receivedAt":"2013-08-16T09:26:28Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Thomas Rast writes:\n\n> Stefan Beller writes:\n>\n>> However please do check if this patch brings the promised performance\n>> on your own, as you're likely using different hardware and another\n>> software setup. Feel free to share your performance differences.\n>\n> I get this on an i7-M620 laptop from t/perf/p0001-rev-list.sh:\n>\n> Test HEAD next \n> -------------------------------------------------------------------------------\n> 0001.1: rev-list --all 6.29(6.03+0.22) 6.33(6.06+0.24) +0.6% \n> 0001.2: rev-list --all --objects 53.22(52.48+0.54) 54.90(54.15+0.55) +3.2%*\n> -------------------------------------------------------------------------------\n> Significance hints: '.' 0.1 '*' 0.05 '**' 0.01 '***' 0.001\n[...]\n> I trust the laptop numbers less because it has far more thermal (and\n> thus throttling) issues, but the runs do show a significant difference,\n> though less than you claimed.\n\nWell, as I feared... another run on the same laptop:\n\nTest HEAD next \n------------------------------------------------------------------------------\n0001.1: rev-list --all 6.41(6.14+0.24) 6.36(6.10+0.23) -0.9%* \n0001.2: rev-list --all --objects 54.60(53.84+0.55) 54.23(53.50+0.53) -0.7%\n------------------------------------------------------------------------------\nSignificance hints: '.' 0.1 '*' 0.05 '**' 0.01 '***' 0.001\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"225320","messageId":"520DF3B3.3050900@googlemail.com","threadId":"34703","inReplyTo":"8761v6dm0r.fsf@linux-k42r.v.cablecom.net","subject":"Re: [PATCH] lookup_object: split up displacement penalty for hash collisions","fromName":"Stefan Beller","fromEmail":"stefanbeller@googlemail.com","sentAt":"2013-08-16T09:41:07Z","receivedAt":"2013-08-16T09:41:07Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On 08/16/2013 11:26 AM, Thomas Rast wrote:\n> Thomas Rast writes:\n> \n>> Stefan Beller writes:\n>>\n>>> However please do check if this patch brings the promised performance\n>>> on your own, as you're likely using different hardware and another\n>>> software setup. Feel free to share your performance differences.\n>>\n>> I get this on an i7-M620 laptop from t/perf/p0001-rev-list.sh:\n>>\n>> Test HEAD next \n>> -------------------------------------------------------------------------------\n>> 0001.1: rev-list --all 6.29(6.03+0.22) 6.33(6.06+0.24) +0.6% \n>> 0001.2: rev-list --all --objects 53.22(52.48+0.54) 54.90(54.15+0.55) +3.2%*\n>> -------------------------------------------------------------------------------\n>> Significance hints: '.' 0.1 '*' 0.05 '**' 0.01 '***' 0.001\n> [...]\n>> I trust the laptop numbers less because it has far more thermal (and\n>> thus throttling) issues, but the runs do show a significant difference,\n>> though less than you claimed.\n> \n> Well, as I feared... another run on the same laptop:\n> \n> Test HEAD next \n> ------------------------------------------------------------------------------\n> 0001.1: rev-list --all 6.41(6.14+0.24) 6.36(6.10+0.23) -0.9%* \n> 0001.2: rev-list --all --objects 54.60(53.84+0.55) 54.23(53.50+0.53) -0.7%\n> ------------------------------------------------------------------------------\n> Significance hints: '.' 0.1 '*' 0.05 '**' 0.01 '***' 0.001\n> \n\nI did some more tests as well, and I seem to have just been lucky with\nthe results initially posted. Now I got a negative impact as well on one\ntest, so that patch is not worth for includsion.\n\nThanks,\nStefan\n\n"},{"id":"225328","messageId":"20130816095722.GA11201@sigill.intra.peff.net","threadId":"34703","inReplyTo":"8761v6dm0r.fsf@linux-k42r.v.cablecom.net","subject":"Re: [PATCH] lookup_object: split up displacement penalty for hash collisions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-16T09:57:22Z","receivedAt":"2013-08-16T09:57:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 16, 2013 at 11:26:28AM +0200, Thomas Rast wrote:\n\n> > I trust the laptop numbers less because it has far more thermal (and\n> > thus throttling) issues, but the runs do show a significant difference,\n> > though less than you claimed.\n> \n> Well, as I feared... another run on the same laptop:\n> \n> Test HEAD next \n> ------------------------------------------------------------------------------\n> 0001.1: rev-list --all 6.41(6.14+0.24) 6.36(6.10+0.23) -0.9%* \n> 0001.2: rev-list --all --objects 54.60(53.84+0.55) 54.23(53.50+0.53) -0.7%\n> ------------------------------------------------------------------------------\n> Significance hints: '.' 0.1 '*' 0.05 '**' 0.01 '***' 0.001\n\nYeah, I get similar results on my i7-840QM. The new code is sometimes\nfaster and sometimes slower, never wins by more than 1%, and is well\nwithin the run-to-run noise (which seems to vary by up to 5%).\n\nI think the reason is that having a \"2-deep\" LRU cache helps less than\none might hope. There are a lot of objects in the hash table, but only a\nsmall fraction are \"hot\" at any time; specifically, those objects that\nare in the currently-examined tree. When we hit the \"X\" object from\nStefan's diagrams, we know that it is hot. But the \"B\" object may or may\nnot be hot. If it is, Stefan's optimization helps; if not, it does\nnothing.\n\nBut statistically it probably isn't hot. There are ~3 million objects in\nthe kernel repo, but only ~40,000 tree entries. So we would naively\nexpect it to have an effect in only ~1% of cases (I am not sure if that\nis accurate, though, as \"hot\" items within the same collision sequence\nwould tend to float to the front of the chain). I suspect any savings\nin those 1% are eaten up by the extra swapping, as well as the fact that\nthe \"hot\" B actually moves to the middle.\n\nAnother way to think about it is that if B is hot, it will then get\nlooked up again and get shifted to the front of the chain, pushing X\nback. So this is really only a win when two hot entries, X and B,\ncollide and trade the front position back and forth.\n\nIn that case, it seems like we would want to move B to the second\nposition. This lets the 2-hot case just keep swapping the hot items back\nand forth as quickly as possible. To the detriment of C, D, etc, which\nnever get promoted. But the likelihood of having _3_ hot items in a\ncollision chain is even less than 2.\n\nThat's all vague and hand-wavy intuition of course, and might be\ncompletely wrong. But it's at least a working theory that explains the\nexperimental results.\n\n-Peff\n"},{"id":"225343","messageId":"20130816134952.GG20138@sigill.intra.peff.net","threadId":"34703","inReplyTo":"20130816095722.GA11201@sigill.intra.peff.net","subject":"Re: [PATCH] lookup_object: split up displacement penalty for hash collisions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-16T13:49:52Z","receivedAt":"2013-08-16T13:49:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 16, 2013 at 05:57:22AM -0400, Jeff King wrote:\n\n> In that case, it seems like we would want to move B to the second\n> position. This lets the 2-hot case just keep swapping the hot items back\n> and forth as quickly as possible. To the detriment of C, D, etc, which\n> never get promoted. But the likelihood of having _3_ hot items in a\n> collision chain is even less than 2.\n\nThat was one of the cases Stefan considered in the original patch, but\ndidn't show code. Here's my make-shift code to try it; one could also\nparameterize it to shift down at most N items, and then just bump the\nN+1th item to the end (so the existing behavior is N=0, my patch is N+1,\netc).\n\nHowever, I measured no speedup at all. Oh well. It was worth a shot.\n\n---\n object.c | 17 +++++++++++++++--\n 1 file changed, 15 insertions(+), 2 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex d8a4b1f..f7ca969 100644\n--- a/object.c\n+++ b/object.c\n@@ -71,7 +71,7 @@ struct object *lookup_object(const unsigned char *sha1)\n \n struct object *lookup_object(const unsigned char *sha1)\n {\n-\tunsigned int i, first;\n+\tunsigned int i, first, middle;\n \tstruct object *obj;\n \n \tif (!obj_hash)\n@@ -90,9 +90,22 @@ struct object *lookup_object(const unsigned char *sha1)\n \t\t * Move object to where we started to look for it so\n \t\t * that we do not need to walk the hash table the next\n \t\t * time we look for it.\n+\t\t *\n+\t\t * However, we don't want to penalize the object being\n+\t\t * moved from the first position, so shift it down only one\n+\t\t * slot, and bump the next object to the end. This is faster\n+\t\t * than shifting the whole chain down, and covers the common\n+\t\t * case of a few \"hot\" items near the front of the chain.\n \t\t */\n+\t\tint second = (first + 1) % obj_hash_size;\n \t\tstruct object *tmp = obj_hash[i];\n-\t\tobj_hash[i] = obj_hash[first];\n+\n+\t\tif (i != second) {\n+\t\t\tobj_hash[i] = obj_hash[second];\n+\t\t\tobj_hash[second] = obj_hash[first];\n+\t\t} else\n+\t\t\tobj_hash[i] = obj_hash[first];\n+\n \t\tobj_hash[first] = tmp;\n \t}\n \treturn obj;\n-- \n1.8.4.rc2.28.g6bb5f3f\n"}]}