{"thread":{"id":"33325","subject":"[Toy PATCH] Avoid spilling collided entries in object hash table to the next slots","startedAt":"2013-03-29T14:47:49Z","lastAt":"2013-03-30T00:38:07Z","messageCount":4,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano","Duy Nguyen"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"212620","messageId":"1364568469-2250-1-git-send-email-pclouds@gmail.com","threadId":"33325","inReplyTo":null,"subject":"[Toy PATCH] Avoid spilling collided entries in object hash table to the next slots","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-29T14:47:49Z","receivedAt":"2013-03-29T14:47:49Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"If a position in object hash table is taken, we currently check out\nthe next one. This could potentially create long object chains. We\ncould create linked lists instead and leave the next slot alone.\n\nThis patch relies on the fact that pointers are usually aligned more\nthan one byte and it uses the first bit as \"object vs linked list\"\nindicator. Architectures that don't support this can fall back to\noriginal implementation.\n\nThe saving is real, although not ground breaking. I'm just not sure it\nis worth the ugliness that comes with this patch. Although we could\navoid the alignment problem by saving that bit in a separate bitmap.\n\"git rev-list --objects --all\" on linux-2.6.git:\n\n        before       after\nreal    0m33.407s    0m31.732s\nuser    0m32.926s    0m31.460s\nsys     0m0.407s     0m0.202s\n\nlookup_object() goes down from 30% to 27% in perf reports.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n object.c | 42 ++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 42 insertions(+)\n\ndiff --git a/object.c b/object.c\nindex bcfd2c6..7b013a0 100644\n--- a/object.c\n+++ b/object.c\n@@ -8,6 +8,17 @@\n static struct object **obj_hash;\n static int nr_objs, obj_hash_size;\n \n+#ifdef USE_LINKED_LIST\n+struct obj_list {\n+\tstruct object *obj;\n+\tstruct obj_list *next;\n+};\n+\n+#define IS_LST(x) ((intptr_t)(x) & 1)\n+#define MAKE_LST(x) (struct object *)((intptr_t)(x) | 1)\n+#define GET_LST(x) (struct obj_list *)((intptr_t)(x) & ~1)\n+#endif\n+\n unsigned int get_max_object_index(void)\n {\n \treturn obj_hash_size;\n@@ -53,13 +64,30 @@ static unsigned int hash_obj(struct object *obj, unsigned int n)\n static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)\n {\n \tunsigned int j = hash_obj(obj, size);\n+#ifdef USE_LINKED_LIST\n+\tstruct obj_list *lst, *o;\n+\n+\tif (!hash[j]) {\n+\t\thash[j] = obj;\n+\t\treturn;\n+\t}\n \n+\to = xmalloc(sizeof(*o));\n+\to->obj = obj;\n+\n+\tif (IS_LST(hash[j]))\n+\t\to->next = GET_LST(hash[j]);\n+\telse\n+\t\to->next = NULL;\n+\thash[j] = MAKE_LST(o);\n+#else\n \twhile (hash[j]) {\n \t\tj++;\n \t\tif (j >= size)\n \t\t\tj = 0;\n \t}\n \thash[j] = obj;\n+#endif\n }\n \n static unsigned int hashtable_index(const unsigned char *sha1)\n@@ -78,6 +106,19 @@ struct object *lookup_object(const unsigned char *sha1)\n \t\treturn NULL;\n \n \ti = hashtable_index(sha1);\n+#ifdef USE_LINKED_LIST\n+\tif (IS_LST(obj_hash[i])) {\n+\t\tstruct obj_list *lst;\n+\t\tfor (lst = GET_LST(obj_hash[i]); lst; lst = lst->next) {\n+\t\t\tif (!hashcmp(lst->obj->sha1, sha1))\n+\t\t\t\treturn lst->obj;\n+\t\t}\n+\t\treturn NULL;\n+\t} else {\n+\t\tstruct object *obj = obj_hash[i];\n+\t\treturn obj && !hashcmp(sha1, obj->sha1) ? obj : NULL;\n+\t}\n+#else\n \twhile ((obj = obj_hash[i]) != NULL) {\n \t\tif (!hashcmp(sha1, obj->sha1))\n \t\t\tbreak;\n@@ -86,6 +127,7 @@ struct object *lookup_object(const unsigned char *sha1)\n \t\t\ti = 0;\n \t}\n \treturn obj;\n+#endif\n }\n \n void grow_object_hash_to(unsigned long nr)\n-- \n1.8.2.83.gc99314b\n"},{"id":"212629","messageId":"7vd2uip1p4.fsf@alter.siamese.dyndns.org","threadId":"33325","inReplyTo":"1364568469-2250-1-git-send-email-pclouds@gmail.com","subject":"Re: [Toy PATCH] Avoid spilling collided entries in object hash table to the next slots","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-29T17:15:19Z","receivedAt":"2013-03-29T17:15:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n\n> If a position in object hash table is taken, we currently check out\n> the next one. This could potentially create long object chains. We\n> could create linked lists instead and leave the next slot alone.\n\nIn the current code, not just the logic in lookup_object(), but the\nlogic to enforce load factor when create_object() decides to call\ngrow_object_hash() and object enumeration implemented by\nget_max_object_index() and get_indexed_object() are closely tied to\nthe open addressing scheme.  If you want to switch to any other\nmethod (e.g. separate chaining) these need to be updated quite a\nbit.\n\nI do not see get_max_object_index() and get_indexed_object() updated\nat all.  Do fsck, index-pack, name-rev and upload-pack still work?\n\nThis particular implementation that uses a fake \"union\" is a bit\nugly, but in general, it may be worth rethinking the object hash\nimplementation.  I vaguely recall trying cuckoo in the vicinity of\nthis code.\n"},{"id":"212639","messageId":"7vsj3enjhx.fsf@alter.siamese.dyndns.org","threadId":"33325","inReplyTo":"7vd2uip1p4.fsf@alter.siamese.dyndns.org","subject":"Re: [Toy PATCH] Avoid spilling collided entries in object hash table to the next slots","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-29T18:33:46Z","receivedAt":"2013-03-29T18:33:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n>\n>> If a position in object hash table is taken, we currently check out\n>> the next one. This could potentially create long object chains. We\n>> could create linked lists instead and leave the next slot alone.\n>\n> In the current code, not just the logic in lookup_object(), but the\n> logic to enforce load factor when create_object() decides to call\n> grow_object_hash() and object enumeration implemented by\n> get_max_object_index() and get_indexed_object() are closely tied to\n> the open addressing scheme.  If you want to switch to any other\n> method (e.g. separate chaining) these need to be updated quite a\n> bit.\n>\n> I do not see get_max_object_index() and get_indexed_object() updated\n> at all.  Do fsck, index-pack, name-rev and upload-pack still work?\n\nYou may want to start with a bit more abstraction around the\nhashtable API.  Perhaps like this?\n\nThe idea is to let your object enumerator to be not just a simple\nunsigned int into the flat hashtable, but be something like\n\n\ttypedef struct {\n        \tunsigned int slot;\n                struct obj_list *list;\n\t} object_enumerator;\n\nYou store the current index in obj_hash[] to enu.slot, and if that\nis IS_LST(), the linked-list element you are looking at in enu.list.\nWhen you \"increment\" the iterator in object_enumerator_next(), you\nincrement enu.slot only after you reach the tail of the enu.list.\n\n\n\n builtin/fsck.c       | 17 ++++++++++-------\n builtin/index-pack.c | 11 +++++++----\n builtin/name-rev.c   | 20 +++++++++++---------\n object.c             | 22 +++++++++++++++++++---\n object.h             |  8 ++++++--\n upload-pack.c        | 23 ++++++++++++++---------\n 6 files changed, 67 insertions(+), 34 deletions(-)\n\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex bb9a2cd..5688cad 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -270,22 +270,25 @@ static void check_object(struct object *obj)\n \n static void check_connectivity(void)\n {\n-\tint i, max;\n+\tint max;\n+\tobject_enumerator enu;\n \n \t/* Traverse the pending reachable objects */\n \ttraverse_reachable();\n \n \t/* Look up all the requirements, warn about missing objects.. */\n-\tmax = get_max_object_index();\n+\tmax = begin_object_enumeration(&enu);\n \tif (verbose)\n \t\tfprintf(stderr, \"Checking connectivity (%d objects)\\n\", max);\n \n-\tfor (i = 0; i < max; i++) {\n-\t\tstruct object *obj = get_indexed_object(i);\n-\n-\t\tif (obj)\n-\t\t\tcheck_object(obj);\n+\tif (max) {\n+\t\tdo {\n+\t\t\tstruct object *obj = get_enumerated_object(&enu);\n+\t\t\tif (obj)\n+\t\t\t\tcheck_object(obj);\n+\t\t} while (object_enumeration_next(&enu));\n \t}\n+\tend_object_enumeration(&enu);\n }\n \n static int fsck_obj(struct object *obj)\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex ef62124..1d5b65c 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -195,11 +195,14 @@ static void check_object(struct object *obj)\n \n static void check_objects(void)\n {\n-\tunsigned i, max;\n+\tobject_enumerator enu;\n \n-\tmax = get_max_object_index();\n-\tfor (i = 0; i < max; i++)\n-\t\tcheck_object(get_indexed_object(i));\n+\tif (begin_object_enumeration(&enu)) {\n+\t\tdo {\n+\t\t\tcheck_object(get_enumerated_object(&enu));\n+\t\t} while (object_enumeration_next(&enu));\n+\t}\n+\tend_object_enumeration(&enu);\n }\n \n \ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 6238247..239c3ef 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -286,16 +286,18 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\t\tname_rev_line(p, &data);\n \t\t}\n \t} else if (all) {\n-\t\tint i, max;\n-\n-\t\tmax = get_max_object_index();\n-\t\tfor (i = 0; i < max; i++) {\n-\t\t\tstruct object *obj = get_indexed_object(i);\n-\t\t\tif (!obj || obj->type != OBJ_COMMIT)\n-\t\t\t\tcontinue;\n-\t\t\tshow_name(obj, NULL,\n-\t\t\t\t  always, allow_undefined, data.name_only);\n+\t\tobject_enumerator enu;\n+\n+\t\tif (begin_object_enumeration(&enu)) {\n+\t\t\tdo {\n+\t\t\t\tstruct object *obj = get_enumerated_object(&enu);\n+\t\t\t\tif (!obj || obj->type != OBJ_COMMIT)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tshow_name(obj, NULL,\n+\t\t\t\t\t  always, allow_undefined, data.name_only);\n+\t\t\t} while (object_enumeration_next(&enu));\n \t\t}\n+\t\tend_object_enumeration(&enu);\n \t} else {\n \t\tint i;\n \t\tfor (i = 0; i < revs.nr; i++)\ndiff --git a/object.c b/object.c\nindex 20703f5..f5b754f 100644\n--- a/object.c\n+++ b/object.c\n@@ -8,14 +8,30 @@\n static struct object **obj_hash;\n static int nr_objs, obj_hash_size;\n \n-unsigned int get_max_object_index(void)\n+unsigned int begin_object_enumeration(object_enumerator *enu)\n {\n+\t*enu = 0;\n \treturn obj_hash_size;\n }\n \n-struct object *get_indexed_object(unsigned int idx)\n+struct object *get_enumerated_object(object_enumerator *enu)\n {\n-\treturn obj_hash[idx];\n+\tint ix = *enu;\n+\n+\tif (obj_hash_size <= ix)\n+\t\tdie(\"BUG: get_enumerated_object() called beyond the end\");\n+\treturn obj_hash[*enu];\n+}\n+\n+int object_enumeration_next(object_enumerator *enu)\n+{\n+\treturn ++*enu < obj_hash_size;\n+}\n+\n+void end_object_enumeration(object_enumerator *enu)\n+{\n+\t/* Nothing to free (yet) */\n+\t;\n }\n \n static const char *object_type_strings[] = {\ndiff --git a/object.h b/object.h\nindex 97d384b..5435d58 100644\n--- a/object.h\n+++ b/object.h\n@@ -35,8 +35,12 @@ struct object {\n extern const char *typename(unsigned int type);\n extern int type_from_string(const char *str);\n \n-extern unsigned int get_max_object_index(void);\n-extern struct object *get_indexed_object(unsigned int);\n+typedef unsigned int object_enumerator;\n+\n+extern unsigned int begin_object_enumeration(object_enumerator *);\n+extern struct object *get_enumerated_object(object_enumerator *);\n+extern int object_enumeration_next(object_enumerator *);\n+extern void end_object_enumeration(object_enumerator *);\n \n /*\n  * This can be used to see if we have heard of the object before, but\ndiff --git a/upload-pack.c b/upload-pack.c\nindex f5673ee..618b211 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -502,6 +502,7 @@ static void check_non_tip(void)\n \tstruct object *o;\n \tchar namebuf[42]; /* ^ + SHA-1 + LF */\n \tint i;\n+\tobject_enumerator enu;\n \n \t/* In the normal in-process case non-tip request can never happen */\n \tif (!stateless_rpc)\n@@ -525,16 +526,20 @@ static void check_non_tip(void)\n \n \tnamebuf[0] = '^';\n \tnamebuf[41] = '\\n';\n-\tfor (i = get_max_object_index(); 0 < i; ) {\n-\t\to = get_indexed_object(--i);\n-\t\tif (!o)\n-\t\t\tcontinue;\n-\t\tif (!is_our_ref(o))\n-\t\t\tcontinue;\n-\t\tmemcpy(namebuf + 1, sha1_to_hex(o->sha1), 40);\n-\t\tif (write_in_full(cmd.in, namebuf, 42) < 0)\n-\t\t\tgoto error;\n+\n+\tif (begin_object_enumeration(&enu)) {\n+\t\tdo {\n+\t\t\to = get_enumerated_object(&enu);\n+\t\t\tif (!o)\n+\t\t\t\tcontinue;\n+\t\t\tif (!is_our_ref(o))\n+\t\t\t\tcontinue;\n+\t\t\tmemcpy(namebuf + 1, sha1_to_hex(o->sha1), 40);\n+\t\t\tif (write_in_full(cmd.in, namebuf, 42) < 0)\n+\t\t\t\tgoto error;\n+\t\t} while (object_enumeration_next(&enu));\n \t}\n+\tend_object_enumeration(&enu);\n \tnamebuf[40] = '\\n';\n \tfor (i = 0; i < want_obj.nr; i++) {\n \t\to = want_obj.objects[i].item;\n"},{"id":"212667","messageId":"CACsJy8Atw3wBCboXsS2MTj80T91A5zDXdXBjgJnmZx8G67O4xQ@mail.gmail.com","threadId":"33325","inReplyTo":"7vd2uip1p4.fsf@alter.siamese.dyndns.org","subject":"Re: [Toy PATCH] Avoid spilling collided entries in object hash table to the next slots","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-30T00:38:07Z","receivedAt":"2013-03-30T00:38:07Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Mar 30, 2013 at 12:15 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n>\n>> If a position in object hash table is taken, we currently check out\n>> the next one. This could potentially create long object chains. We\n>> could create linked lists instead and leave the next slot alone.\n>\n> In the current code, not just the logic in lookup_object(), but the\n> logic to enforce load factor when create_object() decides to call\n> grow_object_hash() and object enumeration implemented by\n> get_max_object_index() and get_indexed_object() are closely tied to\n> the open addressing scheme.  If you want to switch to any other\n> method (e.g. separate chaining) these need to be updated quite a\n> bit.\n>\n> I do not see get_max_object_index() and get_indexed_object() updated\n> at all.  Do fsck, index-pack, name-rev and upload-pack still work?\n\nNo, apparently not. I should have been hit hard by not updating\ngrow_object_hash(). But I think it was ok because I was on top of my\npreallocation patch and there probably were not many chains before\nthat patch kicked in.\n\n> This particular implementation that uses a fake \"union\" is a bit\n> ugly, but in general, it may be worth rethinking the object hash\n> implementation.  I vaguely recall trying cuckoo in the vicinity of\n> this code.\n\nYeah I saw that. Need to read and maybe try again some time. Still\nplaying with the linked list idea. If every time we find something in\na chain, we swap it to top (with hope it'll be accessed more often),\nthen the number of traversing in chains goes down from 33m times to\n21.5m times. If we just push it up one node in the linked list, it's\n21.3m times. Interesting.\n--\nDuy\n"}]}