{"thread":{"id":"25816","subject":"[PATCH/RFC] fast-import: insert new object entries at start of hash bucket","startedAt":"2010-11-23T07:53:48Z","lastAt":"2010-11-23T23:29:37Z","messageCount":6,"participants":["Jonathan Nieder","Sverre Rabbelier","Shawn Pearce"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"156353","messageId":"20101123075348.GA10367@burratino","threadId":"25816","inReplyTo":null,"subject":"[PATCH/RFC] fast-import: insert new object entries at start of hash bucket","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-11-23T07:53:48Z","receivedAt":"2010-11-23T07:53:48Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"From: David Barr \n\nMore often than not, find_object is called for recently inserted objects.\nOptimise for this case by inserting new entries at the start of the chain.\nThis doesn't affect the cost of new inserts but reduces the cost of find\nand insert for existing object entries.\n\nSigned-off-by: David Barr \nSigned-off-by: Jonathan Nieder \n---\nHi,\n\nAfter importing the first 500000 revs or so of the ASF repo with\nsvn-fe, it seems that fast-import gets a bit sluggish because its\nobject table fills up. David noticed that one can get a bit of a\nspeed-up by noticing that objects are likely to be accessed soon after\nthey are inserted in this workflow. (The basis for most svn deltas\ncomes from the revision just dumped.)\n\nI would guess other workflows would display the same tendency if any;\nat least, the same blob is likely to come up repeatedly in a few revs\nand then not be mentioned for a while. Though maybe there is some\nreason to make the opposite assumption that I have not thought of.\nShawn?\n\nA more dramatic improvement comes from increasing the size of the hash\ntable; in particular, David noticed it allows the CPU usage to\nincrease from ~60% to 100% of one core. So presumably we should make\nthe size of the hash table dynamic.\n\nOther aspects to investigate: choice of hash function; is it worth\nmoving accessed entries to the front of hash chains when they already\nexist?\n\nTimings in interesting workflows would also be nice.\n\nRegardless, this seems like a good change on its own, especially\nbecause it simplifies the code.\n\nThoughts?\nJonathan\n\n fast-import.c | 9 ++-------\n 1 files changed, 2 insertions(+), 7 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 77549eb..e2f4874 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -539,22 +539,17 @@ static struct object_entry *insert_object(unsigned char *sha1)\n {\n \tunsigned int h = sha1[0] << 8 | sha1[1];\n \tstruct object_entry *e = object_table[h];\n-\tstruct object_entry *p = NULL;\n \n \twhile (e) {\n \t\tif (!hashcmp(sha1, e->idx.sha1))\n \t\t\treturn e;\n-\t\tp = e;\n \t\te = e->next;\n \t}\n \n \te = new_object(sha1);\n-\te->next = NULL;\n+\te->next = object_table[h];\n \te->idx.offset = 0;\n-\tif (p)\n-\t\tp->next = e;\n-\telse\n-\t\tobject_table[h] = e;\n+\tobject_table[h] = e;\n \treturn e;\n }\n \n-- \n1.7.2.3\n"},{"id":"156376","messageId":"AANLkTikK+vO2fLseChD8iccA0=M0FXp6TmWAPeaK9v+R@mail.gmail.com","threadId":"25816","inReplyTo":"20101123075348.GA10367@burratino","subject":"Re: [PATCH/RFC] fast-import: insert new object entries at start of hash bucket","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2010-11-23T12:51:16Z","receivedAt":"2010-11-23T12:51:16Z","isPatch":true,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Tue, Nov 23, 2010 at 08:53, Jonathan Nieder wrote:\n> Thoughts?\n\nAre there (m)any non-artificial cases for which this slows things down (a lot)?\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"156424","messageId":"20101123181956.GG12113@burratino","threadId":"25816","inReplyTo":"AANLkTikK+vO2fLseChD8iccA0=M0FXp6TmWAPeaK9v+R@mail.gmail.com","subject":"Re: [PATCH/RFC] fast-import: insert new object entries at start of hash bucket","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-11-23T18:19:56Z","receivedAt":"2010-11-23T18:19:56Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Sverre Rabbelier wrote:\n> On Tue, Nov 23, 2010 at 08:53, Jonathan Nieder wrote:\n\n>> Thoughts?\n>\n> Are there (m)any non-artificial cases for which this slows things down (a lot)?\n\nIf a very common blob (e.g., the empty blob) is in the same bucket as\na few uncommon ones, it is likely to be inserted first and this would\nslow down access to it.\n"},{"id":"156453","messageId":"AANLkTikqUjjjMRzWTcEOs+2PGu=-9VVbdn0YgpabFaDu@mail.gmail.com","threadId":"25816","inReplyTo":"20101123075348.GA10367@burratino","subject":"Re: [PATCH/RFC] fast-import: insert new object entries at start of hash bucket","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2010-11-23T22:33:52Z","receivedAt":"2010-11-23T22:33:52Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Nov 22, 2010 at 11:53 PM, Jonathan Nieder wrote:\n> More often than not, find_object is called for recently inserted objects.\n> Optimise for this case by inserting new entries at the start of the chain.\n> This doesn't affect the cost of new inserts but reduces the cost of find\n> and insert for existing object entries.\n\nThis is a good change. I totally agree with it.\n\n> I would guess other workflows would display the same tendency if any;\n> at least, the same blob is likely to come up repeatedly in a few revs\n> and then not be mentioned for a while.  Though maybe there is some\n> reason to make the opposite assumption that I have not thought of.\n> Shawn?\n\nThe new entry was put onto the end of the hash chain because I wasn't\nthinking when I wrote that code. For some reason I assumed it made\nsense to put it onto the end of the chain, because I had already\nwalked the chain to see if it already exists... and by the time I\nreached the end, I had the tail, so I might as well put the new item\non to the tail.\n\nMoving the new item to the head works because it is somewhat likely\nthat the new item will be asked for in the near future, and older\nitems are less likely to be asked for. So I can see how this can\noffer a small CPU time improvement for a very big import.\n\n> A more dramatic improvement comes from increasing the size of the hash\n> table; in particular, David noticed it allows the CPU usage to\n> increase from ~60% to 100% of one core.  So presumably we should make\n> the size of the hash table dynamic.\n\nUhm. Wait, the table isn't already dynamic? I cheated that badly and\nmade the table fixed size?\n\nI can tell you why its fixed size... when I wrote fast-import to\nsupport the Mozilla repository import, we had an estimate on the\nnumber of objects that we needed fast-import to handle in a given run.\n From that estimate we concluded that a table of 2^16 was sufficiently\nlarge enough, as the hash chains would only be some small N long given\nthe total number of objects we needed to handle for Mozilla. Doubling\nthat into 2^17 or larger wasn't useful, and using a smaller table like\n2^14 produced too long of a chain.\n\nOnce this code was working, we moved on to other features, and never\nreconsidered the table size. This table should be growing if the\ninitial 2^16 isn't big enough. Its just that nobody has ever noticed\nthat I hardcoded the size. :-)\n\n> Other aspects to investigate: choice of hash function;\n\nWhy? SHA-1 is pretty uniform in its distribution. The object_table\nis taking the first 16 bits and using that to index the object, that's\nthe first 4 hex digits. The Linux kernel uniquely identifies an\nobject with under 10 hex digits, or 40 leading bits. The table just\nneeds to double or quadruple its size (and have the hash function\ninclude that many more bits) when an arbitrary bucket's chain length\ngets over some reasonable constant number (e.g. 16). We probably do\nneed to cap the table size though, especially on 32 bit builds of Git.\n\n> is it worth\n> moving accessed entries to the front of hash chains when they already\n> exist?\n\nMaybe, maybe not? It depends on what the front end is doing.\n\nIf the front end is feeding hex SHA-1s, and will frequently reuse the\nsame blobs, yes. Otherwise, maybe not. The only time we are looking\nfor an object in the object_table is when we are about to insert an\nobject and need to avoid a duplicate (that's the insert_object code\npath), or when we have to page in a tree into the branch cache.\n\nIf the branch cache is spilling, you probably should be increasing its\nsize so that it doesn't spill as often.\n\nThe code within store_tree() is really inefficient. It looks up the\nold tree to find out how its stored... we could store that struct\nobject_entry* inside of the struct tree_content. We also could avoid\ncalling store_object() if the tree hasn't been modified. The way I\nread this store_tree() code, every subdirectory is recursed into even\nif no modifications were made inside of that subdirectory during the\ncurrent commit. We just need to format the tree, and if the SHA-1 is\nthe same as the old SHA-1, skip back out without calling\nstore_object(). That should give you a pretty dramatic reduction on\nthe number of times the object_table is accessed during an import.\n\n-- \nShawn.\n"},{"id":"156454","messageId":"20101123231718.GA4317@burratino","threadId":"25816","inReplyTo":"AANLkTikqUjjjMRzWTcEOs+2PGu=-9VVbdn0YgpabFaDu@mail.gmail.com","subject":"Re: [PATCH/RFC] fast-import: insert new object entries at start of hash bucket","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-11-23T23:17:18Z","receivedAt":"2010-11-23T23:17:18Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Shawn Pearce wrote:\n> On Mon, Nov 22, 2010 at 11:53 PM, Jonathan Nieder wrote:\n\n>> Other aspects to investigate: choice of hash function;\n>\n> Why? SHA-1 is pretty uniform in its distribution.\n\nI got distracted for a moment by the atom table, but since that does\nnot have a big effect on performance it's probably not worth spending\ntime on. Sorry about that; please ignore.\n\n[...]\n> The way I\n> read this store_tree() code, every subdirectory is recursed into even\n> if no modifications were made inside of that subdirectory during the\n> current commit.\n\nDoesn't the is_null_sha1 check avoid that?\n\nTo further explain the workload: svn-fe receives its blobs from svn\nin the form of deltas. So the conversation might go like this:\n\n\tS\tcommit refs/heads/master\n\tS\tmark :10000\n\tS\tcommitter felicity \n\tS\tdata 74\n\tS\tbug 3097: switch spamd from doing 'fork per message' to a 'prefork' model\n\tS\tcat incubator/spamassassin/trunk/spamd/spamd.raw\n\tF\t89d56462577b8b7b4f4115f2a47f0b3da22b791a blob 63633\n\tF\t#!/usr/bin/perl -w -T\n\t...\n\tS\tM 100644 inline incubator/spamassassin/trunk/spamd/spamd.raw\n\tS\tdata 62114\n\t...\n\nCurrent svn-fe in vcs-svn-pu requests the preimage blobs using marks,\nbut the idea is the same.\n\nIf this proves a bottleneck I suppose we could cache the content of\nfrequently-requested old blobs and keep pointers to that in the\nin-core tree.\n"},{"id":"156456","messageId":"AANLkTimG2V2h=z3t0kHxOy65W7JjayNb1RA8E4AabCV+@mail.gmail.com","threadId":"25816","inReplyTo":"20101123231718.GA4317@burratino","subject":"Re: [PATCH/RFC] fast-import: insert new object entries at start of hash bucket","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2010-11-23T23:29:37Z","receivedAt":"2010-11-23T23:29:37Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Nov 23, 2010 at 3:17 PM, Jonathan Nieder wrote:\n> Shawn Pearce wrote:\n>> On Mon, Nov 22, 2010 at 11:53 PM, Jonathan Nieder wrote:\n>>                                                           The way I\n>> read this store_tree() code, every subdirectory is recursed into even\n>> if no modifications were made inside of that subdirectory during the\n>> current commit.\n>\n> Doesn't the is_null_sha1 check avoid that?\n\nOh, right, yes. That check avoids processing a tree that wasn't\nmodified. Damn that code isn't very clear. :-(\n\n> To further explain the workload: svn-fe receives its blobs from svn\n> in the form of deltas.  So the conversation might go like this:\n...\n> Current svn-fe in vcs-svn-pu requests the preimage blobs using marks,\n> but the idea is the same.\n>\n> If this proves a bottleneck I suppose we could cache the content of\n> frequently-requested old blobs and keep pointers to that in the\n> in-core tree.\n\nOK, now I get it.\n\nfast-import already uses sha1_file.c's delta base cache for the delta\nbases that are frequently accessed. It *may* help an importer that\nneeds to keep refetching the same blob to cache the blob itself rather\nthan its delta base (and reapply every time). It might not help too,\nit may hurt to try and keep recently accessed objects that the\nimporter won't need to request again.\n\n-- \nShawn.\n"}]}