{"thread":{"id":"28071","subject":"[PATCH 00/11] Micro-optimizing lookup_object()","startedAt":"2011-08-11T17:53:05Z","lastAt":"2011-08-15T23:19:00Z","messageCount":15,"participants":["Junio C Hamano","Thomas Rast"],"isPatch":true,"patchVersion":1,"patchTotal":11},"messages":[{"id":"173288","messageId":"1313085196-13249-1-git-send-email-gitster@pobox.com","threadId":"28071","inReplyTo":null,"subject":"[PATCH 00/11] Micro-optimizing lookup_object()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-11T17:53:05Z","receivedAt":"2011-08-11T17:53:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I noticed that a typical \"git repack -a -d -f\" spends about 50% of the\ntime during the \"Counting objects\" phase inside lookup_object(). The\nlook-up is implemented as a hashtable with linear probing that limits the\nmaximum load-factor to 50%, and during repacking the Linux kernel\nrepository, we count 2,139,209 objects, and the worst case we probe 50\nhash entries to find a single object in the hash table due to slot\ncollisions. The lookup_object() function is called 88,603,392 times.\n\nAfter cleaning up the existing code a bit, this series adds \"--count-only\"\noption to \"pack-objects\" to tell it to stop after the \"Counting objects\"\nphase for benchmarking purposes. To emulate the \"Counting objects\" phase\nof a full repack, we can run this (perhaps under \"/usr/bin/time\"):\n\n  git pack-objects --count-only --keep-true-parents --honor-pack-keep \\\n      --non-empty --all --reflog --no-reuse-delta \\\n      --delta-base-offset --stdout </dev/null >/dev/null\n\nOn my development box, the slightly cleaned-up existing linear probing\ncode gives (best of three runs with hot cache):\n\n  31.89user 2.16system 0:34.16elapsed 99%CPU (0avgtext+0avgdata 2965264maxresident)k\n  0inputs+0outputs (0major+225336minor)pagefaults 0swaps\n\nThen the series replaces lookup_object(), insert_obj_hash() and\ngrow_object_hash() with a naive implementation of cuckoo hashing that uses\ntwo hash functions. The performance is not very impressive, and this wastes\ntoo much memory, due to its rather poor strategy to re-grow the table size:\n\n  32.04user 3.43system 0:35.58elapsed 99%CPU (0avgtext+0avgdata 8178672maxresident)k\n  0inputs+0outputs (0major+1206546minor)pagefaults 0swaps\n\nAs we have 20-byte object names as the hash key material, we could easily\nextend this to use 5 hash functions instead of 2. This reduces the memory\nusage by improving the load factor, but we spend extra cycles in lookup:\n\n  31.66user 2.14system 0:33.91elapsed 99%CPU (0avgtext+0avgdata 2874176maxresident)k\n  0inputs+0outputs (0major+225342minor)pagefaults 0swaps\n\nAt this step with 5-way cuckoo, we are slightly better than the original\nlinear probing. By using smaller number of hash functions, we can reduce\nthe cycles we need in lookup, while we lose on the load factor.\n\nHere is what we get from the code with 4 hashes:\n\n  30.88user 2.32system 0:33.31elapsed 99%CPU (0avgtext+0avgdata 3135984maxresident)k\n  0inputs+0outputs (0major+290857minor)pagefaults 0swaps\n\nAnd here is with 3 hashes:\n\n  30.68user 2.26system 0:33.05elapsed 99%CPU (0avgtext+0avgdata 3660832maxresident)k\n  0inputs+0outputs (0major+421963minor)pagefaults 0swaps\n\nThe best balance is somewhere between 3-hash and 4-hash, it seems. We are\ngetting ~4% runtime performance improvements (31.89 vs 30.68).\n\nJust as a sanity check, the final patch in the series reduces the number\nof hashes back to 2, which yields a similar performance characteristics\nfrom the original \"naive\" cuckoo implementation:\n\n  31.06user 3.22system 0:34.39elapsed 99%CPU (0avgtext+0avgdata 8176512maxresident)k\n  0inputs+0outputs (0major+1206542minor)pagefaults 0swaps\n\nThe real optimization opportunity _may_ be to reduce the calls we make to\nthe function---we are calling lookup() 40+ times on one object. But that\nis outside the scope of this series.\n\nThis series is not for application but primarily is to serve as the\nsupplimental data for the above numbers. A re-rolled series that consists\nof the earlier clean-ups and then a patch to replace the linear probing\nwith 4-way cuckoo will be queued instead in 'pu'.\n\nJunio C Hamano (11):\n  object.c: code movement for readability\n  object.c: remove duplicated code for object hashing\n  pack-objects --count-only\n  object: next_size() helper for readability\n  object hash: we know the table size is a power of two\n  object: growing the hash-table more aggressively does not help much\n  object: try naive cuckoo hashing\n  object: try 5-way cuckoo -- use all 20-bytes of SHA-1\n  object: try 4-way cuckoo\n  object: try 3-way cuckoo\n  object: try 2-way cuckoo again\n\n builtin/pack-objects.c |    7 +++\n object.c               |  138 +++++++++++++++++++++++++++++-------------------\n 2 files changed, 91 insertions(+), 54 deletions(-)\n\n-- \n1.7.6.433.g1421f\n"},{"id":"173289","messageId":"1313085196-13249-2-git-send-email-gitster@pobox.com","threadId":"28071","inReplyTo":"1313085196-13249-1-git-send-email-gitster@pobox.com","subject":"[PATCH 01/11] object.c: code movement for readability","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-11T17:53:06Z","receivedAt":"2011-08-11T17:53:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This only moves the lines around a bit to gather the definitions of code\nand data that manage the hash function and the object hash table into one\nplace (examine \"blame -M\" output to see nothing new is introduced).\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n object.c |   40 ++++++++++++++++++++--------------------\n 1 files changed, 20 insertions(+), 20 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex 31976b5..35ff130 100644\n--- a/object.c\n+++ b/object.c\n@@ -5,19 +5,6 @@\n #include \"commit.h\"\n #include \"tag.h\"\n \n-static struct object **obj_hash;\n-static int nr_objs, obj_hash_size;\n-\n-unsigned int get_max_object_index(void)\n-{\n-\treturn obj_hash_size;\n-}\n-\n-struct object *get_indexed_object(unsigned int idx)\n-{\n-\treturn obj_hash[idx];\n-}\n-\n static const char *object_type_strings[] = {\n \tNULL,\t\t/* OBJ_NONE = 0 */\n \t\"commit\",\t/* OBJ_COMMIT = 1 */\n@@ -43,6 +30,19 @@ int type_from_string(const char *str)\n \tdie(\"invalid object type \\\"%s\\\"\", str);\n }\n \n+static struct object **obj_hash;\n+static int nr_objs, obj_hash_size;\n+\n+unsigned int get_max_object_index(void)\n+{\n+\treturn obj_hash_size;\n+}\n+\n+struct object *get_indexed_object(unsigned int idx)\n+{\n+\treturn obj_hash[idx];\n+}\n+\n static unsigned int hash_obj(struct object *obj, unsigned int n)\n {\n \tunsigned int hash;\n@@ -50,6 +50,13 @@ static unsigned int hash_obj(struct object *obj, unsigned int n)\n \treturn hash % n;\n }\n \n+static unsigned int hashtable_index(const unsigned char *sha1)\n+{\n+\tunsigned int i;\n+\tmemcpy(&i, sha1, sizeof(unsigned int));\n+\treturn i % obj_hash_size;\n+}\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@@ -62,13 +69,6 @@ static void insert_obj_hash(struct object *obj, struct object **hash, unsigned i\n \thash[j] = obj;\n }\n \n-static unsigned int hashtable_index(const unsigned char *sha1)\n-{\n-\tunsigned int i;\n-\tmemcpy(&i, sha1, sizeof(unsigned int));\n-\treturn i % obj_hash_size;\n-}\n-\n struct object *lookup_object(const unsigned char *sha1)\n {\n \tunsigned int i;\n-- \n1.7.6.433.g1421f\n"},{"id":"173290","messageId":"1313085196-13249-3-git-send-email-gitster@pobox.com","threadId":"28071","inReplyTo":"1313085196-13249-1-git-send-email-gitster@pobox.com","subject":"[PATCH 02/11] object.c: remove duplicated code for object hashing","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-11T17:53:07Z","receivedAt":"2011-08-11T17:53:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The index into object hash was computed in two different places,\nrisking them to diverge. Implement a single helper function and\nuse it in these two locations.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n object.c |   17 +++++------------\n 1 files changed, 5 insertions(+), 12 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex 35ff130..4ff2d7d 100644\n--- a/object.c\n+++ b/object.c\n@@ -43,23 +43,16 @@ struct object *get_indexed_object(unsigned int idx)\n \treturn obj_hash[idx];\n }\n \n-static unsigned int hash_obj(struct object *obj, unsigned int n)\n+static unsigned int hash_val(const unsigned char *sha1)\n {\n \tunsigned int hash;\n-\tmemcpy(&hash, obj->sha1, sizeof(unsigned int));\n-\treturn hash % n;\n-}\n-\n-static unsigned int hashtable_index(const unsigned char *sha1)\n-{\n-\tunsigned int i;\n-\tmemcpy(&i, sha1, sizeof(unsigned int));\n-\treturn i % obj_hash_size;\n+\tmemcpy(&hash, sha1, sizeof(unsigned int));\n+\treturn hash;\n }\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+\tunsigned int j = hash_val(obj->sha1) % size;\n \n \twhile (hash[j]) {\n \t\tj++;\n@@ -77,7 +70,7 @@ struct object *lookup_object(const unsigned char *sha1)\n \tif (!obj_hash)\n \t\treturn NULL;\n \n-\ti = hashtable_index(sha1);\n+\ti = hash_val(sha1) % obj_hash_size;\n \twhile ((obj = obj_hash[i]) != NULL) {\n \t\tif (!hashcmp(sha1, obj->sha1))\n \t\t\tbreak;\n-- \n1.7.6.433.g1421f\n"},{"id":"173298","messageId":"1313085196-13249-4-git-send-email-gitster@pobox.com","threadId":"28071","inReplyTo":"1313085196-13249-1-git-send-email-gitster@pobox.com","subject":"[PATCH 03/11] pack-objects --count-only","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-11T17:53:08Z","receivedAt":"2011-08-11T17:53:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This is merely to help debugging the bottleneck of \"Counting objects\"\nphase of the pack-objects process.  Use it like this:\n\ngit pack-objects --count-only --keep-true-parents --honor-pack-keep \\\n\t--non-empty --all --reflog --no-reuse-delta \\\n\t--delta-base-offset --stdout </dev/null >/dev/null\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n builtin/pack-objects.c |    7 +++++++\n 1 files changed, 7 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex f402a84..6a208a9 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -2121,6 +2121,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tint use_internal_rev_list = 0;\n \tint thin = 0;\n \tint all_progress_implied = 0;\n+\tint count_only = 0;\n \tuint32_t i;\n \tconst char **rp_av;\n \tint rp_ac_alloc = 64;\n@@ -2291,6 +2292,10 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\t\tgrafts_replace_parents = 0;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(\"--count-only\", arg)) {\n+\t\t\tcount_only = 1;\n+\t\t\tcontinue;\n+\t\t}\n \t\tusage(pack_usage);\n \t}\n \n@@ -2348,6 +2353,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \n \tif (non_empty && !nr_result)\n \t\treturn 0;\n+\tif (count_only)\n+\t\treturn 0;\n \tif (nr_result)\n \t\tprepare_pack(window, depth);\n \twrite_pack_file();\n-- \n1.7.6.433.g1421f\n"},{"id":"173291","messageId":"1313085196-13249-5-git-send-email-gitster@pobox.com","threadId":"28071","inReplyTo":"1313085196-13249-1-git-send-email-gitster@pobox.com","subject":"[PATCH 04/11] object: next_size() helper for readability","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-11T17:53:09Z","receivedAt":"2011-08-11T17:53:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Move the heuristics to grow the table size into a separate\nhelper function to make the caller more readable.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n object.c |    7 ++++++-\n 1 files changed, 6 insertions(+), 1 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex 4ff2d7d..259a67e 100644\n--- a/object.c\n+++ b/object.c\n@@ -81,10 +81,15 @@ struct object *lookup_object(const unsigned char *sha1)\n \treturn obj;\n }\n \n+static int next_size(int sz)\n+{\n+\treturn sz < 32 ? 32 : 2 * sz;\n+}\n+\n 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+\tint new_hash_size = next_size(obj_hash_size);\n \tstruct object **new_hash;\n \n \tnew_hash = xcalloc(new_hash_size, sizeof(struct object *));\n-- \n1.7.6.433.g1421f\n"},{"id":"173296","messageId":"1313085196-13249-6-git-send-email-gitster@pobox.com","threadId":"28071","inReplyTo":"1313085196-13249-1-git-send-email-gitster@pobox.com","subject":"[PATCH 05/11] object hash: we know the table size is a power of two","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-11T17:53:10Z","receivedAt":"2011-08-11T17:53:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Signed-off-by: Junio C Hamano <gitster@pobox.com>\n---\n object.c |    4 ++--\n 1 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex 259a67e..d95d7a6 100644\n--- a/object.c\n+++ b/object.c\n@@ -52,7 +52,7 @@ static unsigned int hash_val(const unsigned char *sha1)\n \n static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)\n {\n-\tunsigned int j = hash_val(obj->sha1) % size;\n+\tunsigned int j = hash_val(obj->sha1) & (size-1);\n \n \twhile (hash[j]) {\n \t\tj++;\n@@ -70,7 +70,7 @@ struct object *lookup_object(const unsigned char *sha1)\n \tif (!obj_hash)\n \t\treturn NULL;\n \n-\ti = hash_val(sha1) % obj_hash_size;\n+\ti = hash_val(sha1) & (obj_hash_size-1);\n \twhile ((obj = obj_hash[i]) != NULL) {\n \t\tif (!hashcmp(sha1, obj->sha1))\n \t\t\tbreak;\n-- \n1.7.6.433.g1421f\n"},{"id":"173295","messageId":"1313085196-13249-7-git-send-email-gitster@pobox.com","threadId":"28071","inReplyTo":"1313085196-13249-1-git-send-email-gitster@pobox.com","subject":"[PATCH 06/11] object: growing the hash-table more aggressively does not help much","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-11T17:53:11Z","receivedAt":"2011-08-11T17:53:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Signed-off-by: Junio C Hamano <gitster@pobox.com>\n---\n../+v/2555c0d98970098861c97b7746f2b8846c823e6f/git-pack-objects\nCounting objects: 2139209, done.\n32.07user 1.96system 0:34.15elapsed 99%CPU (0avgtext+0avgdata 2966176maxresident)k\n0inputs+0outputs (0major+225410minor)pagefaults 0swaps\nCounting objects: 2139209, done.\n31.89user 2.16system 0:34.16elapsed 99%CPU (0avgtext+0avgdata 2965264maxresident)k\n0inputs+0outputs (0major+225336minor)pagefaults 0swaps\nCounting objects: 2139209, done.\n32.01user 2.12system 0:34.23elapsed 99%CPU (0avgtext+0avgdata 2964832maxresident)k\n0inputs+0outputs (0major+225332minor)pagefaults 0swaps\n---\n object.c |    3 ++-\n 1 files changed, 2 insertions(+), 1 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex d95d7a6..c2c0a7d 100644\n--- a/object.c\n+++ b/object.c\n@@ -83,7 +83,8 @@ struct object *lookup_object(const unsigned char *sha1)\n \n static int next_size(int sz)\n {\n-\treturn sz < 32 ? 32 : 2 * sz;\n+\treturn (sz < 32 ? 32 :\n+\t\t(sz < 1024 * 1024 ? 8 : 2) * sz);\n }\n \n static void grow_object_hash(void)\n-- \n1.7.6.433.g1421f\n"},{"id":"173292","messageId":"1313085196-13249-8-git-send-email-gitster@pobox.com","threadId":"28071","inReplyTo":"1313085196-13249-1-git-send-email-gitster@pobox.com","subject":"[PATCH 07/11] object: try naive cuckoo hashing","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-11T17:53:12Z","receivedAt":"2011-08-11T17:53:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Signed-off-by: Junio C Hamano <gitster@pobox.com>\n\n---\n../+v/65c71a61547aecd8a6830391fda31ed5d18e0529/git-pack-objects\nCounting objects: 2139209, done.\n32.04user 3.43system 0:35.58elapsed 99%CPU (0avgtext+0avgdata 8178672maxresident)k\n0inputs+0outputs (0major+1206546minor)pagefaults 0swaps\nCounting objects: 2139209, done.\n33.41user 3.15system 0:36.67elapsed 99%CPU (0avgtext+0avgdata 8178688maxresident)k\n0inputs+0outputs (0major+1206547minor)pagefaults 0swaps\nCounting objects: 2139209, done.\n32.24user 3.17system 0:35.51elapsed 99%CPU (0avgtext+0avgdata 8179968maxresident)k\n0inputs+0outputs (0major+1206598minor)pagefaults 0swaps\n---\n object.c |   99 ++++++++++++++++++++++++++++++++++++++++++--------------------\n 1 files changed, 67 insertions(+), 32 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex c2c0a7d..7624c48 100644\n--- a/object.c\n+++ b/object.c\n@@ -50,33 +50,52 @@ static unsigned int hash_val(const unsigned char *sha1)\n \treturn hash;\n }\n \n-static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)\n-{\n-\tunsigned int j = hash_val(obj->sha1) & (size-1);\n \n-\twhile (hash[j]) {\n-\t\tj++;\n-\t\tif (j >= size)\n-\t\t\tj = 0;\n-\t}\n-\thash[j] = obj;\n-}\n+#define H1(sha1) (hash_val(sha1) % obj_hash_size)\n+#define H2(sha1) (hash_val((sha1) + sizeof(unsigned int)) % obj_hash_size)\n \n struct object *lookup_object(const unsigned char *sha1)\n {\n-\tunsigned int i;\n \tstruct object *obj;\n \n \tif (!obj_hash)\n \t\treturn NULL;\n \n-\ti = hash_val(sha1) & (obj_hash_size-1);\n-\twhile ((obj = obj_hash[i]) != NULL) {\n-\t\tif (!hashcmp(sha1, obj->sha1))\n-\t\t\tbreak;\n-\t\ti++;\n-\t\tif (i == obj_hash_size)\n-\t\t\ti = 0;\n+\tif ((obj = obj_hash[H1(sha1)]) && !hashcmp(sha1, obj->sha1))\n+\t\treturn obj;\n+\tif ((obj = obj_hash[H2(sha1)]) && !hashcmp(sha1, obj->sha1))\n+\t\treturn obj;\n+\treturn NULL;\n+}\n+\n+static void grow_object_hash(void); /* forward */\n+\n+/*\n+ * A naive single-table cuckoo hashing implementation.\n+ * Return NULL when \"obj\" is successfully inserted. Otherwise\n+ * return a pointer to the object to be inserted (which may\n+ * be different from the original obj). The caller is expected\n+ * to grow the hash table and re-insert the returned object.\n+ */\n+static struct object *insert_obj_hash(struct object *obj)\n+{\n+\tint loop;\n+\n+\tfor (loop = obj_hash_size / 2; 0 <= loop; loop--) {\n+\t\tstruct object *tmp_obj;\n+\t\tunsigned int ix;\n+\n+\t\tix = H1(obj->sha1);\n+\t\tif (!obj_hash[ix]) {\n+\t\t\tobj_hash[ix] = obj;\n+\t\t\treturn NULL;\n+\t\t}\n+\t\tix = H2(obj->sha1);\n+\t\ttmp_obj = obj_hash[ix];\n+\t\tobj_hash[ix] = obj;\n+\t\tif (!tmp_obj)\n+\t\t\treturn NULL;\n+\t\tobj = tmp_obj;\n \t}\n \treturn obj;\n }\n@@ -89,25 +108,36 @@ static int next_size(int sz)\n \n static void grow_object_hash(void)\n {\n-\tint i;\n-\tint new_hash_size = next_size(obj_hash_size);\n-\tstruct object **new_hash;\n-\n-\tnew_hash = xcalloc(new_hash_size, sizeof(struct object *));\n-\tfor (i = 0; i < obj_hash_size; i++) {\n-\t\tstruct object *obj = obj_hash[i];\n-\t\tif (!obj)\n+\tstruct object **current_hash;\n+\tint current_size;\n+\n+\tcurrent_hash = obj_hash;\n+\tcurrent_size = obj_hash_size;\n+\twhile (1) {\n+\t\tint i;\n+\t\tobj_hash_size = next_size(obj_hash_size);\n+\t\tobj_hash = xcalloc(obj_hash_size, sizeof(struct object *));\n+\n+\t\tfor (i = 0; i < current_size; i++) {\n+\t\t\tif (!current_hash[i])\n+\t\t\t\tcontinue;\n+\t\t\tif (insert_obj_hash(current_hash[i]))\n+\t\t\t\tbreak;\n+\t\t}\n+\t\tif (i < current_size) {\n+\t\t\t/* too small - grow and retry */\n+\t\t\tfree(obj_hash);\n \t\t\tcontinue;\n-\t\tinsert_obj_hash(obj, new_hash, new_hash_size);\n+\t\t}\n+\t\tfree(current_hash);\n+\t\treturn;\n \t}\n-\tfree(obj_hash);\n-\tobj_hash = new_hash;\n-\tobj_hash_size = new_hash_size;\n }\n \n void *create_object(const unsigned char *sha1, int type, void *o)\n {\n \tstruct object *obj = o;\n+\tstruct object *to_insert;\n \n \tobj->parsed = 0;\n \tobj->used = 0;\n@@ -117,8 +147,13 @@ void *create_object(const unsigned char *sha1, int type, void *o)\n \n \tif (obj_hash_size - 1 <= nr_objs * 2)\n \t\tgrow_object_hash();\n-\n-\tinsert_obj_hash(obj, obj_hash, obj_hash_size);\n+\tto_insert = obj;\n+\twhile (1) {\n+\t\tto_insert = insert_obj_hash(to_insert);\n+\t\tif (!to_insert)\n+\t\t\tbreak;\n+\t\tgrow_object_hash();\n+\t}\n \tnr_objs++;\n \treturn obj;\n }\n-- \n1.7.6.433.g1421f\n"},{"id":"173293","messageId":"1313085196-13249-9-git-send-email-gitster@pobox.com","threadId":"28071","inReplyTo":"1313085196-13249-1-git-send-email-gitster@pobox.com","subject":"[PATCH 08/11] object: try 5-way cuckoo -- use all 20-bytes of SHA-1","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-11T17:53:13Z","receivedAt":"2011-08-11T17:53:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Signed-off-by: Junio C Hamano <gitster@pobox.com>\n---\n../+v/ced878c983ddc9a256b22535aa8af006529ec3d0/git-pack-objects\nCounting objects: 2139209, done.\n31.66user 2.14system 0:33.91elapsed 99%CPU (0avgtext+0avgdata 2874176maxresident)k\n0inputs+0outputs (0major+225342minor)pagefaults 0swaps\nCounting objects: 2139209, done.\n31.79user 2.03system 0:33.93elapsed 99%CPU (0avgtext+0avgdata 2875808maxresident)k\n0inputs+0outputs (0major+225444minor)pagefaults 0swaps\nCounting objects: 2139209, done.\n31.80user 1.94system 0:33.84elapsed 99%CPU (0avgtext+0avgdata 2875792maxresident)k\n0inputs+0outputs (0major+225443minor)pagefaults 0swaps\n---\n object.c |   43 ++++++++++++++++++++++++++++++-------------\n 1 files changed, 30 insertions(+), 13 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex 7624c48..c777520 100644\n--- a/object.c\n+++ b/object.c\n@@ -43,27 +43,27 @@ struct object *get_indexed_object(unsigned int idx)\n \treturn obj_hash[idx];\n }\n \n-static unsigned int hash_val(const unsigned char *sha1)\n-{\n-\tunsigned int hash;\n-\tmemcpy(&hash, sha1, sizeof(unsigned int));\n-\treturn hash;\n-}\n-\n \n-#define H1(sha1) (hash_val(sha1) % obj_hash_size)\n-#define H2(sha1) (hash_val((sha1) + sizeof(unsigned int)) % obj_hash_size)\n+#define H(hv,ix) ((hv[ix]) & (obj_hash_size-1))\n \n struct object *lookup_object(const unsigned char *sha1)\n {\n \tstruct object *obj;\n+\tunsigned int hashval[5];\n \n \tif (!obj_hash)\n \t\treturn NULL;\n \n-\tif ((obj = obj_hash[H1(sha1)]) && !hashcmp(sha1, obj->sha1))\n+\tmemcpy(hashval, sha1, 20);\n+\tif ((obj = obj_hash[H(hashval, 0)]) && !hashcmp(sha1, obj->sha1))\n+\t\treturn obj;\n+\tif ((obj = obj_hash[H(hashval, 1)]) && !hashcmp(sha1, obj->sha1))\n+\t\treturn obj;\n+\tif ((obj = obj_hash[H(hashval, 2)]) && !hashcmp(sha1, obj->sha1))\n \t\treturn obj;\n-\tif ((obj = obj_hash[H2(sha1)]) && !hashcmp(sha1, obj->sha1))\n+\tif ((obj = obj_hash[H(hashval, 3)]) && !hashcmp(sha1, obj->sha1))\n+\t\treturn obj;\n+\tif ((obj = obj_hash[H(hashval, 4)]) && !hashcmp(sha1, obj->sha1))\n \t\treturn obj;\n \treturn NULL;\n }\n@@ -84,13 +84,30 @@ static struct object *insert_obj_hash(struct object *obj)\n \tfor (loop = obj_hash_size / 2; 0 <= loop; loop--) {\n \t\tstruct object *tmp_obj;\n \t\tunsigned int ix;\n+\t\tunsigned int hashval[5];\n \n-\t\tix = H1(obj->sha1);\n+\t\tmemcpy(hashval, obj->sha1, 20);\n+\t\tix = H(hashval, 0);\n+\t\tif (!obj_hash[ix]) {\n+\t\t\tobj_hash[ix] = obj;\n+\t\t\treturn NULL;\n+\t\t}\n+\t\tix = H(hashval, 1);\n+\t\tif (!obj_hash[ix]) {\n+\t\t\tobj_hash[ix] = obj;\n+\t\t\treturn NULL;\n+\t\t}\n+\t\tix = H(hashval, 2);\n+\t\tif (!obj_hash[ix]) {\n+\t\t\tobj_hash[ix] = obj;\n+\t\t\treturn NULL;\n+\t\t}\n+\t\tix = H(hashval, 3);\n \t\tif (!obj_hash[ix]) {\n \t\t\tobj_hash[ix] = obj;\n \t\t\treturn NULL;\n \t\t}\n-\t\tix = H2(obj->sha1);\n+\t\tix = H(hashval, 4);\n \t\ttmp_obj = obj_hash[ix];\n \t\tobj_hash[ix] = obj;\n \t\tif (!tmp_obj)\n-- \n1.7.6.433.g1421f\n"},{"id":"173299","messageId":"1313085196-13249-10-git-send-email-gitster@pobox.com","threadId":"28071","inReplyTo":"1313085196-13249-1-git-send-email-gitster@pobox.com","subject":"[PATCH 09/11] object: try 4-way cuckoo","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-11T17:53:14Z","receivedAt":"2011-08-11T17:53:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The more we probe alternative slots, the more expensive average\nlook-up gets, while it helps reduce the load factor of the hash\ntable.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n../+v/6bb99816f5676ed5ddb6922363b7470a7e8c61f7/git-pack-objects\nCounting objects: 2139209, done.\n31.09user 2.05system 0:33.25elapsed 99%CPU (0avgtext+0avgdata 3135840maxresident)k\n0inputs+0outputs (0major+290849minor)pagefaults 0swaps\nCounting objects: 2139209, done.\n31.12user 2.14system 0:33.37elapsed 99%CPU (0avgtext+0avgdata 3136128maxresident)k\n0inputs+0outputs (0major+290866minor)pagefaults 0swaps\nCounting objects: 2139209, done.\n31.17user 2.01system 0:33.29elapsed 99%CPU (0avgtext+0avgdata 3136512maxresident)k\n0inputs+0outputs (0major+290890minor)pagefaults 0swaps\n---\n object.c |   15 ++++-----------\n 1 files changed, 4 insertions(+), 11 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex c777520..caced56 100644\n--- a/object.c\n+++ b/object.c\n@@ -49,12 +49,12 @@ struct object *get_indexed_object(unsigned int idx)\n struct object *lookup_object(const unsigned char *sha1)\n {\n \tstruct object *obj;\n-\tunsigned int hashval[5];\n+\tunsigned int hashval[4];\n \n \tif (!obj_hash)\n \t\treturn NULL;\n \n-\tmemcpy(hashval, sha1, 20);\n+\tmemcpy(hashval, sha1, 16);\n \tif ((obj = obj_hash[H(hashval, 0)]) && !hashcmp(sha1, obj->sha1))\n \t\treturn obj;\n \tif ((obj = obj_hash[H(hashval, 1)]) && !hashcmp(sha1, obj->sha1))\n@@ -63,8 +63,6 @@ struct object *lookup_object(const unsigned char *sha1)\n \t\treturn obj;\n \tif ((obj = obj_hash[H(hashval, 3)]) && !hashcmp(sha1, obj->sha1))\n \t\treturn obj;\n-\tif ((obj = obj_hash[H(hashval, 4)]) && !hashcmp(sha1, obj->sha1))\n-\t\treturn obj;\n \treturn NULL;\n }\n \n@@ -84,9 +82,9 @@ static struct object *insert_obj_hash(struct object *obj)\n \tfor (loop = obj_hash_size / 2; 0 <= loop; loop--) {\n \t\tstruct object *tmp_obj;\n \t\tunsigned int ix;\n-\t\tunsigned int hashval[5];\n+\t\tunsigned int hashval[4];\n \n-\t\tmemcpy(hashval, obj->sha1, 20);\n+\t\tmemcpy(hashval, obj->sha1, 16);\n \t\tix = H(hashval, 0);\n \t\tif (!obj_hash[ix]) {\n \t\t\tobj_hash[ix] = obj;\n@@ -103,11 +101,6 @@ static struct object *insert_obj_hash(struct object *obj)\n \t\t\treturn NULL;\n \t\t}\n \t\tix = H(hashval, 3);\n-\t\tif (!obj_hash[ix]) {\n-\t\t\tobj_hash[ix] = obj;\n-\t\t\treturn NULL;\n-\t\t}\n-\t\tix = H(hashval, 4);\n \t\ttmp_obj = obj_hash[ix];\n \t\tobj_hash[ix] = obj;\n \t\tif (!tmp_obj)\n-- \n1.7.6.433.g1421f\n"},{"id":"173297","messageId":"1313085196-13249-11-git-send-email-gitster@pobox.com","threadId":"28071","inReplyTo":"1313085196-13249-1-git-send-email-gitster@pobox.com","subject":"[PATCH 10/11] object: try 3-way cuckoo","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-11T17:53:15Z","receivedAt":"2011-08-11T17:53:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Signed-off-by: Junio C Hamano <gitster@pobox.com>\n---\n../+v/48b49262cd2d0d64696b489fe5bdfa8efb9180f5/git-pack-objects\nCounting objects: 2139209, done.\n30.68user 2.26system 0:33.05elapsed 99%CPU (0avgtext+0avgdata 3660832maxresident)k\n0inputs+0outputs (0major+421963minor)pagefaults 0swaps\nCounting objects: 2139209, done.\n30.76user 2.26system 0:33.12elapsed 99%CPU (0avgtext+0avgdata 3660480maxresident)k\n0inputs+0outputs (0major+421941minor)pagefaults 0swaps\nCounting objects: 2139209, done.\n30.74user 2.33system 0:33.18elapsed 99%CPU (0avgtext+0avgdata 3661696maxresident)k\n0inputs+0outputs (0major+422017minor)pagefaults 0swaps\n---\n object.c |   15 ++++-----------\n 1 files changed, 4 insertions(+), 11 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex caced56..18e6bcf 100644\n--- a/object.c\n+++ b/object.c\n@@ -49,20 +49,18 @@ struct object *get_indexed_object(unsigned int idx)\n struct object *lookup_object(const unsigned char *sha1)\n {\n \tstruct object *obj;\n-\tunsigned int hashval[4];\n+\tunsigned int hashval[3];\n \n \tif (!obj_hash)\n \t\treturn NULL;\n \n-\tmemcpy(hashval, sha1, 16);\n+\tmemcpy(hashval, sha1, 12);\n \tif ((obj = obj_hash[H(hashval, 0)]) && !hashcmp(sha1, obj->sha1))\n \t\treturn obj;\n \tif ((obj = obj_hash[H(hashval, 1)]) && !hashcmp(sha1, obj->sha1))\n \t\treturn obj;\n \tif ((obj = obj_hash[H(hashval, 2)]) && !hashcmp(sha1, obj->sha1))\n \t\treturn obj;\n-\tif ((obj = obj_hash[H(hashval, 3)]) && !hashcmp(sha1, obj->sha1))\n-\t\treturn obj;\n \treturn NULL;\n }\n \n@@ -82,9 +80,9 @@ static struct object *insert_obj_hash(struct object *obj)\n \tfor (loop = obj_hash_size / 2; 0 <= loop; loop--) {\n \t\tstruct object *tmp_obj;\n \t\tunsigned int ix;\n-\t\tunsigned int hashval[4];\n+\t\tunsigned int hashval[3];\n \n-\t\tmemcpy(hashval, obj->sha1, 16);\n+\t\tmemcpy(hashval, obj->sha1, 12);\n \t\tix = H(hashval, 0);\n \t\tif (!obj_hash[ix]) {\n \t\t\tobj_hash[ix] = obj;\n@@ -96,11 +94,6 @@ static struct object *insert_obj_hash(struct object *obj)\n \t\t\treturn NULL;\n \t\t}\n \t\tix = H(hashval, 2);\n-\t\tif (!obj_hash[ix]) {\n-\t\t\tobj_hash[ix] = obj;\n-\t\t\treturn NULL;\n-\t\t}\n-\t\tix = H(hashval, 3);\n \t\ttmp_obj = obj_hash[ix];\n \t\tobj_hash[ix] = obj;\n \t\tif (!tmp_obj)\n-- \n1.7.6.433.g1421f\n"},{"id":"173294","messageId":"1313085196-13249-12-git-send-email-gitster@pobox.com","threadId":"28071","inReplyTo":"1313085196-13249-1-git-send-email-gitster@pobox.com","subject":"[PATCH 11/11] object: try 2-way cuckoo again","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-11T17:53:16Z","receivedAt":"2011-08-11T17:53:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This should match the first \"naive\" cuckoo hashing implementation.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n../+v/ddb2c7c09c7af16bf00aa5aef6cdf54ae4611aec/git-pack-objects\nCounting objects: 2139209, done.\n31.28user 3.15system 0:34.53elapsed 99%CPU (0avgtext+0avgdata 8177056maxresident)k\n0inputs+0outputs (0major+1206514minor)pagefaults 0swaps\nCounting objects: 2139209, done.\n31.06user 3.26system 0:34.43elapsed 99%CPU (0avgtext+0avgdata 8177056maxresident)k\n0inputs+0outputs (0major+1206514minor)pagefaults 0swaps\nCounting objects: 2139209, done.\n31.06user 3.22system 0:34.39elapsed 99%CPU (0avgtext+0avgdata 8176512maxresident)k\n0inputs+0outputs (0major+1206542minor)pagefaults 0swaps\n---\n object.c |   15 ++++-----------\n 1 files changed, 4 insertions(+), 11 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex 18e6bcf..fc08e5b 100644\n--- a/object.c\n+++ b/object.c\n@@ -49,18 +49,16 @@ struct object *get_indexed_object(unsigned int idx)\n struct object *lookup_object(const unsigned char *sha1)\n {\n \tstruct object *obj;\n-\tunsigned int hashval[3];\n+\tunsigned int hashval[2];\n \n \tif (!obj_hash)\n \t\treturn NULL;\n \n-\tmemcpy(hashval, sha1, 12);\n+\tmemcpy(hashval, sha1, 8);\n \tif ((obj = obj_hash[H(hashval, 0)]) && !hashcmp(sha1, obj->sha1))\n \t\treturn obj;\n \tif ((obj = obj_hash[H(hashval, 1)]) && !hashcmp(sha1, obj->sha1))\n \t\treturn obj;\n-\tif ((obj = obj_hash[H(hashval, 2)]) && !hashcmp(sha1, obj->sha1))\n-\t\treturn obj;\n \treturn NULL;\n }\n \n@@ -80,20 +78,15 @@ static struct object *insert_obj_hash(struct object *obj)\n \tfor (loop = obj_hash_size / 2; 0 <= loop; loop--) {\n \t\tstruct object *tmp_obj;\n \t\tunsigned int ix;\n-\t\tunsigned int hashval[3];\n+\t\tunsigned int hashval[2];\n \n-\t\tmemcpy(hashval, obj->sha1, 12);\n+\t\tmemcpy(hashval, obj->sha1, 8);\n \t\tix = H(hashval, 0);\n \t\tif (!obj_hash[ix]) {\n \t\t\tobj_hash[ix] = obj;\n \t\t\treturn NULL;\n \t\t}\n \t\tix = H(hashval, 1);\n-\t\tif (!obj_hash[ix]) {\n-\t\t\tobj_hash[ix] = obj;\n-\t\t\treturn NULL;\n-\t\t}\n-\t\tix = H(hashval, 2);\n \t\ttmp_obj = obj_hash[ix];\n \t\tobj_hash[ix] = obj;\n \t\tif (!tmp_obj)\n-- \n1.7.6.433.g1421f\n"},{"id":"173324","messageId":"7vd3gbplpf.fsf@alter.siamese.dyndns.org","threadId":"28071","inReplyTo":"1313085196-13249-1-git-send-email-gitster@pobox.com","subject":"[FFT/PATCH 12/11] object.c: make object hash implementation more opaque","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-11T23:33:48Z","receivedAt":"2011-08-11T23:33:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"There are only a handful of callers that want to enumerate all the objects\nknown to the process. Unfortunately they at least know that the object\nhash can be iterated over with an integer index.\n\nIntroduce an opaque \"struct object_cursor\" type to hide the implementation\ndetail, so that later we may be able to switch to an implementation that\nis not a based on a flat and sparse array that is used as a hash table.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n\n * This is not necessary for the purpose of the earlier \"cuckoo\" update,\n   as that still is an implementation based on a single flat sparse array,\n   but I am throwing it out as a food-for-thought.\n\n   - The function \"object_cursor_max()\" returns obj_hash_size, but it only\n     is used by fsck to give an overestimate of the number of objects to\n     check. We could change it to return nr_obj to give a more precise\n     number, but I kept the behaviour bug-for-bug compatible for now.\n\n   - Later if we need to libify the in-core object store, we would wrap\n     obj_hash, nr_obj and obj_hash_size into a single \"struct obj_ctx\"\n     (the context of a series of git operations that access the object\n     store), and have a pointer to it in the \"struct object_cursor\".\n     get_object_cursor() API function may get a new variant that takes a\n     pointer to \"struct obj_ctx\" to switch between contexts, etc.\n\n   This patch is designed to apply before all the others, outside the main\n   series. If this \"more opaque\" approach is going in a desirable\n   direction, the \"cuckoo\" series should be rebased on top of this.\n\n builtin/fsck.c       |   17 ++++++++---------\n builtin/index-pack.c |   10 ++++++----\n builtin/name-rev.c   |   12 +++++-------\n object.c             |   34 ++++++++++++++++++++++++++++++----\n object.h             |    7 +++++--\n 5 files changed, 54 insertions(+), 26 deletions(-)\n\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex 5ae0366..a71b36d 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -266,22 +266,21 @@ static void check_object(struct object *obj)\n \n static void check_connectivity(void)\n {\n-\tint i, max;\n+\tstruct object_cursor *objects;\n+\tstruct object *obj;\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+\tobjects = get_object_cursor();\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+\t\tfprintf(stderr, \"Checking connectivity (%d objects)\\n\",\n+\t\t\tobject_cursor_max(objects));\n \n-\t\tif (obj)\n-\t\t\tcheck_object(obj);\n-\t}\n+\twhile ((obj = get_next_object(objects)) != NULL)\n+\t\tcheck_object(obj);\n+\tfree_object_cursor(objects);\n }\n \n static int fsck_sha1(const unsigned char *sha1)\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex e40451f..ca172d5 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -104,11 +104,13 @@ static void check_object(struct object *obj)\n \n static void check_objects(void)\n {\n-\tunsigned i, max;\n+\tstruct object_cursor *objects;\n+\tstruct object *obj;\n \n-\tmax = get_max_object_index();\n-\tfor (i = 0; i < max; i++)\n-\t\tcheck_object(get_indexed_object(i));\n+\tobjects = get_object_cursor();\n+\twhile ((obj = get_next_object(objects)) != NULL)\n+\t\tcheck_object(obj);\n+\tfree_object_cursor(objects);\n }\n \n \ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 31f5c1c..ec6b952 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -284,16 +284,14 @@ 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+\t\tstruct object_cursor *objects;\n+\t\tstruct object *obj;\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)\n-\t\t\t\tcontinue;\n+\t\tobjects = get_object_cursor();\n+\t\twhile ((obj = get_next_object(objects)) != NULL)\n \t\t\tshow_name(obj, NULL,\n \t\t\t\t  always, allow_undefined, data.name_only);\n-\t\t}\n+\t\tfree_object_cursor(objects);\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 31976b5..986d243 100644\n--- a/object.c\n+++ b/object.c\n@@ -8,14 +8,40 @@\n static struct object **obj_hash;\n static int nr_objs, obj_hash_size;\n \n-unsigned int get_max_object_index(void)\n+struct object_cursor {\n+\tint cursor_at;\n+};\n+\n+struct object_cursor *get_object_cursor(void)\n {\n-\treturn obj_hash_size;\n+\tstruct object_cursor *objects;\n+\tobjects = xmalloc(sizeof(*objects));\n+\tobjects->cursor_at = 0;\n+\treturn objects;\n+}\n+\n+int object_cursor_max(struct object_cursor *objects)\n+{\n+\treturn obj_hash_size; /* nr_objs is more precise, though */\n+}\n+\n+struct object *get_next_object(struct object_cursor *objects)\n+{\n+\tint i = objects->cursor_at;\n+\twhile (i < obj_hash_size) {\n+\t\tstruct object *obj = obj_hash[i++];\n+\t\tif (!obj)\n+\t\t\tcontinue;\n+\t\tobjects->cursor_at = i;\n+\t\treturn obj;\n+\t}\n+\tobjects->cursor_at = i;\n+\treturn NULL;\n }\n \n-struct object *get_indexed_object(unsigned int idx)\n+void free_object_cursor(struct object_cursor *objects)\n {\n-\treturn obj_hash[idx];\n+\tfree(objects);\n }\n \n static const char *object_type_strings[] = {\ndiff --git a/object.h b/object.h\nindex b6618d9..fdd14a1 100644\n--- a/object.h\n+++ b/object.h\n@@ -35,8 +35,11 @@ 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+struct object_cursor; /* opaque */\n+extern struct object_cursor *get_object_cursor(void);\n+extern int object_cursor_max(struct object_cursor *);\n+extern struct object *get_next_object(struct object_cursor *);\n+extern void free_object_cursor(struct object_cursor *);\n \n /*\n  * This can be used to see if we have heard of the object before, but\n"},{"id":"173404","messageId":"201108121759.24884.trast@student.ethz.ch","threadId":"28071","inReplyTo":"1313085196-13249-1-git-send-email-gitster@pobox.com","subject":"git_checkattr() is inefficient when repeated [Re: [PATCH 00/11] Micro-optimizing lookup_object()]","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2011-08-12T15:59:24Z","receivedAt":"2011-08-12T15:59:24Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano wrote:\n> 4-way cuckoo\n\nCool stuff!\n\nWhile looking at the performance of it, I noticed something odd about\npacking: stracing the command you gave for your timings\n\n  strace -o pack.trace \\\n    ./git-pack-objects --count-only --keep-true-parents --honor-pack-keep \\\n    --non-empty --all --reflog --no-reuse-delta --delta-base-offset \\\n    --stdout  </dev/null >/dev/null\n\nyields the fairly crazy\n\n  $ grep -c 'open.*attrib' pack.trace \n  4398\n\nincluding runs such as (with a line of context for clarity)\n\n  munmap(0x7f9cd39f7000, 4096)            = 0\n  open(\"compat/.gitattributes\", O_RDONLY) = -1 ENOENT (No such file or directory)\n  open(\"compat/.gitattributes\", O_RDONLY) = -1 ENOENT (No such file or directory)\n  open(\"compat/.gitattributes\", O_RDONLY) = -1 ENOENT (No such file or directory)\n  open(\"compat/.gitattributes\", O_RDONLY) = -1 ENOENT (No such file or directory)\n  open(\"compat/.gitattributes\", O_RDONLY) = -1 ENOENT (No such file or directory)\n  open(\"compat/.gitattributes\", O_RDONLY) = -1 ENOENT (No such file or directory)\n  open(\"compat/.gitattributes\", O_RDONLY) = -1 ENOENT (No such file or directory)\n  open(\"compat/.gitattributes\", O_RDONLY) = -1 ENOENT (No such file or directory)\n  open(\"t/.gitattributes\", O_RDONLY)      = 3\n  fstat(3, {st_mode=S_IFREG|0644, st_size=36, ...}) = 0\n\nSo calling git_checkattr in a loop is quite inefficient.  Indeed\nthere's a good optimization opportunity: compiled for 4-way hashing I\nhave (best of 3)\n\n  6.76user 0.23system 0:07.02elapsed 99%CPU (0avgtext+0avgdata 479792maxresident)\n\nbut making no_try_delta() in pack-objects.c a dummy 'return 0' gives\n\n  6.45user 0.13system 0:06.61elapsed 99%CPU (0avgtext+0avgdata 478256maxresident)\n\nWhich would be a 4.5% speedup.  Obviously that won't quite be\nattainable since we want the attributes mechanism to work, but we\nstill shouldn't have to open 4398 .gitattributes files when there are\nonly 8 .gitattributes plus one .git/info/attributes.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"173561","messageId":"7vliuujmaj.fsf@alter.siamese.dyndns.org","threadId":"28071","inReplyTo":"201108121759.24884.trast@student.ethz.ch","subject":"Re: git_checkattr() is inefficient when repeated [Re: [PATCH 00/11] Micro-optimizing lookup_object()]","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-15T23:19:00Z","receivedAt":"2011-08-15T23:19:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast <trast@student.ethz.ch> writes:\n\n> Which would be a 4.5% speedup.  Obviously that won't quite be\n> attainable since we want the attributes mechanism to work, but we\n> still shouldn't have to open 4398 .gitattributes files when there are\n> only 8 .gitattributes plus one .git/info/attributes.\n\nTrue. At runtime, the attribute mechanism wants a stack of per-directory\nattributes it can walk up to find the applicable ones maintained for the\ndirectory it currently is looking at, and the elements near the leaf are\npopped from the stack to be discarded when the caller goes on to inspect\npaths in a different directory (IOW the machinery is optimized for callers\nthat walk the paths in order, without randomly jumping around).\n\nBut at least within a process like pack-objects that are known to be long\nlived, we should be able to instead _keep_ the elements that are popped\nwhen we leave directories at deeper levels, and bring them back to the\nstack when the caller asks for a path in that directory later, without\ngoing back to the filesystem.\n"}]}