{"thread":{"id":"33602","subject":"[PATCH] Hold an 'unsigned long' chunk of the sha1 in obj_hash","startedAt":"2013-04-25T18:04:01Z","lastAt":"2013-05-02T08:52:04Z","messageCount":7,"participants":["Thomas Rast","Junio C Hamano","Duy Nguyen","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"215462","messageId":"6c2b67a2f0b67ee796c7676e3febe4c61ab85d4a.1366912627.git.trast@inf.ethz.ch","threadId":"33602","inReplyTo":null,"subject":"[PATCH] Hold an 'unsigned long' chunk of the sha1 in obj_hash","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-04-25T18:04:01Z","receivedAt":"2013-04-25T18:04:01Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"The existing obj_hash is really straightforward: it holds a struct\nobject * and spills into the subsequent slots (linear probing), which\nis good enough because it doesn't need to support deletion.\n\nHowever, this arrangement has pretty bad cache locality in the case of\ncollisions. Because the sha1 is contained in the object itself, it\nresides in a different memory region from the hash table. So whenever\nwe have to process a hash collision, we need to access (and\npotentially fetch from slower caches or memory) an object that we are\nnot going to use again.\n\nAnd probing lookups happen a lot: some simple instrumentation shows\nthat 'git rev-list --all --objects' on my git.git,\n\n* 19.4M objects are accessed in lookup_object and grow_object_hash\n combined, while\n\n* the linear probing loops in lookup_object and insert_obj_hash run a\n total of 9.4M times.\n\nSo we take a slightly different approach, and trade some memory for\nbetter cache locality. Namely, we change the hash table slots to\ncontain\n\n struct object *obj;\n unsigned long sha1prefix;\n\nWe use this new 'sha1prefix' field to store the first part of the\nobject's sha1, from which its hash table slot is computed. This\nallows us to do two things with data that resides inside the hash\ntable:\n\n* In lookup_object(), we can do a pre-filtering of the probed slots;\n the probability that we need to actually peek inside any colliding\n object(s) is very small.\n\n* In grow_object_hash(), we actually do not need to look inside the\n objects at all. This should give a substantial speedup during\n hashtable resizing.\n\nThe choice of 'long' makes it the same size as a pointer (to which any\nsmaller data type would be padded anyway) on x86 and x86_64 Linuxen,\nand probably many others. So the hash table will be twice as big as\nbefore.\n\nI get a decent speedup, for example using git.git as a test\nrepository:\n\nTest before after\n---------------------------------------------------------------------------------\n0001.1: rev-list --all 0.42(0.40+0.01) 0.41(0.39+0.01) -1.5%**\n0001.2: rev-list --all --objects 2.40(2.37+0.03) 2.28(2.25+0.03) -5.0%***\n---------------------------------------------------------------------------------\n\nAnd even more in linux.git:\n\n---------------------------------------------------------------------------------\n0001.1: rev-list --all 3.31(3.19+0.12) 3.21(3.09+0.11) -2.9%**\n0001.2: rev-list --all --objects 27.99(27.70+0.26) 25.99(25.71+0.25) -7.1%***\n---------------------------------------------------------------------------------\n\nSigned-off-by: Thomas Rast \n---\n\nI expected the big win to be in grow_object_hash(), but perf says that\n'git rev-list --all --objects' spends a whopping 33.6% of its time in\nlookup_object(), and this change gets that down to 30.0%.\n\n object.c | 58 ++++++++++++++++++++++++++++++++++++----------------------\n 1 file changed, 36 insertions(+), 22 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex 20703f5..6b84c87 100644\n--- a/object.c\n+++ b/object.c\n@@ -5,7 +5,12 @@\n #include \"commit.h\"\n #include \"tag.h\"\n \n-static struct object **obj_hash;\n+struct obj_hash_ent {\n+\tstruct object *obj;\n+\tunsigned long sha1prefix;\n+};\n+\n+static struct obj_hash_ent *obj_hash;\n static int nr_objs, obj_hash_size;\n \n unsigned int get_max_object_index(void)\n@@ -15,7 +20,7 @@ unsigned int get_max_object_index(void)\n \n struct object *get_indexed_object(unsigned int idx)\n {\n-\treturn obj_hash[idx];\n+\treturn obj_hash[idx].obj;\n }\n \n static const char *object_type_strings[] = {\n@@ -43,43 +48,52 @@ int type_from_string(const char *str)\n \tdie(\"invalid object type \\\"%s\\\"\", str);\n }\n \n-static unsigned int hash_obj(struct object *obj, unsigned int n)\n+static unsigned long hash_sha1(const unsigned char *sha1)\n {\n-\tunsigned int hash;\n-\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n-\treturn hash % n;\n+\tunsigned long sha1prefix;\n+\tmemcpy(&sha1prefix, sha1, sizeof(unsigned long));\n+\treturn sha1prefix;\n }\n \n-static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)\n+static unsigned long hash_obj(struct object *obj)\n {\n-\tunsigned int j = hash_obj(obj, size);\n+\treturn hash_sha1(obj->sha1);\n+}\n \n-\twhile (hash[j]) {\n+static void insert_obj_hash_1(struct object *obj, struct obj_hash_ent *hash, unsigned int size,\n+\t\t\t unsigned long sha1prefix)\n+{\n+\tunsigned int j = (unsigned int) sha1prefix % size;\n+\n+\twhile (hash[j].obj) {\n \t\tj++;\n \t\tif (j >= size)\n \t\t\tj = 0;\n \t}\n-\thash[j] = obj;\n+\thash[j].obj = obj;\n+\thash[j].sha1prefix = sha1prefix;\n }\n \n-static unsigned int hashtable_index(const unsigned char *sha1)\n+static void insert_obj_hash(struct object *obj, struct obj_hash_ent *table, unsigned int size)\n {\n-\tunsigned int i;\n-\tmemcpy(&i, sha1, sizeof(unsigned int));\n-\treturn i % obj_hash_size;\n+\tunsigned long sha1prefix = hash_obj(obj);\n+\tinsert_obj_hash_1(obj, table, size, sha1prefix);\n }\n \n struct object *lookup_object(const unsigned char *sha1)\n {\n+\tunsigned long sha1prefix;\n \tunsigned int i;\n \tstruct object *obj;\n \n \tif (!obj_hash)\n \t\treturn NULL;\n \n-\ti = hashtable_index(sha1);\n-\twhile ((obj = obj_hash[i]) != NULL) {\n-\t\tif (!hashcmp(sha1, obj->sha1))\n+\tsha1prefix = hash_sha1(sha1);\n+\ti = (unsigned int) sha1prefix % obj_hash_size;\n+\twhile ((obj = obj_hash[i].obj) != NULL) {\n+\t\tif (obj_hash[i].sha1prefix == sha1prefix\n+\t\t && !hashcmp(sha1, obj->sha1))\n \t\t\tbreak;\n \t\ti++;\n \t\tif (i == obj_hash_size)\n@@ -92,14 +106,14 @@ static void grow_object_hash(void)\n {\n \tint i;\n \tint new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;\n-\tstruct object **new_hash;\n+\tstruct obj_hash_ent *new_hash;\n \n-\tnew_hash = xcalloc(new_hash_size, sizeof(struct object *));\n+\tnew_hash = xcalloc(new_hash_size, sizeof(struct obj_hash_ent));\n \tfor (i = 0; i < obj_hash_size; i++) {\n-\t\tstruct object *obj = obj_hash[i];\n+\t\tstruct object *obj = obj_hash[i].obj;\n \t\tif (!obj)\n \t\t\tcontinue;\n-\t\tinsert_obj_hash(obj, new_hash, new_hash_size);\n+\t\tinsert_obj_hash_1(obj, new_hash, new_hash_size, obj_hash[i].sha1prefix);\n \t}\n \tfree(obj_hash);\n \tobj_hash = new_hash;\n@@ -302,7 +316,7 @@ void clear_object_flags(unsigned flags)\n \tint i;\n \n \tfor (i=0; i < obj_hash_size; i++) {\n-\t\tstruct object *obj = obj_hash[i];\n+\t\tstruct object *obj = obj_hash[i].obj;\n \t\tif (obj)\n \t\t\tobj->flags &= ~flags;\n \t}\n-- \n1.8.2.1.961.g06c38a5.dirty\n"},{"id":"215501","messageId":"7vobd22wto.fsf@alter.siamese.dyndns.org","threadId":"33602","inReplyTo":"6c2b67a2f0b67ee796c7676e3febe4c61ab85d4a.1366912627.git.trast@inf.ethz.ch","subject":"Re: [PATCH] Hold an 'unsigned long' chunk of the sha1 in obj_hash","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-25T20:13:07Z","receivedAt":"2013-04-25T20:13:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> So we take a slightly different approach, and trade some memory for\n> better cache locality.\n\nInteresting. It feels somewhat bait-and-switch to reveal that the\nabove \"some\" turns out to be \"double\" later, but the resulting code\ndoes not look too bad, and the numbers do not look insignificant.\n"},{"id":"215508","messageId":"87bo92gvw2.fsf@hexa.v.cablecom.net","threadId":"33602","inReplyTo":"7vobd22wto.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] Hold an 'unsigned long' chunk of the sha1 in obj_hash","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-04-25T21:09:33Z","receivedAt":"2013-04-25T21:09:33Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Thomas Rast writes:\n>\n>> So we take a slightly different approach, and trade some memory for\n>> better cache locality.\n>\n> Interesting. It feels somewhat bait-and-switch to reveal that the\n> above \"some\" turns out to be \"double\" later, but the resulting code\n> does not look too bad, and the numbers do not look insignificant.\n\nOh, that wasn't the intent. I was too lazy to gather some memory\nnumbers, so here's an estimate on the local effect and some measurements\non the global one.\n\nstruct object is at least 24 bytes (flags etc. and sha1). We grow the\nhash by 2x whenever it reaches 50% load, so it is always at least 25%\nloaded.\n\nA 25% loaded hash-table used to consist of 75% pointers (8 bytes) and\n25% pointers-to-struct-object (32 bytes), for 14 bytes per average slot.\nNow it's 22 bytes (one more unsigned long) per slot, i.e., a 60%\nincrease for the data managed by the hash table.\n\nBut that's using the crudest estimates I could think of. If we assume\nthat an average blob and tree is at least as big as the smallest\npossible commit, we'd guess that objects are at least ~240 bytes (this\nis still somewhat of an estimate and assumes that you don't go and\nhandcraft commits with single-digit timestamps). So the numbers above\ngo up by 25% * 240 per average slot, and work out to an about 11%\noverall increase.\n\nHere are some real numbers from /usr/bin/time git rev-list --all --objects:\n\nbefore:\n\n 2.30user 0.02system 0:02.33elapsed 99%CPU (0avgtext+0avgdata 247760maxresident)k\n 0inputs+0outputs (0major+17844minor)pagefaults 0swaps\n\nafter:\n\n 2.18user 0.02system 0:02.21elapsed 99%CPU (0avgtext+0avgdata 261936maxresident)k \n 0inputs+0outputs (0major+18202minor)pagefaults 0swaps\n\nSo that would be about 14MB or 5.7% of extra memory.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"215510","messageId":"CACsJy8CJO+rLHgMo+F_fsWBj7Nm0rbpVNHTLXbi7u60+rT0OJQ@mail.gmail.com","threadId":"33602","inReplyTo":"6c2b67a2f0b67ee796c7676e3febe4c61ab85d4a.1366912627.git.trast@inf.ethz.ch","subject":"Re: [PATCH] Hold an 'unsigned long' chunk of the sha1 in obj_hash","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-04-25T21:12:10Z","receivedAt":"2013-04-25T21:12:10Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Apr 26, 2013 at 1:04 AM, Thomas Rast wrote:\n> So we take a slightly different approach, and trade some memory for\n> better cache locality. Namely, we change the hash table slots to\n> contain\n>\n> struct object *obj;\n> unsigned long sha1prefix;\n>\n> We use this new 'sha1prefix' field to store the first part of the\n> object's sha1, from which its hash table slot is computed.\n\nClever. I went a similar road before. But I put the whole 20-byte\nsha-1 in obj_hash, which makes obj_hash even bigger and less\ncache-friendly.\n--\nDuy\n"},{"id":"216195","messageId":"20130501204947.GA12789@sigill.intra.peff.net","threadId":"33602","inReplyTo":"6c2b67a2f0b67ee796c7676e3febe4c61ab85d4a.1366912627.git.trast@inf.ethz.ch","subject":"Re: [PATCH] Hold an 'unsigned long' chunk of the sha1 in obj_hash","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-01T20:49:47Z","receivedAt":"2013-05-01T20:49:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 25, 2013 at 08:04:01PM +0200, Thomas Rast wrote:\n\n> And probing lookups happen a lot: some simple instrumentation shows\n> that 'git rev-list --all --objects' on my git.git,\n> \n> * 19.4M objects are accessed in lookup_object and grow_object_hash\n> combined, while\n> \n> * the linear probing loops in lookup_object and insert_obj_hash run a\n> total of 9.4M times.\n> \n> So we take a slightly different approach, and trade some memory for\n> better cache locality. Namely, we change the hash table slots to\n> contain\n> \n> struct object *obj;\n> unsigned long sha1prefix;\n\nI think this is a clever idea, though I do worry about the extra memory\nuse (it's not all _that_ much in the grand scheme, but it works against\nthe cache locality benefit). I just posted (but forgot to cc you) a\npatch that takes a different approach: to actually move the likely\ncandidate to the front of the collision change. The patch is here:\n\n http://article.gmane.org/gmane.comp.version-control.git/223139\n\nIt does a bit better than the numbers you have here:\n\n> I get a decent speedup, for example using git.git as a test\n> repository:\n> \n> Test before after\n> ---------------------------------------------------------------------------------\n> 0001.1: rev-list --all 0.42(0.40+0.01) 0.41(0.39+0.01) -1.5%**\n> 0001.2: rev-list --all --objects 2.40(2.37+0.03) 2.28(2.25+0.03) -5.0%***\n> ---------------------------------------------------------------------------------\n> \n> And even more in linux.git:\n> \n> ---------------------------------------------------------------------------------\n> 0001.1: rev-list --all 3.31(3.19+0.12) 3.21(3.09+0.11) -2.9%**\n> 0001.2: rev-list --all --objects 27.99(27.70+0.26) 25.99(25.71+0.25) -7.1%***\n> ---------------------------------------------------------------------------------\n\nIt _might_ still be advantageous to do your patch on top, but I suspect\nit will diminish the returns from your patch (since the point of it is\nto probe less far down the chain on average).\n\n> I expected the big win to be in grow_object_hash(), but perf says that\n> 'git rev-list --all --objects' spends a whopping 33.6% of its time in\n> lookup_object(), and this change gets that down to 30.0%.\n\nI'm not surprised. I spent some time trying to optimize grow_object_hash\nand realized that it doesn't make much difference. The killer in\n\"rev-list --objects --all\" is that we hit the same tree entry objects\nover and over.\n\nAnother avenue I'd like to explore is actually doing a tree-diff from\nthe last processed commit, since we should need to examine only the\nchanged entries. I suspect it won't be a big benefit, though, because\neven though the tree diff can happen in O(# of entries), we are trying\nto beat doing an O(1) hash for each entry. So it's the same algorithmic\ncomplexity, and it is hard to beat a few hashcmp() calls. We'll see.\n\n-Peff\n"},{"id":"216223","messageId":"20130502005317.GA29159@sigill.intra.peff.net","threadId":"33602","inReplyTo":"20130501204947.GA12789@sigill.intra.peff.net","subject":"[PATCH] process tree diffs during \"rev-list --objects\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-02T00:53:17Z","receivedAt":"2013-05-02T00:53:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, May 01, 2013 at 04:49:47PM -0400, Jeff King wrote:\n\n> Another avenue I'd like to explore is actually doing a tree-diff from\n> the last processed commit, since we should need to examine only the\n> changed entries. I suspect it won't be a big benefit, though, because\n> even though the tree diff can happen in O(# of entries), we are trying\n> to beat doing an O(1) hash for each entry. So it's the same algorithmic\n> complexity, and it is hard to beat a few hashcmp() calls. We'll see.\n\nAs I suspected, this is not a win:\n\nTest origin this tree\n--------------------------------------------------------------------------\n0001.1: rev-list --all 0.40(0.37+0.02) 0.40(0.38+0.01) +0.0%\n0001.2: rev-list --all --objects 2.22(2.16+0.05) 2.41(2.16+0.24) +8.6%\n\nI've included the patch below for reference. It really does work as\nplanned; the number of calls to lookup_object for doing \"rev-list --all\n--objects\" on git.git is reduced from ~15M to ~2.6M. But the benefit is\neaten up by the extra tree-processing time. For fun, here's an excerpt\nfrom the \"perf diff\" between the two versions:\n\n +10.51% git [.] update_tree_entry\n +8.97% git [.] lookup_object\n +7.81% git [.] process_tree\n +5.20% libc-2.13.so [.] __memcmp_sse4_1\n +3.77% libc-2.13.so [.] __strlen_sse42\n +2.69% git [.] base_name_compare\n [....]\n -7.90% git [.] tree_entry\n -39.19% git [.] lookup_object\n\nShawn had suggested trying to store the tree deltas in such a way that\nthese tree comparisons could be done more cheaply. That might tip things\nin favor of the tree-diff approach.\n\n-Peff\n\n---\ndiff --git a/list-objects.c b/list-objects.c\nindex 3dd4a96..b87a049 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -59,8 +59,57 @@ static void process_tree(struct rev_info *revs,\n \t/* Nothing to do */\n }\n \n+static struct tree *skip_processed_entries(struct tree_desc *cur,\n+\t\t\t\t\t struct tree_desc *old)\n+{\n+\twhile (cur->size && old->size) {\n+\t\tint cmp = base_name_compare(cur->entry.path,\n+\t\t\t\t\t tree_entry_len(&cur->entry),\n+\t\t\t\t\t 0, /* ignore mode */\n+\t\t\t\t\t old->entry.path,\n+\t\t\t\t\t tree_entry_len(&old->entry),\n+\t\t\t\t\t 0);\n+\t\tif (cmp > 0) {\n+\t\t\t/*\n+\t\t\t * Old tree has something we do not; ignore it, as it\n+\t\t\t * was already processed.\n+\t\t\t */\n+\t\t\tupdate_tree_entry(old);\n+\t\t}\n+\t\telse if (cmp == 0) {\n+\t\t\t/*\n+\t\t\t * We have the same path; if the sha1s match, then we\n+\t\t\t * have already processed it and can ignore. Otherwise,\n+\t\t\t * return for processing, but also provide the old\n+\t\t\t * tree so that we can recurse.\n+\t\t\t */\n+\t\t\tif (!hashcmp(cur->entry.sha1, old->entry.sha1)) {\n+\t\t\t\tupdate_tree_entry(cur);\n+\t\t\t\tupdate_tree_entry(old);\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\tstruct object *o = lookup_object(old->entry.sha1);\n+\t\t\t\tupdate_tree_entry(old);\n+\t\t\t\tif (o && o->type == OBJ_TREE)\n+\t\t\t\t\treturn (struct tree *)o;\n+\t\t\t\telse\n+\t\t\t\t\treturn NULL;\n+\t\t\t}\n+\t\t}\n+\t\telse {\n+\t\t\t/*\n+\t\t\t * We have an entry the old one does not; we must look\n+\t\t\t * at it (and there is no matching old tree to report).\n+\t\t\t */\n+\t\t\treturn NULL;\n+\t\t}\n+\t}\n+\treturn NULL;\n+}\n+\n static void process_tree(struct rev_info *revs,\n \t\t\t struct tree *tree,\n+\t\t\t struct tree *old_tree,\n \t\t\t show_object_fn show,\n \t\t\t struct name_path *path,\n \t\t\t struct strbuf *base,\n@@ -68,7 +117,7 @@ static void process_tree(struct rev_info *revs,\n \t\t\t void *cb_data)\n {\n \tstruct object *obj = &tree->object;\n-\tstruct tree_desc desc;\n+\tstruct tree_desc desc, old_desc;\n \tstruct name_entry entry;\n \tstruct name_path me;\n \tenum interesting match = revs->diffopt.pathspec.nr == 0 ?\n@@ -97,7 +146,18 @@ static void process_tree(struct rev_info *revs,\n \n \tinit_tree_desc(&desc, tree->buffer, tree->size);\n \n-\twhile (tree_entry(&desc, &entry)) {\n+\tif (old_tree)\n+\t\tinit_tree_desc(&old_desc, old_tree->buffer, old_tree->size);\n+\telse\n+\t\tinit_tree_desc(&old_desc, NULL, 0);\n+\n+\twhile (desc.size) {\n+\t\tstruct tree *old_tree;\n+\n+\t\told_tree = skip_processed_entries(&desc, &old_desc);\n+\t\tif (!tree_entry(&desc, &entry))\n+\t\t\tbreak;\n+\n \t\tif (match != all_entries_interesting) {\n \t\t\tmatch = tree_entry_interesting(&entry, base, 0,\n \t\t\t\t\t\t &revs->diffopt.pathspec);\n@@ -109,7 +169,7 @@ static void process_tree(struct rev_info *revs,\n \n \t\tif (S_ISDIR(entry.mode))\n \t\t\tprocess_tree(revs,\n-\t\t\t\t lookup_tree(entry.sha1),\n+\t\t\t\t lookup_tree(entry.sha1), old_tree,\n \t\t\t\t show, &me, base, entry.path,\n \t\t\t\t cb_data);\n \t\telse if (S_ISGITLINK(entry.mode))\n@@ -123,8 +183,6 @@ static void process_tree(struct rev_info *revs,\n \t\t\t\t cb_data);\n \t}\n \tstrbuf_setlen(base, baselen);\n-\tfree(tree->buffer);\n-\ttree->buffer = NULL;\n }\n \n static void mark_edge_parents_uninteresting(struct commit *commit,\n@@ -173,6 +231,7 @@ void traverse_commit_list(struct rev_info *revs,\n \tint i;\n \tstruct commit *commit;\n \tstruct strbuf base;\n+\tstruct tree *last_root_tree = NULL;\n \n \tstrbuf_init(&base, PATH_MAX);\n \twhile ((commit = get_revision(revs)) != NULL) {\n@@ -196,8 +255,9 @@ void traverse_commit_list(struct rev_info *revs,\n \t\t\tcontinue;\n \t\t}\n \t\tif (obj->type == OBJ_TREE) {\n-\t\t\tprocess_tree(revs, (struct tree *)obj, show_object,\n-\t\t\t\t NULL, &base, name, data);\n+\t\t\tprocess_tree(revs, (struct tree *)obj, last_root_tree,\n+\t\t\t\t show_object, NULL, &base, name, data);\n+\t\t\tlast_root_tree = (struct tree *)obj;\n \t\t\tcontinue;\n \t\t}\n \t\tif (obj->type == OBJ_BLOB) {\n"},{"id":"216234","messageId":"87vc71u5l7.fsf@linux-k42r.v.cablecom.net","threadId":"33602","inReplyTo":"20130501204947.GA12789@sigill.intra.peff.net","subject":"Re: [PATCH] Hold an 'unsigned long' chunk of the sha1 in obj_hash","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-05-02T08:52:04Z","receivedAt":"2013-05-02T08:52:04Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Jeff King writes:\n\n> It _might_ still be advantageous to do your patch on top, but I suspect\n> it will diminish the returns from your patch (since the point of it is\n> to probe less far down the chain on average).\n\nNo, mine makes it slower again. Apparently the increased size is no\nlonger worth it. You'll need a wide window to read this:\n\nTest next tr/hash-speedup jk/hash-speedup both-hash-speedup \n----------------------------------------------------------------------------------------------------------------------------------------\n0001.1: rev-list --all 0.66(0.63+0.02) 0.66(0.63+0.03) -0.4% 0.66(0.63+0.03) -0.6% 0.66(0.62+0.03) -0.6% \n0001.2: rev-list --all --objects 4.12(4.05+0.05) 3.81(3.74+0.06) -7.6%*** 3.50(3.43+0.05) -15.1%*** 3.56(3.49+0.05) -13.7%***\n----------------------------------------------------------------------------------------------------------------------------------------\n\nNote that the scripts always generate the percentages and significance\nw.r.t. the first column. Comparing yours with both instead gives\n\nTest jk/hash-speedup both-hash-speedup \n---------------------------------------------------------------------------\n0001.1: rev-list --all 0.66(0.63+0.03) 0.66(0.62+0.03) +0.0% \n0001.2: rev-list --all --objects 3.50(3.43+0.05) 3.56(3.49+0.05) +1.6%*\n---------------------------------------------------------------------------\n\nwhich is still significant (in the statistical p=5% sense).\n\nFor kicks I also ran some other tests, which generally show that the\nspeedups are limited to this specific workload:\n\nTest next tr/hash-speedup jk/hash-speedup both-hash-speedup \n-------------------------------------------------------------------------------------------------------------------------------\n3201.1: branch --contains 0.76(0.74+0.02) 0.75(0.73+0.02) -1.0%* 0.77(0.74+0.02) +0.7% 0.76(0.73+0.02) -0.7% \n4000.1: log -3000 (baseline) 0.12(0.09+0.02) 0.12(0.10+0.02) +3.2% 0.12(0.10+0.01) +0.0% 0.12(0.10+0.02) +3.2% \n4000.2: log --raw -3000 (tree-only) 0.53(0.47+0.05) 0.52(0.46+0.05) -0.9% 0.53(0.46+0.06) +0.0% 0.52(0.45+0.06) -0.9% \n4000.3: log -p -3000 (Myers) 2.39(2.23+0.14) 2.38(2.23+0.13) -0.4% 2.38(2.23+0.14) -0.4% 2.38(2.23+0.13) -0.5% \n4000.4: log -p -3000 --histogram 2.43(2.28+0.13) 2.43(2.28+0.13) -0.0% 2.43(2.28+0.13) -0.1% 2.43(2.28+0.14) +0.1% \n4000.5: log -p -3000 --patience 2.72(2.57+0.12) 2.74(2.59+0.12) +0.7% 2.72(2.57+0.13) +0.2% 2.74(2.59+0.13) +0.8%.\n-------------------------------------------------------------------------------------------------------------------------------\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"}]}