{"thread":{"id":"11425","subject":"[PATCH WIP] sha1-lookup: more memory efficient search in sorted list of SHA-1","startedAt":"2007-12-30T10:22:55Z","lastAt":"2008-01-01T14:51:30Z","messageCount":14,"participants":["Junio C Hamano","Marco Costalba","Linus Torvalds","Shawn O. Pearce","Jeff King","Pierre Habouzit"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"64201","messageId":"7vd4soa3cw.fsf@gitster.siamese.dyndns.org","threadId":"11425","inReplyTo":null,"subject":"[PATCH WIP] sha1-lookup: more memory efficient search in sorted list of SHA-1","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-12-30T10:22:55Z","receivedAt":"2007-12-30T10:22:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Currently, when looking for a packed object from the pack idx, a\nsimple binary search is used.\n\nA conventional binary search loop looks like this:\n\n        unsigned lo, hi;\n        do {\n                unsigned mi = (lo + hi) / 2;\n                int cmp = \"entry pointed at by mi\" minus \"target\";\n                if (!cmp)\n                        return (mi is the wanted one)\n                if (cmp > 0)\n                        hi = mi; \"mi is larger than target\"\n                else\n                        lo = mi+1; \"mi is smaller than target\"\n        } while (lo < hi);\n\nThe invariants are:\n\n  - When entering the loop, 'lo' points at a slot that is never\n    above the target (it could be at the target), 'hi' points at\n    a slot that is guaranteed to be above the target (it can\n    never be at the target).\n\n  - We find a point 'mi' between 'lo' and 'hi' ('mi' could be\n    the same as 'lo', but never can be the same as 'hi'), and\n    check if 'mi' hits the target.  There are three cases:\n\n     - if it is a hit, we have found the SHA-1;\n\n     - if it is strictly higher than the target, we set it to\n       'hi', and repeat the search.\n\n     - if it is strictly lower than the target, we update 'lo'\n       to one slot after it, because we allow 'lo' to be at the\n       target.\n\n    If the loop exits, there is no matching entry.\n\nWhen choosing 'mi', we do not have to take the \"middle\" but\nanywhere in between 'lo' and 'hi', as long as lo <= mi < hi is\nsatisfied.  When we somehow know that the distance between the\ntarget and 'lo' is much shorter than the target and 'hi', we\ncould pick 'mi' that is much closer to 'lo' than (hi+lo)/2,\nwhich a conventional binary search would pick.\n\nThis patch takes advantage of the fact that the SHA-1 is a good\nhash function, and as long as there are enough entries in the\ntable, we can expect uniform distribution.  An entry that begins\nwith for example \"deadbeef...\" is much likely to appear much\nlater than in the midway of a reasonably populated table.  In\nfact, it can be expected to be near 87% (222/256) from the top\nof the table.\n\nThis is a work-in-progress and has switches to allow easier\nexperiments and debugging.  Exporting GIT_USE_LOOKUP environment\nvariable enables this code.\n\nOn my admittedly memory starved machine, with a partial KDE\nrepository (3.0G pack with 95M idx):\n\n    $ GIT_USE_LOOKUP=t git log -800 --stat HEAD >/dev/null\n    3.93user 0.16system 0:04.09elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n    0inputs+0outputs (0major+55588minor)pagefaults 0swaps\n\nWithout the patch, the numbers are:\n\n    $ git log -800 --stat HEAD >/dev/null\n    4.00user 0.15system 0:04.17elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n    0inputs+0outputs (0major+60258minor)pagefaults 0swaps\n\nIn the same repository:\n\n    $ GIT_USE_LOOKUP=t git log -2000 HEAD >/dev/null\n    0.12user 0.00system 0:00.12elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k\n    0inputs+0outputs (0major+4241minor)pagefaults 0swaps\n\nWithout the patch, the numbers are:\n\n    $ git log -2000 HEAD >/dev/null\n    0.05user 0.01system 0:00.07elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n    0inputs+0outputs (0major+8506minor)pagefaults 0swaps\n\nThere isn't much time difference, but the number of minor faults\nseems to show that we are touching much smaller number of pages,\nwhich is expected.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n Makefile      |    6 ++-\n sha1-lookup.c |  153 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n sha1-lookup.h |    9 +++\n sha1_file.c   |   35 ++++++++++++-\n 4 files changed, 198 insertions(+), 5 deletions(-)\n create mode 100644 sha1-lookup.c\n create mode 100644 sha1-lookup.h\n\ndiff --git a/Makefile b/Makefile\nindex 21c80e6..9cff3ca 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -293,7 +293,8 @@ LIB_H = \\\n \trun-command.h strbuf.h tag.h tree.h git-compat-util.h revision.h \\\n \ttree-walk.h log-tree.h dir.h path-list.h unpack-trees.h builtin.h \\\n \tutf8.h reflog-walk.h patch-ids.h attr.h decorate.h progress.h \\\n-\tmailmap.h remote.h parse-options.h transport.h diffcore.h hash.h\n+\tmailmap.h remote.h parse-options.h transport.h diffcore.h hash.h \\\n+\tsha1-lookup.h\n \n DIFF_OBJS = \\\n \tdiff.o diff-lib.o diffcore-break.o diffcore-order.o \\\n@@ -316,7 +317,8 @@ LIB_OBJS = \\\n \talloc.o merge-file.o path-list.o help.o unpack-trees.o $(DIFF_OBJS) \\\n \tcolor.o wt-status.o archive-zip.o archive-tar.o shallow.o utf8.o \\\n \tconvert.o attr.o decorate.o progress.o mailmap.o symlinks.o remote.o \\\n-\ttransport.o bundle.o walker.o parse-options.o ws.o\n+\ttransport.o bundle.o walker.o parse-options.o ws.o \\\n+\tsha1-lookup.o\n \n BUILTIN_OBJS = \\\n \tbuiltin-add.o \\\ndiff --git a/sha1-lookup.c b/sha1-lookup.c\nnew file mode 100644\nindex 0000000..f5c9094\n--- /dev/null\n+++ b/sha1-lookup.c\n@@ -0,0 +1,153 @@\n+#include \"cache.h\"\n+#include \"sha1-lookup.h\"\n+\n+/*\n+ * Conventional binary search loop looks like this:\n+ *\n+ *\tunsigned lo, hi;\n+ *      do {\n+ *              unsigned mi = (lo + hi) / 2;\n+ *              int cmp = \"entry pointed at by mi\" minus \"target\";\n+ *              if (!cmp)\n+ *                      return (mi is the wanted one)\n+ *              if (cmp > 0)\n+ *                      hi = mi; \"mi is larger than target\"\n+ *              else\n+ *                      lo = mi+1; \"mi is smaller than target\"\n+ *      } while (lo < hi);\n+ *\n+ * The invariants are:\n+ *\n+ * - When entering the loop, lo points at a slot that is never\n+ *   above the target (it could be at the target), hi points at a\n+ *   slot that is guaranteed to be above the target (it can never\n+ *   be at the target).\n+ *\n+ * - We find a point 'mi' between lo and hi (mi could be the same\n+ *   as lo, but never can be as same as hi), and check if it hits\n+ *   the target.  There are three cases:\n+ *\n+ *    - if it is a hit, we are happy.\n+ *\n+ *    - if it is strictly higher than the target, we set it to hi,\n+ *      and repeat the search.\n+ *\n+ *    - if it is strictly lower than the target, we update lo to\n+ *      one slot after it, because we allow lo to be at the target.\n+ *\n+ *   If the loop exits, there is no matching entry.\n+ *\n+ * When choosing 'mi', we do not have to take the \"middle\" but\n+ * anywhere in between lo and hi, as long as lo <= mi < hi is\n+ * satisfied.  When we somehow know that the distance between the\n+ * target and lo is much shorter than the target and hi, we could\n+ * pick mi that is much closer to lo than the midway.\n+ *\n+ * Now, we can take advantage of the fact that SHA-1 is a good hash\n+ * function, and as long as there are enough entries in the table, we\n+ * can expect uniform distribution.  An entry that begins with for\n+ * example \"deadbeef...\" is much likely to appear much later than in\n+ * the midway of the table.  It can reasonably be expected to be near\n+ * 87% (222/256) from the top of the table.\n+ *\n+ * The table at \"table\" holds at least \"nr\" entries of \"elem_size\"\n+ * bytes each.  Each entry has the SHA-1 key at \"key_offset\".  The\n+ * table is sorted by the SHA-1 key of the entries.  The caller wants\n+ * to find the entry with \"key\", and knows that the entry at \"lo\" is\n+ * not higher than the entry it is looking for, and that the entry at\n+ * \"hi\" is higher than the entry it is looking for.\n+ */\n+int sha1_entry_pos(const void *table,\n+\t\t   size_t elem_size,\n+\t\t   size_t key_offset,\n+\t\t   unsigned lo, unsigned hi, unsigned nr,\n+\t\t   const unsigned char *key)\n+{\n+\tconst unsigned char *base = table;\n+\tconst unsigned char *hi_key, *lo_key;\n+\tunsigned ofs_0;\n+\tstatic int debug_lookup = -1;\n+\n+\tif (debug_lookup < 0)\n+\t\tdebug_lookup = !!getenv(\"GIT_DEBUG_LOOKUP\");\n+\n+\tif (!nr || lo >= hi)\n+\t\treturn -1;\n+\n+\tif (nr == hi)\n+\t\thi_key = NULL;\n+\telse\n+\t\thi_key = base + elem_size * hi + key_offset;\n+\tlo_key = base + elem_size * lo + key_offset;\n+\n+\tofs_0 = 0;\n+\tdo {\n+\t\tint cmp;\n+\t\tunsigned ofs, mi, range;\n+\t\tunsigned lov, hiv, kyv;\n+\t\tconst unsigned char *mi_key;\n+\n+\t\trange = hi - lo;\n+\t\tif (hi_key) {\n+\t\t\tfor (ofs = ofs_0; ofs < 20; ofs++)\n+\t\t\t\tif (lo_key[ofs] != hi_key[ofs])\n+\t\t\t\t\tbreak;\n+\t\t\tofs_0 = ofs;\n+\t\t\t/*\n+\t\t\t * byte 0 thru (ofs-1) are the same between\n+\t\t\t * lo and hi; ofs is the first byte that is\n+\t\t\t * different.\n+\t\t\t */\n+\t\t\thiv = hi_key[ofs_0];\n+\t\t\tif (ofs_0 < 19)\n+\t\t\t\thiv = (hiv << 8) | hi_key[ofs_0+1];\n+\t\t} else {\n+\t\t\thiv = 256;\n+\t\t\tif (ofs_0 < 19)\n+\t\t\t\thiv <<= 8;\n+\t\t}\n+\t\tlov = lo_key[ofs_0];\n+\t\tkyv = key[ofs_0];\n+\t\tif (ofs_0 < 19) {\n+\t\t\tlov = (lov << 8) | lo_key[ofs_0+1];\n+\t\t\tkyv = (kyv << 8) | key[ofs_0+1];\n+\t\t}\n+\t\tassert(lov < hiv);\n+\n+\t\tif (kyv < lov)\n+\t\t\treturn -1 - lo;\n+\t\tif (hiv < kyv)\n+\t\t\treturn -1 - hi;\n+\n+\t\tif (kyv == lov && lov < hiv - 1)\n+\t\t\tkyv++;\n+\t\telse if (kyv == hiv - 1 && lov < kyv)\n+\t\t\tkyv--;\n+\n+\t\tmi = (range - 1) * (kyv - lov) / (hiv - lov) + lo;\n+\n+\t\tif (debug_lookup) {\n+\t\t\tprintf(\"lo %u hi %u rg %u mi %u \", lo, hi, range, mi);\n+\t\t\tprintf(\"ofs %u lov %x, hiv %x, kyv %x\\n\",\n+\t\t\t       ofs_0, lov, hiv, kyv);\n+\t\t}\n+\t\tif (!(lo <= mi && mi < hi))\n+\t\t\tdie(\"assertion failure lo %u mi %u hi %u %s\",\n+\t\t\t    lo, mi, hi, sha1_to_hex(key));\n+\n+\t\tmi_key = base + elem_size * mi + key_offset;\n+\t\tcmp = memcmp(mi_key + ofs_0, key + ofs_0, 20 - ofs_0);\n+\t\tif (!cmp)\n+\t\t\treturn mi;\n+\t\tif (cmp > 0) {\n+\t\t\thi = mi;\n+\t\t\thi_key = mi_key;\n+\t\t}\n+\t\telse {\n+\t\t\tlo = mi + 1;\n+\t\t\tlo_key = mi_key + elem_size;\n+\t\t}\n+\t} while (lo < hi);\n+\treturn -lo-1;\n+}\n+\ndiff --git a/sha1-lookup.h b/sha1-lookup.h\nnew file mode 100644\nindex 0000000..3249a81\n--- /dev/null\n+++ b/sha1-lookup.h\n@@ -0,0 +1,9 @@\n+#ifndef SHA1_LOOKUP_H\n+#define SHA1_LOOKUP_H\n+\n+extern int sha1_entry_pos(const void *table,\n+\t\t\t  size_t elem_size,\n+\t\t\t  size_t key_offset,\n+\t\t\t  unsigned lo, unsigned hi, unsigned nr,\n+\t\t\t  const unsigned char *key);\n+#endif\ndiff --git a/sha1_file.c b/sha1_file.c\nindex b0c2435..e99136a 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -14,6 +14,7 @@\n #include \"tag.h\"\n #include \"tree.h\"\n #include \"refs.h\"\n+#include \"sha1-lookup.h\"\n \n #ifndef O_NOATIME\n #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))\n@@ -1655,7 +1656,12 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n {\n \tconst uint32_t *level1_ofs = p->index_data;\n \tconst unsigned char *index = p->index_data;\n-\tunsigned hi, lo;\n+\tunsigned hi, lo, stride;\n+\tstatic int use_lookup = -1;\n+\tstatic int debug_lookup = -1;\n+\n+\tif (debug_lookup < 0)\n+\t\tdebug_lookup = !!getenv(\"GIT_DEBUG_LOOKUP\");\n \n \tif (!index) {\n \t\tif (open_pack_index(p))\n@@ -1670,11 +1676,34 @@ off_t find_pack_entry_one(const unsigned char *sha1,\n \tindex += 4 * 256;\n \thi = ntohl(level1_ofs[*sha1]);\n \tlo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));\n+\tif (p->index_version > 1) {\n+\t\tstride = 20;\n+\t} else {\n+\t\tstride = 24;\n+\t\tindex += 4;\n+\t}\n+\n+\tif (debug_lookup)\n+\t\tprintf(\"%02x%02x%02x... lo %u hi %u nr %u\\n\",\n+\t\t       sha1[0], sha1[1], sha1[2], lo, hi, p->num_objects);\n+\n+\tif (use_lookup < 0)\n+\t\tuse_lookup = !!getenv(\"GIT_USE_LOOKUP\");\n+\tif (use_lookup) {\n+\t\tint pos = sha1_entry_pos(index, stride, 0,\n+\t\t\t\t\t lo, hi, p->num_objects, sha1);\n+\t\tif (pos < 0)\n+\t\t\treturn 0;\n+\t\treturn nth_packed_object_offset(p, pos);\n+\t}\n \n \tdo {\n \t\tunsigned mi = (lo + hi) / 2;\n-\t\tunsigned x = (p->index_version > 1) ? (mi * 20) : (mi * 24 + 4);\n-\t\tint cmp = hashcmp(index + x, sha1);\n+\t\tint cmp = hashcmp(index + mi * stride, sha1);\n+\n+\t\tif (debug_lookup)\n+\t\t\tprintf(\"lo %u hi %u rg %u mi %u\\n\",\n+\t\t\t       lo, hi, hi - lo, mi);\n \t\tif (!cmp)\n \t\t\treturn nth_packed_object_offset(p, mi);\n \t\tif (cmp > 0)\n-- \n1.5.4.rc2.3.g441ed\n"},{"id":"64213","messageId":"7vtzm08l9w.fsf@gitster.siamese.dyndns.org","threadId":"11425","inReplyTo":"7vd4soa3cw.fsf@gitster.siamese.dyndns.org","subject":"[PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-12-30T11:38:51Z","receivedAt":"2007-12-30T11:38:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"If we pick 'mi' between 'lo' and 'hi' at 50%, which was what the\nsimple binary search did, we are halving the search space\nwhether the entry at 'mi' is lower or higher than the target.\n\nThe previous patch was about picking not the middle but closer\nto 'hi', when we know the target is a lot closer to 'hi' than it\nis to 'lo'.  However, if it turns out that the entry at 'mi' is\nhigher than the target, we would end up reducing the search\nspace only by the difference between 'mi' and 'hi' (which by\ndefinition is less than 50% --- that was the whole point of not\nusing the simple binary search), which made the search less\nefficient.  And the risk of overshooting is high, because we try\nto be too precise.\n\nThis tweaks the selection of 'mi' to be a bit closer to the\nmiddle than we would otherwise pick to avoid the problem.\n\nWith this patch, we actually see slight improvements in\nexecution time as well.  In the same partial kde repository\n(3.0GB pack, 95MB idx; the numbers are from the same machine as\nbefore, best of 5 runs):\n\n    $ GIT_USE_LOOKUP=t git log -800 --stat HEAD >/dev/null\n    3.88user 0.18system 0:04.07elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n    0inputs+0outputs (0major+56378minor)pagefaults 0swaps\n\n    $ git log -800 --stat HEAD >/dev/null\n    3.93user 0.18system 0:04.11elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n    0inputs+0outputs (0major+60258minor)pagefaults 0swaps\n\n    $ GIT_USE_LOOKUP=t git log -2000 HEAD >/dev/null\n    0.05user 0.00system 0:00.06elapsed 95%CPU (0avgtext+0avgdata 0maxresident)k\n    0inputs+0outputs (0major+4517minor)pagefaults 0swaps\n\n    $ git log -2000 HEAD >/dev/null\n    0.10user 0.03system 0:00.14elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n    0inputs+0outputs (0major+8505minor)pagefaults 0swaps\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n\n * This is no way close to even 'pu' yet, but I found it an\n   interesting mental exercise with a bit of random hackery.\n\n sha1-lookup.c |   30 +++++++++++++++++++++++++-----\n 1 files changed, 25 insertions(+), 5 deletions(-)\n\ndiff --git a/sha1-lookup.c b/sha1-lookup.c\nindex f5c9094..b309270 100644\n--- a/sha1-lookup.c\n+++ b/sha1-lookup.c\n@@ -50,6 +50,12 @@\n  * the midway of the table.  It can reasonably be expected to be near\n  * 87% (222/256) from the top of the table.\n  *\n+ * However, we do not want to pick \"mi\" too precisely.  If the entry at\n+ * the 87% in the above example turns out to be higher than the target\n+ * we are looking for, we would end up narrowing the search space down\n+ * only by 13%, instead of 50% we would get if we did a simple binary\n+ * search.  So we would want to hedge our bets by being less aggressive.\n+ *\n  * The table at \"table\" holds at least \"nr\" entries of \"elem_size\"\n  * bytes each.  Each entry has the SHA-1 key at \"key_offset\".  The\n  * table is sorted by the SHA-1 key of the entries.  The caller wants\n@@ -119,11 +125,25 @@ int sha1_entry_pos(const void *table,\n \t\tif (hiv < kyv)\n \t\t\treturn -1 - hi;\n \n-\t\tif (kyv == lov && lov < hiv - 1)\n-\t\t\tkyv++;\n-\t\telse if (kyv == hiv - 1 && lov < kyv)\n-\t\t\tkyv--;\n-\n+\t\t/*\n+\t\t * Even if we know the target is much closer to 'hi'\n+\t\t * than 'lo', if we pick too precisely and overshoot\n+\t\t * (e.g. when we know 'mi' is closer to 'hi' than to\n+\t\t * 'lo', pick 'mi' that is higher than the target), we\n+\t\t * end up narrowing the search space by a smaller\n+\t\t * amount (i.e. the distance between 'mi' and 'hi')\n+\t\t * than what we would have (i.e. about half of 'lo'\n+\t\t * and 'hi').  Hedge our bets to pick 'mi' less\n+\t\t * aggressively, i.e. make 'mi' a bit closer to the\n+\t\t * middle than we would otherwise pick.\n+\t\t */\n+\t\tkyv = (kyv * 1022 + lov + hiv) / 1024;\n+\t\tif (lov < hiv - 1) {\n+\t\t\tif (kyv == lov)\n+\t\t\t\tkyv++;\n+\t\t\telse if (kyv == hiv)\n+\t\t\t\tkyv--;\n+\t\t}\n \t\tmi = (range - 1) * (kyv - lov) / (hiv - lov) + lo;\n \n \t\tif (debug_lookup) {\n-- \n1.5.4.rc2.3.g441ed\n"},{"id":"64236","messageId":"e5bfff550712301106l133dd38btd2cc4be02159387d@mail.gmail.com","threadId":"11425","inReplyTo":"7vtzm08l9w.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-12-30T19:06:25Z","receivedAt":"2007-12-30T19:06:25Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Dec 30, 2007 12:38 PM, Junio C Hamano <gitster@pobox.com> wrote:\n>\n> With this patch, we actually see slight improvements in\n> execution time as well.\n\nI have applied both your patch above and what we have discussed today,\nthe patch to speedup prefixcmp() and mine experimental one to avoid a\nlookup loop in strbuf_expand().\n\nI don't see big differences with or without you patch applied.\n\nJust for document the profiling I have uploaded a snapshot of\nKCachegrind profiling data on a run of git-log on the git tree:\n\nhttp://digilander.libero.it/mcostalba/callgrind_git_log1.png\n\n>From there you can see that pretty.c and strbuf.c, after all the\noptimizations, account for less then 8% of total time.\nThe biggest part is that 86.64% that is due almost entirely to zlib.\n\nIn particular\n\nst = inflate(&stream, Z_FINISH);\n\ncalled from unpack_compressed_entry() in sha1_file.c accounts for 72%\nof total time.\n\n\nMarco\n"},{"id":"64237","messageId":"e5bfff550712301112w4f5db2e1x86d25be52373f641@mail.gmail.com","threadId":"11425","inReplyTo":"e5bfff550712301106l133dd38btd2cc4be02159387d@mail.gmail.com","subject":"Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-12-30T19:12:02Z","receivedAt":"2007-12-30T19:12:02Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Dec 30, 2007 8:06 PM, Marco Costalba <mcostalba@gmail.com> wrote:\n>\n> In particular\n>\n> st = inflate(&stream, Z_FINISH);\n>\n> called from unpack_compressed_entry() in sha1_file.c accounts for 72%\n> of total time.\n>\n\nThat's the snapshot:\n\nhttp://digilander.libero.it/mcostalba/callgrind_git_log2.png\n"},{"id":"64238","messageId":"alpine.LFD.1.00.0712301150120.32517@woody.linux-foundation.org","threadId":"11425","inReplyTo":"7vtzm08l9w.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-12-30T19:58:02Z","receivedAt":"2007-12-30T19:58:02Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 30 Dec 2007, Junio C Hamano wrote:\n> \n> With this patch, we actually see slight improvements in\n> execution time as well.  In the same partial kde repository\n> (3.0GB pack, 95MB idx; the numbers are from the same machine as\n> before, best of 5 runs):\n\nOk, I tried this a year ago, and never got any real improvement. And mine \nwas buggy. See\n\n\thttp://marc.info/?l=git&m=117537594112450&w=2\n\nand I decided it wasn't worth it. Yours looks much better, and seems to \nget a real performance improvement, so go for it, but I doubt that the \nactual object lookup is really ever the main issue. I've never seen it \nstand out in the real profiles, although if it is able to cut down on IO \n(and your minor fault numbers are promising!), it might be more important \nthan I'd otherwise think.\n\n\t\tLinus\n"},{"id":"64239","messageId":"7vodc77t0o.fsf@gitster.siamese.dyndns.org","threadId":"11425","inReplyTo":"alpine.LFD.1.00.0712301150120.32517@woody.linux-foundation.org","subject":"Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-12-30T21:49:11Z","receivedAt":"2007-12-30T21:49:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Sun, 30 Dec 2007, Junio C Hamano wrote:\n>> \n>> With this patch, we actually see slight improvements in\n>> execution time as well.  In the same partial kde repository\n>> (3.0GB pack, 95MB idx; the numbers are from the same machine as\n>> before, best of 5 runs):\n>\n> Ok, I tried this a year ago, and never got any real improvement.\n\nYes, I remember that one.\n\n> and I decided it wasn't worth it. Yours looks much better, and seems to \n> get a real performance improvement, so go for it, but I doubt that the \n> actual object lookup is really ever the main issue. I've never seen it \n> stand out in the real profiles, although if it is able to cut down on IO \n> (and your minor fault numbers are promising!), it might be more important \n> than I'd otherwise think.\n\nThe cost of the key comparison done in each round is\ninsignificant compared to the actual cost of accessing the\nobject data through zlib.  The only potential performance\nbenefit that could come from this patch to reduce the average\nnumber of rounds in the search is I/O reduction.\n\nThe only case I can think of that this may matter in real life\nis accessing only small number of objects in a history with a\nhuge pack.  Once you dig down the history deep enough to check\nenough number of objects inside a single process, you would need\nto touch every page of the mapped idx and the minor-fault gain\nrapidly diminishes.\n\nAccessing only small number of objects in a huge history most\noften happens when building near the tip of the history\n(e.g. commit, rebase, merge), but these operations tend to deal\nwith very young objects, often unpacked.  We check pack first\nand then loose objects, so the search for young loose objects\nwill benefit from the patch because the negative look-up to\nnotice that they do not live in any pack also becomes cheaper,\nbut I do not think it is such a big deal.\n"},{"id":"64241","messageId":"e5bfff550712301404g273dd092w9b36b48d94ed1e70@mail.gmail.com","threadId":"11425","inReplyTo":"7vodc77t0o.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-12-30T22:04:19Z","receivedAt":"2007-12-30T22:04:19Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Dec 30, 2007 10:49 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Linus Torvalds <torvalds@linux-foundation.org> writes:\n>\n>\n> The cost of the key comparison done in each round is\n> insignificant compared to the actual cost of accessing the\n> object data through zlib.\n\nSorry to ask, but just out of curiosity, what were the reasons to\nchoose zlib compression algorithm among the possible ones?\n\nThere is a thread where this has been discussed in the past? Sorry to\nask but I didn't find such a thread myself.\n\nThanks\nMarco\n"},{"id":"64278","messageId":"alpine.LFD.1.00.0712311232520.32517@woody.linux-foundation.org","threadId":"11425","inReplyTo":"e5bfff550712301404g273dd092w9b36b48d94ed1e70@mail.gmail.com","subject":"Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-12-31T20:37:36Z","receivedAt":"2007-12-31T20:37:36Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 30 Dec 2007, Marco Costalba wrote:\n> \n> Sorry to ask, but just out of curiosity, what were the reasons to\n> choose zlib compression algorithm among the possible ones?\n\nIt's out there, it's common, it's stable, and it's very good \"on average\". \n\nIn other words, other compression methods tend to be worse. No, zlib isn't \nperfect, but it was the obvious default choice for me (I've used it \nbefore, we use it in the kernel, it's usually good enough), and I actually \nexpected the SHA1 to be the bigger expense.\n\nEven today, I don't really know of a better compression choice, despite \nnow being more aware of how critical uncompression performance is.\n\nAnd quite honestly I'm not really even sure that the performance downside \nis entirely about zlib itself: I suspect a lot of the reason zlib shows up \nin the profiles is that the source data is usually cold in the cache, so \nit probably takes a lot of cache misses (it also will take all the page \nfaults!).\n\nQuite possibly, the cache miss costs dominate over any algorithmic costs.\n\n\t\tLinus\n"},{"id":"64283","messageId":"20071231224015.GW14735@spearce.org","threadId":"11425","inReplyTo":"e5bfff550712301106l133dd38btd2cc4be02159387d@mail.gmail.com","subject":"Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-12-31T22:40:15Z","receivedAt":"2007-12-31T22:40:15Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Marco Costalba <mcostalba@gmail.com> wrote:\n> Just for document the profiling I have uploaded a snapshot of\n> KCachegrind profiling data on a run of git-log on the git tree:\n> \n> http://digilander.libero.it/mcostalba/callgrind_git_log1.png\n> \n> From there you can see that pretty.c and strbuf.c, after all the\n> optimizations, account for less then 8% of total time.\n> The biggest part is that 86.64% that is due almost entirely to zlib.\n> \n> In particular\n> \n> st = inflate(&stream, Z_FINISH);\n> \n> called from unpack_compressed_entry() in sha1_file.c accounts for 72%\n> of total time.\n\nThat's one of the areas where packv4 was actually a reasonably\ngood gain.  It was faster for packv4 to convert a dict based commit\nor tree into the canonical raw format used by git than it was for\nzlib inflate to decompress the very same data.\n\nIt wasn't a huge gain, but if I recall we were saving a good half\nsecond on a 4 second \"git log --raw >/dev/null\" time.  And that\nwas before we even tried to improve the tree walking APIs to\ntake advantage of the smaller (and easier to read) dict based\ntree objects.\n\nLinus already mentioned in another reply on this thread that the\ninflate time may be all page faults.  The savings we were seeing\nfrom the dict based format may have simply been due to less page\nfaults; the dict based format was slightly smaller so we probably\ngot a lot more in disk cache at once.\n\n-- \nShawn.\n"},{"id":"64286","messageId":"e5bfff550712311547x484757f8lc3c8456a2719e827@mail.gmail.com","threadId":"11425","inReplyTo":"alpine.LFD.1.00.0712311232520.32517@woody.linux-foundation.org","subject":"Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-12-31T23:47:47Z","receivedAt":"2007-12-31T23:47:47Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Dec 31, 2007 9:37 PM, Linus Torvalds <torvalds@linux-foundation.org> wrote:\n>\n>\n> Even today, I don't really know of a better compression choice, despite\n> now being more aware of how critical uncompression performance is.\n>\n\nIn the kernel, from not long ago, is used also LZO compression that\n_seems_ much faster to decompress then zlib\n\nhttp://lkml.org/lkml/2007/5/1/297\n\nThe developer, Richard Purdie, says it's also 40% faster to read for jffs2.\n\n>\n> Quite possibly, the cache miss costs dominate over any algorithmic costs.\n>\n\nWhat way could be used to build up a test to check this?\n\n\nThanks\nMarco\n"},{"id":"64289","messageId":"20080101063616.GA21605@coredump.intra.peff.net","threadId":"11425","inReplyTo":"alpine.LFD.1.00.0712311232520.32517@woody.linux-foundation.org","subject":"Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-01-01T06:36:16Z","receivedAt":"2008-01-01T06:36:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Dec 31, 2007 at 12:37:36PM -0800, Linus Torvalds wrote:\n\n> And quite honestly I'm not really even sure that the performance downside \n> is entirely about zlib itself: I suspect a lot of the reason zlib shows up \n> in the profiles is that the source data is usually cold in the cache, so \n> it probably takes a lot of cache misses (it also will take all the page \n> faults!).\n\nzlib makes a noticeable impact in real world cases. On a git.git repo,\nfully packed with stock config, warm cache:\n\n  $ /usr/bin/time git whatchanged >/dev/null\n  4.12user 0.37system 0:04.50elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n  0inputs+0outputs (0major+6452minor)pagefaults 0swaps\n\n  $ git config pack.compression 0\n  $ git repack -a -d -f\n  $ /usr/bin/time git whatchanged >/dev/null\n  2.93user 0.43system 0:03.36elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n  0inputs+0outputs (0major+8501minor)pagefaults 0swaps\n\nMore pagefaults, but a 25% improvement in wall clock time.  The packfile\nis noticeably larger (55M versus 40M), so I'm sure the cold cache case\nsucks. It may also change with larger repos, where the packfile size\ndifference kills your cache.\n\n-Peff\n"},{"id":"64293","messageId":"e5bfff550801010040k59c9608do1acb9da548620f85@mail.gmail.com","threadId":"11425","inReplyTo":"20080101063616.GA21605@coredump.intra.peff.net","subject":"Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2008-01-01T08:40:21Z","receivedAt":"2008-01-01T08:40:21Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Jan 1, 2008 7:36 AM, Jeff King <peff@peff.net> wrote:\n>\n> The packfile is noticeably larger (55M versus 40M)\n\nWell 55M versus 40M is _only_  27% of compression ratio. It means that\nthe compression algorithm is not so fundamental because the data is\nalready, how to say, well packaged.\n\nIOW if a compression algorithm X is say 30% less size efficient then\nzlib it means that the final packfile size using X would be 44.5M\ninstead of 40M, i.e. only 11% bigger then using zlib.\n\n\nMarco\n"},{"id":"64294","messageId":"e5bfff550801010101w9d32122l1d7d76f2813a2eca@mail.gmail.com","threadId":"11425","inReplyTo":"e5bfff550801010040k59c9608do1acb9da548620f85@mail.gmail.com","subject":"Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2008-01-01T09:01:21Z","receivedAt":"2008-01-01T09:01:21Z","isPatch":true,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Jan 1, 2008 9:40 AM, Marco Costalba <mcostalba@gmail.com> wrote:\n> On Jan 1, 2008 7:36 AM, Jeff King <peff@peff.net> wrote:\n> >\n> > The packfile is noticeably larger (55M versus 40M)\n>\n> Well 55M versus 40M is _only_  27% of compression ratio. It means that\n> the compression algorithm is not so fundamental because the data is\n> already, how to say, well packaged.\n>\n\nI think zlib is a very good general purpose algorithm, but is main\nstrength is to give good final file sizes, it is mainly intended for\nfiles that are seldom decompressed.\n\nFor the use we do in git IMHO it would seem appropriate to look for\nalgorithms used in the field of filesystem compression, where\ndecompression penalty is a design goal. I know very little about this\nbut I think among kernel people, expert and competent hackers should\nnot be difficult to find, given that compressed filesystem are around\nfrom many years under linux/fs/ directory.\n\nMarco\n"},{"id":"64298","messageId":"20080101145130.GD3893@artemis.madism.org","threadId":"11425","inReplyTo":"20080101063616.GA21605@coredump.intra.peff.net","subject":"Re: [PATCH WIP] sha1-lookup: make selection of 'middle' less aggressive","fromName":"Pierre Habouzit","fromEmail":"madcoder@debian.org","sentAt":"2008-01-01T14:51:30Z","receivedAt":"2008-01-01T14:51:30Z","isPatch":true,"sender":{"key":"madcoder@debian.org","avatar":"https://avatars.githubusercontent.com/u/44708?v=4"},"body":"On Tue, Jan 01, 2008 at 06:36:16AM +0000, Jeff King wrote:\n> zlib makes a noticeable impact in real world cases. On a git.git repo,\n> fully packed with stock config, warm cache:\n\nOn linux-2.6.git, with compressed packs:\n\n    $ =time git whatchanged >|/dev/null\n    19.67user 1.24system 0:21.01elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n    0inputs+0outputs (0major+38556minor)pagefaults 0swaps\n\nWithout compression:\n\n    $ =time git whatchanged >|/dev/null\n    14.41user 1.23system 0:15.67elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n    0inputs+0outputs (0major+44678minor)pagefaults 0swaps\n\n\n> More pagefaults, but a 25% improvement in wall clock time.  The packfile\n> is noticeably larger (55M versus 40M), so I'm sure the cold cache case\n> sucks. It may also change with larger repos, where the packfile size\n> difference kills your cache.\n\n  The packfile is _incredibly_ larger (~200Mo -> ~420, though I suppose\nthe first one was packed with a larger window, coming from kernel.org).\nI experience the same 25% wall clock reduction here as well. Though,\neven if larger, linux-2.6.git still stays in RAM easily on my machine.\n\n  On an unrelated note, I wonder if it wouldn't be possible for git at\nfetch time to \"share\" a very efficient pack that was computed on some\nhost. I mean, if I'm not mistaken, at clone time you get the efficient\npack, but at fetch time only incremental parts. I wonder if there would\nbe ways to say \"hey, we recomputed here a very very very good pack, take\nit instead of yours.\n\n-- \n·O·  Pierre Habouzit\n··O                                                madcoder@debian.org\nOOO                                                http://www.madism.org\n"}]}