{"thread":{"id":"42956","subject":"[PATCH v2 0/7] speed up pack-objects counting with many packs","startedAt":"2016-07-29T04:04:31Z","lastAt":"2016-08-11T16:19:10Z","messageCount":35,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":7},"messages":[{"id":"292485","messageId":"20160729040422.GA19678@sigill.intra.peff.net","threadId":"42956","inReplyTo":null,"subject":"[PATCH v2 0/7] speed up pack-objects counting with many packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-29T04:04:23Z","receivedAt":"2016-07-29T04:04:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This is a follow-up to the patches in\n\n http://public-inbox.org/git/20160725184938.GA12871@sigill.intra.peff.net/\n\nthat are currently queued in jk/pack-objects-optim-skimming. Roughly,\nthey try to optimize a loop that is O(nr_objects * nr_packs) by breaking\nout early in some cases.\n\nI had written those patches a while ago and confirmed that they did\nspeed up a particular nasty case I had. But when I tried to write a\nt/perf test to show off the improvement, I found that they didn't help!\nThe reason is that the optimizations are heavily dependent on the order\nof the packs, and which objects go in which pack. The loop has the same\nworst-case complexity as it always did, but we rely on getting lucky to\nbreak out early.\n\nI think the perf test I've included here is more representative of a\nreal-world workloads, and with an extra optimization, I was able to show\ngood numbers with it.\n\nThe general strategy is to order the pack lookups in most-recently-used\norder. This replaces an existing 1-element MRU cache in the normal pack\nlookup code, and replaces a straight reverse-chronological iteration in\npack-objects.\n\nAll credit for thinking of this scheme goes to Michael Haggerty, who\nsuggested the idea to me about six months ago. It seemed like a lot of\nwork at the time, so I didn't do it. :) But as I started to implement\nthe same 1-element cache in pack-objects, I found that the code actually\ngets rather awkward. The MRU solution makes the callers easier to read,\nand of course it turns out to be faster, to boot.\n\nAnyway, enough chit-chat. The patches are:\n\n [1/7]: t/perf: add tests for many-pack scenarios\n [2/7]: sha1_file: drop free_pack_by_name\n [3/7]: add generic most-recently-used list\n [4/7]: find_pack_entry: replace last_found_pack with MRU cache\n [5/7]: pack-objects: break out of want_object loop early\n [6/7]: pack-objects: compute local/ignore_pack_keep early\n [7/7]: pack-objects: use mru list when iterating over packs\n\nThe actual optimizations are in patches 4 and 7, which have their own\nnumbers. But here are end-to-end numbers for the series against the tip\nof master (for the meanings, see the discussion in patch 1, and the\nanalysis in 4 and 7):\n\n[p5303, linux.git]\nTest origin HEAD\n-------------------------------------------------------------------------\n5303.3: rev-list (1) 31.48(31.20+0.27) 31.18(30.95+0.22) -1.0%\n5303.4: repack (1) 40.74(39.27+2.56) 40.30(38.96+2.47) -1.1%\n5303.6: rev-list (50) 31.65(31.38+0.26) 31.26(31.02+0.23) -1.2%\n5303.7: repack (50) 60.90(71.03+2.13) 46.95(57.46+1.85) -22.9%\n5303.9: rev-list (1000) 38.63(38.25+0.37) 31.91(31.61+0.28) -17.4%\n5303.10: repack (1000) 392.52(467.09+5.05) 87.38(159.98+2.92) -77.7%\n\n[p5303, git.git]\nTest origin HEAD\n---------------------------------------------------------------------\n5303.3: rev-list (1) 1.55(1.54+0.00) 1.56(1.54+0.01) +0.6%\n5303.4: repack (1) 1.83(1.82+0.06) 1.82(1.82+0.05) -0.5%\n5303.6: rev-list (50) 1.58(1.56+0.02) 1.58(1.57+0.00) +0.0%\n5303.7: repack (50) 2.50(3.16+0.04) 2.32(2.92+0.09) -7.2%\n5303.9: rev-list (1000) 2.64(2.61+0.02) 2.23(2.21+0.01) -15.5%\n5303.10: repack (1000) 12.68(19.07+0.30) 7.51(13.86+0.20) -40.8%\n\nFor curiosity, I also ran the git.git case with 10,000 packs. This is\neven more silly, but it shows that the problem does get worse and worse\nas the number grows, but that the patches do continue to help:\n\nTest origin HEAD\n-------------------------------------------------------------------------\n5303.12: rev-list (10,000) 26.00(25.86+0.13) 15.76(15.62+0.13) -39.4%\n5303.13: repack (10,000) 164.11(175.30+1.34) 51.48(62.96+1.18) -68.6%\n\n-Peff\n"},{"id":"292486","messageId":"20160729040609.GA22408@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160729040422.GA19678@sigill.intra.peff.net","subject":"[PATCH v2 1/7] t/perf: add tests for many-pack scenarios","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-29T04:06:09Z","receivedAt":"2016-07-29T04:06:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Git's pack storage does efficient (log n) lookups in a\nsingle packfile's index, but if we have multiple packfiles,\nwe have to linearly search each for a given object. This\npatch introduces some timing tests for cases where we have a\nlarge number of packs, so that we can measure any\nimprovements we make in the following patches.\n\nThe main thing we want to time is object lookup. To do this,\nwe measure \"git rev-list --objects --all\", which does a\nfairly large number of object lookups (essentially one per\nobject in the repository).\n\nHowever, we also measure the time to do a full repack, which\nis interesting for two reasons. One is that in addition to\nthe usual pack lookup, it has its own linear iteration over\nthe list of packs. And two is that because it it is the tool\none uses to go from an inefficient many-pack situation back\nto a single pack, we care about its performance not only at\nmarginal numbers of packs, but at the extreme cases (e.g.,\nif you somehow end up with 5,000 packs, it is the only way\nto get back to 1 pack, so we need to make sure it performs\nwell).\n\nWe measure the performance of each command in three\nscenarios: 1 pack, 50 packs, and 1,000 packs.\n\nThe 1-pack case is a baseline; any optimizations we do to\nhandle multiple packs cannot possibly perform better than\nthis.\n\nThe 50-pack case is as far as Git should generally allow\nyour repository to go, if you have auto-gc enabled with the\ndefault settings. So this represents the maximum performance\nimprovement we would expect under normal circumstances.\n\nThe 1,000-pack case is hopefully rare, though I have seen it\nin the wild where automatic maintenance was broken for some\ntime (and the repository continued to receive pushes). This\nrepresents cases where we care less about general\nperformance, but want to make sure that a full repack\ncommand does not take excessively long.\n\nSigned-off-by: Jeff King \n---\nBy the way, a caution before you run this. It takes one the order of an\nhour to run on linux.git. So if you're comparing a few builds, be\npatient. :)\n\n t/perf/p5303-many-packs.sh | 87 ++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 87 insertions(+)\n create mode 100755 t/perf/p5303-many-packs.sh\n\ndiff --git a/t/perf/p5303-many-packs.sh b/t/perf/p5303-many-packs.sh\nnew file mode 100755\nindex 0000000..3779851\n--- /dev/null\n+++ b/t/perf/p5303-many-packs.sh\n@@ -0,0 +1,87 @@\n+#!/bin/sh\n+\n+test_description='performance with large numbers of packs'\n+. ./perf-lib.sh\n+\n+test_perf_large_repo\n+\n+# A real many-pack situation would probably come from having a lot of pushes\n+# over time. We don't know how big each push would be, but we can fake it by\n+# just walking the first-parent chain and having every 5 commits be their own\n+# \"push\". This isn't _entirely_ accurate, as real pushes would have some\n+# duplicate objects due to thin-pack fixing, but it's a reasonable\n+# approximation.\n+#\n+# And then all of the rest of the objects can go in a single packfile that\n+# represents the state before any of those pushes (actually, we'll generate\n+# that first because in such a setup it would be the oldest pack, and we sort\n+# the packs by reverse mtime inside git).\n+repack_into_n () {\n+\trm -rf staging &&\n+\tmkdir staging &&\n+\n+\tgit rev-list --first-parent HEAD |\n+\tsed -n '1~5p' |\n+\thead -n \"$1\" |\n+\tperl -e 'print reverse <>' \\\n+\t>pushes\n+\n+\t# create base packfile\n+\thead -n 1 pushes |\n+\tgit pack-objects --delta-base-offset --revs staging/pack\n+\n+\t# and then incrementals between each pair of commits\n+\tlast= &&\n+\twhile read rev\n+\tdo\n+\t\tif test -n \"$last\"; then\n+\t\t\t{\n+\t\t\t\techo \"$rev\" &&\n+\t\t\t\techo \"^$last\"\n+\t\t\t} |\n+\t\t\tgit pack-objects --delta-base-offset --revs \\\n+\t\t\t\tstaging/pack || return 1\n+\t\tfi\n+\t\tlast=$rev\n+\tdone /dev/null\n+\t'\n+\n+\t# This simulates the interesting part of the repack, which is the\n+\t# actual pack generation, without smudging the on-disk setup\n+\t# between trials.\n+\ttest_perf \"repack ($nr_packs)\" '\n+\t\tgit pack-objects --keep-true-parents \\\n+\t\t --honor-pack-keep --non-empty --all \\\n+\t\t --reflog --indexed-objects --delta-base-offset \\\n+\t\t --stdout /dev/null\n+\t'\n+done\n+\n+test_done\n-- \n2.9.2.607.g98dce7b\n\n"},{"id":"292487","messageId":"20160729040647.GB22408@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160729040422.GA19678@sigill.intra.peff.net","subject":"[PATCH v2 2/7] sha1_file: drop free_pack_by_name","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-29T04:06:48Z","receivedAt":"2016-07-29T04:06:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The point of this function is to drop an entry from the\n\"packed_git\" cache that points to a file we might be\noverwriting, because our contents may not be the same (and\nhence the only caller was pack-objects as it moved a\ntemporary packfile into place).\n\nIn older versions of git, this could happen because the\nnames of packfiles were derived from the set of objects they\ncontained, not the actual bits on disk. But since 1190a1a\n(pack-objects: name pack files after trailer hash,\n2013-12-05), the name reflects the actual bits on disk, and\nany two packfiles with the same name can be used\ninterchangeably.\n\nDropping this function not only saves a few lines of code,\nit makes the lifetime of \"struct packed_git\" much easier to\nreason about: namely, we now do not ever free these structs.\n\nSigned-off-by: Jeff King \n---\n cache.h | 1 -\n pack-write.c | 1 -\n sha1_file.c | 30 ------------------------------\n 3 files changed, 32 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 3855ddf..57ef726 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1416,7 +1416,6 @@ extern unsigned char *use_pack(struct packed_git *, struct pack_window **, off_t\n extern void close_pack_windows(struct packed_git *);\n extern void close_all_packs(void);\n extern void unuse_pack(struct pack_window **);\n-extern void free_pack_by_name(const char *);\n extern void clear_delta_base_cache(void);\n extern struct packed_git *add_packed_git(const char *path, size_t path_len, int local);\n \ndiff --git a/pack-write.c b/pack-write.c\nindex 33293ce..ea0b788 100644\n--- a/pack-write.c\n+++ b/pack-write.c\n@@ -354,7 +354,6 @@ void finish_tmp_packfile(struct strbuf *name_buffer,\n \t\tdie_errno(\"unable to make temporary index file readable\");\n \n \tstrbuf_addf(name_buffer, \"%s.pack\", sha1_to_hex(sha1));\n-\tfree_pack_by_name(name_buffer->buf);\n \n \tif (rename(pack_tmp_name, name_buffer->buf))\n \t\tdie_errno(\"unable to rename temporary pack file\");\ndiff --git a/sha1_file.c b/sha1_file.c\nindex d5e1121..e045d2f 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -891,36 +891,6 @@ void close_pack_index(struct packed_git *p)\n \t}\n }\n \n-/*\n- * This is used by git-repack in case a newly created pack happens to\n- * contain the same set of objects as an existing one. In that case\n- * the resulting file might be different even if its name would be the\n- * same. It is best to close any reference to the old pack before it is\n- * replaced on disk. Of course no index pointers or windows for given pack\n- * must subsist at this point. If ever objects from this pack are requested\n- * again, the new version of the pack will be reinitialized through\n- * reprepare_packed_git().\n- */\n-void free_pack_by_name(const char *pack_name)\n-{\n-\tstruct packed_git *p, **pp = &packed_git;\n-\n-\twhile (*pp) {\n-\t\tp = *pp;\n-\t\tif (strcmp(pack_name, p->pack_name) == 0) {\n-\t\t\tclear_delta_base_cache();\n-\t\t\tclose_pack(p);\n-\t\t\tfree(p->bad_object_sha1);\n-\t\t\t*pp = p->next;\n-\t\t\tif (last_found_pack == p)\n-\t\t\t\tlast_found_pack = NULL;\n-\t\t\tfree(p);\n-\t\t\treturn;\n-\t\t}\n-\t\tpp = &p->next;\n-\t}\n-}\n-\n static unsigned int get_max_fd_limit(void)\n {\n #ifdef RLIMIT_NOFILE\n-- \n2.9.2.607.g98dce7b\n\n"},{"id":"292488","messageId":"20160729040659.GC22408@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160729040422.GA19678@sigill.intra.peff.net","subject":"[PATCH v2 3/7] add generic most-recently-used list","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-29T04:06:59Z","receivedAt":"2016-07-29T04:07:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"There are a few places in Git that would benefit from a fast\nmost-recently-used cache (e.g., the list of packs, which we\nsearch linearly but would like to order based on locality).\nThis patch introduces a generic list that can be used to\nstore arbitrary pointers in most-recently-used order.\n\nThe implementation is just a doubly-linked list, where\n\"marking\" an item as used moves it to the front of the list.\nInsertion and marking are O(1), and iteration is O(n).\n\nThere's no lookup support provided; if you need fast\nlookups, you are better off with a different data structure\nin the first place.\n\nThere is also no deletion support. This would not be hard to\ndo, but it's not necessary for handling pack structs, which\nare created and never removed.\n\nSigned-off-by: Jeff King \n---\n Makefile | 1 +\n mru.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++++++\n mru.h | 45 +++++++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 96 insertions(+)\n create mode 100644 mru.c\n create mode 100644 mru.h\n\ndiff --git a/Makefile b/Makefile\nindex 6a13386..ad3624d 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -755,6 +755,7 @@ LIB_OBJS += merge.o\n LIB_OBJS += merge-blobs.o\n LIB_OBJS += merge-recursive.o\n LIB_OBJS += mergesort.o\n+LIB_OBJS += mru.o\n LIB_OBJS += name-hash.o\n LIB_OBJS += notes.o\n LIB_OBJS += notes-cache.o\ndiff --git a/mru.c b/mru.c\nnew file mode 100644\nindex 0000000..9dedae0\n--- /dev/null\n+++ b/mru.c\n@@ -0,0 +1,50 @@\n+#include \"cache.h\"\n+#include \"mru.h\"\n+\n+void mru_append(struct mru *mru, void *item)\n+{\n+\tstruct mru_entry *cur = xmalloc(sizeof(*cur));\n+\tcur->item = item;\n+\tcur->prev = mru->tail;\n+\tcur->next = NULL;\n+\n+\tif (mru->tail)\n+\t\tmru->tail->next = cur;\n+\telse\n+\t\tmru->head = cur;\n+\tmru->tail = cur;\n+}\n+\n+void mru_mark(struct mru *mru, struct mru_entry *entry)\n+{\n+\t/* If we're already at the front of the list, nothing to do */\n+\tif (mru->head == entry)\n+\t\treturn;\n+\n+\t/* Otherwise, remove us from our current slot... */\n+\tif (entry->prev)\n+\t\tentry->prev->next = entry->next;\n+\tif (entry->next)\n+\t\tentry->next->prev = entry->prev;\n+\telse\n+\t\tmru->tail = entry->prev;\n+\n+\t/* And insert us at the beginning. */\n+\tentry->prev = NULL;\n+\tentry->next = mru->head;\n+\tif (mru->head)\n+\t\tmru->head->prev = entry;\n+\tmru->head = entry;\n+}\n+\n+void mru_clear(struct mru *mru)\n+{\n+\tstruct mru_entry *p = mru->head;\n+\n+\twhile (p) {\n+\t\tstruct mru_entry *to_free = p;\n+\t\tp = p->next;\n+\t\tfree(to_free);\n+\t}\n+\tmru->head = mru->tail = NULL;\n+}\ndiff --git a/mru.h b/mru.h\nnew file mode 100644\nindex 0000000..42e4aea\n--- /dev/null\n+++ b/mru.h\n@@ -0,0 +1,45 @@\n+#ifndef MRU_H\n+#define MRU_H\n+\n+/**\n+ * A simple most-recently-used cache, backed by a doubly-linked list.\n+ *\n+ * Usage is roughly:\n+ *\n+ * // Create a list. Zero-initialization is required.\n+ * static struct mru cache;\n+ * mru_append(&cache, item);\n+ * ...\n+ *\n+ * // Iterate in MRU order.\n+ * struct mru_entry *p;\n+ * for (p = cache.head; p; p = p->next) {\n+ *\tif (matches(p->item))\n+ *\t\tbreak;\n+ * }\n+ *\n+ * // Mark an item as used, moving it to the front of the list.\n+ * mru_mark(&cache, p);\n+ *\n+ * // Reset the list to empty, cleaning up all resources.\n+ * mru_clear(&cache);\n+ *\n+ * Note that you SHOULD NOT call mru_mark() and then continue traversing the\n+ * list; it reorders the marked item to the front of the list, and therefore\n+ * you will begin traversing the whole list again.\n+ */\n+\n+struct mru_entry {\n+\tvoid *item;\n+\tstruct mru_entry *prev, *next;\n+};\n+\n+struct mru {\n+\tstruct mru_entry *head, *tail;\n+};\n+\n+void mru_append(struct mru *mru, void *item);\n+void mru_mark(struct mru *mru, struct mru_entry *entry);\n+void mru_clear(struct mru *mru);\n+\n+#endif /* MRU_H */\n-- \n2.9.2.607.g98dce7b\n\n"},{"id":"292489","messageId":"20160729040946.GD22408@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160729040422.GA19678@sigill.intra.peff.net","subject":"[PATCH v2 4/7] find_pack_entry: replace last_found_pack with MRU cache","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-29T04:09:46Z","receivedAt":"2016-07-29T04:09:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Each pack has an index for looking up entries in O(log n)\ntime, but if we have multiple packs, we have to scan through\nthem linearly. This can produce a measurable overhead for\nsome operations.\n\nWe dealt with this long ago in f7c22cc (always start looking\nup objects in the last used pack first, 2007-05-30), which\nkeeps what is essentially a 1-element most-recently-used\ncache. In theory, we should be able to do better by keeping\na similar but longer cache, that is the same length as the\npack-list itself.\n\nSince we now have a convenient generic MRU structure, we can\nplug it in and measure. Here are the numbers for running\np5303 against linux.git:\n\nTest HEAD^ HEAD\n------------------------------------------------------------------------\n5303.3: rev-list (1) 31.56(31.28+0.27) 31.30(31.08+0.20) -0.8%\n5303.4: repack (1) 40.62(39.35+2.36) 40.60(39.27+2.44) -0.0%\n5303.6: rev-list (50) 31.31(31.06+0.23) 31.23(31.00+0.22) -0.3%\n5303.7: repack (50) 58.65(69.12+1.94) 58.27(68.64+2.05) -0.6%\n5303.9: rev-list (1000) 38.74(38.40+0.33) 31.87(31.62+0.24) -17.7%\n5303.10: repack (1000) 367.20(441.80+4.62) 342.00(414.04+3.72) -6.9%\n\nThe main numbers of interest here are the rev-list ones\n(since that is exercising the normal object lookup code\npath). The single-pack case shouldn't improve at all; the\n260ms speedup there is just part of the run-to-run noise\n(but it's important to note that we didn't make anything\nworse with the overhead of maintaining our cache). In the\n50-pack case, we see similar results. There may be a slight\nimprovement, but it's mostly within the noise.\n\nThe 1000-pack case does show a big improvement, though. That\ncarries over to the repack case, as well. Even though we\nhaven't touched its pack-search loop yet, it does still do a\nlot of normal object lookups (e.g., for the internal\nrevision walk), and so improves.\n\nAs a point of reference, I also ran the 1000-pack test\nagainst a version of HEAD^ with the last_found_pack\noptimization disabled. It takes ~60s, so that gives an\nindication of how much even the single-element cache is\nhelping.\n\nFor comparison, here's a smaller repository, git.git:\n\nTest HEAD^ HEAD\n---------------------------------------------------------------------\n5303.3: rev-list (1) 1.56(1.54+0.01) 1.54(1.51+0.02) -1.3%\n5303.4: repack (1) 1.84(1.80+0.10) 1.82(1.80+0.09) -1.1%\n5303.6: rev-list (50) 1.58(1.55+0.02) 1.59(1.57+0.01) +0.6%\n5303.7: repack (50) 2.50(3.18+0.04) 2.50(3.14+0.04) +0.0%\n5303.9: rev-list (1000) 2.76(2.71+0.04) 2.24(2.21+0.02) -18.8%\n5303.10: repack (1000) 13.21(19.56+0.25) 11.66(18.01+0.21) -11.7%\n\nYou can see that the percentage improvement is similar.\nThat's because the lookup we are optimizing is roughly\nO(nr_objects * nr_packs). Since the number of packs is\nconstant in both tests, we'd expect the improvement to be\nlinear in the number of objects. But the whole process is\nalso linear in the number of objects, so the improvement\nis a constant factor.\n\nThe exact improvement does also depend on the contents of\nthe packs. In p5303, the extra packs all have 5 first-parent\ncommits in them, which is a reasonable simulation of a\npushed-to repository. But it also means that only 250\nfirst-parent commits are in those packs (compared to almost\n50,000 total in linux.git), and the rest are in the huge\n\"base\" pack. So once we start looking at history in taht big\npack, that's where we'll find most everything, and even the\n1-element cache gets close to 100% cache hits. You could\nalmost certainly show better numbers with a more\npathological case (e.g., distributing the objects more\nevenly across the packs). But that's simply not that\nrealistic a scenario, so it makes more sense to focus on\nthese numbers.\n\nThe implementation itself is a straightforward application\nof the MRU code. We provide an MRU-ordered list of packs\nthat shadows the packed_git list. This is easy to do because\nwe only create and revise the pack list in one place. The\n\"reprepare\" code path actually drops the whole MRU and\nreplaces it for simplicity. It would be more efficient to\njust add new entries, but there's not much point in\noptimizing here; repreparing happens rarely, and only after\ndoing a lot of other expensive work. The key things to keep\noptimized are traversal (which is just a normal linked list,\nalbeit with one extra level of indirection over the regular\npacked_git list), and marking (which is a constant number of\npointer assignments, though slightly more than the old\nlast_found_pack was; it doesn't seem to create a measurable\nslowdown, though).\n\nSigned-off-by: Jeff King \n---\nI could see an argument against this, which is basically:\n\n - this is touching a really critical and core part of the code\n\n - in normal cases, we should never grow beyond 50 packs\n\n - it seems to be a wash at 50 packs\n\nSo it's all risk and no benefit. But it definitely _does_ help in the\nmore pathological cases, which are sadly a thing I have seen more than\nonce. So I tried hard to show that it does no harm, performance-wise,\nfor the smaller cases. As for complexity, you can be the judge. I think\nthe call-site here is improved, but of course that's because the\ncomplexity is hidden in the mru_mark() function.\n\n cache.h | 7 +++++++\n sha1_file.c | 36 ++++++++++++++++++------------------\n 2 files changed, 25 insertions(+), 18 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 57ef726..9b4b08f 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1377,6 +1377,13 @@ extern struct packed_git {\n \tchar pack_name[FLEX_ARRAY]; /* more */\n } *packed_git;\n \n+/*\n+ * A most-recently-used ordered version of the packed_git list, which can\n+ * be iterated instead of packed_git (and marked via mru_mark).\n+ */\n+struct mru;\n+extern struct mru *packed_git_mru;\n+\n struct pack_entry {\n \toff_t offset;\n \tunsigned char sha1[20];\ndiff --git a/sha1_file.c b/sha1_file.c\nindex e045d2f..4eb3318 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -23,6 +23,7 @@\n #include \"bulk-checkin.h\"\n #include \"streaming.h\"\n #include \"dir.h\"\n+#include \"mru.h\"\n \n #ifndef O_NOATIME\n #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))\n@@ -59,14 +60,6 @@ static struct cached_object empty_tree = {\n \t0\n };\n \n-/*\n- * A pointer to the last packed_git in which an object was found.\n- * When an object is sought, we look in this packfile first, because\n- * objects that are looked up at similar times are often in the same\n- * packfile as one another.\n- */\n-static struct packed_git *last_found_pack;\n-\n static struct cached_object *find_cached_object(const unsigned char *sha1)\n {\n \tint i;\n@@ -522,6 +515,9 @@ static size_t peak_pack_mapped;\n static size_t pack_mapped;\n struct packed_git *packed_git;\n \n+static struct mru packed_git_mru_storage;\n+struct mru *packed_git_mru = &packed_git_mru_storage;\n+\n void pack_report(void)\n {\n \tfprintf(stderr,\n@@ -1355,6 +1351,15 @@ static void rearrange_packed_git(void)\n \tfree(ary);\n }\n \n+static void prepare_packed_git_mru(void)\n+{\n+\tstruct packed_git *p;\n+\n+\tmru_clear(packed_git_mru);\n+\tfor (p = packed_git; p; p = p->next)\n+\t\tmru_append(packed_git_mru, p);\n+}\n+\n static int prepare_packed_git_run_once = 0;\n void prepare_packed_git(void)\n {\n@@ -1370,6 +1375,7 @@ void prepare_packed_git(void)\n \t\talt->name[-1] = '/';\n \t}\n \trearrange_packed_git();\n+\tprepare_packed_git_mru();\n \tprepare_packed_git_run_once = 1;\n }\n \n@@ -2574,21 +2580,15 @@ static int fill_pack_entry(const unsigned char *sha1,\n */\n static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)\n {\n-\tstruct packed_git *p;\n+\tstruct mru_entry *p;\n \n \tprepare_packed_git();\n \tif (!packed_git)\n \t\treturn 0;\n \n-\tif (last_found_pack && fill_pack_entry(sha1, e, last_found_pack))\n-\t\treturn 1;\n-\n-\tfor (p = packed_git; p; p = p->next) {\n-\t\tif (p == last_found_pack)\n-\t\t\tcontinue; /* we already checked this one */\n-\n-\t\tif (fill_pack_entry(sha1, e, p)) {\n-\t\t\tlast_found_pack = p;\n+\tfor (p = packed_git_mru->head; p; p = p->next) {\n+\t\tif (fill_pack_entry(sha1, e, p->item)) {\n+\t\t\tmru_mark(packed_git_mru, p);\n \t\t\treturn 1;\n \t\t}\n \t}\n-- \n2.9.2.607.g98dce7b\n\n"},{"id":"292490","messageId":"20160729041031.GE22408@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160729040422.GA19678@sigill.intra.peff.net","subject":"[PATCH v2 5/7] pack-objects: break out of want_object loop early","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-29T04:10:31Z","receivedAt":"2016-07-29T04:10:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When pack-objects collects the list of objects to pack\n(either from stdin, or via its internal rev-list), it\nfilters each one through want_object_in_pack().\n\nThis function loops through each existing packfile, looking\nfor the object. When we find it, we mark the pack/offset\ncombo for later use. However, we can't just return \"yes, we\nwant it\" at that point. If --honor-pack-keep is in effect,\nwe must keep looking to find it in _all_ packs, to make sure\nnone of them has a .keep. Likewise, if --local is in effect,\nwe must make sure it is not present in any non-local pack.\n\nAs a result, the sum effort of these calls is effectively\nO(nr_objects * nr_packs). In an ordinary repository, we have\nonly a handful of packs, and this doesn't make a big\ndifference. But in pathological cases, it can slow the\ncounting phase to a crawl.\n\nThis patch notices the case that we have neither \"--local\"\nnor \"--honor-pack-keep\" in effect and breaks out of the loop\nearly, after finding the first instance. Note that our worst\ncase is still \"objects * packs\" (i.e., we might find each\nobject in the last pack we look in), but in practice we will\noften break out early. On an \"average\" repo, my git.git with\n8 packs, this shows a modest 2% (a few dozen milliseconds)\nimprovement in the counting-objects phase of \"git\npack-objects --all \n---\nSame as earlier, though I took the re-ordering and comment from Junio\nthat came out of the earlier discussion.\n\n builtin/pack-objects.c | 16 ++++++++++++++++\n 1 file changed, 16 insertions(+)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex a2f8cfd..8ad11f2 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -977,6 +977,22 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t\t\t\treturn 1;\n \t\t\tif (incremental)\n \t\t\t\treturn 0;\n+\n+\t\t\t/*\n+\t\t\t * When asked to do --local (do not include an\n+\t\t\t * object that appears in a pack we borrow\n+\t\t\t * from elsewhere) or --honor-pack-keep (do not\n+\t\t\t * include an object that appears in a pack marked\n+\t\t\t * with .keep), we need to make sure no copy of this\n+\t\t\t * object come from in _any_ pack that causes us to\n+\t\t\t * omit it, and need to complete this loop. When\n+\t\t\t * neither option is in effect, we know the object\n+\t\t\t * we just found is going to be packed, so break\n+\t\t\t * out of the loop to return 1 now.\n+\t\t\t */\n+\t\t\tif (!ignore_packed_keep && !local)\n+\t\t\t\tbreak;\n+\n \t\t\tif (local && !p->pack_local)\n \t\t\t\treturn 0;\n \t\t\tif (ignore_packed_keep && p->pack_local && p->pack_keep)\n-- \n2.9.2.607.g98dce7b\n\n"},{"id":"292491","messageId":"20160729041130.GF22408@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160729040422.GA19678@sigill.intra.peff.net","subject":"[PATCH v2 6/7] pack-objects: compute local/ignore_pack_keep early","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-29T04:11:31Z","receivedAt":"2016-07-29T04:11:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"In want_object_in_pack(), we can exit early from our loop if\nneither \"local\" nor \"ignore_pack_keep\" are set. If they are,\nhowever, we must examine each pack to see if it has the\nobject and is non-local or has a \".keep\".\n\nIt's quite common for there to be no non-local or .keep\npacks at all, in which case we know ahead of time that\nlooking further will be pointless. We can pre-compute this\nby simply iterating over the list of packs ahead of time,\nand dropping the flags if there are no packs that could\nmatch.\n\nAnother similar strategy would be to modify the loop in\nwant_object_in_pack() to notice that we have already found\nthe object once, and that we are looping only to check for\n\"local\" and \"keep\" attributes. If a pack has neither of\nthose, we can skip the call to find_pack_entry_one(), which\nis the expensive part of the loop.\n\nThis has two advantages:\n\n - it isn't all-or-nothing; we still get some improvement\n when there's a small number of kept or non-local packs,\n and a large number of non-kept local packs\n\n - it eliminates any possible race where we add new\n non-local or kept packs after our initial scan. In\n practice, I don't think this race matters; we already\n cache the packed_git information, so somebody who adds a\n new pack or .keep file after we've started will not be\n noticed at all, unless we happen to need to call\n reprepare_packed_git() because a lookup fails.\n\n In other words, we're already racy, and the race is not\n a big deal (losing the race means we might include an\n object in the pack that would not otherwise be, which is\n an acceptable outcome).\n\nHowever, it also has a disadvantage: we still loop over the\nrest of the packs for each object to check their flags. This\nis much less expensive than doing the object lookup, but\nstill not free. So if we wanted to implement that strategy\nto cover the non-all-or-nothing cases, we could do so in\naddition to this one (so you get the most speedup in the\nall-or-nothing case, and the best we can do in the other\ncases). But given that the all-or-nothing case is likely the\nmost common, it is probably not worth the trouble, and we\ncan revisit this later if evidence points otherwise.\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 26 +++++++++++++++++++++++++-\n 1 file changed, 25 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 8ad11f2..c4c2a3c 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -46,6 +46,7 @@ static int keep_unreachable, unpack_unreachable, include_tag;\n static unsigned long unpack_unreachable_expiration;\n static int pack_loose_unreachable;\n static int local;\n+static int have_non_local_packs;\n static int incremental;\n static int ignore_packed_keep;\n static int allow_ofs_delta;\n@@ -990,7 +991,8 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t\t\t * we just found is going to be packed, so break\n \t\t\t * out of the loop to return 1 now.\n \t\t\t */\n-\t\t\tif (!ignore_packed_keep && !local)\n+\t\t\tif (!ignore_packed_keep &&\n+\t\t\t (!local || !have_non_local_packs))\n \t\t\t\tbreak;\n \n \t\t\tif (local && !p->pack_local)\n@@ -2799,6 +2801,28 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\tprogress = 2;\n \n \tprepare_packed_git();\n+\tif (ignore_packed_keep) {\n+\t\tstruct packed_git *p;\n+\t\tfor (p = packed_git; p; p = p->next)\n+\t\t\tif (p->pack_local && p->pack_keep)\n+\t\t\t\tbreak;\n+\t\tif (!p) /* no keep-able packs found */\n+\t\t\tignore_packed_keep = 0;\n+\t}\n+\tif (local) {\n+\t\t/*\n+\t\t * unlike ignore_packed_keep above, we do not want to\n+\t\t * unset \"local\" based on looking at packs, as it\n+\t\t * also covers non-local objects\n+\t\t */\n+\t\tstruct packed_git *p;\n+\t\tfor (p = packed_git; p; p = p->next) {\n+\t\t\tif (!p->pack_local) {\n+\t\t\t\thave_non_local_packs = 1;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t}\n \n \tif (progress)\n \t\tprogress_state = start_progress(_(\"Counting objects\"), 0);\n-- \n2.9.2.607.g98dce7b\n\n"},{"id":"292492","messageId":"20160729041524.GG22408@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160729040422.GA19678@sigill.intra.peff.net","subject":"[PATCH v2 7/7] pack-objects: use mru list when iterating over packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-29T04:15:24Z","receivedAt":"2016-07-29T04:15:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"In the original implementation of want_object_in_pack(), we\nalways looked for the object in every pack, so the order did\nnot matter for performance.\n\nAs of the last few patches, however, we can now often break\nout of the loop early after finding the first instance, and\navoid looking in the other packs at all. In this case, pack\norder can make a big difference, because we'd like to find\nthe objects by looking at as few packs as possible.\n\nThis patch switches us to the same packed_git_mru list that\nis now used by normal object lookups.\n\nHere are timings for p5303 on linux.git:\n\nTest HEAD^ HEAD\n------------------------------------------------------------------------\n5303.3: rev-list (1) 31.31(31.07+0.23) 31.28(31.00+0.27) -0.1%\n5303.4: repack (1) 40.35(38.84+2.60) 40.53(39.31+2.32) +0.4%\n5303.6: rev-list (50) 31.37(31.15+0.21) 31.41(31.16+0.24) +0.1%\n5303.7: repack (50) 58.25(68.54+2.03) 47.28(57.66+1.89) -18.8%\n5303.9: rev-list (1000) 31.91(31.57+0.33) 31.93(31.64+0.28) +0.1%\n5303.10: repack (1000) 304.80(376.00+3.92) 87.21(159.54+2.84) -71.4%\n\nThe rev-list numbers are unchanged, which makes sense (they\nare not exercising this code at all). The 50- and 1000-pack\nrepack cases show considerable improvement.\n\nThe single-pack repack case doesn't, of course; there's\nnothing to improve. In fact, it gives us a baseline for how\nfast we could possibly go. You can see that though rev-list\ncan approach the single-pack case even with 1000 packs,\nrepack doesn't. The reason is simple: the loop we are\noptimizing is only part of what the repack is doing. After\nthe \"counting\" phase, we do delta compression, which is much\nmore expensive when there are multiple packs, because we\nhave fewer deltas we can reuse (you can also see that these\nnumbers come from a multicore machine; the CPU times are\nmuch higher than the wall-clock times due to the delta\nphase).\n\nSo the good news is that in cases with many packs, we used\nto be dominated by the \"counting\" phase, and now we are\ndominated by the delta compression (which is faster, and\nwhich we have already parallelized).\n\nHere are similar numbers for git.git:\n\nTest HEAD^ HEAD\n---------------------------------------------------------------------\n5303.3: rev-list (1) 1.55(1.51+0.02) 1.54(1.53+0.00) -0.6%\n5303.4: repack (1) 1.82(1.80+0.08) 1.82(1.78+0.09) +0.0%\n5303.6: rev-list (50) 1.58(1.57+0.00) 1.58(1.56+0.01) +0.0%\n5303.7: repack (50) 2.50(3.12+0.07) 2.31(2.95+0.06) -7.6%\n5303.9: rev-list (1000) 2.22(2.20+0.02) 2.23(2.19+0.03) +0.5%\n5303.10: repack (1000) 10.47(16.78+0.22) 7.50(13.76+0.22) -28.4%\n\nNot as impressive in terms of percentage, but still\nmeasurable wins. If you look at the wall-clock time\nimprovements in the 1000-pack case, you can see that linux\nimproved by roughly 10x as many seconds as git. That's\nbecause it has roughly 10x as many objects, and we'd expect\nthis improvement to scale linearly with the number of\nobjects (since the number of packs is kept constant). It's\njust that the \"counting\" phase is a smaller percentage of\nthe total time spent for a git.git repack, and hence the\npercentage win is smaller.\n\nThe implementation itself is a straightforward use of the\nMRU code. We only bother marking a pack as used when we know\nthat we are able to break early out of the loop, for two\nreasons:\n\n 1. If we can't break out early, it does no good; we have\n to visit each pack anyway, so we might as well avoid\n even the minor overhead of managing the cache order.\n\n 2. The mru_mark() function reorders the list, which would\n screw up our traversal. So it is only safe to mark when\n we are about to break out of the loop. We could record\n the found pack and mark it after the loop finishes, of\n course, but that's more complicated and it doesn't buy\n us anything due to (1).\n\nNote that this reordering does have a potential impact on\nthe final pack, as we store only a single \"found\" pack for\neach object, even if it is present in multiple packs. In\nprinciple, any copy is acceptable, as they all refer to the\nsame content. But in practice, they may differ in whether\nthey are stored as deltas, against which base, etc. This may\nhave an impact on delta reuse, and even the delta search\n(since we skip pairs that were already in the same pack).\n\nIt's not clear whether this change of order would hurt or\neven help average cases, though. The most likely reason to\nhave duplicate objects is from the completion of thin packs\n(e.g., you have some objects, then receive several pushes;\nthe packs you receive may be thin on the wire, with deltas\nthat refer to bases outside the pack, but we complete them\nwith duplicate base objects when indexing them).\n\nIn such a case the current code would always find the thin\nduplicates (because we currently walk the packs in reverse\nchronological order). With this patch, it's possible that\nsome of them would be found in older packs instead. But\nagain, it's unclear whether that is a net win or loss in\npractice.\n\nSigned-off-by: Jeff King \n---\nSo obviously the \"unclear\" at the end makes me nervous. My gut feeling\nis that it will be a wash (the existing ordering was simply what\nhappened to occur, and was not really planned for this particular use,\nso there may be some small wins and some small losses which will cancel\nout). But unlike the original two optimizations, this has not been\ndeployed at GitHub, so I don't have any empirical data (and even if it\nwere, I'm not quite sure what I'd measure. I guess pack size, there's so\nmuch noise in such a measurement I expect any change would be lost).\n\n builtin/pack-objects.c | 10 +++++++---\n 1 file changed, 7 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex c4c2a3c..d686e08 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -23,6 +23,7 @@\n #include \"reachable.h\"\n #include \"sha1-array.h\"\n #include \"argv-array.h\"\n+#include \"mru.h\"\n \n static const char *pack_usage[] = {\n \tN_(\"git pack-objects --stdout [...] [< | < ]\"),\n@@ -957,7 +958,7 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t\t\t struct packed_git **found_pack,\n \t\t\t off_t *found_offset)\n {\n-\tstruct packed_git *p;\n+\tstruct mru_entry *entry;\n \n \tif (!exclude && local && has_loose_object_nonlocal(sha1))\n \t\treturn 0;\n@@ -965,7 +966,8 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t*found_pack = NULL;\n \t*found_offset = 0;\n \n-\tfor (p = packed_git; p; p = p->next) {\n+\tfor (entry = packed_git_mru->head; entry; entry = entry->next) {\n+\t\tstruct packed_git *p = entry->item;\n \t\toff_t offset = find_pack_entry_one(sha1, p);\n \t\tif (offset) {\n \t\t\tif (!*found_pack) {\n@@ -992,8 +994,10 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t\t\t * out of the loop to return 1 now.\n \t\t\t */\n \t\t\tif (!ignore_packed_keep &&\n-\t\t\t (!local || !have_non_local_packs))\n+\t\t\t (!local || !have_non_local_packs)) {\n+\t\t\t\tmru_mark(packed_git_mru, entry);\n \t\t\t\tbreak;\n+\t\t\t}\n \n \t\t\tif (local && !p->pack_local)\n \t\t\t\treturn 0;\n-- \n2.9.2.607.g98dce7b\n"},{"id":"292493","messageId":"20160729054536.GA27343@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160729041524.GG22408@sigill.intra.peff.net","subject":"Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-07-29T05:45:37Z","receivedAt":"2016-07-29T05:45:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 29, 2016 at 12:15:24AM -0400, Jeff King wrote:\n\n> Note that this reordering does have a potential impact on\n> the final pack, as we store only a single \"found\" pack for\n> each object, even if it is present in multiple packs. In\n> principle, any copy is acceptable, as they all refer to the\n> same content. But in practice, they may differ in whether\n> they are stored as deltas, against which base, etc. This may\n> have an impact on delta reuse, and even the delta search\n> (since we skip pairs that were already in the same pack).\n> \n> It's not clear whether this change of order would hurt or\n> even help average cases, though. The most likely reason to\n> have duplicate objects is from the completion of thin packs\n> (e.g., you have some objects, then receive several pushes;\n> the packs you receive may be thin on the wire, with deltas\n> that refer to bases outside the pack, but we complete them\n> with duplicate base objects when indexing them).\n> \n> In such a case the current code would always find the thin\n> duplicates (because we currently walk the packs in reverse\n> chronological order). With this patch, it's possible that\n> some of them would be found in older packs instead. But\n> again, it's unclear whether that is a net win or loss in\n> practice.\n\nHmm, so the efficacy of packing aside, this does definitely have a\nnegative effect.\n\nI happened to have a repository sitting around that has 15 million\nobjects and 3600 packs (don't ask), so this seemed like a good test.\n\nWith this patch series, it took 11 minutes to do the counting, delta\ncompression, and write phases. Without it, after 11 minutes git had not\neven gotten 10% of the way through counting. So that's good news.\n\nThe not-so-good news is that during the write phase, it hit the\n\"recursive delta detected\" warning in write_one(), many times.\n\nI think what is happening is that in the original code, we cannot ever\nsee a delta cycle, because the pack ordering is fixed. So if `A` is a\ndelta of `B`, then we know that they must both exist in the same pack\n(since we do not do cross-pack deltas on disk). And because we look at\nthe packs in the same order for each object, we know that if we are\ngoing to find `A`, we must either find `B` in the same pack (or a prior\none if there is another duplicate). But if we do so, then we cannot\nalso find `B` as a delta of `A` in that pack (because we know that packs\ndo not have delta cycles themselves) or an earlier pack (because if so,\nwe would have found `A` in that pack, too).\n\nBut because this series switches the order of pack-lookup between\nobjects, it is possible for us to find a `B` which is a delta against\n`A` in one pack, and then another copy of `A` which is a delta against\nanother copy of `B` from another pack. We add both of the deltas to our\npacking list, but at write time when we try to write out all of the\nbases for `A`, we realize that whoops, we are recursing infinitely.\n\nAs it turns out, Git actually handles this pretty well! Upon noticing\nthe recursion, it breaks the delta chain and writes out one of the\nobjects as a full base. This is due to Junio's f63c79d (pack-object:\ntolerate broken packs that have duplicated objects, 2011-11-16), though\nI think we later decided that duplicated objects were simply insane.\n\nSo one option is to simply silence the warning, because the resulting\npack is perfectly fine. But we do notice this during the write phase,\nafter the delta search is done. So it's possible that the resulting pack\nis not as small as it could be (i.e., we break the chain with a base\nobject, but it's possible if we looked that we could have broken the\nchain by making a delta against an existing base object). So I wonder if\nit's possible to detect this case earlier, during the \"can we reuse this\ndelta\" bits of check_object().\n\nSuggestions welcome. I haven't really dug past what I've written here,\nand it's way too late here to go any further tonight.\n\n-Peff\n"},{"id":"292516","messageId":"xmqqr3acpjvo.fsf@gitster.mtv.corp.google.com","threadId":"42956","inReplyTo":"20160729054536.GA27343@sigill.intra.peff.net","subject":"Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-07-29T15:02:51Z","receivedAt":"2016-07-29T15:03:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Fri, Jul 29, 2016 at 12:15:24AM -0400, Jeff King wrote:\n>\n> But because this series switches the order of pack-lookup between\n> objects, it is possible for us to find a `B` which is a delta against\n> `A` in one pack, and then another copy of `A` which is a delta against\n> another copy of `B` from another pack. We add both of the deltas to our\n> packing list, but at write time when we try to write out all of the\n> bases for `A`, we realize that whoops, we are recursing infinitely.\n>\n> As it turns out, Git actually handles this pretty well! Upon noticing\n> the recursion, it breaks the delta chain and writes out one of the\n> objects as a full base. This is due to Junio's f63c79d (pack-object:\n> tolerate broken packs that have duplicated objects, 2011-11-16), though\n> I think we later decided that duplicated objects were simply insane.\n>\n> So one option is to simply silence the warning, because the resulting\n> pack is perfectly fine.\n\nThanks for a great analysis.\n\nMy gut feeling is that keeping the warning is preferred if possible,\nbecause f63c79db (pack-object: tolerate broken packs that have\nduplicated objects, 2011-11-16) was made as the last ditch effort to\nwarn about the presence of the problem in the delta-base selection\ncode without harming the users.\n\n> So it's possible that the resulting pack\n> is not as small as it could be (i.e., we break the chain with a base\n> object, but it's possible if we looked that we could have broken the\n> chain by making a delta against an existing base object). So I wonder if\n> it's possible to detect this case earlier, during the \"can we reuse this\n> delta\" bits of check_object().\n\nI'd let the issue simmer in my mind a bit for now, as I do not\nthink of a neat trick offhand.\n"},{"id":"293353","messageId":"20160808145042.uwrk2m6jq3m4li37@sigill.intra.peff.net","threadId":"42956","inReplyTo":"xmqqr3acpjvo.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-08T14:50:43Z","receivedAt":"2016-08-08T14:50:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 29, 2016 at 08:02:51AM -0700, Junio C Hamano wrote:\n\n> > So it's possible that the resulting pack\n> > is not as small as it could be (i.e., we break the chain with a base\n> > object, but it's possible if we looked that we could have broken the\n> > chain by making a delta against an existing base object). So I wonder if\n> > it's possible to detect this case earlier, during the \"can we reuse this\n> > delta\" bits of check_object().\n>\n> I'd let the issue simmer in my mind a bit for now, as I do not\n> think of a neat trick offhand.\n\nSorry, I let this go a bit longer than intended. Here's where I'm at\nwith my thinking.\n\nTo recap the issue for those just joining us, the series in question\nchanges the order in which pack-objects will look at the existing\npackfiles (in order to make the counting step faster when you have many\npacks). This can introduce cycles in reused deltas because we might find\n\"A\" as a delta of \"B\" in one pack, but \"B\" as a delta of \"A\" in another\npack. Whereas the current code, with a static pack ordering, will always\nfind such an \"A\" and \"B\" in the same pack, so as long as that pack does\nnot have a cycle, our set of reused deltas won't either.\n\nThe current code does detect the cycle, but not until the write phase\n(at which point we issue a warning, throw out the delta, and output the\nfull object).\n\nHere's a list of approaches I think we can use to fix this:\n\n 1. squelch the warning and ignore it. The downside here, besides not\n warning the user about true in-pack cycles, is that we have no\n opportunity to actually find a new delta (because we realize the\n problem only after the delta-compression phase).\n\n My test repository is a bad packing of all of the forks of\n torvalds/linux, with 3600 packs. I'm happy to share it if anybody\n wants to see it, but note that it is 11GB.\n\n The space overhead of the resulting pack in this case is ~3.2%\n (versus a pack generated by the original code, using the static\n pack order). Which is really not that bad, but I'm sure there are\n more pathological cases (i.e., there were on the order of hundreds\n or maybe thousands of cycles that needed broken, out of about 15\n million total objects; but one could imagine the worst case as\n nr_of_objects/2).\n\n 2. break the cycles in check_object(), when we consider whether we can\n reuse the delta.\n\n The obvious advantage here (over breaking it in the writing phase)\n is that we can then feed the object into the normal\n delta-compression phase.\n\n The question is: how?\n\n 2a. One way to do so is to provide a total ordering over the packs.\n\t I.e., if \"A\" is a delta of \"B\", then allow the delta to be\n\t reused iff the pack containing \"A\" sorts before or equal to the\n\t pack containing \"B\". The actual ordering doesn't matter for\n\t purposes of the cycle-breaking, as long as its consistent.\n\n\t I implemented this using the mtime of the packs (breaking ties\n\t by their names), as that would give us results close to the\n\n\t Unsurprisingly, this adds a bit of CPU time (because we have\n\t more delta objects to search), though it's dwarfed by the wins\n\t you get from the sped-up counting phase (in my tests, 20\n\t seconds of extra delta search for 39 minutes of \"counting\n\t objects\" savings).\n\n\t But it doesn't actually help the resulting pack size. It's\n\t still about 3.2% overhead (it's actually just slightly worse\n\t than case 1).\n\n\t I think what happens is that we throw out a lot of deltas, even\n\t ones that _aren't_ cycles, but just happened to be found in\n\t packs that are \"backwards\" in the total order. And then we have\n\t to do a delta search on them, but of course that can't always\n\t find a good match.\n\n\t I also tried two other variants here. The pack order for the\n\t cycle-breaking step shouldn't matter, so I wondered what would\n\t happen if I reversed it. It does indeed produce different\n\t results. The resulting pack is slightly better, at 2.6%\n\t overhead. But we spend even more time looking for deltas (IOW,\n\t we threw out more of them).\n\n\t I also tried bumping the pack window size, under the theory\n\t that maybe we just aren't finding great deltas for the ones we\n\t throw out. But it didn't seem to make much difference.\n\n\t So I like the simplicity of this idea (which, by the way, was\n\t not mine, but came from an off-list discussion with Michael).\n\t But I think it's a dead-end, because it throws away too many\n\t deltas that _could_ be reused.\n\n 2b. Another option is to do real cycle analysis, and break the\n cycles.\n\n\t This is tricky to do in check_object() because we are actually\n\t filling out the delta pointers as we go. So I think we would\n\t have to make two passes: one to come up with a tentative list\n\t of deltas to reuse, and then one to check them for cycles.\n\n\t If done right, the cycle check should be linear in the number\n\t of objects (it's basically a depth-first search). In fact, I\n\t think it would look a lot like what write_object() is doing.\n\t We'd just be moving the logic _before_ the delta-compression\n\t phase, instead of after.\n\n\t This is the one approach I've considered but have not yet\n\t implemented. So no numbers.\n\n 3. Pick a consistent pack order up front, and stop changing it\n mid-search.\n\n The question, of course, is which order.\n\n For my test repo, this is actually pretty easy. There's one\n gigantic pack with 15 million objects in it, and then 3600 small\n packs with a handful of objects from pushes. The giant pack is the\n oldest, so the normal \"reverse chronological\" pack order makes\n counting effectively O(m*n), because the majority of the objects\n are found in the very last pack.\n\n So an obvious thing to try is just reversing it. And indeed, the\n counting is quite fast then (similar to the MRU numbers). Though of\n course one can come up with a case where the objects are more\n evenly split across the packs, and it would not help (you can come\n up with pathological cases for MRU, too, but they're much less\n likely in practice, because it's really exploiting locality).\n\n But I was surprised to find that the resulting pack is even worse,\n at 4.5% overhead.\n\n I can't really explain that, and I'm starting to come to the\n conclusion that there's a fair bit of luck and black magic involved\n in delta reuse. I would not be at all surprised to find a test case\n where reversing the order actually _improved_ things.\n\n It may be that the numbers I saw in my (2a) tests were not because\n we broke deltas and couldn't find replacements, but simply because\n we get more and better deltas by looking in the smaller, newer\n packs first.\n\nSo that's where I'm at. Mostly puzzled, and wondering if any of my\nexperiments were even valid or showing anything interesting, and not\njust somewhat random artifacts of the deltas that happen to be in this\nparticular test case. Worse, it may be that looking in the small packs\n_is_ objectively better, and we're losing that in any kind of\npack-ordering changes (which is an inherent part of my speed-up strategy\nfor the counting phase[1]).\n\nI've yet to implement 2b, true cycle-detection before delta-compression.\nBut I have a feeling it will somehow show that my resulting pack is\nabout 3% worse. :-/\n\n-Peff\n\n[1] So obviously one option is to figure out a way to speed up the\n counting phase without changing the pack order. The only way I can\n think of is to build a master object index, where each entry has all\n of the packs that a given object can be found in, in their correct\n pack order.\n\n That would be fairly easy to implement as a hash table, but:\n\n - it would require a fair bit of memory; the pack .idx for this\n\trepo is 500MB, and we usually get to just mmap it. OTOH, the\n\tbiggest part of that is the sha1s, so we could possibly just\n\treference them by pointer into the mmap'd data. And it's not\n\tlike you don't need much more than 500MB to hold the list of\n\tobjects to pack.\n\n - it's inherently O(nr_of_objects_in_repo) in CPU and memory to\n\tbuild the index, whereas some operations are\n\tO(nr_of_objects_to_be_packed). In this case it's probably OK (we\n\tdo pay for extra entries for each of the duplicates, but it's\n\tlargely on the order of 15 million objects). But it's a big\n\texpense if you're just packing a few of the objects.\n\n So I dunno. I really like the MRU approach if we can salvage it.\n"},{"id":"293362","messageId":"xmqq8tw7gr82.fsf@gitster.mtv.corp.google.com","threadId":"42956","inReplyTo":"20160808145042.uwrk2m6jq3m4li37@sigill.intra.peff.net","subject":"Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-08T16:28:29Z","receivedAt":"2016-08-08T16:28:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Here's a list of approaches I think we can use to fix this:\n>\n> 1. squelch the warning and ignore it. The downside here, besides not\n> warning the user about true in-pack cycles, is that we have no\n> opportunity to actually find a new delta (because we realize the\n> problem only after the delta-compression phase).\n>\n> My test repository is a bad packing of all of the forks of\n> torvalds/linux, with 3600 packs. I'm happy to share it if anybody\n> wants to see it, but note that it is 11GB.\n>\n> The space overhead of the resulting pack in this case is ~3.2%\n> (versus a pack generated by the original code, using the static\n> pack order). Which is really not that bad, but I'm sure there are\n> more pathological cases (i.e., there were on the order of hundreds\n> or maybe thousands of cycles that needed broken, out of about 15\n> million total objects; but one could imagine the worst case as\n> nr_of_objects/2).\n> ...\n>\n> So I dunno. I really like the MRU approach if we can salvage it.\n\nI think I share the same feeling. As long as the chance is small\nenough that the pack reordering creates a new cycle, the resulting\npack would not become too bloated by the last-ditch cycle breaking\ncode and finding a replacement delta instead of inflating it may not\nbe worth the trouble.\n\nIt worries me a lot to lose the warning unconditionally, though.\nThat's the (only) coal-mine canary that lets us notice a problem\nwhen we actually start hitting that last-ditch cycle breaking too\noften.\n"},{"id":"293364","messageId":"20160808165127.fvhnkcfsj4vif7iu@sigill.intra.peff.net","threadId":"42956","inReplyTo":"xmqq8tw7gr82.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-08T16:51:28Z","receivedAt":"2016-08-08T16:51:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 08, 2016 at 09:28:29AM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > Here's a list of approaches I think we can use to fix this:\n> >\n> > 1. squelch the warning and ignore it. The downside here, besides not\n> > warning the user about true in-pack cycles, is that we have no\n> > opportunity to actually find a new delta (because we realize the\n> > problem only after the delta-compression phase).\n> >\n> > My test repository is a bad packing of all of the forks of\n> > torvalds/linux, with 3600 packs. I'm happy to share it if anybody\n> > wants to see it, but note that it is 11GB.\n> >\n> > The space overhead of the resulting pack in this case is ~3.2%\n> > (versus a pack generated by the original code, using the static\n> > pack order). Which is really not that bad, but I'm sure there are\n> > more pathological cases (i.e., there were on the order of hundreds\n> > or maybe thousands of cycles that needed broken, out of about 15\n> > million total objects; but one could imagine the worst case as\n> > nr_of_objects/2).\n> > ...\n> >\n> > So I dunno. I really like the MRU approach if we can salvage it.\n> \n> I think I share the same feeling. As long as the chance is small\n> enough that the pack reordering creates a new cycle, the resulting\n> pack would not become too bloated by the last-ditch cycle breaking\n> code and finding a replacement delta instead of inflating it may not\n> be worth the trouble.\n\nLet me see how complicated it is to do the cycle-detection earlier. It\nreally shouldn't be that hard (we don't even need an auxiliary data\nstructure; we can just smudge the index value like write_object does).\nI'm very curious to see the pack resulting pack size.\n\n> It worries me a lot to lose the warning unconditionally, though.\n> That's the (only) coal-mine canary that lets us notice a problem\n> when we actually start hitting that last-ditch cycle breaking too\n> often.\n\nThe dedicated cycle-detection will lose that warning, too (it doesn't\ntouch that code, but it's effectively checking the same thing earlier).\n\nI agree it's unfortunate to lose. On the other hand, it is being lost\nbecause we are correctly handling the cycles, and there is nothing to\nwarn about. So it ceases to be a problem, and starts being a normal,\nacceptable thing.\n\n-Peff\n"},{"id":"293366","messageId":"xmqqzionfafj.fsf@gitster.mtv.corp.google.com","threadId":"42956","inReplyTo":"20160808165127.fvhnkcfsj4vif7iu@sigill.intra.peff.net","subject":"Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-08T17:16:32Z","receivedAt":"2016-08-08T17:16:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n>> It worries me a lot to lose the warning unconditionally, though.\n>> That's the (only) coal-mine canary that lets us notice a problem\n>> when we actually start hitting that last-ditch cycle breaking too\n>> often.\n>\n> The dedicated cycle-detection will lose that warning, too (it doesn't\n> touch that code, but it's effectively checking the same thing earlier).\n>\n> I agree it's unfortunate to lose. On the other hand, it is being lost\n> because we are correctly handling the cycles, and there is nothing to\n> warn about. So it ceases to be a problem, and starts being a normal,\n> acceptable thing.\n\nThat unfortunately is beside the point. The existing cycle breaking\nwas meant to be a last ditch effort to avoid producing a broken pack\n(i.e. a suboptimal pack without cycle is better than unusable pack\nwith delta cycle), while letting us know that we found a case where\nthe remainder of the pack building machinery does not function well\nwithout it (so that we know we broke something when we tweaked the\nmachinery without intending to break it). Squelching the warnings\nfeels similar to \"we see too many valgrind warnings, so let's stop\nrunning valgrind\"; I was hoping there would be a solution more like\n\"instead of not running, let's teach valgrind this and that codepath\nis OK\".\n"},{"id":"293487","messageId":"20160809140411.7745apztp36nwshx@sigill.intra.peff.net","threadId":"42956","inReplyTo":"xmqqzionfafj.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-09T14:04:12Z","receivedAt":"2016-08-09T14:04:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 08, 2016 at 10:16:32AM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> >> It worries me a lot to lose the warning unconditionally, though.\n> >> That's the (only) coal-mine canary that lets us notice a problem\n> >> when we actually start hitting that last-ditch cycle breaking too\n> >> often.\n> >\n> > The dedicated cycle-detection will lose that warning, too (it doesn't\n> > touch that code, but it's effectively checking the same thing earlier).\n> >\n> > I agree it's unfortunate to lose. On the other hand, it is being lost\n> > because we are correctly handling the cycles, and there is nothing to\n> > warn about. So it ceases to be a problem, and starts being a normal,\n> > acceptable thing.\n> \n> That unfortunately is beside the point. The existing cycle breaking\n> was meant to be a last ditch effort to avoid producing a broken pack\n> (i.e. a suboptimal pack without cycle is better than unusable pack\n> with delta cycle), while letting us know that we found a case where\n> the remainder of the pack building machinery does not function well\n> without it (so that we know we broke something when we tweaked the\n> machinery without intending to break it). Squelching the warnings\n> feels similar to \"we see too many valgrind warnings, so let's stop\n> running valgrind\"; I was hoping there would be a solution more like\n> \"instead of not running, let's teach valgrind this and that codepath\n> is OK\".\n\nI don't think there is a way to do \"this code path is OK\", exactly.\nThough by putting cycle-breaking at the check_object() stage, the\nwarning at the write_object() stage would continue to ensure that we\ndon't introduce any new cycles with our delta search. So that does have\nsome value.\n\nHere's the code to do the cycle-breaking. Aside from the \"hacky\" bit,\nit's quite simple. I added a new state enum to object_entry to handle\nthe graph traversal. Since it only needs 2 bits, I _assume_ a compiler\ncan fit it in with the bitfields above (or at the very least give it its\nown single byte so we just use what would otherwise be struct padding).\nBut I didn't check; if it turns out not to be the case we can easily\nemulate it with two bitfields. The write_object() check abuses the\n\"idx.offset\" field to keep the same state, but we could convert it to\nuse these flags if we care.\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex c91d54a..07b6fea 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1499,6 +1499,67 @@ static int pack_offset_sort(const void *_a, const void *_b)\n \t\t\t(a->in_pack_offset > b->in_pack_offset);\n }\n \n+/*\n+ * Follow the chain of deltas from this entry onward, throwing away any links\n+ * that cause us to hit a cycle (as determined by the DFS state flags in\n+ * the entries).\n+ */\n+static void break_delta_cycles(struct object_entry *entry)\n+{\n+\t/* If it's not a delta, it can't be part of a cycle. */\n+\tif (!entry->delta) {\n+\t\tentry->dfs_state = DFS_DONE;\n+\t\treturn;\n+\t}\n+\n+\tswitch (entry->dfs_state) {\n+\tcase DFS_NONE:\n+\t\t/*\n+\t\t * This is the first time we've seen the object. We become part\n+\t\t * of the active potential cycle and recurse.\n+\t\t */\n+\t\tentry->dfs_state = DFS_ACTIVE;\n+\t\tbreak_delta_cycles(entry->delta);\n+\t\tentry->dfs_state = DFS_DONE;\n+\t\tbreak;\n+\n+\tcase DFS_DONE:\n+\t\t/* object already examined, and not part of a cycle */\n+\t\tbreak;\n+\n+\tcase DFS_ACTIVE:\n+\t\t/*\n+\t\t * We found a cycle that needs broken. We have to not only\n+\t\t * drop our entry->delta link, but we need to remove\n+\t\t * ourselves from the delta_sibling chain of our base.\n+\t\t */\n+\t\t{\n+\t\t\tstruct object_entry **p = &entry->delta->delta_child;\n+\t\t\twhile (*p) {\n+\t\t\t\tif (*p == entry)\n+\t\t\t\t\t*p = (*p)->delta_sibling;\n+\t\t\t\telse\n+\t\t\t\t\tp = &(*p)->delta_sibling;\n+\t\t\t}\n+\t\t}\n+\t\tentry->delta = NULL;\n+\n+\t\t/*\n+\t\t * XXX This is hacky. We need to figure out our real size (not\n+\t\t * the delta size). check_object() already does this, so let's\n+\t\t * just re-run it, but telling it not to reuse any deltas. This\n+\t\t * probably should just be a single function to track down the\n+\t\t * size from the delta (or even just sha1_object_info(),\n+\t\t * though that is a little less efficient because we already\n+\t\t * know which pack we're in).\n+\t\t */\n+\t\treuse_delta = 0;\n+\t\tcheck_object(entry);\n+\t\treuse_delta = 1;\n+\t\tbreak;\n+\t}\n+}\n+\n static void get_object_details(void)\n {\n \tuint32_t i;\n@@ -1516,6 +1577,13 @@ static void get_object_details(void)\n \t\t\tentry->no_try_delta = 1;\n \t}\n \n+\t/*\n+\t * This must happen in a second pass, since we rely on the delta\n+\t * information for the whole list being completed.\n+\t */\n+\tfor (i = 0; i < to_pack.nr_objects; i++)\n+\t\tbreak_delta_cycles(&to_pack.objects[i]);\n+\n \tfree(sorted_by_offset);\n }\n \ndiff --git a/pack-objects.h b/pack-objects.h\nindex d1b98b3..cc9b9a9 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -27,6 +27,15 @@ struct object_entry {\n \tunsigned no_try_delta:1;\n \tunsigned tagged:1; /* near the very tip of refs */\n \tunsigned filled:1; /* assigned write-order */\n+\n+\t/*\n+\t * State flags for depth-first search used for analyzing delta cycles.\n+\t */\n+\tenum {\n+\t\tDFS_NONE = 0,\n+\t\tDFS_ACTIVE,\n+\t\tDFS_DONE\n+\t} dfs_state;\n };\n \n struct packing_data {\n\n\nIt seems to perform well, and it does break the cycles (the later check\nduring the write does not kick in, and we get no warnings). I didn't dig\ninto the fates of specific objects, but any cycles should be added to\nthe delta-compression phase.\n\nThe resulting pack size is almost exactly what it was with hitting the\nwrite_object() check. So that means all of my testing was really not\nthat interesting, because the extra space isn't coming from the delta\ncycles at all. It's simply an artifact of the different set of objects\nwe happen to find (just as reversing the pack list produces a different\norder, with a different size).\n\nSo it happens to be a 3% loss in this case. I'm not convinced it would\nnot actually be a win in some other cases. But more importantly, in a\nrepository with fewer packs, it would likely be a much smaller\ndifference (in either direction), just because there's less play in\nwhere we find a given object.\n\nI think my preference is to clean up the \"hacky\" bit of this patch, and\nthen apply the earlier MRU patch on top of it (which takes my repack\nfrom 44 minutes to 5 minutes for this particular test set). I see you\ngraduated the earlier bits of the series to \"master\" already.\n\n-Peff\n"},{"id":"293508","messageId":"20160809174528.2ydgkhd7ayclat3t@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160809140411.7745apztp36nwshx@sigill.intra.peff.net","subject":"Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-09T17:45:29Z","receivedAt":"2016-08-09T17:45:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 09, 2016 at 10:04:11AM -0400, Jeff King wrote:\n\n> Here's the code to do the cycle-breaking.\n> [...]\n> It seems to perform well, and it does break the cycles (the later check\n> during the write does not kick in, and we get no warnings). I didn't dig\n> into the fates of specific objects, but any cycles should be added to\n> the delta-compression phase.\n\nCurious about that last part, I did the repack both with and without\nthis patch. We should be able to see the difference in the progress\nmeter from the \"Compressing\" phase. And indeed, it goes from 3030778\nobjects to 3031056, an increase of 278 objects. Which just so happens to\nbe exactly the number of \"warning: recursive delta detected\" lines that\nare printed without the patch.\n\nNot surprising, but a nice confirmation that everything is working as\nexpected. But while looking at this, I managed to unravel what's been\ngoing on this whole time.\n\nI ran the repack again with stock git (no MRU patch), and the number of\nobjects in the delta phase jumped to 3087880, around 56,000 more than\nwith the MRU patch. So that's probably where the magic \"3%\" is coming\nfrom. By looking at the smaller packs first, we are more likely to find\ncopies of objects which _aren't_ deltas, and then consider them for\ndelta compression. And that compression tends to find a better match\nthan reusing what was in the big pack, and we end up with a slightly\nsmaller output pack.\n\nSo why are the deltas we find so much better than what is in the big\npack?\n\nThere's something rather subtle going on, and it has to do with the fact\nthat the existing pack was _not_ made by a stock version of git.\n\nI may have mentioned before that I have some patches which restrict the\ndelta selection process. The goal is that if you have several \"islands\"\nof refs (in my case, refs corresponding to particular forks of a\nrepository), it's desirable that you don't make a delta against a base\nthat is not reachable from all of the same islands. Otherwise, when\nsomebody fetches or clones the fork, you have to throw away the delta\nand find one from scratch. If this happens a lot, it gets expensive.\nUnsurprisingly, the packfiles produced with the island-restrictions\nturned on are slightly worse than normal packfiles (because we reject\nsome delta possibilities that might be better).\n\nWhen I did my testing, I did not enable the delta islands, because I\ndidn't want them to influence the results. But of course their effect\ncould still be seen in the deltas in the existing packfile, because it\ncame off our production servers (because I wanted a real-world test\ncase). So any pack ordering which ends up reusing _fewer_ of those\ndeltas is going to be a net win in size, because it's going to find new\ndeltas without being hampered by the island restrictions. And that's\nexactly what happened in my tests; the stock pack ordering finds more\nobjects in the newer packs, has fewer deltas to reuse, and is able to\nfind better unrestricted deltas.\n\nUnfortunately I don't have a real-world test case that's been packed up\nuntil now with stock git. So the next-best thing I can do is re-run my\ntests with the island restrictions turned on, so that newly-found deltas\ndo not have an unfair advantage. And here are the sizes for each case\nafter doing so:\n\n 7848512375 before.git/objects/pack/pack-2f5878f6569cd6682e7084318de311ed26d19af5.pack\n 7851778788 mru.git/objects/pack/pack-7694766c660eaa0e27e4e51a77bd5c457c3d2f1d.pack\n 7851165480 cycle-break.git/objects/pack/pack-cfaceb3423993c72e4ac588c30c94da2d087145a.pack\n\nThe MRU case _is_ slightly bigger, but only by 0.04%. And then adding\nthe cycle-breaking on top of that reclaims a little bit of space,\nbecause rather than throwing out those 287 deltas at the write phase,\nit's able to add those objects back to the delta search and find new\ndeltas for them.\n\nSo there. Mystery solved, and I feel confident in saying that the MRU\npatches _don't_ represent a real regression in pack size. We do need to\ndeal with the cycles, of course, but it's less an issue of size and more\none of correctness (well, the pack is correct either way, but still, it\nseems more correct to realize during the correct phase that we cannot\nreuse those deltas).\n\nI also suspect that one of the tricks I tried, simply reversing the pack\norder (so the big pack is at the front, but the order is stable) would\nwork very well for this case. But as I mentioned before, I prefer the\nMRU strategy because it's less susceptible to pathological cases.\n\n-Peff\n"},{"id":"293513","messageId":"xmqqvaz9akbk.fsf@gitster.mtv.corp.google.com","threadId":"42956","inReplyTo":"20160809174528.2ydgkhd7ayclat3t@sigill.intra.peff.net","subject":"Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-09T18:06:23Z","receivedAt":"2016-08-09T18:06:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I ran the repack again with stock git (no MRU patch), and the number of\n> objects in the delta phase jumped to 3087880, around 56,000 more than\n> with the MRU patch. So that's probably where the magic \"3%\" is coming\n> from. By looking at the smaller packs first, we are more likely to find\n> copies of objects which _aren't_ deltas, and then consider them for\n> delta compression. And that compression tends to find a better match\n> than reusing what was in the big pack, and we end up with a slightly\n> smaller output pack.\n\nYeah, that is a very plausible explanation.\n\n> So why are the deltas we find so much better than what is in the big\n> pack?\n>\n> There's something rather subtle going on, and it has to do with the fact\n> that the existing pack was _not_ made by a stock version of git.\n\n;-)\n\n> I may have mentioned before that I have some patches which restrict the\n> delta selection process. The goal is that if you have several \"islands\"\n> of refs (in my case, refs corresponding to particular forks of a\n> repository), it's desirable that you don't make a delta against a base\n> that is not reachable from all of the same islands. \n\nThat also explains it. It is expected (small) price to pay to\nensure the islands are standalone.\n\n> I also suspect that one of the tricks I tried, simply reversing the pack\n> order (so the big pack is at the front, but the order is stable) would\n> work very well for this case. But as I mentioned before, I prefer the\n> MRU strategy because it's less susceptible to pathological cases.\n\nYup, excellent. Thanks for working on this.\n"},{"id":"293544","messageId":"xmqq7fbp8tki.fsf@gitster.mtv.corp.google.com","threadId":"42956","inReplyTo":"20160809140411.7745apztp36nwshx@sigill.intra.peff.net","subject":"Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-09T22:29:33Z","receivedAt":"2016-08-09T22:29:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Here's the code to do the cycle-breaking. Aside from the \"hacky\" bit,\n> it's quite simple. I added a new state enum to object_entry to handle\n> the graph traversal. Since it only needs 2 bits, I _assume_ a compiler\n> can fit it in with the bitfields above (or at the very least give it its\n> own single byte so we just use what would otherwise be struct padding).\n> But I didn't check; if it turns out not to be the case we can easily\n> emulate it with two bitfields. The write_object() check abuses the\n> \"idx.offset\" field to keep the same state, but we could convert it to\n> use these flags if we care.\n\n> @@ -1516,6 +1577,13 @@ static void get_object_details(void)\n> \t\t\tentry->no_try_delta = 1;\n> \t}\n> \n> +\t/*\n> +\t * This must happen in a second pass, since we rely on the delta\n> +\t * information for the whole list being completed.\n> +\t */\n> +\tfor (i = 0; i < to_pack.nr_objects; i++)\n> +\t\tbreak_delta_cycles(&to_pack.objects[i]);\n> +\n> \tfree(sorted_by_offset);\n> }\n\nA potential cycle can only come from reusing deltas across packs in\nan unstable order, that happens way before we do the find_delta()\nthing, so this is a good place to have the new call. While reading\nbreak_delta_cycles(), I was wondering if what it does is safe under\nmulti-threading but there is no need to worry.\n\nThe recursiveness of break-delta-cycles is not too bad for the same\nreason why it is OK to recurse in check_delta_limit(), I would guess?\n\nThis is not new with this change, but I am not quite sure what in\nthe current code prevents us from busting the delta limit for reused\nones, though.\n\n> I think my preference is to clean up the \"hacky\" bit of this patch, and\n> then apply the earlier MRU patch on top of it (which takes my repack\n> from 44 minutes to 5 minutes for this particular test set).\n\nYup, with something like this to break the delta chain _and_ allow\nan object to go through the usual deltify machinery, I'd say the MRU\npatch is a wonderful thing to have.\n\n"},{"id":"293561","messageId":"xmqqbn107epz.fsf@gitster.mtv.corp.google.com","threadId":"42956","inReplyTo":"20160810115206.l57qpehpabthnl6c@sigill.intra.peff.net","subject":"Re: [PATCH v3 0/2] pack-objects mru","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-10T16:47:52Z","receivedAt":"2016-08-10T18:05:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n>> This is not new with this change, but I am not quite sure what in\n>> the current code prevents us from busting the delta limit for reused\n>> ones, though.\n>\n> I think in the current code you are limited by the depth you might find\n> in a single existing pack (since we never reuse cross-pack deltas).\n\nSorry for going deeper in the tangent, but I vaguely recall raising\nit long time ago as a potential issue that delta reuse out of an\noriginal pack created with deep delta chain may bust a delta chain\nlimit when repacking with shorter delta chain limit; I just do not\nremember where that discussion went (i.e. decided to be a non-issue?\nwe added code to avoid it? etc.)\n\n> However, I think with cross-pack deltas, you could have a situation\n> like:\n>\n> pack 1: A -> B -> C\n> pack 2: C -> D -> E\n>\n> and pick A and B from the first pack, and C, D, and E from the second.\n> Then you end up with:\n>\n> A -> B -> C -> D -> E\n>\n> in the output. IOW, I think the absolute worst case chain is the\n> max_depth times the number of packs.\n\nAlso if pack1 and pack2 were created with depth limit of 3 and we\nare repacking with depth limit of 2, then we are busting the limit\nalready with or without cross-pack chaining, I would think.\n\n> I'm not sure how much we should be worried about it. We could fill in\n> the depth values when adding a reused delta, but I don't think we have\n> the number handy; we'd have to actually walk the chain (though with\n> delta-base-offset, that is reasonably cheap).\n\nTrue. It is something we may want to keep back in our mind and\nrevisit later. It is definitely not a low-hanging fruit, but\nsomething that should go to the leftover-bits list.\n\n> The second patch is the same as before, though I tweaked the commit\n> message a bit, so please replace what is at the tip of\n> jk/pack-objects-optim-mru.\n>\n> [1/2]: pack-objects: break delta cycles before delta-search phase\n> [2/2]: pack-objects: use mru list when iterating over packs\n\nThanks.\n"},{"id":"293589","messageId":"20160810115206.l57qpehpabthnl6c@sigill.intra.peff.net","threadId":"42956","inReplyTo":"xmqq7fbp8tki.fsf@gitster.mtv.corp.google.com","subject":"[PATCH v3 0/2] pack-objects mru","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-10T11:52:06Z","receivedAt":"2016-08-10T18:59:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 09, 2016 at 03:29:33PM -0700, Junio C Hamano wrote:\n\n> > @@ -1516,6 +1577,13 @@ static void get_object_details(void)\n> > \t\t\tentry->no_try_delta = 1;\n> > \t}\n> > \n> > +\t/*\n> > +\t * This must happen in a second pass, since we rely on the delta\n> > +\t * information for the whole list being completed.\n> > +\t */\n> > +\tfor (i = 0; i < to_pack.nr_objects; i++)\n> > +\t\tbreak_delta_cycles(&to_pack.objects[i]);\n> > +\n> > \tfree(sorted_by_offset);\n> > }\n> \n> A potential cycle can only come from reusing deltas across packs in\n> an unstable order, that happens way before we do the find_delta()\n> thing, so this is a good place to have the new call. While reading\n> break_delta_cycles(), I was wondering if what it does is safe under\n> multi-threading but there is no need to worry.\n\nIt definitely is not multi-threaded safe (and I'm not sure it could\neasily be made so). But yeah, it is quick and happens as part of the\nget_object_details() look at the objects, which is where we make\ndecisions about delta reuse.\n\n> The recursiveness of break-delta-cycles is not too bad for the same\n> reason why it is OK to recurse in check_delta_limit(), I would guess?\n\nYes, and for the same reason that it is OK in write_one(); the recursion\nis limited by the depth of the delta chains.\n\n> This is not new with this change, but I am not quite sure what in\n> the current code prevents us from busting the delta limit for reused\n> ones, though.\n\nI think in the current code you are limited by the depth you might find\nin a single existing pack (since we never reuse cross-pack deltas).\nThere is a comment in check_object() that claims:\n\n\t* Depth value does not matter - find_deltas() will\n\t* never consider reused delta as the base object to\n\t* deltify other objects against, in order to avoid\n\t* circular deltas.\n\nbut I do not recall seeing code to enforce that (but presumably that is\njust beacuse it is a corner of the code I have not seen yet).\n\nHowever, I think with cross-pack deltas, you could have a situation\nlike:\n\n pack 1: A -> B -> C\n pack 2: C -> D -> E\n\nand pick A and B from the first pack, and C, D, and E from the second.\nThen you end up with:\n\n A -> B -> C -> D -> E\n\nin the output. IOW, I think the absolute worst case chain is the\nmax_depth times the number of packs. In practice I'd expect it to be\nmuch smaller.\n\nI'm not sure how much we should be worried about it. We could fill in\nthe depth values when adding a reused delta, but I don't think we have\nthe number handy; we'd have to actually walk the chain (though with\ndelta-base-offset, that is reasonably cheap).\n\n> > I think my preference is to clean up the \"hacky\" bit of this patch, and\n> > then apply the earlier MRU patch on top of it (which takes my repack\n> > from 44 minutes to 5 minutes for this particular test set).\n> \n> Yup, with something like this to break the delta chain _and_ allow\n> an object to go through the usual deltify machinery, I'd say the MRU\n> patch is a wonderful thing to have.\n\nHere are cleaned-up patches. The cycle-breaking patch is cleaned up and\nhas tests. I erred on the side of verbosity in the comments there,\nbecause it literally took me hours to come up with a reliable working\nset of commands (and a convincing argument that it's correct). Hopefully\nit doesn't put anyone to sleep. :)\n\nThe second patch is the same as before, though I tweaked the commit\nmessage a bit, so please replace what is at the tip of\njk/pack-objects-optim-mru.\n\n [1/2]: pack-objects: break delta cycles before delta-search phase\n [2/2]: pack-objects: use mru list when iterating over packs\n\n-Peff\n"},{"id":"293598","messageId":"20160810120248.i2hvm2q6ag3rvsk4@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160810115206.l57qpehpabthnl6c@sigill.intra.peff.net","subject":"[PATCH v3 1/2] pack-objects: break delta cycles before delta-search phase","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-10T12:02:49Z","receivedAt":"2016-08-10T19:09:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We do not allow cycles in the delta graph of a pack (i.e., A\nis a delta of B which is a delta of A) for the obvious\nreason that you cannot actually access any of the objects in\nsuch a case.\n\nThere's a last-ditch attempt to notice cycles during the\nwrite phase, during which we issue a warning to the user and\nwrite one of the objects out in full. However, this is\n\"last-ditch\" for two reasons:\n\n 1. By this time, it's too late to find another delta for\n the object, so the resulting pack is larger than it\n otherwise could be.\n\n 2. The warning is there because this is something that\n _shouldn't_ ever happen. If it does, then either:\n\n a. a pack we are reusing deltas from had its own\n cycle\n\n b. we are reusing deltas from multiple packs, and\n we found a cycle among them (i.e., A is a delta of\n B in one pack, but B is a delta of A in another,\n and we choose to use both deltas).\n\n c. there is a bug in the delta-search code\n\n So this code serves as a final check that none of these\n things has happened, warns the user, and prevents us\n from writing a bogus pack.\n\nRight now, (2b) should never happen because of the static\nordering of packs in want_object_in_pack(). If two objects\nhave a delta relationship, then they must be in the same\npack, and therefore we will find them from that same pack.\n\nHowever, a future patch would like to change that static\nordering, which will make (2b) a common occurrence. In\npreparation, we should be able to handle those kinds of\ncycles better. This patch does by introducing a\ncycle-breaking step during the get_object_details() phase,\nwhen we are deciding which deltas can be reused. That gives\nus the chance to feed the objects into the delta search as\nif the cycle did not exist.\n\nWe'll leave the detection and warning in the write_object()\nphase in place, as it still serves as a check for case (2c).\n\nThis does mean we will stop warning for (2a). That case is\ncaused by bogus input packs, and we ideally would warn the\nuser about it. However, since those cycles show up after\npicking reusable deltas, they look the same as (2b) to us;\nour new code will break the cycles early and the last-ditch\ncheck will never see them.\n\nWe could do analysis on any cycles that we find to\ndistinguish the two cases (i.e., it is a bogus pack if and\nonly if every delta in the cycle is in the same pack), but\nwe don't need to. If there is a cycle inside a pack, we'll\nrun into problems not only reusing the delta, but accessing\nthe object data at all. So when we try to dig up the actual\nsize of the object, we'll hit that same cycle and kick in\nour usual complain-and-try-another-source code.\n\nSigned-off-by: Jeff King \n---\nActually, skimming the sha1_file code, I am not 100% sure that we detect\ncycles in OBJ_REF_DELTA (you cannot have cycles in OBJ_OFS_DELTA since\nthey always point backwards in the pack). But if that is the case, then\nI think we should fix that, not worry about special-casing it here.\n\n builtin/pack-objects.c | 83 +++++++++++++++++++++++++++++\n pack-objects.h | 9 ++++\n t/t5314-pack-cycle-detection.sh | 113 ++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 205 insertions(+)\n create mode 100755 t/t5314-pack-cycle-detection.sh\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 4a63398..3e30eae 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1495,6 +1495,82 @@ static int pack_offset_sort(const void *_a, const void *_b)\n \t\t\t(a->in_pack_offset > b->in_pack_offset);\n }\n \n+/*\n+ * Drop an on-disk delta we were planning to reuse. Naively, this would\n+ * just involve blanking out the \"delta\" field, but we have to deal\n+ * with two extra pieces of book-keeping:\n+ *\n+ * 1. Removing ourselves from the delta_sibling linked list.\n+ *\n+ * 2. Updating our size; check_object() will have filled in the size of our\n+ * delta, but a non-delta object needs it true size.\n+ */\n+static void drop_reused_delta(struct object_entry *entry)\n+{\n+\tstruct object_entry **p = &entry->delta->delta_child;\n+\tstruct pack_window *w_curs = NULL;\n+\n+\twhile (*p) {\n+\t\tif (*p == entry)\n+\t\t\t*p = (*p)->delta_sibling;\n+\t\telse\n+\t\t\tp = &(*p)->delta_sibling;\n+\t}\n+\tentry->delta = NULL;\n+\n+\tentry->size = get_size_from_delta(entry->in_pack, &w_curs,\n+\t\t\t entry->in_pack_offset + entry->in_pack_header_size);\n+\tunuse_pack(&w_curs);\n+\n+\t/*\n+\t * If we failed to get the size from this pack for whatever reason,\n+\t * fall back to sha1_object_info, which may find another copy. And if\n+\t * that fails, the error will be recorded in entry->type and dealt\n+\t * with in prepare_pack().\n+\t */\n+\tif (entry->size == 0)\n+\t\tentry->type = sha1_object_info(entry->idx.sha1, &entry->size);\n+}\n+\n+/*\n+ * Follow the chain of deltas from this entry onward, throwing away any links\n+ * that cause us to hit a cycle (as determined by the DFS state flags in\n+ * the entries).\n+ */\n+static void break_delta_cycles(struct object_entry *entry)\n+{\n+\t/* If it's not a delta, it can't be part of a cycle. */\n+\tif (!entry->delta) {\n+\t\tentry->dfs_state = DFS_DONE;\n+\t\treturn;\n+\t}\n+\n+\tswitch (entry->dfs_state) {\n+\tcase DFS_NONE:\n+\t\t/*\n+\t\t * This is the first time we've seen the object. We mark it as\n+\t\t * part of the active potential cycle and recurse.\n+\t\t */\n+\t\tentry->dfs_state = DFS_ACTIVE;\n+\t\tbreak_delta_cycles(entry->delta);\n+\t\tentry->dfs_state = DFS_DONE;\n+\t\tbreak;\n+\n+\tcase DFS_DONE:\n+\t\t/* object already examined, and not part of a cycle */\n+\t\tbreak;\n+\n+\tcase DFS_ACTIVE:\n+\t\t/*\n+\t\t * We found a cycle that needs broken. It would be correct to\n+\t\t * break any link in the chain, but it's convenient to\n+\t\t * break this one.\n+\t\t */\n+\t\tdrop_reused_delta(entry);\n+\t\tbreak;\n+\t}\n+}\n+\n static void get_object_details(void)\n {\n \tuint32_t i;\n@@ -1512,6 +1588,13 @@ static void get_object_details(void)\n \t\t\tentry->no_try_delta = 1;\n \t}\n \n+\t/*\n+\t * This must happen in a second pass, since we rely on the delta\n+\t * information for the whole list being completed.\n+\t */\n+\tfor (i = 0; i < to_pack.nr_objects; i++)\n+\t\tbreak_delta_cycles(&to_pack.objects[i]);\n+\n \tfree(sorted_by_offset);\n }\n \ndiff --git a/pack-objects.h b/pack-objects.h\nindex d1b98b3..cc9b9a9 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -27,6 +27,15 @@ struct object_entry {\n \tunsigned no_try_delta:1;\n \tunsigned tagged:1; /* near the very tip of refs */\n \tunsigned filled:1; /* assigned write-order */\n+\n+\t/*\n+\t * State flags for depth-first search used for analyzing delta cycles.\n+\t */\n+\tenum {\n+\t\tDFS_NONE = 0,\n+\t\tDFS_ACTIVE,\n+\t\tDFS_DONE\n+\t} dfs_state;\n };\n \n struct packing_data {\ndiff --git a/t/t5314-pack-cycle-detection.sh b/t/t5314-pack-cycle-detection.sh\nnew file mode 100755\nindex 0000000..db9d71b\n--- /dev/null\n+++ b/t/t5314-pack-cycle-detection.sh\n@@ -0,0 +1,113 @@\n+#!/bin/sh\n+\n+test_description='test handling of inter-pack delta cycles during repack\n+\n+The goal here is to create a situation where we have two blobs, A and B, with A\n+as a delta against B in one pack, and vice versa in the other. Then if we can\n+persuade a full repack to find A from one pack and B from the other, that will\n+give us a cycle when we attempt to reuse those deltas.\n+\n+The trick is in the \"persuade\" step, as it depends on the internals of how\n+pack-objects picks which pack to reuse the deltas from. But we can assume\n+that it does so in one of two general strategies:\n+\n+ 1. Using a static ordering of packs. In this case, no inter-pack cycles can\n+ happen. Any objects with a delta relationship must be present in the same\n+ pack (i.e., no \"--thin\" packs on disk), so we will find all related objects\n+ from that pack. So assuming there are no cycles within a single pack (and\n+ we avoid generating them via pack-objects or importing them via\n+ index-pack), then our result will have no cycles.\n+\n+ So this case should pass the tests no matter how we arrange things.\n+\n+ 2. Picking the next pack to examine based on locality (i.e., where we found\n+ something else recently).\n+\n+ In this case, we want to make sure that we find the delta versions of A and\n+ B and not their base versions. We can do this by putting two blobs in each\n+ pack. The first is a \"dummy\" blob that can only be found in the pack in\n+ question. And then the second is the actual delta we want to find.\n+\n+ The two blobs must be present in the same tree, not present in other trees,\n+ and the dummy pathname must sort before the delta path.\n+\n+The setup below focuses on case 2. We have two commits HEAD and HEAD^, each\n+which has two files: \"dummy\" and \"file\". Then we can make two packs which\n+contain:\n+\n+ [pack one]\n+ HEAD:dummy\n+ HEAD:file (as delta against HEAD^:file)\n+ HEAD^:file (as base)\n+\n+ [pack two]\n+ HEAD^:dummy\n+ HEAD^:file (as delta against HEAD:file)\n+ HEAD:file (as base)\n+\n+Then no matter which order we start looking at the packs in, we know that we\n+will always find a delta for \"file\", because its lookup will always come\n+immediately after the lookup for \"dummy\".\n+'\n+. ./test-lib.sh\n+\n+\n+\n+# Create a pack containing the the tree $1 and blob $1:file, with\n+# the latter stored as a delta against $2:file.\n+#\n+# We convince pack-objects to make the delta in the direction of our choosing\n+# by marking $2 as a preferred-base edge. That results in $1:file as a thin\n+# delta, and index-pack completes it by adding $2:file as a base.\n+#\n+# Note that the two variants of \"file\" must be similar enough to convince git\n+# to create the delta.\n+make_pack () {\n+\t {\n+\t\t echo \"-$(git rev-parse $2)\"\n+\t\t echo \"$(git rev-parse $1:dummy) dummy\"\n+\t\t echo \"$(git rev-parse $1:file) file\"\n+\t } |\n+\t git pack-objects --stdout |\n+\t git index-pack --stdin --fix-thin\n+}\n+\n+test_expect_success 'setup' '\n+\ttest-genrandom base 4096 >base &&\n+\tfor i in one two\n+\tdo\n+\t\t# we want shared content here to encourage deltas...\n+\t\tcp base file &&\n+\t\techo $i >>file &&\n+\n+\t\t# ...whereas dummy should be short, because we do not want\n+\t\t# deltas that would create duplicates when we --fix-thin\n+\t\techo $i >dummy &&\n+\n+\t\tgit add file dummy &&\n+\t\ttest_tick &&\n+\t\tgit commit -m $i ||\n+\t\treturn 1\n+\tdone &&\n+\n+\tmake_pack HEAD^ HEAD &&\n+\tmake_pack HEAD HEAD^\n+'\n+\n+test_expect_success 'repack' '\n+\t# We first want to check that we do not have any internal errors,\n+\t# and also that we do not hit the last-ditch cycle-breaking code\n+\t# in write_object(), which will issue a warning to stderr.\n+\t>expect &&\n+\tgit repack -ad 2>stderr &&\n+\ttest_cmp expect stderr &&\n+\n+\t# And then double-check that the resulting pack is usable (i.e.,\n+\t# we did not fail to notice any cycles). We know we are accessing\n+\t# the objects via the new pack here, because \"repack -d\" will have\n+\t# removed the others.\n+\tgit cat-file blob HEAD:file >/dev/null &&\n+\tgit cat-file blob HEAD^:file >/dev/null\n+'\n+\n+test_done\n-- \n2.9.2.790.gaa5bc72\n\n"},{"id":"293599","messageId":"20160810120301.cof3pd3mseb2cb4r@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160810115206.l57qpehpabthnl6c@sigill.intra.peff.net","subject":"[PATCH v3 2/2] pack-objects: use mru list when iterating over packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-10T12:03:01Z","receivedAt":"2016-08-10T19:09:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"In the original implementation of want_object_in_pack(), we\nalways looked for the object in every pack, so the order did\nnot matter for performance.\n\nAs of the last few patches, however, we can now often break\nout of the loop early after finding the first instance, and\navoid looking in the other packs at all. In this case, pack\norder can make a big difference, because we'd like to find\nthe objects by looking at as few packs as possible.\n\nThis patch switches us to the same packed_git_mru list that\nis now used by normal object lookups.\n\nHere are timings for p5303 on linux.git:\n\nTest HEAD^ HEAD\n------------------------------------------------------------------------\n5303.3: rev-list (1) 31.31(31.07+0.23) 31.28(31.00+0.27) -0.1%\n5303.4: repack (1) 40.35(38.84+2.60) 40.53(39.31+2.32) +0.4%\n5303.6: rev-list (50) 31.37(31.15+0.21) 31.41(31.16+0.24) +0.1%\n5303.7: repack (50) 58.25(68.54+2.03) 47.28(57.66+1.89) -18.8%\n5303.9: rev-list (1000) 31.91(31.57+0.33) 31.93(31.64+0.28) +0.1%\n5303.10: repack (1000) 304.80(376.00+3.92) 87.21(159.54+2.84) -71.4%\n\nThe rev-list numbers are unchanged, which makes sense (they\nare not exercising this code at all). The 50- and 1000-pack\nrepack cases show considerable improvement.\n\nThe single-pack repack case doesn't, of course; there's\nnothing to improve. In fact, it gives us a baseline for how\nfast we could possibly go. You can see that though rev-list\ncan approach the single-pack case even with 1000 packs,\nrepack doesn't. The reason is simple: the loop we are\noptimizing is only part of what the repack is doing. After\nthe \"counting\" phase, we do delta compression, which is much\nmore expensive when there are multiple packs, because we\nhave fewer deltas we can reuse (you can also see that these\nnumbers come from a multicore machine; the CPU times are\nmuch higher than the wall-clock times due to the delta\nphase).\n\nSo the good news is that in cases with many packs, we used\nto be dominated by the \"counting\" phase, and now we are\ndominated by the delta compression (which is faster, and\nwhich we have already parallelized).\n\nHere are similar numbers for git.git:\n\nTest HEAD^ HEAD\n---------------------------------------------------------------------\n5303.3: rev-list (1) 1.55(1.51+0.02) 1.54(1.53+0.00) -0.6%\n5303.4: repack (1) 1.82(1.80+0.08) 1.82(1.78+0.09) +0.0%\n5303.6: rev-list (50) 1.58(1.57+0.00) 1.58(1.56+0.01) +0.0%\n5303.7: repack (50) 2.50(3.12+0.07) 2.31(2.95+0.06) -7.6%\n5303.9: rev-list (1000) 2.22(2.20+0.02) 2.23(2.19+0.03) +0.5%\n5303.10: repack (1000) 10.47(16.78+0.22) 7.50(13.76+0.22) -28.4%\n\nNot as impressive in terms of percentage, but still\nmeasurable wins. If you look at the wall-clock time\nimprovements in the 1000-pack case, you can see that linux\nimproved by roughly 10x as many seconds as git. That's\nbecause it has roughly 10x as many objects, and we'd expect\nthis improvement to scale linearly with the number of\nobjects (since the number of packs is kept constant). It's\njust that the \"counting\" phase is a smaller percentage of\nthe total time spent for a git.git repack, and hence the\npercentage win is smaller.\n\nThe implementation itself is a straightforward use of the\nMRU code. We only bother marking a pack as used when we know\nthat we are able to break early out of the loop, for two\nreasons:\n\n 1. If we can't break out early, it does no good; we have\n to visit each pack anyway, so we might as well avoid\n even the minor overhead of managing the cache order.\n\n 2. The mru_mark() function reorders the list, which would\n screw up our traversal. So it is only safe to mark when\n we are about to break out of the loop. We could record\n the found pack and mark it after the loop finishes, of\n course, but that's more complicated and it doesn't buy\n us anything due to (1).\n\nNote that this reordering does have a potential impact on\nthe final pack, as we store only a single \"found\" pack for\neach object, even if it is present in multiple packs. In\nprinciple, any copy is acceptable, as they all refer to the\nsame content. But in practice, they may differ in whether\nthey are stored as deltas, against which base, etc. This may\nhave an impact on delta reuse, and even the delta search\n(since we skip pairs that were already in the same pack).\n\nIt's not clear whether this change of order would hurt or\neven help average cases, though. The most likely reason to\nhave duplicate objects is from the completion of thin packs\n(e.g., you have some objects in a \"base\" pack, then receive\nseveral pushes; the packs you receive may be thin on the\nwire, with deltas that refer to bases outside the pack, but\nwe complete them with duplicate base objects when indexing\nthem).\n\nIn such a case the current code would always find the thin\nduplicates (because we currently walk the packs in reverse\nchronological order). Whereas with this patch, some of those\nduplicates would be found in the base pack instead.\n\nIn my tests repacking a real-world case of linux.git with\n3600 thin-pack pushes (on top of a large \"base\" pack), the\nresulting pack was about 0.04% larger with this patch. On\nthe other hand, because we were more likely to hit the base\npack, there were more opportunities for delta reuse, and we\nhad 50,000 fewer objects to examine in the delta search.\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 10 +++++++---\n 1 file changed, 7 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 3e30eae..f89a206 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -23,6 +23,7 @@\n #include \"reachable.h\"\n #include \"sha1-array.h\"\n #include \"argv-array.h\"\n+#include \"mru.h\"\n \n static const char *pack_usage[] = {\n \tN_(\"git pack-objects --stdout [...] [< | < ]\"),\n@@ -958,7 +959,7 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t\t\t struct packed_git **found_pack,\n \t\t\t off_t *found_offset)\n {\n-\tstruct packed_git *p;\n+\tstruct mru_entry *entry;\n \n \tif (!exclude && local && has_loose_object_nonlocal(sha1))\n \t\treturn 0;\n@@ -966,7 +967,8 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t*found_pack = NULL;\n \t*found_offset = 0;\n \n-\tfor (p = packed_git; p; p = p->next) {\n+\tfor (entry = packed_git_mru->head; entry; entry = entry->next) {\n+\t\tstruct packed_git *p = entry->item;\n \t\toff_t offset = find_pack_entry_one(sha1, p);\n \t\tif (offset) {\n \t\t\tif (!*found_pack) {\n@@ -993,8 +995,10 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t\t\t * out of the loop to return 1 now.\n \t\t\t */\n \t\t\tif (!ignore_packed_keep &&\n-\t\t\t (!local || !have_non_local_packs))\n+\t\t\t (!local || !have_non_local_packs)) {\n+\t\t\t\tmru_mark(packed_git_mru, entry);\n \t\t\t\tbreak;\n+\t\t\t}\n \n \t\t\tif (local && !p->pack_local)\n \t\t\t\treturn 0;\n-- \n2.9.2.790.gaa5bc72\n"},{"id":"293635","messageId":"xmqqr39w4bvx.fsf@gitster.mtv.corp.google.com","threadId":"42956","inReplyTo":"20160810120248.i2hvm2q6ag3rvsk4@sigill.intra.peff.net","subject":"Re: [PATCH v3 1/2] pack-objects: break delta cycles before delta-search phase","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-10T20:17:22Z","receivedAt":"2016-08-10T20:17:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> ...\n> We could do analysis on any cycles that we find to\n> distinguish the two cases (i.e., it is a bogus pack if and\n> only if every delta in the cycle is in the same pack), but\n> we don't need to. If there is a cycle inside a pack, we'll\n> run into problems not only reusing the delta, but accessing\n> the object data at all. So when we try to dig up the actual\n> size of the object, we'll hit that same cycle and kick in\n> our usual complain-and-try-another-source code.\n\nI agree with all of the above reasoning.\n\n> Actually, skimming the sha1_file code, I am not 100% sure that we detect\n> cycles in OBJ_REF_DELTA (you cannot have cycles in OBJ_OFS_DELTA since\n> they always point backwards in the pack). But if that is the case, then\n> I think we should fix that, not worry about special-casing it here.\n\nYes, but sha1_file.c? It is the reading side and it is too late if\nwe notice a problem, I would think.\n\n> +/*\n> + * Drop an on-disk delta we were planning to reuse. Naively, this would\n> + * just involve blanking out the \"delta\" field, but we have to deal\n> + * with two extra pieces of book-keeping:\n> + *\n> + * 1. Removing ourselves from the delta_sibling linked list.\n> + *\n> + * 2. Updating our size; check_object() will have filled in the size of our\n> + * delta, but a non-delta object needs it true size.\n\nExcellent point.\n\n> +/*\n> + * Follow the chain of deltas from this entry onward, throwing away any links\n> + * that cause us to hit a cycle (as determined by the DFS state flags in\n> + * the entries).\n> + */\n> +static void break_delta_cycles(struct object_entry *entry)\n> +{\n> +\t/* If it's not a delta, it can't be part of a cycle. */\n> +\tif (!entry->delta) {\n> +\t\tentry->dfs_state = DFS_DONE;\n> +\t\treturn;\n> +\t}\n> +\n> +\tswitch (entry->dfs_state) {\n> +\tcase DFS_NONE:\n> +\t\t/*\n> +\t\t * This is the first time we've seen the object. We mark it as\n> +\t\t * part of the active potential cycle and recurse.\n> +\t\t */\n> +\t\tentry->dfs_state = DFS_ACTIVE;\n> +\t\tbreak_delta_cycles(entry->delta);\n> +\t\tentry->dfs_state = DFS_DONE;\n> +\t\tbreak;\n> +\n> +\tcase DFS_DONE:\n> +\t\t/* object already examined, and not part of a cycle */\n> +\t\tbreak;\n> +\n> +\tcase DFS_ACTIVE:\n> +\t\t/*\n> +\t\t * We found a cycle that needs broken. It would be correct to\n> +\t\t * break any link in the chain, but it's convenient to\n> +\t\t * break this one.\n> +\t\t */\n> +\t\tdrop_reused_delta(entry);\n> +\t\tbreak;\n> +\t}\n> +}\n\nDo we need to do anything to the DFS state of an entry when\ndrop_reused_delta() resets its other fields? If we had this and\nstarted from A (read \"A--->B\" as \"A is based on B\"):\n\n A--->B--->C--->A\n\nwe paint A as ACTIVE, visit B and then C and paint them as active,\nand when we visit A for the second time, we drop it (i.e. break the\nlink between A and B), return and paint C as DONE, return and paint\nB as DONE, and leaving A painted as ACTIVE, while the chain is now\n\n B--->C--->A\n\nIf we later find D that is directly based on A, wouldn't we end up\nvisiting A and attempt to drop it again? drop_reused_delta() is\nidempotent so there will be no data structure corruption, I think,\nbut we can safely declare that the entry is now DONE after calling\ndrop_reused_delta() on it (either in the function or in the caller\nafter it calls the function), no?\n\n> + 2. Picking the next pack to examine based on locality (i.e., where we found\n> + something else recently).\n> +\n> + In this case, we want to make sure that we find the delta versions of A and\n> + B and not their base versions. We can do this by putting two blobs in each\n> + pack. The first is a \"dummy\" blob that can only be found in the pack in\n> + question. And then the second is the actual delta we want to find.\n> +\n> + The two blobs must be present in the same tree, not present in other trees,\n> + and the dummy pathname must sort before the delta path.\n\n> +# Create a pack containing the the tree $1 and blob $1:file, with\n> +# the latter stored as a delta against $2:file.\n> +#\n> +# We convince pack-objects to make the delta in the direction of our choosing\n> +# by marking $2 as a preferred-base edge. That results in $1:file as a thin\n> +# delta, and index-pack completes it by adding $2:file as a base.\n\nTricky but clever and correct ;-)\n\n> +make_pack () {\n> +\t {\n> +\t\t echo \"-$(git rev-parse $2)\"\n\nIs everybody's 'echo' happy with dash followed by unknown string?\n\n> +\t\t echo \"$(git rev-parse $1:dummy) dummy\"\n> +\t\t echo \"$(git rev-parse $1:file) file\"\n> +\t } |\n> +\t git pack-objects --stdout |\n> +\t git index-pack --stdin --fix-thin\n\nAn alternative\n\n\tgit pack-objects --stdout <<-EOF |\n\t-$(git rev-parse $2)\n $(git rev-parse $1:dummy) dummy\n $(git rev-parse $1:file) file\n\tEOF\n git index-pack --stdin --fix-thin\n\nlooks somewhat ugly, though.\n\n> +}\n"},{"id":"293688","messageId":"20160811044809.ep22lybdyfzmx4pl@sigill.intra.peff.net","threadId":"42956","inReplyTo":"xmqqbn107epz.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v3 0/2] pack-objects mru","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-11T04:48:09Z","receivedAt":"2016-08-11T04:48:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 10, 2016 at 09:47:52AM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> >> This is not new with this change, but I am not quite sure what in\n> >> the current code prevents us from busting the delta limit for reused\n> >> ones, though.\n> >\n> > I think in the current code you are limited by the depth you might find\n> > in a single existing pack (since we never reuse cross-pack deltas).\n> \n> Sorry for going deeper in the tangent, but I vaguely recall raising\n> it long time ago as a potential issue that delta reuse out of an\n> original pack created with deep delta chain may bust a delta chain\n> limit when repacking with shorter delta chain limit; I just do not\n> remember where that discussion went (i.e. decided to be a non-issue?\n> we added code to avoid it? etc.)\n\nDigging on the list and in the history, I found your e4c9327\n(pack-objects: avoid delta chains that are too long., 2006-02-17). That\napproach went away with Nico's 898b14c (pack-objects: rework\ncheck_delta_limit usage, 2007-04-16), which I think is where we are at\ntoday.\n\nI found the patches for both on the list, but no interesting discussion.\n\nIt looks like 898b14c does the depth check dynamically in find_delta. So\nwe would not build on a too-long chain, but I do not see anything that\nprevents us from creating a too-long chain purely out of reused deltas.\n\nWhich means that even without my patches, repacking with a shorter delta\nchain does not guarantee you do not have a longer chain. And mine\nintroduces a potential \"packs * max_depth\" problem (I also think\ncheck_delta_limit could recurse very deeply if given a pathologically\nweird pack that has insane delta limits, but presumably we would just\nrun out of stack and crash, which seems like an OK outcome for such\nmaliciousness).\n\nI guess it would not be that hard to break the reused chains as part of\nthe DFS search I introduced (we are recursing already; just stop\nrecursing and break when we hit the max-depth).\n\n> > However, I think with cross-pack deltas, you could have a situation\n> > like:\n> >\n> > pack 1: A -> B -> C\n> > pack 2: C -> D -> E\n> >\n> > and pick A and B from the first pack, and C, D, and E from the second.\n> > Then you end up with:\n> >\n> > A -> B -> C -> D -> E\n> >\n> > in the output. IOW, I think the absolute worst case chain is the\n> > max_depth times the number of packs.\n> \n> Also if pack1 and pack2 were created with depth limit of 3 and we\n> are repacking with depth limit of 2, then we are busting the limit\n> already with or without cross-pack chaining, I would think.\n\nRight, though that is at least bounded to \"what you packed with before\",\nwhich people do not usually change (OTOH, we accept packs from random\nstrangers via the protocol).\n\n-Peff\n"},{"id":"293689","messageId":"20160811050252.g3iusy7bp3j6tzte@sigill.intra.peff.net","threadId":"42956","inReplyTo":"xmqqr39w4bvx.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v3 1/2] pack-objects: break delta cycles before delta-search phase","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-11T05:02:52Z","receivedAt":"2016-08-11T05:03:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 10, 2016 at 01:17:22PM -0700, Junio C Hamano wrote:\n\n> > Actually, skimming the sha1_file code, I am not 100% sure that we detect\n> > cycles in OBJ_REF_DELTA (you cannot have cycles in OBJ_OFS_DELTA since\n> > they always point backwards in the pack). But if that is the case, then\n> > I think we should fix that, not worry about special-casing it here.\n> \n> Yes, but sha1_file.c? It is the reading side and it is too late if\n> we notice a problem, I would think.\n\nWe already are covered on the writing side. That is what your code in\nwrite_one() does. The reason to warn is on the reading side (\"I fixed\nthis for you, but by the way, your existing packs were bogus\").\n\nBut of more concern is whether read_sha1_file() would recurse\ninfinitely, which would be bad (though I do not think it would be a\nfeasible attack vector; index-pack already rejects such packs before\nthey are admitted to the repository).\n\n> > + * 2. Updating our size; check_object() will have filled in the size of our\n> > + * delta, but a non-delta object needs it true size.\n> \n> Excellent point.\n\nI was not clever enough to think of it; the pack-objects code is filled\nwith nice assertions (Thanks, Nico!) that help out when you are stupid. :)\n\nOne thing to be careful of is that there are more things this\ndrop_reused_delta() should be doing. But I looked through the rest of\ncheck_object() and could not find anything else.\n\n> > +\tcase DFS_ACTIVE:\n> > +\t\t/*\n> > +\t\t * We found a cycle that needs broken. It would be correct to\n> > +\t\t * break any link in the chain, but it's convenient to\n> > +\t\t * break this one.\n> > +\t\t */\n> > +\t\tdrop_reused_delta(entry);\n> > +\t\tbreak;\n> > +\t}\n> > +}\n> \n> Do we need to do anything to the DFS state of an entry when\n> drop_reused_delta() resets its other fields?\n\nGood catch. It should be marked DONE after we have broken the delta. It\ndoesn't matter in practice, because...\n\n> If we later find D that is directly based on A, wouldn't we end up\n> visiting A and attempt to drop it again? drop_reused_delta() is\n> idempotent so there will be no data structure corruption, I think,\n> but we can safely declare that the entry is now DONE after calling\n> drop_reused_delta() on it (either in the function or in the caller\n> after it calls the function), no?\n\nI think the idempotency of drop_reused_delta() doesn't matter. When we\nvisit A again later, its \"delta\" field will be NULL, so we'll hit the\ncondition at the top of the function: this is a base object, mark DONE\nand don't recurse.\n\nSo it's correct as-is, but I agree it feels weird that the DFS would end\nwith some objects potentially marked ACTIVE. Everything should be DONE\nat the end.\n\n> > +# Create a pack containing the the tree $1 and blob $1:file, with\n> > +# the latter stored as a delta against $2:file.\n> > +#\n> > +# We convince pack-objects to make the delta in the direction of our choosing\n> > +# by marking $2 as a preferred-base edge. That results in $1:file as a thin\n> > +# delta, and index-pack completes it by adding $2:file as a base.\n> \n> Tricky but clever and correct ;-)\n\nThanks, it took a long time to think up. ;)\n\nI actually wish we had better tools for making fake packs. Something\nwhere you could say \"add A, then add B as a delta of A, then...\".\nBecause you often have to jump through quite a few hoops to convince\npack-objects to generate the pack you want, and even some things are\nimpossible (for example, I would like to make a chain of 10 deltas; how\ndo I convince the delta search to put my objects in the right order?).\n\nI tried briefly yesterday to convince pack-objects to just take a list\nof objects and their deltas, but it got ugly very quickly. I think we'd\nbe better off writing a new tool that happens to reuse some of the\nformatting functions from pack-objects. But even then, we've got to\nwrite an .idx, which means going through index-pack (which will complain\nif we are writing bogus packs for testing odd situations), or we have to\nkeep a valid list of \"struct object_entry\" to feed to the idx writer.\n\nSo even that approach is not quite trivial.\n\n> > +make_pack () {\n> > +\t {\n> > +\t\t echo \"-$(git rev-parse $2)\"\n> \n> Is everybody's 'echo' happy with dash followed by unknown string?\n\nI'd assume so because it will be \"-\", and I think echoes which\ntake options are careful about that.\n\nStill, it would not be hard to tweak.\n\n> > +\t\t echo \"$(git rev-parse $1:dummy) dummy\"\n> > +\t\t echo \"$(git rev-parse $1:file) file\"\n> > +\t } |\n> > +\t git pack-objects --stdout |\n> > +\t git index-pack --stdin --fix-thin\n> \n> An alternative\n> \n> \tgit pack-objects --stdout <<-EOF |\n> \t-$(git rev-parse $2)\n> $(git rev-parse $1:dummy) dummy\n> $(git rev-parse $1:file) file\n> \tEOF\n> git index-pack --stdin --fix-thin\n> \n> looks somewhat ugly, though.\n\nYeah, I think we would be better to just switch to printf if we want to\nbe careful.\n\nI'll follow-up with a patch.\n\n-Peff\n"},{"id":"293690","messageId":"20160811051514.7f2llllaw7lmnsy2@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160811050252.g3iusy7bp3j6tzte@sigill.intra.peff.net","subject":"[PATCH v4 1/2] pack-objects: break delta cycles before delta-search phase","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-11T05:15:14Z","receivedAt":"2016-08-11T05:15:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 11, 2016 at 01:02:52AM -0400, Jeff King wrote:\n\n> Yeah, I think we would be better to just switch to printf if we want to\n> be careful.\n> \n> I'll follow-up with a patch.\n\nHere it is. It switches out the echos for printfs (which, ironically,\n_do_ complain about the \"-\" argument if you do so naively, but of course\nthe right way is \"printf '%s\\n' -whatever\").\n\nIt also sets the dfs_state flag to DONE after breaking a delta, as\ndiscussed.\n\nPatch 2/2 on top does not need any adjustment, so I won't bother sending\nit.\n\n-- >8 --\nSubject: [PATCH] pack-objects: break delta cycles before delta-search phase\n\nWe do not allow cycles in the delta graph of a pack (i.e., A\nis a delta of B which is a delta of A) for the obvious\nreason that you cannot actually access any of the objects in\nsuch a case.\n\nThere's a last-ditch attempt to notice cycles during the\nwrite phase, during which we issue a warning to the user and\nwrite one of the objects out in full. However, this is\n\"last-ditch\" for two reasons:\n\n 1. By this time, it's too late to find another delta for\n the object, so the resulting pack is larger than it\n otherwise could be.\n\n 2. The warning is there because this is something that\n _shouldn't_ ever happen. If it does, then either:\n\n a. a pack we are reusing deltas from had its own\n cycle\n\n b. we are reusing deltas from multiple packs, and\n we found a cycle among them (i.e., A is a delta of\n B in one pack, but B is a delta of A in another,\n and we choose to use both deltas).\n\n c. there is a bug in the delta-search code\n\n So this code serves as a final check that none of these\n things has happened, warns the user, and prevents us\n from writing a bogus pack.\n\nRight now, (2b) should never happen because of the static\nordering of packs in want_object_in_pack(). If two objects\nhave a delta relationship, then they must be in the same\npack, and therefore we will find them from that same pack.\n\nHowever, a future patch would like to change that static\nordering, which will make (2b) a common occurrence. In\npreparation, we should be able to handle those kinds of\ncycles better. This patch does by introducing a\ncycle-breaking step during the get_object_details() phase,\nwhen we are deciding which deltas can be reused. That gives\nus the chance to feed the objects into the delta search as\nif the cycle did not exist.\n\nWe'll leave the detection and warning in the write_object()\nphase in place, as it still serves as a check for case (2c).\n\nThis does mean we will stop warning for (2a). That case is\ncaused by bogus input packs, and we ideally would warn the\nuser about it. However, since those cycles show up after\npicking reusable deltas, they look the same as (2b) to us;\nour new code will break the cycles early and the last-ditch\ncheck will never see them.\n\nWe could do analysis on any cycles that we find to\ndistinguish the two cases (i.e., it is a bogus pack if and\nonly if every delta in the cycle is in the same pack), but\nwe don't need to. If there is a cycle inside a pack, we'll\nrun into problems not only reusing the delta, but accessing\nthe object data at all. So when we try to dig up the actual\nsize of the object, we'll hit that same cycle and kick in\nour usual complain-and-try-another-source code.\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 84 +++++++++++++++++++++++++++++\n pack-objects.h | 9 ++++\n t/t5314-pack-cycle-detection.sh | 113 ++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 206 insertions(+)\n create mode 100755 t/t5314-pack-cycle-detection.sh\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 4a63398..b8e4e41 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1495,6 +1495,83 @@ static int pack_offset_sort(const void *_a, const void *_b)\n \t\t\t(a->in_pack_offset > b->in_pack_offset);\n }\n \n+/*\n+ * Drop an on-disk delta we were planning to reuse. Naively, this would\n+ * just involve blanking out the \"delta\" field, but we have to deal\n+ * with two extra pieces of book-keeping:\n+ *\n+ * 1. Removing ourselves from the delta_sibling linked list.\n+ *\n+ * 2. Updating our size; check_object() will have filled in the size of our\n+ * delta, but a non-delta object needs it true size.\n+ */\n+static void drop_reused_delta(struct object_entry *entry)\n+{\n+\tstruct object_entry **p = &entry->delta->delta_child;\n+\tstruct pack_window *w_curs = NULL;\n+\n+\twhile (*p) {\n+\t\tif (*p == entry)\n+\t\t\t*p = (*p)->delta_sibling;\n+\t\telse\n+\t\t\tp = &(*p)->delta_sibling;\n+\t}\n+\tentry->delta = NULL;\n+\n+\tentry->size = get_size_from_delta(entry->in_pack, &w_curs,\n+\t\t\t entry->in_pack_offset + entry->in_pack_header_size);\n+\tunuse_pack(&w_curs);\n+\n+\t/*\n+\t * If we failed to get the size from this pack for whatever reason,\n+\t * fall back to sha1_object_info, which may find another copy. And if\n+\t * that fails, the error will be recorded in entry->type and dealt\n+\t * with in prepare_pack().\n+\t */\n+\tif (entry->size == 0)\n+\t\tentry->type = sha1_object_info(entry->idx.sha1, &entry->size);\n+}\n+\n+/*\n+ * Follow the chain of deltas from this entry onward, throwing away any links\n+ * that cause us to hit a cycle (as determined by the DFS state flags in\n+ * the entries).\n+ */\n+static void break_delta_cycles(struct object_entry *entry)\n+{\n+\t/* If it's not a delta, it can't be part of a cycle. */\n+\tif (!entry->delta) {\n+\t\tentry->dfs_state = DFS_DONE;\n+\t\treturn;\n+\t}\n+\n+\tswitch (entry->dfs_state) {\n+\tcase DFS_NONE:\n+\t\t/*\n+\t\t * This is the first time we've seen the object. We mark it as\n+\t\t * part of the active potential cycle and recurse.\n+\t\t */\n+\t\tentry->dfs_state = DFS_ACTIVE;\n+\t\tbreak_delta_cycles(entry->delta);\n+\t\tentry->dfs_state = DFS_DONE;\n+\t\tbreak;\n+\n+\tcase DFS_DONE:\n+\t\t/* object already examined, and not part of a cycle */\n+\t\tbreak;\n+\n+\tcase DFS_ACTIVE:\n+\t\t/*\n+\t\t * We found a cycle that needs broken. It would be correct to\n+\t\t * break any link in the chain, but it's convenient to\n+\t\t * break this one.\n+\t\t */\n+\t\tdrop_reused_delta(entry);\n+\t\tentry->dfs_state = DFS_DONE;\n+\t\tbreak;\n+\t}\n+}\n+\n static void get_object_details(void)\n {\n \tuint32_t i;\n@@ -1512,6 +1589,13 @@ static void get_object_details(void)\n \t\t\tentry->no_try_delta = 1;\n \t}\n \n+\t/*\n+\t * This must happen in a second pass, since we rely on the delta\n+\t * information for the whole list being completed.\n+\t */\n+\tfor (i = 0; i < to_pack.nr_objects; i++)\n+\t\tbreak_delta_cycles(&to_pack.objects[i]);\n+\n \tfree(sorted_by_offset);\n }\n \ndiff --git a/pack-objects.h b/pack-objects.h\nindex d1b98b3..cc9b9a9 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -27,6 +27,15 @@ struct object_entry {\n \tunsigned no_try_delta:1;\n \tunsigned tagged:1; /* near the very tip of refs */\n \tunsigned filled:1; /* assigned write-order */\n+\n+\t/*\n+\t * State flags for depth-first search used for analyzing delta cycles.\n+\t */\n+\tenum {\n+\t\tDFS_NONE = 0,\n+\t\tDFS_ACTIVE,\n+\t\tDFS_DONE\n+\t} dfs_state;\n };\n \n struct packing_data {\ndiff --git a/t/t5314-pack-cycle-detection.sh b/t/t5314-pack-cycle-detection.sh\nnew file mode 100755\nindex 0000000..f7dbdfb\n--- /dev/null\n+++ b/t/t5314-pack-cycle-detection.sh\n@@ -0,0 +1,113 @@\n+#!/bin/sh\n+\n+test_description='test handling of inter-pack delta cycles during repack\n+\n+The goal here is to create a situation where we have two blobs, A and B, with A\n+as a delta against B in one pack, and vice versa in the other. Then if we can\n+persuade a full repack to find A from one pack and B from the other, that will\n+give us a cycle when we attempt to reuse those deltas.\n+\n+The trick is in the \"persuade\" step, as it depends on the internals of how\n+pack-objects picks which pack to reuse the deltas from. But we can assume\n+that it does so in one of two general strategies:\n+\n+ 1. Using a static ordering of packs. In this case, no inter-pack cycles can\n+ happen. Any objects with a delta relationship must be present in the same\n+ pack (i.e., no \"--thin\" packs on disk), so we will find all related objects\n+ from that pack. So assuming there are no cycles within a single pack (and\n+ we avoid generating them via pack-objects or importing them via\n+ index-pack), then our result will have no cycles.\n+\n+ So this case should pass the tests no matter how we arrange things.\n+\n+ 2. Picking the next pack to examine based on locality (i.e., where we found\n+ something else recently).\n+\n+ In this case, we want to make sure that we find the delta versions of A and\n+ B and not their base versions. We can do this by putting two blobs in each\n+ pack. The first is a \"dummy\" blob that can only be found in the pack in\n+ question. And then the second is the actual delta we want to find.\n+\n+ The two blobs must be present in the same tree, not present in other trees,\n+ and the dummy pathname must sort before the delta path.\n+\n+The setup below focuses on case 2. We have two commits HEAD and HEAD^, each\n+which has two files: \"dummy\" and \"file\". Then we can make two packs which\n+contain:\n+\n+ [pack one]\n+ HEAD:dummy\n+ HEAD:file (as delta against HEAD^:file)\n+ HEAD^:file (as base)\n+\n+ [pack two]\n+ HEAD^:dummy\n+ HEAD^:file (as delta against HEAD:file)\n+ HEAD:file (as base)\n+\n+Then no matter which order we start looking at the packs in, we know that we\n+will always find a delta for \"file\", because its lookup will always come\n+immediately after the lookup for \"dummy\".\n+'\n+. ./test-lib.sh\n+\n+\n+\n+# Create a pack containing the the tree $1 and blob $1:file, with\n+# the latter stored as a delta against $2:file.\n+#\n+# We convince pack-objects to make the delta in the direction of our choosing\n+# by marking $2 as a preferred-base edge. That results in $1:file as a thin\n+# delta, and index-pack completes it by adding $2:file as a base.\n+#\n+# Note that the two variants of \"file\" must be similar enough to convince git\n+# to create the delta.\n+make_pack () {\n+\t{\n+\t\tprintf '%s\\n' \"-$(git rev-parse $2)\"\n+\t\tprintf '%s dummy\\n' \"$(git rev-parse $1:dummy)\"\n+\t\tprintf '%s file\\n' \"$(git rev-parse $1:file)\"\n+\t} |\n+\tgit pack-objects --stdout |\n+\tgit index-pack --stdin --fix-thin\n+}\n+\n+test_expect_success 'setup' '\n+\ttest-genrandom base 4096 >base &&\n+\tfor i in one two\n+\tdo\n+\t\t# we want shared content here to encourage deltas...\n+\t\tcp base file &&\n+\t\techo $i >>file &&\n+\n+\t\t# ...whereas dummy should be short, because we do not want\n+\t\t# deltas that would create duplicates when we --fix-thin\n+\t\techo $i >dummy &&\n+\n+\t\tgit add file dummy &&\n+\t\ttest_tick &&\n+\t\tgit commit -m $i ||\n+\t\treturn 1\n+\tdone &&\n+\n+\tmake_pack HEAD^ HEAD &&\n+\tmake_pack HEAD HEAD^\n+'\n+\n+test_expect_success 'repack' '\n+\t# We first want to check that we do not have any internal errors,\n+\t# and also that we do not hit the last-ditch cycle-breaking code\n+\t# in write_object(), which will issue a warning to stderr.\n+\t>expect &&\n+\tgit repack -ad 2>stderr &&\n+\ttest_cmp expect stderr &&\n+\n+\t# And then double-check that the resulting pack is usable (i.e.,\n+\t# we did not fail to notice any cycles). We know we are accessing\n+\t# the objects via the new pack here, because \"repack -d\" will have\n+\t# removed the others.\n+\tgit cat-file blob HEAD:file >/dev/null &&\n+\tgit cat-file blob HEAD^:file >/dev/null\n+'\n+\n+test_done\n-- \n2.9.2.790.gaa5bc72\n\n"},{"id":"293692","messageId":"20160811065751.p64bi3sngbeotwc3@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160811050252.g3iusy7bp3j6tzte@sigill.intra.peff.net","subject":"Re: [PATCH v3 1/2] pack-objects: break delta cycles before delta-search phase","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-11T06:57:52Z","receivedAt":"2016-08-11T06:57:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 11, 2016 at 01:02:52AM -0400, Jeff King wrote:\n\n> > > + * 2. Updating our size; check_object() will have filled in the size of our\n> > > + * delta, but a non-delta object needs it true size.\n> > \n> > Excellent point.\n> \n> I was not clever enough to think of it; the pack-objects code is filled\n> with nice assertions (Thanks, Nico!) that help out when you are stupid. :)\n> \n> One thing to be careful of is that there are more things this\n> drop_reused_delta() should be doing. But I looked through the rest of\n> check_object() and could not find anything else.\n\nArgh, I spoke too soon.\n\nIt is true that the size lookup is the only part of check_object()\nwe skip if we are reusing the delta. But what I didn't notice is that\nwhen we choose to reuse a delta, we overwrite entry->type (the real\ntype!) with the in_pack_type (OFS_DELTA, etc). We need to undo that so\nthat later stages see the real type.\n\nI'm not sure how my existing tests worked (I confirmed that they do\nindeed break the delta). It may be that only some code paths actually\ncare about the real type. But when playing with the depth-limit (which\nuses the same drop_reused_delta() helper), I managed to make some pretty\nbroken packs.\n\nSo please disregard the v4 patch I just sent; I haven't triggered it,\nbut I imagine it has the same problem, and I just didn't manage to\ntrigger it.\n\nI'll clean that up and send out a new series.\n\n-Peff\n"},{"id":"293704","messageId":"20160811092030.my5c4x6wplxaf7wz@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160811065751.p64bi3sngbeotwc3@sigill.intra.peff.net","subject":"[PATCH v5] pack-objects mru","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-11T09:20:30Z","receivedAt":"2016-08-11T09:20:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 11, 2016 at 02:57:51AM -0400, Jeff King wrote:\n\n> > One thing to be careful of is that there are more things this\n> > drop_reused_delta() should be doing. But I looked through the rest of\n> > check_object() and could not find anything else.\n> \n> Argh, I spoke too soon.\n> \n> It is true that the size lookup is the only part of check_object()\n> we skip if we are reusing the delta. But what I didn't notice is that\n> when we choose to reuse a delta, we overwrite entry->type (the real\n> type!) with the in_pack_type (OFS_DELTA, etc). We need to undo that so\n> that later stages see the real type.\n> \n> I'm not sure how my existing tests worked (I confirmed that they do\n> indeed break the delta). It may be that only some code paths actually\n> care about the real type. But when playing with the depth-limit (which\n> uses the same drop_reused_delta() helper), I managed to make some pretty\n> broken packs.\n> \n> So please disregard the v4 patch I just sent; I haven't triggered it,\n> but I imagine it has the same problem, and I just didn't manage to\n> trigger it.\n> \n> I'll clean that up and send out a new series.\n\nHere it is. It ended up needing a few preparatory patches.\n\n [1/4]: provide an initializer for \"struct object_info\"\n [2/4]: sha1_file: make packed_object_info public\n [3/4]: pack-objects: break delta cycles before delta-search phase\n [4/4]: pack-objects: use mru list when iterating over packs\n\nI had originally intended to include an extra patch to handle the\n--depth limits better. But after writing it, I'm not sure it's actually\na good idea. I'll post it as an addendum with more discussion.\n\n-Peff\n"},{"id":"293705","messageId":"20160811092434.dtb73p3jrskxy32f@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160811092030.my5c4x6wplxaf7wz@sigill.intra.peff.net","subject":"[PATCH v5 1/4] provide an initializer for \"struct object_info\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-11T09:24:35Z","receivedAt":"2016-08-11T09:24:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"An all-zero initializer is fine for this struct, but because\nthe first element is a pointer, call sites need to know to\nuse \"NULL\" instead of \"0\". Otherwise some static checkers\nlike \"sparse\" will complain; see d099b71 (Fix some sparse\nwarnings, 2013-07-18) for example. So let's provide an\ninitializer to make this easier to get right.\n\nBut let's also comment that memset() to zero is explicitly\nOK[1]. One of the callers embeds object_info in another\nstruct which is initialized via memset (expand_data in\nbuiltin/cat-file.c). Since our subset of C doesn't allow\nassignment from a compound literal, handling this in any\nother way is awkward, so we'd like to keep the ability to\ninitialize by memset(). By documenting this property, it\nshould make anybody who wants to change the initializer\nthink twice before doing so.\n\nThere's one other caller of interest. In parse_sha1_header(),\nwe did not initialize the struct fully in the first place.\nThis turned out not to be a bug because the sub-function it\ncalls does not look at any other fields except the ones we\ndid initialize. But that assumption might not hold in the\nfuture, so it's a dangerous construct. This patch switches\nit to initializing the whole struct, which protects us\nagainst unexpected reads of the other fields.\n\n[1] Obviously using memset() to initialize a pointer\n violates the C standard, but we long ago decided that it\n was an acceptable tradeoff in the real world.\n\nSigned-off-by: Jeff King \n---\n builtin/cat-file.c | 5 ++---\n cache.h | 7 +++++++\n sha1_file.c | 6 ++----\n streaming.c | 2 +-\n 4 files changed, 12 insertions(+), 8 deletions(-)\n\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 2dfe626..2cbc31e 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -28,7 +28,7 @@ static int cat_one_file(int opt, const char *exp_type, const char *obj_name,\n \tchar *buf;\n \tunsigned long size;\n \tstruct object_context obj_context;\n-\tstruct object_info oi = {NULL};\n+\tstruct object_info oi = OBJECT_INFO_INIT;\n \tstruct strbuf sb = STRBUF_INIT;\n \tunsigned flags = LOOKUP_REPLACE_OBJECT;\n \n@@ -378,8 +378,7 @@ static int batch_objects(struct batch_options *opt)\n \tdata.mark_query = 0;\n \n \tif (opt->all_objects) {\n-\t\tstruct object_info empty;\n-\t\tmemset(&empty, 0, sizeof(empty));\n+\t\tstruct object_info empty = OBJECT_INFO_INIT;\n \t\tif (!memcmp(&data.info, &empty, sizeof(empty)))\n \t\t\tdata.skip_object_info = 1;\n \t}\ndiff --git a/cache.h b/cache.h\nindex 95a0bd3..b2e4969 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1550,6 +1550,13 @@ struct object_info {\n \t\t} packed;\n \t} u;\n };\n+\n+/*\n+ * Initializer for a \"struct object_info\" that wants no items. You may\n+ * also memset() the memory to all-zeroes.\n+ */\n+#define OBJECT_INFO_INIT {NULL}\n+\n extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);\n \n /* Dumb servers support */\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 02940f1..b8cc76b 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1730,11 +1730,9 @@ static int parse_sha1_header_extended(const char *hdr, struct object_info *oi,\n \n int parse_sha1_header(const char *hdr, unsigned long *sizep)\n {\n-\tstruct object_info oi;\n+\tstruct object_info oi = OBJECT_INFO_INIT;\n \n \toi.sizep = sizep;\n-\toi.typename = NULL;\n-\toi.typep = NULL;\n \treturn parse_sha1_header_extended(hdr, &oi, LOOKUP_REPLACE_OBJECT);\n }\n \n@@ -2738,7 +2736,7 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,\n int sha1_object_info(const unsigned char *sha1, unsigned long *sizep)\n {\n \tenum object_type type;\n-\tstruct object_info oi = {NULL};\n+\tstruct object_info oi = OBJECT_INFO_INIT;\n \n \toi.typep = &type;\n \toi.sizep = sizep;\ndiff --git a/streaming.c b/streaming.c\nindex 811fcc2..431254b 100644\n--- a/streaming.c\n+++ b/streaming.c\n@@ -135,7 +135,7 @@ struct git_istream *open_istream(const unsigned char *sha1,\n \t\t\t\t struct stream_filter *filter)\n {\n \tstruct git_istream *st;\n-\tstruct object_info oi = {NULL};\n+\tstruct object_info oi = OBJECT_INFO_INIT;\n \tconst unsigned char *real = lookup_replace_object(sha1);\n \tenum input_source src = istream_source(real, type, &oi);\n \n-- \n2.9.2.790.gaa5bc72\n\n"},{"id":"293706","messageId":"20160811092531.5iudoerqgwej7fq4@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160811092030.my5c4x6wplxaf7wz@sigill.intra.peff.net","subject":"[PATCH v5 2/4] sha1_file: make packed_object_info public","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-11T09:25:32Z","receivedAt":"2016-08-11T09:25:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Some code may have a pack/offset pair for an object, but\nwould like to look up more information. Using\nsha1_object_info() is too heavy-weight; it starts from the\nsha1 and has to find the pack again (so not only does it waste\ntime, it might not even find the same instance).\n\nIn some cases, this problem is solved by helpers like\nget_size_from_delta(), which is used by pack-objects to take\na shortcut for objects whose packed representation has\nalready been found. But there's no similar function for\ngetting the object type, for instance. Rather than introduce\none, let's just make the whole packed_object_info() available.\nIt is smart enough to spend effort only on the items the\ncaller wants.\n\nSigned-off-by: Jeff King \n---\n cache.h | 1 +\n sha1_file.c | 4 ++--\n 2 files changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex b2e4969..f23968e 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1558,6 +1558,7 @@ struct object_info {\n #define OBJECT_INFO_INIT {NULL}\n \n extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);\n+extern int packed_object_info(struct packed_git *pack, off_t offset, struct object_info *);\n \n /* Dumb servers support */\n extern int update_server_info(int);\ndiff --git a/sha1_file.c b/sha1_file.c\nindex b8cc76b..5ca0ffa 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1970,8 +1970,8 @@ static enum object_type packed_to_object_type(struct packed_git *p,\n \tgoto out;\n }\n \n-static int packed_object_info(struct packed_git *p, off_t obj_offset,\n-\t\t\t struct object_info *oi)\n+int packed_object_info(struct packed_git *p, off_t obj_offset,\n+\t\t struct object_info *oi)\n {\n \tstruct pack_window *w_curs = NULL;\n \tunsigned long size;\n-- \n2.9.2.790.gaa5bc72\n\n"},{"id":"293707","messageId":"20160811092635.pq33zmfuimrxcvxa@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160811092030.my5c4x6wplxaf7wz@sigill.intra.peff.net","subject":"[PATCH v5 3/4] pack-objects: break delta cycles before delta-search phase","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-11T09:26:36Z","receivedAt":"2016-08-11T09:26:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We do not allow cycles in the delta graph of a pack (i.e., A\nis a delta of B which is a delta of A) for the obvious\nreason that you cannot actually access any of the objects in\nsuch a case.\n\nThere's a last-ditch attempt to notice cycles during the\nwrite phase, during which we issue a warning to the user and\nwrite one of the objects out in full. However, this is\n\"last-ditch\" for two reasons:\n\n 1. By this time, it's too late to find another delta for\n the object, so the resulting pack is larger than it\n otherwise could be.\n\n 2. The warning is there because this is something that\n _shouldn't_ ever happen. If it does, then either:\n\n a. a pack we are reusing deltas from had its own\n cycle\n\n b. we are reusing deltas from multiple packs, and\n we found a cycle among them (i.e., A is a delta of\n B in one pack, but B is a delta of A in another,\n and we choose to use both deltas).\n\n c. there is a bug in the delta-search code\n\n So this code serves as a final check that none of these\n things has happened, warns the user, and prevents us\n from writing a bogus pack.\n\nRight now, (2b) should never happen because of the static\nordering of packs in want_object_in_pack(). If two objects\nhave a delta relationship, then they must be in the same\npack, and therefore we will find them from that same pack.\n\nHowever, a future patch would like to change that static\nordering, which will make (2b) a common occurrence. In\npreparation, we should be able to handle those kinds of\ncycles better. This patch does by introducing a\ncycle-breaking step during the get_object_details() phase,\nwhen we are deciding which deltas can be reused. That gives\nus the chance to feed the objects into the delta search as\nif the cycle did not exist.\n\nWe'll leave the detection and warning in the write_object()\nphase in place, as it still serves as a check for case (2c).\n\nThis does mean we will stop warning for (2a). That case is\ncaused by bogus input packs, and we ideally would warn the\nuser about it. However, since those cycles show up after\npicking reusable deltas, they look the same as (2b) to us;\nour new code will break the cycles early and the last-ditch\ncheck will never see them.\n\nWe could do analysis on any cycles that we find to\ndistinguish the two cases (i.e., it is a bogus pack if and\nonly if every delta in the cycle is in the same pack), but\nwe don't need to. If there is a cycle inside a pack, we'll\nrun into problems not only reusing the delta, but accessing\nthe object data at all. So when we try to dig up the actual\nsize of the object, we'll hit that same cycle and kick in\nour usual complain-and-try-another-source code.\n\nSigned-off-by: Jeff King \n---\nThis has the DONE and printf fixes from v4, along with using\npacked_object_info() to fill in the correct type when drop a delta.\n\n builtin/pack-objects.c | 84 +++++++++++++++++++++++++++++\n pack-objects.h | 9 ++++\n t/t5314-pack-cycle-detection.sh | 113 ++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 206 insertions(+)\n create mode 100755 t/t5314-pack-cycle-detection.sh\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 4a63398..32c1dba 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1495,6 +1495,83 @@ static int pack_offset_sort(const void *_a, const void *_b)\n \t\t\t(a->in_pack_offset > b->in_pack_offset);\n }\n \n+/*\n+ * Drop an on-disk delta we were planning to reuse. Naively, this would\n+ * just involve blanking out the \"delta\" field, but we have to deal\n+ * with some extra book-keeping:\n+ *\n+ * 1. Removing ourselves from the delta_sibling linked list.\n+ *\n+ * 2. Updating our size/type to the non-delta representation. These were\n+ * either not recorded initially (size) or overwritten with the delta type\n+ * (type) when check_object() decided to reuse the delta.\n+ */\n+static void drop_reused_delta(struct object_entry *entry)\n+{\n+\tstruct object_entry **p = &entry->delta->delta_child;\n+\tstruct object_info oi = OBJECT_INFO_INIT;\n+\n+\twhile (*p) {\n+\t\tif (*p == entry)\n+\t\t\t*p = (*p)->delta_sibling;\n+\t\telse\n+\t\t\tp = &(*p)->delta_sibling;\n+\t}\n+\tentry->delta = NULL;\n+\n+\toi.sizep = &entry->size;\n+\toi.typep = &entry->type;\n+\tif (packed_object_info(entry->in_pack, entry->in_pack_offset, &oi) < 0) {\n+\t\t/*\n+\t\t * We failed to get the info from this pack for some reason;\n+\t\t * fall back to sha1_object_info, which may find another copy.\n+\t\t * And if that fails, the error will be recorded in entry->type\n+\t\t * and dealt with in prepare_pack().\n+\t\t */\n+\t\tentry->type = sha1_object_info(entry->idx.sha1, &entry->size);\n+\t}\n+}\n+\n+/*\n+ * Follow the chain of deltas from this entry onward, throwing away any links\n+ * that cause us to hit a cycle (as determined by the DFS state flags in\n+ * the entries).\n+ */\n+static void break_delta_chains(struct object_entry *entry)\n+{\n+\t/* If it's not a delta, it can't be part of a cycle. */\n+\tif (!entry->delta) {\n+\t\tentry->dfs_state = DFS_DONE;\n+\t\treturn;\n+\t}\n+\n+\tswitch (entry->dfs_state) {\n+\tcase DFS_NONE:\n+\t\t/*\n+\t\t * This is the first time we've seen the object. We mark it as\n+\t\t * part of the active potential cycle and recurse.\n+\t\t */\n+\t\tentry->dfs_state = DFS_ACTIVE;\n+\t\tbreak_delta_chains(entry->delta);\n+\t\tentry->dfs_state = DFS_DONE;\n+\t\tbreak;\n+\n+\tcase DFS_DONE:\n+\t\t/* object already examined, and not part of a cycle */\n+\t\tbreak;\n+\n+\tcase DFS_ACTIVE:\n+\t\t/*\n+\t\t * We found a cycle that needs broken. It would be correct to\n+\t\t * break any link in the chain, but it's convenient to\n+\t\t * break this one.\n+\t\t */\n+\t\tdrop_reused_delta(entry);\n+\t\tentry->dfs_state = DFS_DONE;\n+\t\tbreak;\n+\t}\n+}\n+\n static void get_object_details(void)\n {\n \tuint32_t i;\n@@ -1512,6 +1589,13 @@ static void get_object_details(void)\n \t\t\tentry->no_try_delta = 1;\n \t}\n \n+\t/*\n+\t * This must happen in a second pass, since we rely on the delta\n+\t * information for the whole list being completed.\n+\t */\n+\tfor (i = 0; i < to_pack.nr_objects; i++)\n+\t\tbreak_delta_chains(&to_pack.objects[i]);\n+\n \tfree(sorted_by_offset);\n }\n \ndiff --git a/pack-objects.h b/pack-objects.h\nindex d1b98b3..cc9b9a9 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -27,6 +27,15 @@ struct object_entry {\n \tunsigned no_try_delta:1;\n \tunsigned tagged:1; /* near the very tip of refs */\n \tunsigned filled:1; /* assigned write-order */\n+\n+\t/*\n+\t * State flags for depth-first search used for analyzing delta cycles.\n+\t */\n+\tenum {\n+\t\tDFS_NONE = 0,\n+\t\tDFS_ACTIVE,\n+\t\tDFS_DONE\n+\t} dfs_state;\n };\n \n struct packing_data {\ndiff --git a/t/t5314-pack-cycle-detection.sh b/t/t5314-pack-cycle-detection.sh\nnew file mode 100755\nindex 0000000..f7dbdfb\n--- /dev/null\n+++ b/t/t5314-pack-cycle-detection.sh\n@@ -0,0 +1,113 @@\n+#!/bin/sh\n+\n+test_description='test handling of inter-pack delta cycles during repack\n+\n+The goal here is to create a situation where we have two blobs, A and B, with A\n+as a delta against B in one pack, and vice versa in the other. Then if we can\n+persuade a full repack to find A from one pack and B from the other, that will\n+give us a cycle when we attempt to reuse those deltas.\n+\n+The trick is in the \"persuade\" step, as it depends on the internals of how\n+pack-objects picks which pack to reuse the deltas from. But we can assume\n+that it does so in one of two general strategies:\n+\n+ 1. Using a static ordering of packs. In this case, no inter-pack cycles can\n+ happen. Any objects with a delta relationship must be present in the same\n+ pack (i.e., no \"--thin\" packs on disk), so we will find all related objects\n+ from that pack. So assuming there are no cycles within a single pack (and\n+ we avoid generating them via pack-objects or importing them via\n+ index-pack), then our result will have no cycles.\n+\n+ So this case should pass the tests no matter how we arrange things.\n+\n+ 2. Picking the next pack to examine based on locality (i.e., where we found\n+ something else recently).\n+\n+ In this case, we want to make sure that we find the delta versions of A and\n+ B and not their base versions. We can do this by putting two blobs in each\n+ pack. The first is a \"dummy\" blob that can only be found in the pack in\n+ question. And then the second is the actual delta we want to find.\n+\n+ The two blobs must be present in the same tree, not present in other trees,\n+ and the dummy pathname must sort before the delta path.\n+\n+The setup below focuses on case 2. We have two commits HEAD and HEAD^, each\n+which has two files: \"dummy\" and \"file\". Then we can make two packs which\n+contain:\n+\n+ [pack one]\n+ HEAD:dummy\n+ HEAD:file (as delta against HEAD^:file)\n+ HEAD^:file (as base)\n+\n+ [pack two]\n+ HEAD^:dummy\n+ HEAD^:file (as delta against HEAD:file)\n+ HEAD:file (as base)\n+\n+Then no matter which order we start looking at the packs in, we know that we\n+will always find a delta for \"file\", because its lookup will always come\n+immediately after the lookup for \"dummy\".\n+'\n+. ./test-lib.sh\n+\n+\n+\n+# Create a pack containing the the tree $1 and blob $1:file, with\n+# the latter stored as a delta against $2:file.\n+#\n+# We convince pack-objects to make the delta in the direction of our choosing\n+# by marking $2 as a preferred-base edge. That results in $1:file as a thin\n+# delta, and index-pack completes it by adding $2:file as a base.\n+#\n+# Note that the two variants of \"file\" must be similar enough to convince git\n+# to create the delta.\n+make_pack () {\n+\t{\n+\t\tprintf '%s\\n' \"-$(git rev-parse $2)\"\n+\t\tprintf '%s dummy\\n' \"$(git rev-parse $1:dummy)\"\n+\t\tprintf '%s file\\n' \"$(git rev-parse $1:file)\"\n+\t} |\n+\tgit pack-objects --stdout |\n+\tgit index-pack --stdin --fix-thin\n+}\n+\n+test_expect_success 'setup' '\n+\ttest-genrandom base 4096 >base &&\n+\tfor i in one two\n+\tdo\n+\t\t# we want shared content here to encourage deltas...\n+\t\tcp base file &&\n+\t\techo $i >>file &&\n+\n+\t\t# ...whereas dummy should be short, because we do not want\n+\t\t# deltas that would create duplicates when we --fix-thin\n+\t\techo $i >dummy &&\n+\n+\t\tgit add file dummy &&\n+\t\ttest_tick &&\n+\t\tgit commit -m $i ||\n+\t\treturn 1\n+\tdone &&\n+\n+\tmake_pack HEAD^ HEAD &&\n+\tmake_pack HEAD HEAD^\n+'\n+\n+test_expect_success 'repack' '\n+\t# We first want to check that we do not have any internal errors,\n+\t# and also that we do not hit the last-ditch cycle-breaking code\n+\t# in write_object(), which will issue a warning to stderr.\n+\t>expect &&\n+\tgit repack -ad 2>stderr &&\n+\ttest_cmp expect stderr &&\n+\n+\t# And then double-check that the resulting pack is usable (i.e.,\n+\t# we did not fail to notice any cycles). We know we are accessing\n+\t# the objects via the new pack here, because \"repack -d\" will have\n+\t# removed the others.\n+\tgit cat-file blob HEAD:file >/dev/null &&\n+\tgit cat-file blob HEAD^:file >/dev/null\n+'\n+\n+test_done\n-- \n2.9.2.790.gaa5bc72\n\n"},{"id":"293708","messageId":"20160811092657.btqu3qsrdki654pq@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160811092030.my5c4x6wplxaf7wz@sigill.intra.peff.net","subject":"[PATCH v5 4/4] pack-objects: use mru list when iterating over packs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-11T09:26:57Z","receivedAt":"2016-08-11T09:27:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"In the original implementation of want_object_in_pack(), we\nalways looked for the object in every pack, so the order did\nnot matter for performance.\n\nAs of the last few patches, however, we can now often break\nout of the loop early after finding the first instance, and\navoid looking in the other packs at all. In this case, pack\norder can make a big difference, because we'd like to find\nthe objects by looking at as few packs as possible.\n\nThis patch switches us to the same packed_git_mru list that\nis now used by normal object lookups.\n\nHere are timings for p5303 on linux.git:\n\nTest HEAD^ HEAD\n------------------------------------------------------------------------\n5303.3: rev-list (1) 31.31(31.07+0.23) 31.28(31.00+0.27) -0.1%\n5303.4: repack (1) 40.35(38.84+2.60) 40.53(39.31+2.32) +0.4%\n5303.6: rev-list (50) 31.37(31.15+0.21) 31.41(31.16+0.24) +0.1%\n5303.7: repack (50) 58.25(68.54+2.03) 47.28(57.66+1.89) -18.8%\n5303.9: rev-list (1000) 31.91(31.57+0.33) 31.93(31.64+0.28) +0.1%\n5303.10: repack (1000) 304.80(376.00+3.92) 87.21(159.54+2.84) -71.4%\n\nThe rev-list numbers are unchanged, which makes sense (they\nare not exercising this code at all). The 50- and 1000-pack\nrepack cases show considerable improvement.\n\nThe single-pack repack case doesn't, of course; there's\nnothing to improve. In fact, it gives us a baseline for how\nfast we could possibly go. You can see that though rev-list\ncan approach the single-pack case even with 1000 packs,\nrepack doesn't. The reason is simple: the loop we are\noptimizing is only part of what the repack is doing. After\nthe \"counting\" phase, we do delta compression, which is much\nmore expensive when there are multiple packs, because we\nhave fewer deltas we can reuse (you can also see that these\nnumbers come from a multicore machine; the CPU times are\nmuch higher than the wall-clock times due to the delta\nphase).\n\nSo the good news is that in cases with many packs, we used\nto be dominated by the \"counting\" phase, and now we are\ndominated by the delta compression (which is faster, and\nwhich we have already parallelized).\n\nHere are similar numbers for git.git:\n\nTest HEAD^ HEAD\n---------------------------------------------------------------------\n5303.3: rev-list (1) 1.55(1.51+0.02) 1.54(1.53+0.00) -0.6%\n5303.4: repack (1) 1.82(1.80+0.08) 1.82(1.78+0.09) +0.0%\n5303.6: rev-list (50) 1.58(1.57+0.00) 1.58(1.56+0.01) +0.0%\n5303.7: repack (50) 2.50(3.12+0.07) 2.31(2.95+0.06) -7.6%\n5303.9: rev-list (1000) 2.22(2.20+0.02) 2.23(2.19+0.03) +0.5%\n5303.10: repack (1000) 10.47(16.78+0.22) 7.50(13.76+0.22) -28.4%\n\nNot as impressive in terms of percentage, but still\nmeasurable wins. If you look at the wall-clock time\nimprovements in the 1000-pack case, you can see that linux\nimproved by roughly 10x as many seconds as git. That's\nbecause it has roughly 10x as many objects, and we'd expect\nthis improvement to scale linearly with the number of\nobjects (since the number of packs is kept constant). It's\njust that the \"counting\" phase is a smaller percentage of\nthe total time spent for a git.git repack, and hence the\npercentage win is smaller.\n\nThe implementation itself is a straightforward use of the\nMRU code. We only bother marking a pack as used when we know\nthat we are able to break early out of the loop, for two\nreasons:\n\n 1. If we can't break out early, it does no good; we have\n to visit each pack anyway, so we might as well avoid\n even the minor overhead of managing the cache order.\n\n 2. The mru_mark() function reorders the list, which would\n screw up our traversal. So it is only safe to mark when\n we are about to break out of the loop. We could record\n the found pack and mark it after the loop finishes, of\n course, but that's more complicated and it doesn't buy\n us anything due to (1).\n\nNote that this reordering does have a potential impact on\nthe final pack, as we store only a single \"found\" pack for\neach object, even if it is present in multiple packs. In\nprinciple, any copy is acceptable, as they all refer to the\nsame content. But in practice, they may differ in whether\nthey are stored as deltas, against which base, etc. This may\nhave an impact on delta reuse, and even the delta search\n(since we skip pairs that were already in the same pack).\n\nIt's not clear whether this change of order would hurt or\neven help average cases, though. The most likely reason to\nhave duplicate objects is from the completion of thin packs\n(e.g., you have some objects in a \"base\" pack, then receive\nseveral pushes; the packs you receive may be thin on the\nwire, with deltas that refer to bases outside the pack, but\nwe complete them with duplicate base objects when indexing\nthem).\n\nIn such a case the current code would always find the thin\nduplicates (because we currently walk the packs in reverse\nchronological order). Whereas with this patch, some of those\nduplicates would be found in the base pack instead.\n\nIn my tests repacking a real-world case of linux.git with\n3600 thin-pack pushes (on top of a large \"base\" pack), the\nresulting pack was about 0.04% larger with this patch. On\nthe other hand, because we were more likely to hit the base\npack, there were more opportunities for delta reuse, and we\nhad 50,000 fewer objects to examine in the delta search.\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 10 +++++++---\n 1 file changed, 7 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 32c1dba..b745280 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -23,6 +23,7 @@\n #include \"reachable.h\"\n #include \"sha1-array.h\"\n #include \"argv-array.h\"\n+#include \"mru.h\"\n \n static const char *pack_usage[] = {\n \tN_(\"git pack-objects --stdout [...] [< | < ]\"),\n@@ -958,7 +959,7 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t\t\t struct packed_git **found_pack,\n \t\t\t off_t *found_offset)\n {\n-\tstruct packed_git *p;\n+\tstruct mru_entry *entry;\n \n \tif (!exclude && local && has_loose_object_nonlocal(sha1))\n \t\treturn 0;\n@@ -966,7 +967,8 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t*found_pack = NULL;\n \t*found_offset = 0;\n \n-\tfor (p = packed_git; p; p = p->next) {\n+\tfor (entry = packed_git_mru->head; entry; entry = entry->next) {\n+\t\tstruct packed_git *p = entry->item;\n \t\toff_t offset = find_pack_entry_one(sha1, p);\n \t\tif (offset) {\n \t\t\tif (!*found_pack) {\n@@ -993,8 +995,10 @@ static int want_object_in_pack(const unsigned char *sha1,\n \t\t\t * out of the loop to return 1 now.\n \t\t\t */\n \t\t\tif (!ignore_packed_keep &&\n-\t\t\t (!local || !have_non_local_packs))\n+\t\t\t (!local || !have_non_local_packs)) {\n+\t\t\t\tmru_mark(packed_git_mru, entry);\n \t\t\t\tbreak;\n+\t\t\t}\n \n \t\t\tif (local && !p->pack_local)\n \t\t\t\treturn 0;\n-- \n2.9.2.790.gaa5bc72\n"},{"id":"293709","messageId":"20160811095710.p2bffympjlwmv3gc@sigill.intra.peff.net","threadId":"42956","inReplyTo":"20160811092030.my5c4x6wplxaf7wz@sigill.intra.peff.net","subject":"Re: [PATCH v5] pack-objects mru","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-11T09:57:10Z","receivedAt":"2016-08-11T09:57:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 11, 2016 at 05:20:30AM -0400, Jeff King wrote:\n\n> Here it is. It ended up needing a few preparatory patches.\n> \n> [1/4]: provide an initializer for \"struct object_info\"\n> [2/4]: sha1_file: make packed_object_info public\n> [3/4]: pack-objects: break delta cycles before delta-search phase\n> [4/4]: pack-objects: use mru list when iterating over packs\n> \n> I had originally intended to include an extra patch to handle the\n> --depth limits better. But after writing it, I'm not sure it's actually\n> a good idea. I'll post it as an addendum with more discussion.\n\nAnd here's the depth patch. It does work, as you can see by running the\nsnippet at the bottom of the commit message.\n\nBut I began to wonder if it's actually a desirable thing. For instance,\nif you do:\n\n git gc --aggressive\n ... time passes ...\n git gc\n\nthe first gc may generate chains up to 250 objects. When the second gc\nruns (and you may not even run it yourself; it might be \"gc --auto\"!),\nit will generally reuse most of your existing deltas, even though the\ndefault depth is only 50.\n\nBut with the patch below, it will drop deltas from the middle of those\nlong chains, undoing the prior --aggressive results. Worse, we don't\nfind new deltas for those objects, because it falls afoul of the \"they\nare in the same pack, so don't bother looking for a delta\" rule.\n\nAn --aggressive repack of my git.git is 52MB. Repacking that with the\npatch below and \"--depth=50\" bumps it to 55MB. Dumping the \"do not\nbother\" condition in try_delta() drops that to 54MB.\n\nSo it _is_ worse for the space to drop those high-depth deltas. Even if\nwe fixed the \"do not bother\" (e.g., by recording a bit that says \"even\nthough these are in the same pack, try anyway, because we had to break\nthe delta for other reasons\"), it's still a loss.\n\nOTOH, I am not altogether convinced that the tradeoff of a giant --depth\nis worth. I'm looking only at the space here, but deeper delta chains\ncost more CPU to access (especially if they start to exceed the delta\ncache size). And the space savings aren't that amazing. Doing a \"git\nrepack -adf --depth=50 --window=250\" (i.e., if aggressive had just\ntweaked the window size and not the depth in the first place), the\nresult is only 53MB.\n\nSo considering \"--depth\" as a space-saving measure for --aggressive does\nnot seem that effective. But it feels weird to quietly drop actions\npeople might have done with previous aggressive runs.\n\n-- >8 --\nSubject: [PATCH] pack-objects: enforce --depth limit in reused deltas\n\nSince 898b14c (pack-objects: rework check_delta_limit usage,\n2007-04-16), we check the delta depth limit only when\nfiguring out whether we should make a new delta. We don't\nconsider it at all when reusing deltas, which means that\npacking once with --depth=50, and then against with\n--depth=10, the second pack my still contain chains larger\nthan 10.\n\nThis is probably not a huge deal, as it is limited to\nwhatever chains you happened to create in a previous run.\nBut as we start allowing cross-pack delta reuse in a future\ncommit, this maximum will rise to the number of packs times\nthe per-pack depth (in the worst case; on average, it will\nlikely be much smaller).\n\nWe can easily detect this as part of the existing search for\ncycles, since we visit every node in a depth-first way. That\nlets us compute the depth of any node based on the depth of\nits base, because we know the base is DFS_DONE by the time\nwe look at it (modulo any cycles in the graph, but we know\nthere cannot be any because we break them as we see them).\n\nThere is some subtlety worth mentioning, though. We record\nthe depth of each object as we compute it. It might seem\nlike we could save the per-object storage space by just\nkeeping track of the depth of our traversal (i.e., have\nbreak_delta_chains() report how deep it went). But we may\nvisit an object through multiple delta paths, and on\nsubsequent paths we want to know its depth immediately,\nwithout having to walk back down to its final base (doing so\nwould make our graph walk quadratic rather than linear).\n\nLikewise, one could try to record the depth not from the\nbase, but from our starting point (i.e., start\nrecursion_depth at 0, and pass \"recursion_depth + 1\" to each\ninvocation of break_delta_chains()). And then when\nrecursion_depth gets too big, we know that we must cut the\ndelta chain. But that technique is wrong if we do not visit\nthe nodes in topological order. In a chain A->B->C, it\nif we visit \"C\", then \"B\", then \"A\", we will never recurse\ndeeper than 1 link (because we see at each node that we have\nalready visited it).\n\nUnfortunately there is no automated test, because it's hard\nto convince pack-objects to reliably produce delta chains.\nNaively, it would seem that a sequence of ever-increasing\nblobs would work. E.g., something like:\n\n for i in 1 2 3 4 5; do\n test-genrandom $i 4096 >>file\n git add file\n git commit -m $i\n done\n\nwhere a reasonable set of deltas would use \"1:file\" as the\nbase, then \"2:file\" as a delta against that, \"3:file\" as a\ndelta against \"2:file\", and so on, until we have a chain\nwith length 5.\n\nBut the delta search is much more fickle than that. It tends\nto prefer deletions to additions (because they are smaller\nthan additions), so it prefers \"5:file\" as the base, and\nthen the deltas just say \"remove N bytes from the end\".\nMoreover, the delta search has heuristics that penalize\nincreasing depth. So packing the script above actually ends\nup with 2 chains of length 2.\n\nSo I've punted on adding an automated test. One can see the\neffect on a real-world repository by repacking it with a\nsmall --depth value, like:\n\n max_depth() {\n for i in .git/objects/pack/*.pack; do\n git verify-pack -v $i\n done |\n perl -lne '\n /chain length = (\\d+)/ or next;\n $max = $1 if $1 > $max;\n END { print $max }\n '\n }\n\n echo \"before: $(max_depth)\"\n git repack -ad --depth=5\n echo \"after: $(max_depth)\"\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 15 +++++++++++++++\n pack-objects.h | 4 ++++\n 2 files changed, 19 insertions(+)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 32c1dba..d8132a4 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1505,6 +1505,8 @@ static int pack_offset_sort(const void *_a, const void *_b)\n * 2. Updating our size/type to the non-delta representation. These were\n * either not recorded initially (size) or overwritten with the delta type\n * (type) when check_object() decided to reuse the delta.\n+ *\n+ * 3. Resetting our delta depth, as we are now a base object.\n */\n static void drop_reused_delta(struct object_entry *entry)\n {\n@@ -1518,6 +1520,7 @@ static void drop_reused_delta(struct object_entry *entry)\n \t\t\tp = &(*p)->delta_sibling;\n \t}\n \tentry->delta = NULL;\n+\tentry->depth = 0;\n \n \toi.sizep = &entry->size;\n \toi.typep = &entry->type;\n@@ -1536,6 +1539,9 @@ static void drop_reused_delta(struct object_entry *entry)\n * Follow the chain of deltas from this entry onward, throwing away any links\n * that cause us to hit a cycle (as determined by the DFS state flags in\n * the entries).\n+ *\n+ * We also detect too-long reused chains that would violate our --depth\n+ * limit.\n */\n static void break_delta_chains(struct object_entry *entry)\n {\n@@ -1553,6 +1559,15 @@ static void break_delta_chains(struct object_entry *entry)\n \t\t */\n \t\tentry->dfs_state = DFS_ACTIVE;\n \t\tbreak_delta_chains(entry->delta);\n+\n+\t\t/*\n+\t\t * Once we've recursed, our base knows its depth, so we can\n+\t\t * compute ours (and check it against the limit).\n+\t\t */\n+\t\tentry->depth = entry->delta->depth + 1;\n+\t\tif (entry->depth > depth)\n+\t\t\tdrop_reused_delta(entry);\n+\n \t\tentry->dfs_state = DFS_DONE;\n \t\tbreak;\n \ndiff --git a/pack-objects.h b/pack-objects.h\nindex cc9b9a9..03f1191 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -30,12 +30,16 @@ struct object_entry {\n \n \t/*\n \t * State flags for depth-first search used for analyzing delta cycles.\n+\t *\n+\t * The depth is measured in delta-links to the base (so if A is a delta\n+\t * against B, then A has a depth of 1, and B a depth of 0).\n \t */\n \tenum {\n \t\tDFS_NONE = 0,\n \t\tDFS_ACTIVE,\n \t\tDFS_DONE\n \t} dfs_state;\n+\tint depth;\n };\n \n struct packing_data {\n-- \n2.9.2.790.gaa5bc72\n\n"},{"id":"293721","messageId":"xmqqmvkj2vdm.fsf@gitster.mtv.corp.google.com","threadId":"42956","inReplyTo":"20160811095710.p2bffympjlwmv3gc@sigill.intra.peff.net","subject":"Re: [PATCH v5] pack-objects mru","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-08-11T15:11:33Z","receivedAt":"2016-08-11T15:11:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> So considering \"--depth\" as a space-saving measure for --aggressive does\n> not seem that effective. But it feels weird to quietly drop actions\n> people might have done with previous aggressive runs.\n\nThat argument cuts both ways, doesn't it?\n\nIf the user explicitly asks to use lower \"--depth\" from the command\nline when the second repack runs, the intention is clear: the\nexisting pack may use delta chains that are too long and is\ndetrimental to the run-time performance, and the user wants to\ncorrect it by repacking with shorter delta chain.\n\nShould the act of letting \"gc --auto\" use lower \"--depth\", by not\nconfiguring to always use deeper chain, be interpreted the same way?\nI am not sure. The old packing with large --depth is something the\nuser did long time ago, and the decision the user made not to use\nlarge depth always is also something the user did long time ago. I\ndo not think it is so cut-and-dried which one of the two conflicting\nwishes we should honor when running the second repack, especially\nwhen it is run unattended like \"gc --auto\" does.\n\n\n\n"},{"id":"293723","messageId":"20160811161903.zfam5ietxpa2yyqm@sigill.intra.peff.net","threadId":"42956","inReplyTo":"xmqqmvkj2vdm.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v5] pack-objects mru","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-08-11T16:19:03Z","receivedAt":"2016-08-11T16:19:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 11, 2016 at 08:11:33AM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > So considering \"--depth\" as a space-saving measure for --aggressive does\n> > not seem that effective. But it feels weird to quietly drop actions\n> > people might have done with previous aggressive runs.\n> \n> That argument cuts both ways, doesn't it?\n> \n> If the user explicitly asks to use lower \"--depth\" from the command\n> line when the second repack runs, the intention is clear: the\n> existing pack may use delta chains that are too long and is\n> detrimental to the run-time performance, and the user wants to\n> correct it by repacking with shorter delta chain.\n> \n> Should the act of letting \"gc --auto\" use lower \"--depth\", by not\n> configuring to always use deeper chain, be interpreted the same way?\n> I am not sure. The old packing with large --depth is something the\n> user did long time ago, and the decision the user made not to use\n> large depth always is also something the user did long time ago. I\n> do not think it is so cut-and-dried which one of the two conflicting\n> wishes we should honor when running the second repack, especially\n> when it is run unattended like \"gc --auto\" does.\n\nGood points. Explicitly saying \"repack --depth=...\" carries a lot more\nweight to me than \"git gc --auto\" randomly kicking in, as far as knowing\nthat what the user actually wants. My patch doesn't differentiate, of\ncourse, but I think it could.\n\nThe other problem with my patch is the fact that we don't do a good job\nof finding new, in-limit deltas for the ones we discard. If you want to\ndo that, you really need to \"git repack -f\" (at least with the current\ncode). At which point we do not reuse the on-disk deltas at all, and the\nproblem is moot (you could also interpret the fact that the user did\n_not_ pass \"-f\" as \"you want to reuse deltas, which means you want to\nreuse even long chains\", but as you've argued above, you can make a lot\nof guesses about the user's intention from what they did or did not\nsay).\n\nSo if we were to go this route, I don't think my patch is quite\nsufficient; we'd want something else on top to do a better job of\nfinding replacement deltas.\n\nRegarding my \"does not seem that effective\" above, I think we should\ndrop the aggressive depth to 50, and I just posted a patch with\nreasoning and numbers:\n\n http://public-inbox.org/git/20160811161309.ecmebaafcz6rkg6o@sigill.intra.peff.net/\n\nThat's maybe orthogonal, but it does remove the weird \"gc --aggressive\nfollowed by gc --auto produces a bad pack\" issue, because unless you are\ndoing something clever, the depth will always be 50 (modulo people who\ndid an aggressive pack with an older version of git :-/ ).\n\n-Peff\n"}]}