{"thread":{"id":"33697","subject":"[PATCH] lookup_object: prioritize recently found objects","startedAt":"2013-05-01T20:34:50Z","lastAt":"2013-05-03T06:16:05Z","messageCount":12,"participants":["Jeff King","Junio C Hamano","Johannes Sixt"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"216192","messageId":"20130501203449.GA12535@sigill.intra.peff.net","threadId":"33697","inReplyTo":null,"subject":"[PATCH] lookup_object: prioritize recently found objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-01T20:34:50Z","receivedAt":"2013-05-01T20:34:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The lookup_object function is backed by a hash table of all\nobjects we have seen in the program. We manage collisions\nwith a linear walk over the colliding entries, checking each\nwith hashcmp(). The main cost of lookup is in these\nhashcmp() calls; finding our item in the first slot is\ncheaper than finding it in the second slot, which is cheaper\nthan the third, and so on.\n\nIf we assume that there is some locality to the object\nlookups (e.g., if X and Y collide, and we have just looked\nup X, the next lookup is more likely to be for X than for\nY), then we can improve our average lookup speed by checking\nX before Y.\n\nThis patch does so by swapping a found item to the front of\nthe collision chain. The p0001 perf test reveals that this\ndoes indeed exploit locality in the case of \"rev-list --all\n--objects\":\n\nTest                               origin          this tree\n-------------------------------------------------------------------------\n0001.1: rev-list --all             0.40(0.38+0.02) 0.40(0.36+0.03) +0.0%\n0001.2: rev-list --all --objects   2.24(2.17+0.05) 1.86(1.79+0.05) -17.0%\n\nThis is not surprising, as the full object traversal will\nhit the same tree entries over and over (e.g., for every\ncommit that doesn't change \"Documentation/\", we will have to\nlook up the same sha1 just to find out that we already\nprocessed it).\n\nThe reason why this technique works (and does not violate\nany properties of the hash table) is subtle and bears some\nexplanation. Let's imagine we get a lookup for sha1 `X`, and\nit hashes to bucket `i` in our table. That stretch of the\ntable may look like:\n\nindex       | i-1 |  i  | i+1 | i+2 |\n       -----------------------------------\nentry   ... |  A  |  B  |  C  |  X  | ...\n       -----------------------------------\n\nWe start our probe at i, see that B does not match, nor does\nC, and finally find X. There may be multiple C's in the\nmiddle, but we know that there are no empty slots (or else\nwe would not find X at all).\n\nWe do not know the original index of B; it may be `i`, or it\nmay be less than i (e.g., if it were `i-1`, it would collide\nwith A and spill over into the `i` bucket). So it is\nacceptable for us to move it to the right of a contiguous\nstretch of entries (because we will find it from a linear\nwalk starting anywhere at `i` or before), but never to the\nleft (if we moved it to `i-1`, we would miss it when\nstarting our walk at `i`).\n\nWe do know the original index of X; it is `i`, so it is safe\nto place it anywhere in the contiguous stretch between `i`\nand where we found it (`i+2` in the this case).\n\nThis patch does a pure swap; after finding X in the\nsituation above, we would end with:\n\nindex       | i-1 |  i  | i+1 | i+2 |\n       -----------------------------------\nentry   ... |  A  |  X  |  C  |  B  | ...\n       -----------------------------------\n\nWe could instead bump X into the `i` slot, and then shift\nthe whole contiguous chain down by one, resulting in:\n\nindex       | i-1 |  i  | i+1 | i+2 |\n       -----------------------------------\nentry   ... |  A  |  X  |  B  |  C  | ...\n       -----------------------------------\n\nThat puts our chain in true most-recently-used order.\nHowever, experiments show that it is not any faster (and in\nfact, is slightly slower due to the extra manipulation).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nThe speedup on linux.git is less spectacular; I got about 9% improvement\nversus stock git. However, when I combine this with the commit cache we\nwere looking at a few months ago, at which point the lookup_object time\nstarts to dominate, then doing this nets more like 20% on linux.git.\n\nIt may speed up other tree-oriented loads, too, but I didn't measure. At\nthe very least, it should generally not be making other loads worse.\n\n object.c | 9 +++++++--\n 1 file changed, 7 insertions(+), 2 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex 20703f5..1ba2083 100644\n--- a/object.c\n+++ b/object.c\n@@ -71,13 +71,13 @@ struct object *lookup_object(const unsigned char *sha1)\n \n struct object *lookup_object(const unsigned char *sha1)\n {\n-\tunsigned int i;\n+\tunsigned int i, first;\n \tstruct object *obj;\n \n \tif (!obj_hash)\n \t\treturn NULL;\n \n-\ti = hashtable_index(sha1);\n+\tfirst = i = hashtable_index(sha1);\n \twhile ((obj = obj_hash[i]) != NULL) {\n \t\tif (!hashcmp(sha1, obj->sha1))\n \t\t\tbreak;\n@@ -85,6 +85,11 @@ struct object *lookup_object(const unsigned char *sha1)\n \t\tif (i == obj_hash_size)\n \t\t\ti = 0;\n \t}\n+\tif (obj && i != first) {\n+\t\tstruct object *tmp = obj_hash[i];\n+\t\tobj_hash[i] = obj_hash[first];\n+\t\tobj_hash[first] = tmp;\n+\t}\n \treturn obj;\n }\n \n-- \n1.8.2.2.10.geb24d2a\n"},{"id":"216203","messageId":"7vwqri4b4g.fsf@alter.siamese.dyndns.org","threadId":"33697","inReplyTo":"20130501203449.GA12535@sigill.intra.peff.net","subject":"Re: [PATCH] lookup_object: prioritize recently found objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-01T21:57:03Z","receivedAt":"2013-05-01T21:57:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> We could instead bump X into the `i` slot, and then shift\n> the whole contiguous chain down by one, resulting in:\n>\n> index       | i-1 |  i  | i+1 | i+2 |\n>        -----------------------------------\n> entry   ... |  A  |  X  |  B  |  C  | ...\n>        -----------------------------------\n>\n> That puts our chain in true most-recently-used order.\n> However, experiments show that it is not any faster (and in\n> fact, is slightly slower due to the extra manipulation).\n\nMakes quite a lot of sense to me.  Very simple, clean and nice.\n"},{"id":"216231","messageId":"51820B37.8010503@viscovery.net","threadId":"33697","inReplyTo":"20130501203449.GA12535@sigill.intra.peff.net","subject":"Re: [PATCH] lookup_object: prioritize recently found objects","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2013-05-02T06:44:07Z","receivedAt":"2013-05-02T06:44:07Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 5/1/2013 22:34, schrieb Jeff King:\n>  struct object *lookup_object(const unsigned char *sha1)\n>  {\n> -\tunsigned int i;\n> +\tunsigned int i, first;\n>  \tstruct object *obj;\n>  \n>  \tif (!obj_hash)\n>  \t\treturn NULL;\n>  \n> -\ti = hashtable_index(sha1);\n> +\tfirst = i = hashtable_index(sha1);\n>  \twhile ((obj = obj_hash[i]) != NULL) {\n>  \t\tif (!hashcmp(sha1, obj->sha1))\n>  \t\t\tbreak;\n> @@ -85,6 +85,11 @@ struct object *lookup_object(const unsigned char *sha1)\n>  \t\tif (i == obj_hash_size)\n>  \t\t\ti = 0;\n>  \t}\n> +\tif (obj && i != first) {\n> +\t\tstruct object *tmp = obj_hash[i];\n> +\t\tobj_hash[i] = obj_hash[first];\n> +\t\tobj_hash[first] = tmp;\n> +\t}\n>  \treturn obj;\n>  }\n\nThis is one of the places where I think the code does not speak for itself\nand a comment is warranted: The new if statement is not about correctness,\nbut about optimization:\n\n\t\t/*\n\t\t * Move object to where we started to look for it\n\t\t * so that we do not need to walk the hash table\n\t\t * the next time we look for it.\n\t\t */\n\nor something.\n\n-- Hannes\n"},{"id":"216232","messageId":"20130502064630.GA15208@sigill.intra.peff.net","threadId":"33697","inReplyTo":"51820B37.8010503@viscovery.net","subject":"Re: [PATCH] lookup_object: prioritize recently found objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-02T06:46:30Z","receivedAt":"2013-05-02T06:46:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 02, 2013 at 08:44:07AM +0200, Johannes Sixt wrote:\n\n> Am 5/1/2013 22:34, schrieb Jeff King:\n> >  struct object *lookup_object(const unsigned char *sha1)\n> >  {\n> > -\tunsigned int i;\n> > +\tunsigned int i, first;\n> >  \tstruct object *obj;\n> >  \n> >  \tif (!obj_hash)\n> >  \t\treturn NULL;\n> >  \n> > -\ti = hashtable_index(sha1);\n> > +\tfirst = i = hashtable_index(sha1);\n> >  \twhile ((obj = obj_hash[i]) != NULL) {\n> >  \t\tif (!hashcmp(sha1, obj->sha1))\n> >  \t\t\tbreak;\n> > @@ -85,6 +85,11 @@ struct object *lookup_object(const unsigned char *sha1)\n> >  \t\tif (i == obj_hash_size)\n> >  \t\t\ti = 0;\n> >  \t}\n> > +\tif (obj && i != first) {\n> > +\t\tstruct object *tmp = obj_hash[i];\n> > +\t\tobj_hash[i] = obj_hash[first];\n> > +\t\tobj_hash[first] = tmp;\n> > +\t}\n> >  \treturn obj;\n> >  }\n> \n> This is one of the places where I think the code does not speak for itself\n> and a comment is warranted: The new if statement is not about correctness,\n> but about optimization:\n\nI figured the lengthy description in the commit message would be\nsufficient, but I don't mind adding something like your suggestion to\npoint readers of the code in the right direction when they see it.\n\n-Peff\n"},{"id":"216233","messageId":"5182101D.4050807@viscovery.net","threadId":"33697","inReplyTo":"20130502064630.GA15208@sigill.intra.peff.net","subject":"Re: [PATCH] lookup_object: prioritize recently found objects","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2013-05-02T07:05:01Z","receivedAt":"2013-05-02T07:05:01Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 5/2/2013 8:46, schrieb Jeff King:\n> On Thu, May 02, 2013 at 08:44:07AM +0200, Johannes Sixt wrote:\n>> Am 5/1/2013 22:34, schrieb Jeff King:\n>>>  struct object *lookup_object(const unsigned char *sha1)\n>>>  {\n>>> -\tunsigned int i;\n>>> +\tunsigned int i, first;\n>>>  \tstruct object *obj;\n>>>  \n>>>  \tif (!obj_hash)\n>>>  \t\treturn NULL;\n>>>  \n>>> -\ti = hashtable_index(sha1);\n>>> +\tfirst = i = hashtable_index(sha1);\n>>>  \twhile ((obj = obj_hash[i]) != NULL) {\n>>>  \t\tif (!hashcmp(sha1, obj->sha1))\n>>>  \t\t\tbreak;\n>>> @@ -85,6 +85,11 @@ struct object *lookup_object(const unsigned char *sha1)\n>>>  \t\tif (i == obj_hash_size)\n>>>  \t\t\ti = 0;\n>>>  \t}\n>>> +\tif (obj && i != first) {\n>>> +\t\tstruct object *tmp = obj_hash[i];\n>>> +\t\tobj_hash[i] = obj_hash[first];\n>>> +\t\tobj_hash[first] = tmp;\n>>> +\t}\n>>>  \treturn obj;\n>>>  }\n>>\n>> This is one of the places where I think the code does not speak for itself\n>> and a comment is warranted: The new if statement is not about correctness,\n>> but about optimization:\n> \n> I figured the lengthy description in the commit message would be\n> sufficient,\n\nIt's absolutely sufficient *if* one reads the commit message. In this\ncase, though it goes more like \"this function should be trivial, and it is\n-- up to this if statement; what the heck is it good for?\" and the reader\nis forced to dig the history.\n\nBTW, do you notice that the function is now modifying an object (the hash\ntable) even though this is rather unexpected from a \"lookup\" function?\n\n-- Hannes\n"},{"id":"216266","messageId":"7v4nel2xza.fsf@alter.siamese.dyndns.org","threadId":"33697","inReplyTo":"20130502064630.GA15208@sigill.intra.peff.net","subject":"Re: [PATCH] lookup_object: prioritize recently found objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-02T15:38:33Z","receivedAt":"2013-05-02T15:38:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> I figured the lengthy description in the commit message would be\n> sufficient, but I don't mind adding something like your suggestion to\n> point readers of the code in the right direction when they see it.\n\nYeah, I'll squash J6t's comment in and requeue.\n\nIf somebody is learning the internals by reading code, having a\ncomment there would certainly help.\n"},{"id":"216268","messageId":"7vzjwd1j27.fsf@alter.siamese.dyndns.org","threadId":"33697","inReplyTo":"5182101D.4050807@viscovery.net","subject":"Re: [PATCH] lookup_object: prioritize recently found objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-02T15:46:08Z","receivedAt":"2013-05-02T15:46:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Sixt <j.sixt@viscovery.net> writes:\n\n> BTW, do you notice that the function is now modifying an object (the hash\n> table) even though this is rather unexpected from a \"lookup\" function?\n\nAt the philosophical level, \"lookup\" ought to be operating on a\n\"const\" table.  But at the implementation level, the table does not\nhave to be \"const\" in the sense the implemenation language and data\nstructure defines.\n\nI think this patch is a good example of that.\n\nI am kind of surprised that Jeff's attempt to do a full LRU made\nthings worse, though.  The only additional code compared to swap is\na single memmove(): are we colliding too often (having to move a\nlot)?\n"},{"id":"216269","messageId":"20130502154618.GA18462@sigill.intra.peff.net","threadId":"33697","inReplyTo":"5182101D.4050807@viscovery.net","subject":"Re: [PATCH] lookup_object: prioritize recently found objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-02T15:46:18Z","receivedAt":"2013-05-02T15:46:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 02, 2013 at 09:05:01AM +0200, Johannes Sixt wrote:\n\n> > I figured the lengthy description in the commit message would be\n> > sufficient,\n> \n> It's absolutely sufficient *if* one reads the commit message. In this\n> case, though it goes more like \"this function should be trivial, and it is\n> -- up to this if statement; what the heck is it good for?\" and the reader\n> is forced to dig the history.\n\nWhat I really didn't want to do was to rewrite the whole rationale\nagain. I think something like:\n\n  /*\n   * Move the found object to the front of the collision chain;\n   * this is a pure optimization that can make future lookups cheaper,\n   * assuming there is some time-locality to which objects are looked\n   * up.\n   */\n\nwould be enough, and interested parties can go to the commit history (I\ntend to go there pretty rapidly if there is a chunk of code that sticks\nout, but I guess not everybody does).\n\n> BTW, do you notice that the function is now modifying an object (the hash\n> table) even though this is rather unexpected from a \"lookup\" function?\n\nI think this is fine. The function is conceptually constant from the\noutside; callers don't even know about the hash table. They just know\nthat there is some mapping. It's similar to the way that lookup_commit\nwill lazily allocate the \"struct commit\". The callers do not care\nwhether it exists already or not; they care that at the end of the\nfunction, they have a pointer to the commit. Everything else is an\nimplementation detail.\n\n-Peff\n"},{"id":"216270","messageId":"20130502155037.GB18462@sigill.intra.peff.net","threadId":"33697","inReplyTo":"7vzjwd1j27.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] lookup_object: prioritize recently found objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-02T15:50:37Z","receivedAt":"2013-05-02T15:50:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 02, 2013 at 08:46:08AM -0700, Junio C Hamano wrote:\n\n> Johannes Sixt <j.sixt@viscovery.net> writes:\n> \n> > BTW, do you notice that the function is now modifying an object (the hash\n> > table) even though this is rather unexpected from a \"lookup\" function?\n> \n> At the philosophical level, \"lookup\" ought to be operating on a\n> \"const\" table.  But at the implementation level, the table does not\n> have to be \"const\" in the sense the implemenation language and data\n> structure defines.\n> \n> I think this patch is a good example of that.\n\nVery much agreed.\n\n> I am kind of surprised that Jeff's attempt to do a full LRU made\n> things worse, though.  The only additional code compared to swap is\n> a single memmove(): are we colliding too often (having to move a\n> lot)?\n\nI actually didn't use memmove, but a hand-rolled loop. I wonder if that\nwould have made the difference. It's a little tricky because you may\nhave to cross the mod(obj_hash_size) wrap-around. The patch I tested\nwas:\n\ndiff --git a/object.c b/object.c\nindex 1ba2083..8b2412c 100644\n--- a/object.c\n+++ b/object.c\n@@ -85,10 +85,13 @@ struct object *lookup_object(const unsigned char *sha1)\n \t\tif (i == obj_hash_size)\n \t\t\ti = 0;\n \t}\n-\tif (obj && i != first) {\n-\t\tstruct object *tmp = obj_hash[i];\n-\t\tobj_hash[i] = obj_hash[first];\n-\t\tobj_hash[first] = tmp;\n+\tif (obj) {\n+\t\twhile (i != first) {\n+\t\t\tint prev = i ? i - 1 : obj_hash_size - 1;\n+\t\t\tobj_hash[i] = obj_hash[prev];\n+\t\t\ti = prev;\n+\t\t}\n+\t\tobj_hash[i] = obj;\n \t}\n \treturn obj;\n }\n\n-Peff\n"},{"id":"216333","messageId":"5183522D.5060405@viscovery.net","threadId":"33697","inReplyTo":"20130502154618.GA18462@sigill.intra.peff.net","subject":"Re: [PATCH] lookup_object: prioritize recently found objects","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2013-05-03T05:59:09Z","receivedAt":"2013-05-03T05:59:09Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 5/2/2013 17:46, schrieb Jeff King:\n> On Thu, May 02, 2013 at 09:05:01AM +0200, Johannes Sixt wrote:\n>> BTW, do you notice that the function is now modifying an object (the hash\n>> table) even though this is rather unexpected from a \"lookup\" function?\n> \n> I think this is fine. The function is conceptually constant from the\n> outside; callers don't even know about the hash table. They just know\n> that there is some mapping. It's similar to the way that lookup_commit\n> will lazily allocate the \"struct commit\". The callers do not care\n> whether it exists already or not; they care that at the end of the\n> function, they have a pointer to the commit. Everything else is an\n> implementation detail.\n\nCan we be sure that the function is never invoked in concurrently from\ndifferent threads? I attempted to audit code paths, but quickly gave up\nbecause I know too little about this machinery.\n\n-- Hannes\n"},{"id":"216334","messageId":"20130503060244.GA13843@sigill.intra.peff.net","threadId":"33697","inReplyTo":"5183522D.5060405@viscovery.net","subject":"Re: [PATCH] lookup_object: prioritize recently found objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-03T06:02:44Z","receivedAt":"2013-05-03T06:02:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 03, 2013 at 07:59:09AM +0200, Johannes Sixt wrote:\n\n> Am 5/2/2013 17:46, schrieb Jeff King:\n> > On Thu, May 02, 2013 at 09:05:01AM +0200, Johannes Sixt wrote:\n> >> BTW, do you notice that the function is now modifying an object (the hash\n> >> table) even though this is rather unexpected from a \"lookup\" function?\n> > \n> > I think this is fine. The function is conceptually constant from the\n> > outside; callers don't even know about the hash table. They just know\n> > that there is some mapping. It's similar to the way that lookup_commit\n> > will lazily allocate the \"struct commit\". The callers do not care\n> > whether it exists already or not; they care that at the end of the\n> > function, they have a pointer to the commit. Everything else is an\n> > implementation detail.\n> \n> Can we be sure that the function is never invoked in concurrently from\n> different threads? I attempted to audit code paths, but quickly gave up\n> because I know too little about this machinery.\n\nI didn't check explicitly, but in general such a program would already\nneed a mutex to synchronize object lookup. Not for lookup_object\nspecifically, but because lookup_object is mostly used to back\nlookup_commit, lookup_tree, etc, which are already not re-entrant\n(because they lazily insert into the hash behind the scenes).\n\n-Peff\n"},{"id":"216335","messageId":"20130503061605.GB13674@sigill.intra.peff.net","threadId":"33697","inReplyTo":"20130503060244.GA13843@sigill.intra.peff.net","subject":"Re: [PATCH] lookup_object: prioritize recently found objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-03T06:16:05Z","receivedAt":"2013-05-03T06:16:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 03, 2013 at 02:02:44AM -0400, Jeff King wrote:\n\n> > Can we be sure that the function is never invoked in concurrently from\n> > different threads? I attempted to audit code paths, but quickly gave up\n> > because I know too little about this machinery.\n> \n> I didn't check explicitly, but in general such a program would already\n> need a mutex to synchronize object lookup. Not for lookup_object\n> specifically, but because lookup_object is mostly used to back\n> lookup_commit, lookup_tree, etc, which are already not re-entrant\n> (because they lazily insert into the hash behind the scenes).\n\nI just looked through the 25 existing calls to lookup_object. All of\nthem should be OK. Most of them are coupled with immediate calls to\nupdate the hash table and/or to call read_sha1_file (which is also very\nnot-thread-safe). So I don't think the patch introduces any bug into the\ncurrent code.\n\nIt does introduce a potential for future bugs in concurrent code, but I\ndon't know that it makes a significant dent in the current codebase. We\nalready have a lot of non-reentrant functions, including all of the\nother lookup_* functions.  Our concurrent code is typically very careful\nto use a small known-safe subset of functions.\n\nI did look originally at updating the ordering when the hash is already\nbeing updated (i.e., to insert a new entry at the front of a collision\nchain, rather than the back). However, that didn't yield nearly as much\nimprovement. I think partially because the locality of an insert/lookup\npair is not as good as a lookup/lookup pair. And partially because we\ndestroy that ordering for existing entries whenever we grow the hash\ntable.\n\n-Peff\n"}]}