{"thread":{"id":"3307","subject":"[PATCH] Optimization for git-rev-list --objects","startedAt":"2006-02-11T19:14:57Z","lastAt":"2006-02-12T18:34:08Z","messageCount":21,"participants":["Alexandre Julliard","Johannes Schindelin","Linus Torvalds","Junio C Hamano","Florian Weimer"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"15937","messageId":"87slqpg11q.fsf@wine.dyndns.org","threadId":"3307","inReplyTo":null,"subject":"[PATCH] Optimization for git-rev-list --objects","fromName":"Alexandre Julliard","fromEmail":"julliard@winehq.org","sentAt":"2006-02-11T19:14:57Z","receivedAt":"2006-02-11T19:14:57Z","isPatch":true,"sender":{"key":"julliard@winehq.org","avatar":null},"body":"\nWhen building a large list of objects, most of the time is spent in\ncreated_object() inserting the objects in the sorted list. This patch\nsplits the list in 256 sublists to reduce the impact of the O(n^2)\nlist insertion.\n\nOn the WineHQ repository (220,000 objects), the patch reduces the time\nneeded for a 'git-rev-list --objects HEAD' from 2 minutes to 20 seconds.\n\nSigned-off-by: Alexandre Julliard <julliard@winehq.org>\n\n---\n\n fsck-objects.c |   66 +++++++++++++++++++++++++++++---------------------------\n name-rev.c     |    9 ++++----\n object.c       |   24 ++++++++++----------\n object.h       |    4 ++-\n 4 files changed, 53 insertions(+), 50 deletions(-)\n\n68f8fcb7f5883ecc44a80e822e0b78ee8efd9eb9\ndiff --git a/fsck-objects.c b/fsck-objects.c\nindex 9950be2..5bdb21e 100644\n--- a/fsck-objects.c\n+++ b/fsck-objects.c\n@@ -58,45 +58,47 @@ static int objwarning(struct object *obj\n \n static void check_connectivity(void)\n {\n-\tint i;\n+\tint i, j;\n \n \t/* Look up all the requirements, warn about missing objects.. */\n-\tfor (i = 0; i < nr_objs; i++) {\n-\t\tstruct object *obj = objs[i];\n+\tfor (i = 0; i < 256; i++) {\n+\t\tfor (j = 0; j < nr_objs[i]; j++) {\n+\t\t\tstruct object *obj = objs[i][j];\n \n-\t\tif (!obj->parsed) {\n-\t\t\tif (!standalone && has_sha1_file(obj->sha1))\n-\t\t\t\t; /* it is in pack */\n-\t\t\telse\n-\t\t\t\tprintf(\"missing %s %s\\n\",\n-\t\t\t\t       obj->type, sha1_to_hex(obj->sha1));\n-\t\t\tcontinue;\n-\t\t}\n+\t\t\tif (!obj->parsed) {\n+\t\t\t\tif (!standalone && has_sha1_file(obj->sha1))\n+\t\t\t\t\t; /* it is in pack */\n+\t\t\t\telse\n+\t\t\t\t\tprintf(\"missing %s %s\\n\",\n+\t\t\t\t\t       obj->type, sha1_to_hex(obj->sha1));\n+\t\t\t\tcontinue;\n+\t\t\t}\n \n-\t\tif (obj->refs) {\n-\t\t\tconst struct object_refs *refs = obj->refs;\n-\t\t\tunsigned j;\n-\t\t\tfor (j = 0; j < refs->count; j++) {\n-\t\t\t\tstruct object *ref = refs->ref[j];\n-\t\t\t\tif (ref->parsed ||\n-\t\t\t\t    (!standalone && has_sha1_file(ref->sha1)))\n-\t\t\t\t\tcontinue;\n-\t\t\t\tprintf(\"broken link from %7s %s\\n\",\n-\t\t\t\t       obj->type, sha1_to_hex(obj->sha1));\n-\t\t\t\tprintf(\"              to %7s %s\\n\",\n-\t\t\t\t       ref->type, sha1_to_hex(ref->sha1));\n+\t\t\tif (obj->refs) {\n+\t\t\t\tconst struct object_refs *refs = obj->refs;\n+\t\t\t\tunsigned k;\n+\t\t\t\tfor (k = 0; k < refs->count; k++) {\n+\t\t\t\t\tstruct object *ref = refs->ref[k];\n+\t\t\t\t\tif (ref->parsed ||\n+\t\t\t\t\t    (!standalone && has_sha1_file(ref->sha1)))\n+\t\t\t\t\t\tcontinue;\n+\t\t\t\t\tprintf(\"broken link from %7s %s\\n\",\n+\t\t\t\t\t       obj->type, sha1_to_hex(obj->sha1));\n+\t\t\t\t\tprintf(\"              to %7s %s\\n\",\n+\t\t\t\t\t       ref->type, sha1_to_hex(ref->sha1));\n+\t\t\t\t}\n \t\t\t}\n-\t\t}\n \n-\t\tif (show_unreachable && !(obj->flags & REACHABLE)) {\n-\t\t\tprintf(\"unreachable %s %s\\n\",\n-\t\t\t       obj->type, sha1_to_hex(obj->sha1));\n-\t\t\tcontinue;\n-\t\t}\n+\t\t\tif (show_unreachable && !(obj->flags & REACHABLE)) {\n+\t\t\t\tprintf(\"unreachable %s %s\\n\",\n+\t\t\t\t       obj->type, sha1_to_hex(obj->sha1));\n+\t\t\t\tcontinue;\n+\t\t\t}\n \n-\t\tif (!obj->used) {\n-\t\t\tprintf(\"dangling %s %s\\n\", obj->type, \n-\t\t\t       sha1_to_hex(obj->sha1));\n+\t\t\tif (!obj->used) {\n+\t\t\t\tprintf(\"dangling %s %s\\n\", obj->type, \n+\t\t\t\t       sha1_to_hex(obj->sha1));\n+\t\t\t}\n \t\t}\n \t}\n }\ndiff --git a/name-rev.c b/name-rev.c\nindex bbadb91..9a8d086 100644\n--- a/name-rev.c\n+++ b/name-rev.c\n@@ -230,11 +230,12 @@ int main(int argc, char **argv)\n \t\t\t\tfwrite(p_start, p - p_start, 1, stdout);\n \t\t}\n \t} else if (all) {\n-\t\tint i;\n+\t\tint i, j;\n \n-\t\tfor (i = 0; i < nr_objs; i++)\n-\t\t\tprintf(\"%s %s\\n\", sha1_to_hex(objs[i]->sha1),\n-\t\t\t\t\tget_rev_name(objs[i]));\n+\t\tfor (i = 0; i < 256; i++)\n+\t\t\tfor (j = 0; j < nr_objs[i]; j++)\n+\t\t\t\tprintf(\"%s %s\\n\", sha1_to_hex(objs[i][j]->sha1),\n+\t\t\t\t\t\tget_rev_name(objs[i][j]));\n \t} else\n \t\tfor ( ; revs; revs = revs->next)\n \t\t\tprintf(\"%s %s\\n\", revs->name, get_rev_name(revs->item));\ndiff --git a/object.c b/object.c\nindex 1577f74..fcd4d0c 100644\n--- a/object.c\n+++ b/object.c\n@@ -5,19 +5,19 @@\n #include \"commit.h\"\n #include \"tag.h\"\n \n-struct object **objs;\n-int nr_objs;\n-static int obj_allocs;\n+struct object **objs[256];\n+int nr_objs[256];\n+static int obj_allocs[256];\n \n int track_object_refs = 1;\n \n static int find_object(const unsigned char *sha1)\n {\n-\tint first = 0, last = nr_objs;\n+\tint first = 0, last = nr_objs[*sha1];\n \n         while (first < last) {\n                 int next = (first + last) / 2;\n-                struct object *obj = objs[next];\n+                struct object *obj = objs[*sha1][next];\n                 int cmp;\n \n                 cmp = memcmp(sha1, obj->sha1, 20);\n@@ -36,7 +36,7 @@ struct object *lookup_object(const unsig\n {\n \tint pos = find_object(sha1);\n \tif (pos >= 0)\n-\t\treturn objs[pos];\n+\t\treturn objs[*sha1][pos];\n \treturn NULL;\n }\n \n@@ -54,17 +54,17 @@ void created_object(const unsigned char \n \t\tdie(\"Inserting %s twice\\n\", sha1_to_hex(sha1));\n \tpos = -pos-1;\n \n-\tif (obj_allocs == nr_objs) {\n-\t\tobj_allocs = alloc_nr(obj_allocs);\n-\t\tobjs = xrealloc(objs, obj_allocs * sizeof(struct object *));\n+\tif (obj_allocs[*sha1] == nr_objs[*sha1]) {\n+\t\tobj_allocs[*sha1] = alloc_nr(obj_allocs[*sha1]);\n+\t\tobjs[*sha1] = xrealloc(objs[*sha1], obj_allocs[*sha1] * sizeof(struct object *));\n \t}\n \n \t/* Insert it into the right place */\n-\tmemmove(objs + pos + 1, objs + pos, (nr_objs - pos) * \n+\tmemmove(objs[*sha1] + pos + 1, objs[*sha1] + pos, (nr_objs[*sha1] - pos) * \n \t\tsizeof(struct object *));\n \n-\tobjs[pos] = obj;\n-\tnr_objs++;\n+\tobjs[*sha1][pos] = obj;\n+\tnr_objs[*sha1]++;\n }\n \n struct object_refs *alloc_object_refs(unsigned count)\ndiff --git a/object.h b/object.h\nindex 0e76182..dcd6ac4 100644\n--- a/object.h\n+++ b/object.h\n@@ -23,8 +23,8 @@ struct object {\n };\n \n extern int track_object_refs;\n-extern int nr_objs;\n-extern struct object **objs;\n+extern int nr_objs[256];\n+extern struct object **objs[256];\n \n /** Internal only **/\n struct object *lookup_object(const unsigned char *sha1);\n-- \n1.1.6.g68f8\n\n\n-- \nAlexandre Julliard\njulliard@winehq.org\n"},{"id":"15945","messageId":"Pine.LNX.4.63.0602120254260.10235@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"3307","inReplyTo":"87slqpg11q.fsf@wine.dyndns.org","subject":"[PATCH] Use a hashtable for objects instead of a sorted list","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-02-12T01:57:57Z","receivedAt":"2006-02-12T01:57:57Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nIn a simple test, this brings down the CPU time from 47 sec to 22 sec.\n\nSigned-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>\n\n---\n\n\tOn Sat, 11 Feb 2006, Alexandre Julliard wrote:\n\n\t> When building a large list of objects, most of the time is spent in\n\t> created_object() inserting the objects in the sorted list. This patch\n\t> splits the list in 256 sublists to reduce the impact of the O(n^2)\n\t> list insertion.\n\n\tYour patch brought down the CPU time to 27 sec in my test.\n\n fsck-objects.c |    5 +++-\n name-rev.c     |    7 +++---\n object.c       |   67 +++++++++++++++++++++++++++++++++-----------------------\n object.h       |    2 +-\n 4 files changed, 48 insertions(+), 33 deletions(-)\n\ndiff --git a/fsck-objects.c b/fsck-objects.c\nindex 9950be2..6439d55 100644\n--- a/fsck-objects.c\n+++ b/fsck-objects.c\n@@ -61,9 +61,12 @@ static void check_connectivity(void)\n \tint i;\n \n \t/* Look up all the requirements, warn about missing objects.. */\n-\tfor (i = 0; i < nr_objs; i++) {\n+\tfor (i = 0; i < obj_allocs; i++) {\n \t\tstruct object *obj = objs[i];\n \n+\t\tif (!obj)\n+\t\t\tcontinue;\n+\n \t\tif (!obj->parsed) {\n \t\t\tif (!standalone && has_sha1_file(obj->sha1))\n \t\t\t\t; /* it is in pack */\ndiff --git a/name-rev.c b/name-rev.c\nindex bdaa59b..08faa54 100644\n--- a/name-rev.c\n+++ b/name-rev.c\n@@ -303,9 +303,10 @@ int main(int argc, char **argv)\n \t} else if (all) {\n \t\tint i;\n \n-\t\tfor (i = 0; i < nr_objs; i++)\n-\t\t\tprintf(\"%s %s\\n\", sha1_to_hex(objs[i]->sha1),\n-\t\t\t\t\tget_rev_name(objs[i]));\n+\t\tfor (i = 0; i < obj_allocs; i++)\n+\t\t\tif (objs[i])\n+\t\t\t\tprintf(\"%s %s\\n\", sha1_to_hex(objs[i]->sha1),\n+\t\t\t\t\t\tget_rev_name(objs[i]));\n \t} else\n \t\tfor ( ; revs; revs = revs->next)\n \t\t\tprintf(\"%s %s\\n\", revs->name, get_rev_name(revs->item));\ndiff --git a/object.c b/object.c\nindex 1577f74..3259862 100644\n--- a/object.c\n+++ b/object.c\n@@ -6,30 +6,32 @@\n #include \"tag.h\"\n \n struct object **objs;\n-int nr_objs;\n-static int obj_allocs;\n+static int nr_objs;\n+int obj_allocs;\n \n int track_object_refs = 1;\n \n+static int hashtable_index(const unsigned char *sha1)\n+{\n+\tunsigned int i = *(unsigned int *)sha1;\n+\treturn (int)(i % obj_allocs);\n+}\n+\n static int find_object(const unsigned char *sha1)\n {\n-\tint first = 0, last = nr_objs;\n+\tint i = hashtable_index(sha1);\n+\n+\tif (!objs)\n+\t\treturn -1;\n \n-        while (first < last) {\n-                int next = (first + last) / 2;\n-                struct object *obj = objs[next];\n-                int cmp;\n-\n-                cmp = memcmp(sha1, obj->sha1, 20);\n-                if (!cmp)\n-                        return next;\n-                if (cmp < 0) {\n-                        last = next;\n-                        continue;\n-                }\n-                first = next+1;\n-        }\n-        return -first-1;\n+\twhile (objs[i]) {\n+\t\tif (memcmp(sha1, objs[i]->sha1, 20) == 0)\n+\t\t\treturn i;\n+\t\ti++;\n+\t\tif (i == obj_allocs)\n+\t\t\ti = 0;\n+\t}\n+\treturn -1 - i;\n }\n \n struct object *lookup_object(const unsigned char *sha1)\n@@ -42,7 +44,7 @@ struct object *lookup_object(const unsig\n \n void created_object(const unsigned char *sha1, struct object *obj)\n {\n-\tint pos = find_object(sha1);\n+\tint pos;\n \n \tobj->parsed = 0;\n \tmemcpy(obj->sha1, sha1, 20);\n@@ -50,18 +52,27 @@ void created_object(const unsigned char \n \tobj->refs = NULL;\n \tobj->used = 0;\n \n-\tif (pos >= 0)\n-\t\tdie(\"Inserting %s twice\\n\", sha1_to_hex(sha1));\n-\tpos = -pos-1;\n-\n-\tif (obj_allocs == nr_objs) {\n-\t\tobj_allocs = alloc_nr(obj_allocs);\n+\tif (obj_allocs - 1 <= nr_objs * 2) {\n+\t\tint i, count = obj_allocs;\n+\t\tobj_allocs = (obj_allocs < 32 ? 32 : 2 * obj_allocs);\n \t\tobjs = xrealloc(objs, obj_allocs * sizeof(struct object *));\n+\t\tmemset(objs + count, 0, (obj_allocs - count)\n+\t\t\t\t* sizeof(struct object *));\n+\t\tfor (i = 0; i < count; i++)\n+\t\t\tif (objs[i]) {\n+\t\t\t\tint j = find_object(objs[i]->sha1);\n+\t\t\t\tif (j != i) {\n+\t\t\t\t\tj = -1 - j;\n+\t\t\t\t\tobjs[j] = objs[i];\n+\t\t\t\t\tobjs[i] = NULL;\n+\t\t\t\t}\n+\t\t\t}\n \t}\n \n-\t/* Insert it into the right place */\n-\tmemmove(objs + pos + 1, objs + pos, (nr_objs - pos) * \n-\t\tsizeof(struct object *));\n+\tpos = find_object(sha1);\n+\tif (pos >= 0)\n+\t\tdie(\"Inserting %s twice\\n\", sha1_to_hex(sha1));\n+\tpos = -pos-1;\n \n \tobjs[pos] = obj;\n \tnr_objs++;\ndiff --git a/object.h b/object.h\nindex 0e76182..e08afbd 100644\n--- a/object.h\n+++ b/object.h\n@@ -23,7 +23,7 @@ struct object {\n };\n \n extern int track_object_refs;\n-extern int nr_objs;\n+extern int obj_allocs;\n extern struct object **objs;\n \n /** Internal only **/\n"},{"id":"15947","messageId":"Pine.LNX.4.64.0602111803350.3691@g5.osdl.org","threadId":"3307","inReplyTo":"87slqpg11q.fsf@wine.dyndns.org","subject":"Re: [PATCH] Optimization for git-rev-list --objects","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-12T02:19:09Z","receivedAt":"2006-02-12T02:19:09Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 11 Feb 2006, Alexandre Julliard wrote:\n> \n> When building a large list of objects, most of the time is spent in\n> created_object() inserting the objects in the sorted list. This patch\n> splits the list in 256 sublists to reduce the impact of the O(n^2)\n> list insertion.\n> \n> On the WineHQ repository (220,000 objects), the patch reduces the time\n> needed for a 'git-rev-list --objects HEAD' from 2 minutes to 20 seconds.\n\nGoodie. However, I wonder if we care about the sorting at _all_.\n\nThe sorting really only helps \"find_object()\", and the thing is, we could \ncertainly do that other ways too. Keeping a sorted list is kind of \nsenseless, when the data is so amenable to be kept in a tree.\n\nWe could add left/right pointers to each object, and just keep them in a \ntree. We probably don't even need any fancy balancing, since hashing means \nthat we could just keep the first object we ever allocate as the root, and \nthings should normally be pretty damn balanced.\n\nThen we could do:\n\n\tstatic struct object *root = NULL;\n\n\tstatic struct object **lookup_object_position(unsigned char *sha1)\n\t{\n\t\tstruct object **p = &root;\n\n\t\tfor (;;) {\n\t\t\tstruct object *object = *p;\n\t\t\tint sign;\n\n\t\t\tif (!object)\n\t\t\t\tbreak;\n\t\t\tsign = memcmp(sha1, object->sha1, 20)\n\t\t\tif (!sign)\n\t\t\t\tbreak;\n\t\t\tp = &object->left;\n\t\t\tif (sign < 0)\n\t\t\t\tcontinue;\n\t\t\tp = &object->right;\n\t\t}\n\t\treturn p;\n\t}\n\nand now we _trivially_ have:\n\n\tstruct object *lookup_object(unsigned char *sha1)\n\t{\n\t\treturn *lookup_object_position(unsigned char *sha1);\n\t}\n\n\tvoid created_object(struct object **pos, unsigned char *sha1, struct object *n)\n\t{\n\t\tmemcpy(n->sha1, sha1, 20);\n\t\t*pos = n;\n\t}\n\nand the \"lookup_or_create()\" functions would become\n\n\tstruct tag *lookup_tag(unsigned char *sha1)\n\t{\n\t\tstruct object **p = lookup_object_position(sha1);\n\t\tstruct object *object;\n\n\t\tobject = *p;\n\t\tif (!object) {\n\t\t\tstruct tag *ret = xmalloc(sizeof(struct tag));\n\t\t\tmemset(ret, 0, sizeof(struct tag));\n\t\t\tcreated_object(p, sha1, &ret->object);\n\t\t\tret->object.type = tag_type;\n\t\t\treturn ret;\n\t\t}\n\t\tif (!object->type)\n\t\t\tobj->type = tag_type;\n\n\t\tif (object->type != tag_type) {\n\t\t\terror(\"Object %s is a %s, not a tag\",\n\t\t\t\tsha1_to_hex(sha1), obj->type);\n\t\t\treturn NULL;\n\t\t}\n\t\treturn (struct tag *)obj;\n\t}\n\netc etc.\n\nHmm? That would be a lot faster than what we have now, I suspect, and none \nof the ops are expensive.\n\nAnybody want to try this approach?\n\n\t\tLinus\n"},{"id":"15948","messageId":"7vslqpi9mg.fsf@assigned-by-dhcp.cox.net","threadId":"3307","inReplyTo":"Pine.LNX.4.64.0602111803350.3691@g5.osdl.org","subject":"Re: [PATCH] Optimization for git-rev-list --objects","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-12T02:39:03Z","receivedAt":"2006-02-12T02:39:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> Hmm? That would be a lot faster than what we have now, I suspect, and none \n> of the ops are expensive.\n>\n> Anybody want to try this approach?\n\nI am game.  I was looking at Johannes' patch that uses growing\ncircular hash and having the same thought.\n"},{"id":"15949","messageId":"7virrli9am.fsf@assigned-by-dhcp.cox.net","threadId":"3307","inReplyTo":"Pine.LNX.4.63.0602120254260.10235@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] Use a hashtable for objects instead of a sorted list","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-12T02:46:09Z","receivedAt":"2006-02-12T02:46:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> In a simple test, this brings down the CPU time from 47 sec to 22 sec.\n\nI was planning to take Alexandre's patch, but the approach your\npatch takes feels more correct -- it scales with the number of\nobjects you need to handle, instead of having fixed 256\nhashbuckets.\n\nBTW, your version dumped core in hashtable_index immediately\nafter I started \"git-rev-list --objects HEAD\".  How did you get\n_any_ CPU time?\n\nI am not sure expecting that object name pointers are always\n(unsigned int *) aligned as your patch does is OK.  We may want\nto have something like the attached patch on top of yours.\n\nI am also interested to find out how much the rehashing you do\nwhen you update obj_allocs to a larger value is costing.\n\nAlexandle, if you have a chance, could you try Johannes' patch\non your workload to see if it works OK for you?\n\n-- >8 --\n[PATCH] do not assume object name pointers are uint aligned.\n\nAlso fix an obvious bug that caused it dump core at my first\nattempt.  There might be others but I did not actively look for\nthem.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\ndiff --git a/object.c b/object.c\nindex 3259862..59e5e36 100644\n--- a/object.c\n+++ b/object.c\n@@ -13,17 +13,24 @@ int track_object_refs = 1;\n \n static int hashtable_index(const unsigned char *sha1)\n {\n-\tunsigned int i = *(unsigned int *)sha1;\n-\treturn (int)(i % obj_allocs);\n+\tint cnt;\n+\tunsigned int ix = *sha1++;\n+\n+\tfor (cnt = 1; cnt < sizeof(unsigned int); cnt++) {\n+\t\tix <<= 8;\n+\t\tix |= *sha1++;\n+\t}\n+\treturn (int)(ix % obj_allocs);\n }\n \n static int find_object(const unsigned char *sha1)\n {\n-\tint i = hashtable_index(sha1);\n+\tint i;\n \n \tif (!objs)\n \t\treturn -1;\n \n+\ti = hashtable_index(sha1);\n \twhile (objs[i]) {\n \t\tif (memcmp(sha1, objs[i]->sha1, 20) == 0)\n \t\t\treturn i;\n"},{"id":"15956","messageId":"7vhd75fc6y.fsf_-_@assigned-by-dhcp.cox.net","threadId":"3307","inReplyTo":"7vslqpi9mg.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH] binary-tree-based objects.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-12T04:11:49Z","receivedAt":"2006-02-12T04:11:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This implements Linus' idea to keep objects in a binary tree,\ninstead of using the linear array as we currently do.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n * I haven't benched this seriously yet.  One datapoint:\n\n\ttime git-rev-list --objects v2.6.15..linus | wc -l\n\n   are 53sec vs 22sec improvement with the same output.\n\n fsck-objects.c |   36 +++++++++++++++++----------------\n name-rev.c     |   17 +++++++++++-----\n object.c       |   61 +++++++++++++++++++++-----------------------------------\n object.h       |    3 ++-\n 4 files changed, 55 insertions(+), 62 deletions(-)\n\n3c160f4d94cf16db5dc9c603e98ebacbe9ac4ca7\ndiff --git a/fsck-objects.c b/fsck-objects.c\nindex 9950be2..28a7c1b 100644\n--- a/fsck-objects.c\n+++ b/fsck-objects.c\n@@ -56,23 +56,21 @@ static int objwarning(struct object *obj\n }\n \n \n-static void check_connectivity(void)\n+static void check_connectivity(struct object *obj)\n {\n-\tint i;\n-\n \t/* Look up all the requirements, warn about missing objects.. */\n-\tfor (i = 0; i < nr_objs; i++) {\n-\t\tstruct object *obj = objs[i];\n-\n-\t\tif (!obj->parsed) {\n-\t\t\tif (!standalone && has_sha1_file(obj->sha1))\n-\t\t\t\t; /* it is in pack */\n-\t\t\telse\n-\t\t\t\tprintf(\"missing %s %s\\n\",\n-\t\t\t\t       obj->type, sha1_to_hex(obj->sha1));\n-\t\t\tcontinue;\n-\t\t}\n+ again:\n+\tif (!obj)\n+\t\treturn;\n \n+\tif (!obj->parsed) {\n+\t\tif (!standalone && has_sha1_file(obj->sha1))\n+\t\t\t; /* it is in pack */\n+\t\telse\n+\t\t\tprintf(\"missing %s %s\\n\",\n+\t\t\t       obj->type, sha1_to_hex(obj->sha1));\n+\t}\n+\telse {\n \t\tif (obj->refs) {\n \t\t\tconst struct object_refs *refs = obj->refs;\n \t\t\tunsigned j;\n@@ -91,14 +89,16 @@ static void check_connectivity(void)\n \t\tif (show_unreachable && !(obj->flags & REACHABLE)) {\n \t\t\tprintf(\"unreachable %s %s\\n\",\n \t\t\t       obj->type, sha1_to_hex(obj->sha1));\n-\t\t\tcontinue;\n \t\t}\n-\n-\t\tif (!obj->used) {\n+\t\telse if (!obj->used) {\n \t\t\tprintf(\"dangling %s %s\\n\", obj->type, \n \t\t\t       sha1_to_hex(obj->sha1));\n \t\t}\n \t}\n+\tif (obj->left && obj->right)\n+\t\tcheck_connectivity(obj->left);\n+\tobj = obj->right ? obj->right : obj->left;\n+\tgoto again;\n }\n \n /*\n@@ -556,6 +556,6 @@ int main(int argc, char **argv)\n \t\t}\n \t}\n \n-\tcheck_connectivity();\n+\tcheck_connectivity(objs_root);\n \treturn 0;\n }\ndiff --git a/name-rev.c b/name-rev.c\nindex bbadb91..a4fecfb 100644\n--- a/name-rev.c\n+++ b/name-rev.c\n@@ -120,6 +120,17 @@ static const char* get_rev_name(struct o\n \treturn buffer;\n }\n \t\n+void show_all_names(struct object *obj)\n+{\n+\twhile (obj) {\n+\t\tprintf(\"%s %s\\n\", sha1_to_hex(obj->sha1), get_rev_name(obj));\n+\t\tif (obj->left && obj->right)\n+\t\t\tshow_all_names(obj->left);\n+\t\tobj = obj->right ? obj->right : obj->left;\n+\t}\n+}\n+\n+\n int main(int argc, char **argv)\n {\n \tstruct object_list *revs = NULL;\n@@ -230,11 +241,7 @@ int main(int argc, char **argv)\n \t\t\t\tfwrite(p_start, p - p_start, 1, stdout);\n \t\t}\n \t} else if (all) {\n-\t\tint i;\n-\n-\t\tfor (i = 0; i < nr_objs; i++)\n-\t\t\tprintf(\"%s %s\\n\", sha1_to_hex(objs[i]->sha1),\n-\t\t\t\t\tget_rev_name(objs[i]));\n+\t\tshow_all_names(objs_root);\n \t} else\n \t\tfor ( ; revs; revs = revs->next)\n \t\t\tprintf(\"%s %s\\n\", revs->name, get_rev_name(revs->item));\ndiff --git a/object.c b/object.c\nindex 1577f74..a1b0729 100644\n--- a/object.c\n+++ b/object.c\n@@ -5,65 +5,50 @@\n #include \"commit.h\"\n #include \"tag.h\"\n \n-struct object **objs;\n+struct object *objs_root;\n int nr_objs;\n-static int obj_allocs;\n \n int track_object_refs = 1;\n \n-static int find_object(const unsigned char *sha1)\n+static struct object **lookup_object_position(const unsigned char *sha1)\n {\n-\tint first = 0, last = nr_objs;\n+\tstruct object **p = &objs_root;\n \n-        while (first < last) {\n-                int next = (first + last) / 2;\n-                struct object *obj = objs[next];\n-                int cmp;\n-\n-                cmp = memcmp(sha1, obj->sha1, 20);\n-                if (!cmp)\n-                        return next;\n-                if (cmp < 0) {\n-                        last = next;\n-                        continue;\n-                }\n-                first = next+1;\n-        }\n-        return -first-1;\n+\tfor (;;) {\n+\t\tstruct object *object = *p;\n+\t\tint sign;\n+\n+\t\tif (!object)\n+\t\t\tbreak;\n+\t\tsign = memcmp(sha1, object->sha1, 20);\n+\t\tif (!sign)\n+\t\t\tbreak;\n+\t\tp = &object->left;\n+\t\tif (sign < 0)\n+\t\t\tcontinue;\n+\t\tp = &object->right;\n+\t}\n+\treturn p;\n }\n \n struct object *lookup_object(const unsigned char *sha1)\n {\n-\tint pos = find_object(sha1);\n-\tif (pos >= 0)\n-\t\treturn objs[pos];\n-\treturn NULL;\n+\treturn *lookup_object_position(sha1);\n }\n \n void created_object(const unsigned char *sha1, struct object *obj)\n {\n-\tint pos = find_object(sha1);\n+\tstruct object **op = lookup_object_position(sha1);\n \n \tobj->parsed = 0;\n \tmemcpy(obj->sha1, sha1, 20);\n \tobj->type = NULL;\n \tobj->refs = NULL;\n \tobj->used = 0;\n-\n-\tif (pos >= 0)\n+\tobj->left = obj->right = NULL;\n+\tif (*op)\n \t\tdie(\"Inserting %s twice\\n\", sha1_to_hex(sha1));\n-\tpos = -pos-1;\n-\n-\tif (obj_allocs == nr_objs) {\n-\t\tobj_allocs = alloc_nr(obj_allocs);\n-\t\tobjs = xrealloc(objs, obj_allocs * sizeof(struct object *));\n-\t}\n-\n-\t/* Insert it into the right place */\n-\tmemmove(objs + pos + 1, objs + pos, (nr_objs - pos) * \n-\t\tsizeof(struct object *));\n-\n-\tobjs[pos] = obj;\n+\t*op = obj;\n \tnr_objs++;\n }\n \ndiff --git a/object.h b/object.h\nindex 0e76182..32b276d 100644\n--- a/object.h\n+++ b/object.h\n@@ -19,12 +19,13 @@ struct object {\n \tunsigned char sha1[20];\n \tconst char *type;\n \tstruct object_refs *refs;\n+\tstruct object *left, *right;\n \tvoid *util;\n };\n \n extern int track_object_refs;\n extern int nr_objs;\n-extern struct object **objs;\n+extern struct object *objs_root;\n \n /** Internal only **/\n struct object *lookup_object(const unsigned char *sha1);\n-- \n1.1.6.g69c5\n"},{"id":"15958","messageId":"Pine.LNX.4.64.0602112045340.3691@g5.osdl.org","threadId":"3307","inReplyTo":"7vhd75fc6y.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] binary-tree-based objects.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-12T05:06:38Z","receivedAt":"2006-02-12T05:06:38Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 11 Feb 2006, Junio C Hamano wrote:\n> \n>  * I haven't benched this seriously yet.  One datapoint:\n> \n> \ttime git-rev-list --objects v2.6.15..linus | wc -l\n> \n>    are 53sec vs 22sec improvement with the same output.\n\nAnother datapoint: doing \n\n\ttime git-rev-list --objects HEAD > /dev/null \n\nthree times in a row (to verify that the numbers are stable - they very \nclearly are).\n\nBefore:\n\treal    0m41.322s\tuser    0m40.612s\tsys     0m0.492s\n\treal    0m40.797s\tuser    0m40.140s\tsys     0m0.468s\n\treal    0m40.433s\tuser    0m40.016s\tsys     0m0.412s\n\nAfter:\n\treal    0m22.542s\tuser    0m22.080s\tsys     0m0.448s\n\treal    0m22.660s\tuser    0m22.336s\tsys     0m0.312s\n\treal    0m22.671s\tuser    0m22.236s\tsys     0m0.292s\n\nand doing some trivial oprofile runs shows that the object lookup is no \nlonger dominant (my libc's don't have symbol information, so I don't get \ngood profile data, but it shows that libc and libz are the biggest issues, \nwith memcmp and malloc/free apparently being much bigger issues than the \nobject lookup).\n\n\t\t\tLinus\n"},{"id":"15959","messageId":"Pine.LNX.4.64.0602112117560.3691@g5.osdl.org","threadId":"3307","inReplyTo":"Pine.LNX.4.64.0602112045340.3691@g5.osdl.org","subject":"Re: [PATCH] binary-tree-based objects.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-12T05:22:35Z","receivedAt":"2006-02-12T05:22:35Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 11 Feb 2006, Linus Torvalds wrote:\n> \n> Before:\n> \treal    0m41.322s\tuser    0m40.612s\tsys     0m0.492s\n> \treal    0m40.797s\tuser    0m40.140s\tsys     0m0.468s\n> \treal    0m40.433s\tuser    0m40.016s\tsys     0m0.412s\n> \n> After:\n> \treal    0m22.542s\tuser    0m22.080s\tsys     0m0.448s\n> \treal    0m22.660s\tuser    0m22.336s\tsys     0m0.312s\n> \treal    0m22.671s\tuser    0m22.236s\tsys     0m0.292s\n\nAnd just so you wouldn't think that all my machines are slow..\n\nBefore:\n\treal    0m28.645s\tuser    0m28.366s\tsys     0m0.280s\n\treal    0m28.700s\tuser    0m28.486s\tsys     0m0.212s\n\nAfter:\n\treal    0m16.566s\tuser    0m16.373s\tsys     0m0.196s\n\treal    0m16.512s\tuser    0m16.277s\tsys     0m0.236s\n\nso there (that's all with current kernel HEAD, mostly packed).\n\nNow, I haven't compared it to the other suggested fixes (hashing, and the \n256-way bucket-sorting), but I obviously prefer the tree approach because \nit's my idea (and my ideas are _always_ superior) and because it's so dang \nsimple.\n\nIf somebody shows that the other approaches are faster, then I guess I'll \njust have to sulk in a corner and grown quietly at people.\n\n\t\tLinus\n"},{"id":"15960","messageId":"Pine.LNX.4.64.0602112122400.3691@g5.osdl.org","threadId":"3307","inReplyTo":"Pine.LNX.4.64.0602112117560.3691@g5.osdl.org","subject":"Re: [PATCH] binary-tree-based objects.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-12T05:23:10Z","receivedAt":"2006-02-12T05:23:10Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 11 Feb 2006, Linus Torvalds wrote:\n> \n> If somebody shows that the other approaches are faster, then I guess I'll \n> just have to sulk in a corner and grown quietly at people.\n\ngrowl. growL. With an 'L'!\n\n\t\tLinus\n"},{"id":"15961","messageId":"7v1wy9f7q4.fsf@assigned-by-dhcp.cox.net","threadId":"3307","inReplyTo":"Pine.LNX.4.64.0602112122400.3691@g5.osdl.org","subject":"Re: [PATCH] binary-tree-based objects.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-12T05:48:19Z","receivedAt":"2006-02-12T05:48:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> On Sat, 11 Feb 2006, Linus Torvalds wrote:\n>> \n>> If somebody shows that the other approaches are faster, then I guess I'll \n>> just have to sulk in a corner and grown quietly at people.\n>\n> growl. growL. With an 'L'!\n\nI do not get it.\n\nBut my impression was the circular hash with trivial fixes were\nthe fastest.  I am benching them now.\n"},{"id":"15962","messageId":"7vaccxdsaf.fsf@assigned-by-dhcp.cox.net","threadId":"3307","inReplyTo":"7v1wy9f7q4.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] binary-tree-based objects.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-12T06:07:04Z","receivedAt":"2006-02-12T06:07:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> Linus Torvalds <torvalds@osdl.org> writes:\n>\n>> On Sat, 11 Feb 2006, Linus Torvalds wrote:\n>>> \n>>> If somebody shows that the other approaches are faster, then I guess I'll \n>>> just have to sulk in a corner and grown quietly at people.\n>>\n>> growl. growL. With an 'L'!\n>\n> I do not get it.\n> ...\n\nI first suspected you just meant the typo (s/grown/growl/) but\nit probably is that you really meant GROWL (and sulk).\n\nIt turns out that Johannes (with my patch to fix possible\nunsigned int alignment issue and the initial call to\nfind_object()) is the clear winner.\n\n        base   - tip of \"master\"\n        lt-obj - the binary tree without balancing\n        aj-obj - Alexandre's 256-way buckets\n        js-obj - Johannes' circular hash\n\nAlthough I have _not_ double checked the correctness of them, I\ndid not see major flaw in any of them.\n\nbase/git-rev-list --objects v2.6.14..linus\nreal\t2m32.088s\tuser\t2m2.830s\tsys\t0m0.890s\nreal\t2m6.614s\tuser\t2m1.860s\tsys\t0m0.660s\nreal\t2m13.776s\tuser\t2m2.450s\tsys\t0m0.590s\nreal\t2m6.062s\tuser\t2m2.420s\tsys\t0m0.690s\nreal\t2m15.567s\tuser\t2m3.170s\tsys\t0m0.900s\n\nlt-obj/git-rev-list --objects v2.6.14..linus\nreal\t0m42.889s\tuser\t0m40.170s\tsys\t0m0.570s\nreal\t0m44.247s\tuser\t0m40.320s\tsys\t0m0.530s\nreal\t0m40.891s\tuser\t0m40.110s\tsys\t0m0.500s\nreal\t0m41.874s\tuser\t0m40.090s\tsys\t0m0.530s\nreal\t0m41.596s\tuser\t0m40.050s\tsys\t0m0.600s\n\naj-obj/git-rev-list --objects v2.6.14..linus\nreal\t0m36.842s\tuser\t0m36.200s\tsys\t0m0.490s\nreal\t0m37.178s\tuser\t0m36.740s\tsys\t0m0.390s\nreal\t0m37.222s\tuser\t0m36.540s\tsys\t0m0.610s\nreal\t0m36.924s\tuser\t0m36.410s\tsys\t0m0.360s\nreal\t0m37.341s\tuser\t0m36.150s\tsys\t0m0.620s\n\njs-obj/git-rev-list --objects v2.6.14..linus\nreal\t0m24.689s\tuser\t0m24.120s\tsys\t0m0.390s\nreal\t0m24.753s\tuser\t0m24.020s\tsys\t0m0.360s\nreal\t0m27.650s\tuser\t0m24.470s\tsys\t0m0.440s\nreal\t0m33.480s\tuser\t0m24.030s\tsys\t0m0.460s\nreal\t0m25.329s\tuser\t0m24.490s\tsys\t0m0.390s\n\n\nbase/git-name-rev --all\nreal\t0m4.193s\tuser\t0m4.060s\tsys\t0m0.130s\nreal\t0m4.179s\tuser\t0m4.100s\tsys\t0m0.080s\nreal\t0m4.210s\tuser\t0m4.040s\tsys\t0m0.150s\nreal\t0m4.162s\tuser\t0m4.100s\tsys\t0m0.060s\nreal\t0m4.697s\tuser\t0m4.100s\tsys\t0m0.120s\n\nlt-obj/git-name-rev --all\nreal\t0m2.199s\tuser\t0m2.120s\tsys\t0m0.080s\nreal\t0m2.186s\tuser\t0m2.110s\tsys\t0m0.080s\nreal\t0m2.187s\tuser\t0m2.150s\tsys\t0m0.040s\nreal\t0m2.817s\tuser\t0m2.150s\tsys\t0m0.070s\nreal\t0m2.323s\tuser\t0m2.170s\tsys\t0m0.050s\n\naj-obj/git-name-rev --all\nreal\t0m2.136s\tuser\t0m2.050s\tsys\t0m0.080s\nreal\t0m2.164s\tuser\t0m2.080s\tsys\t0m0.060s\nreal\t0m2.143s\tuser\t0m2.070s\tsys\t0m0.070s\nreal\t0m2.141s\tuser\t0m2.080s\tsys\t0m0.060s\nreal\t0m2.154s\tuser\t0m2.070s\tsys\t0m0.090s\n\njs-obj/git-name-rev --all\nreal\t0m2.047s\tuser\t0m2.010s\tsys\t0m0.040s\nreal\t0m2.040s\tuser\t0m1.970s\tsys\t0m0.070s\nreal\t0m2.025s\tuser\t0m1.970s\tsys\t0m0.060s\nreal\t0m2.170s\tuser\t0m2.020s\tsys\t0m0.030s\nreal\t0m2.046s\tuser\t0m2.010s\tsys\t0m0.030s\n"},{"id":"15963","messageId":"Pine.LNX.4.64.0602112237580.3691@g5.osdl.org","threadId":"3307","inReplyTo":"7vaccxdsaf.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] binary-tree-based objects.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-12T06:53:16Z","receivedAt":"2006-02-12T06:53:16Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 11 Feb 2006, Junio C Hamano wrote:\n> \n> It turns out that Johannes (with my patch to fix possible\n> unsigned int alignment issue and the initial call to\n> find_object()) is the clear winner.\n\nHaving looked at it, I will have to agree. Johannes' approach looks \npretty clean, and has the same memory overhead mine has (two pointers per \nobject in the hash - one used, one empty), but has a lot fewer memcmp() \ncalls and pointer chasing.\n\nSo I'll growl softly but concur. Johannes' code isn't even very complex.\n\n\t\tLinus\n"},{"id":"15964","messageId":"Pine.LNX.4.64.0602112301170.3691@g5.osdl.org","threadId":"3307","inReplyTo":"Pine.LNX.4.64.0602112117560.3691@g5.osdl.org","subject":"Re: [PATCH] binary-tree-based objects.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-12T07:05:06Z","receivedAt":"2006-02-12T07:05:06Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 11 Feb 2006, Linus Torvalds wrote:\n> \n> Before:\n> \treal    0m41.322s\tuser    0m40.612s\tsys     0m0.492s\n> After:\n> \treal    0m22.542s\tuser    0m22.080s\tsys     0m0.448s\nJohannes:\n\treal    0m13.814s\tuser    0m13.492s\tsys     0m0.296s\n\n> And just so you wouldn't think that all my machines are slow..\n> \n> Before:\n> \treal    0m28.645s\tuser    0m28.366s\tsys     0m0.280s\n> After:\n> \treal    0m16.566s\tuser    0m16.373s\tsys     0m0.196s\nJohannes:\n\treal    0m10.239s\tuser    0m10.029s\tsys     0m0.208s\n\nSo the hashing thing is indeed the clear winner.\n\nMake it so. \n\n\t\tLinus\n"},{"id":"15965","messageId":"87oe1dez7k.fsf@wine.dyndns.org","threadId":"3307","inReplyTo":"7virrli9am.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Use a hashtable for objects instead of a sorted list","fromName":"Alexandre Julliard","fromEmail":"julliard@winehq.org","sentAt":"2006-02-12T08:52:15Z","receivedAt":"2006-02-12T08:52:15Z","isPatch":true,"sender":{"key":"julliard@winehq.org","avatar":null},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> I am also interested to find out how much the rehashing you do\n> when you update obj_allocs to a larger value is costing.\n>\n> Alexandle, if you have a chance, could you try Johannes' patch\n> on your workload to see if it works OK for you?\n\nIt works great for me, CPU time is down to 15 sec instead of 20 sec\nwith my patch.\n\n-- \nAlexandre Julliard\njulliard@winehq.org\n"},{"id":"15967","messageId":"87accwlt8k.fsf@mid.deneb.enyo.de","threadId":"3307","inReplyTo":"7virrli9am.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Use a hashtable for objects instead of a sorted list","fromName":"Florian Weimer","fromEmail":"fw@deneb.enyo.de","sentAt":"2006-02-12T11:19:23Z","receivedAt":"2006-02-12T11:19:23Z","isPatch":true,"sender":{"key":"fw@deneb.enyo.de","avatar":null},"body":"* Junio C. Hamano:\n\n>  static int hashtable_index(const unsigned char *sha1)\n>  {\n> -\tunsigned int i = *(unsigned int *)sha1;\n> -\treturn (int)(i % obj_allocs);\n> +\tint cnt;\n\n> +\tunsigned int ix = *sha1++;\n> +\n> +\tfor (cnt = 1; cnt < sizeof(unsigned int); cnt++) {\n> +\t\tix <<= 8;\n> +\t\tix |= *sha1++;\n> +\t}\n\nmemcpy(&ix, sha1, sizeof(ix));\n\n(GCC should do the rest.)\n\n> +\treturn (int)(ix % obj_allocs);\n>  }\n\nreturn (int)(ix & (obj_allocs - 1));\n\nAFAICS, obj_allocs is a power of two.\n"},{"id":"15969","messageId":"7vlkwgdbk6.fsf_-_@assigned-by-dhcp.cox.net","threadId":"3307","inReplyTo":"87accwlt8k.fsf@mid.deneb.enyo.de","subject":"***DONTUSE*** Re: [PATCH] Use a hashtable for objects instead of a sorted list","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-12T12:08:25Z","receivedAt":"2006-02-12T12:08:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Florian Weimer <fw@deneb.enyo.de> writes:\n\n> (GCC should do the rest.)\n>...\n> AFAICS, obj_allocs is a power of two.\n\nYes, I already have something like these in my tree (the latter\ndid not help much as far as I could tell, though).\n\n****HOWEVER****\n\nDo not use this (not just my patch but with the whole hashtable\nversion) in your production repository yet.\n\nI've got a mysterious corruption and bogus output from\nfsck-objects, and have been tracking it (see the timestamp of\nthis message).\n\n1.2.0 will most likely to be be *delayed*.  I have to first make\nsure my private repository is sane.  Grrrrrrrr.\n"},{"id":"15970","messageId":"7vaccwdbfs.fsf@assigned-by-dhcp.cox.net","threadId":"3307","inReplyTo":"87oe1dez7k.fsf@wine.dyndns.org","subject":"Re: [PATCH] Use a hashtable for objects instead of a sorted list","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-12T12:11:03Z","receivedAt":"2006-02-12T12:11:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Alexandre Julliard <julliard@winehq.org> writes:\n\n> Junio C Hamano <junkio@cox.net> writes:\n>\n>> Alexandle, if you have a chance, could you try Johannes' patch\n>> on your workload to see if it works OK for you?\n>\n> It works great for me, CPU time is down to 15 sec instead of 20 sec\n> with my patch.\n\nThanks.  Now we have three independent numbers to back up that\nJohannes is the winner....\n\nGrrrrrrr.  Please, DO NOT USE THIS ONE YET.\n\nAt least, not with your production repository.\n\nI am trying to nail it down but it appears at least fsck-objects\nusing this version gives bogus results.  I am first trying to\nsee if my primary working repository is sane.\n\nOh, and thanks again for your initial patch, which was what\nstarted this drastic improvement.\n"},{"id":"15972","messageId":"7virrkbsgp.fsf@assigned-by-dhcp.cox.net","threadId":"3307","inReplyTo":"7vlkwgdbk6.fsf_-_@assigned-by-dhcp.cox.net","subject":"***DONTUSE*** Re: [PATCH] Use a hashtable for objects instead of a sorted list","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-12T13:46:14Z","receivedAt":"2006-02-12T13:46:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I've pushed things out to \"master\" and \"next\" branch.\n\nQuite a lot of things.\n\nOne thing that I expected to be there is not.  It is the\nhashtable patch.  It is in \"pu\".\n\nI once had it in my private \"next\", but dropped it before\npushing things out.\n\nThe problem does not seem to trigger with casual use, but I\nfound that with a clone from my primary repository with '-l -s'\n(that is, a clone that uses alternates mechanism to borrow from\nmy primary repository), fsck-objects built with the patch seems\nto report bogus things \"missing\".  I have not traced it fully;\ninstead I ended up spending most of the night (I noticed it at\naround 01:30 and now it is 05:30 so that's about four hours)\nrecovering some of my refs and double checking if my primary\nrepository is not corrupt X-<.  At least, the primary repository\nlooks sane now.\n\nWith luck, I would muster enough energy to figure it out, but I\nneed some sleep first.\n\nThe problem seems to be very elusive.  I took a snapshot of the\ntwo repositories involved, so that I can use them as an isolated\ntest case (the one is my primary repository and the other one is\nthe \"-l -s\" clone). The problem is repeatable, but the SHA1 of\nthe file the broken fsck-objects reports to be missing is\ndifferent from the one I observed in the first experiment with\nthe real repositories.  It appears it has something to do with\nthe directory listing order of fsck-objects, which in turn means\nthe reproduction of the problem is related to memory allocation\npatterns, so maybe valgrind would help.  On the other hand, even\nif I published a tarball of these two repositories somewhere,\nother people (or myself) who extract the tarball would probably\nnot see the same SHA1 reported as missing X-<.\n\nAnyway, I've pushed them out before crashing, after I double\nchecked that versions built from my \"master\" and \"next\" do not\nseem to show the problem, while with the one in \"pu\", the first\npatch after merging \"next\" in it being the said patch, exhibits\nthe problem.\n"},{"id":"15974","messageId":"Pine.LNX.4.63.0602121517050.15392@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"3307","inReplyTo":"7vaccwdbfs.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Use a hashtable for objects instead of a sorted list","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-02-12T14:31:33Z","receivedAt":"2006-02-12T14:31:33Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 12 Feb 2006, Junio C Hamano wrote:\n\n> Alexandre Julliard <julliard@winehq.org> writes:\n> \n> > Junio C Hamano <junkio@cox.net> writes:\n> >\n> >> Alexandle, if you have a chance, could you try Johannes' patch\n> >> on your workload to see if it works OK for you?\n> >\n> > It works great for me, CPU time is down to 15 sec instead of 20 sec\n> > with my patch.\n> \n> Thanks.  Now we have three independent numbers to back up that\n> Johannes is the winner....\n> \n> Grrrrrrr.  Please, DO NOT USE THIS ONE YET.\n> \n> At least, not with your production repository.\n> \n> I am trying to nail it down but it appears at least fsck-objects\n> using this version gives bogus results.  I am first trying to\n> see if my primary working repository is sane.\n> \n> Oh, and thanks again for your initial patch, which was what\n> started this drastic improvement.\n\nI am sorry! I tested fsck, but only *once*, since I did not think such a \ncreepy bug was in there. And then, I had to run to sing Beethoven's Missa \nSolemnis, and missed all the action about this patch.\n\nJust a few remarks around the comments in this thread:\n\n- the doubling of obj_allocs is arbitrary. Originally, I planned to do the \ngrowing much faster, which would have been helped by the fact. But it \nturned out my thinking was defective. So, you can grow the hashtable by \nwhatever you like (doubling is quite effective, though).\n\n- hashtable has expected O(1) insertion, and that is what boosts the \nperformance. Since the table growing is linear in the number of objects \n(both size and computing time), and all operations afterwards are linear \non the table, *and the hash is already computed*, the hashtable is \npreferrable over other data structures (sorted list has O(n) insertion \ntime, and tree still O(log n)).\n\n- the bug Junio fixed was not triggered here, since I did all the testing \non my venerable iBook. The PowerPC architecture evidently aligns \nall pointers to 32-bit, so I could reinterpret the pointer as to an \nunsigned int. Note that there is a small overhead in Junio's version, but \nit is probably not worth the hassle to make that a compile time option. \nBut I agree with Florian that memcpy would be more efficient.\n\n- Arithmetic and Boolean operations on 32-bit integers typically are \nhandled very efficiently in modern 32-bit CPUs, so there should be no \nreason to use \"&\" instead of \"%\" (especially since understanding the code \nwouldn't be helped by that).\n\nCiao,\nDscho\n"},{"id":"15976","messageId":"Pine.LNX.4.63.0602121822060.21959@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"3307","inReplyTo":"7virrkbsgp.fsf@assigned-by-dhcp.cox.net","subject":"Re: ***DONTUSE*** Re: [PATCH] Use a hashtable for objects instead of a sorted list","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-02-12T17:26:50Z","receivedAt":"2006-02-12T17:26:50Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 12 Feb 2006, Junio C Hamano wrote:\n\n> The problem does not seem to trigger with casual use, but I\n> found that with a clone from my primary repository with '-l -s'\n> (that is, a clone that uses alternates mechanism to borrow from\n> my primary repository), fsck-objects built with the patch seems\n> to report bogus things \"missing\".  I have not traced it fully;\n> instead I ended up spending most of the night (I noticed it at\n> around 01:30 and now it is 05:30 so that's about four hours)\n> recovering some of my refs and double checking if my primary\n> repository is not corrupt X-<.  At least, the primary repository\n> looks sane now.\n\nCould it be the shallow thing?\n\n+\n+void for_each_object(void (*fn)(struct object *))\n+{\n+       int i;\n+       for (i = 0; i < nr_objs; i++)\n+               fn(objs[i]);\n+}\n\nThis will not work with the hashtable. It has to be something like\n\n\nvoid for_each_object(void (*fn)(struct object *))\n{\n       int i;\n       for (i = 0; i < obj_allocs; i++)\n               if (objs[i])\n\t\t\tfn(objs[i]);\n}\n\nThis error did not trigger here, since I don't use shallow clones.\n\nAgain, sorry for the inconvenience, Junio.\n\nHth,\nDscho\n"},{"id":"15984","messageId":"7v8xsgbf4v.fsf@assigned-by-dhcp.cox.net","threadId":"3307","inReplyTo":"Pine.LNX.4.63.0602121822060.21959@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: ***DONTUSE*** Re: [PATCH] Use a hashtable for objects instead of a sorted list","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-12T18:34:08Z","receivedAt":"2006-02-12T18:34:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> Could it be the shallow thing?\n\nNo, I do not think so.  In the current \"master\", \"next\", \"pu\"\npicture, \"pu\" merges js/obj with the \"8856cc69\" commit and then\nshallow and bind comes later.  That merged version is what I am\ntesting, and also its second parent, which is \"master\" plus\nhashtable.  In either case, shallow and bind are not part of the\npicture.\n\n> Again, sorry for the inconvenience, Junio.\n\nThat is not your fault, and I did not mean to sound I am unhappy\nabout *you*.  I am indeed unhappy because I did not see anything\nobviously or subtly wrong with your patch after I moved call to\nhashtable_index() in find_object().\n\nBut I think Linus nailed it.  I'll see if I can understand his\nexplanation.\n"}]}