{"thread":{"id":"4703","subject":"Re: [RFC] Cache negative delta pairs","startedAt":"2006-06-29T03:09:43Z","lastAt":"2006-07-03T08:11:02Z","messageCount":36,"participants":["Junio C Hamano","Jeff King","Nicolas Pitre","Linus Torvalds","Joel Becker","Jakub Narebski","Johannes Schindelin","Andreas Ericsson"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"22767","messageId":"7v4py4y7wo.fsf@assigned-by-dhcp.cox.net","threadId":"4703","inReplyTo":"20060628223744.GA24421@coredump.intra.peff.net","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-29T03:09:43Z","receivedAt":"2006-06-29T03:09:43Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> From repack to repack, we end up trying to delta many of the same object\n> pairs, which is computationally expensive.\n>...\n> I found this especially to be a problem with repos that consist of many\n> large, unrelated files (e.g., photos). For example, on my test repo\n> (about 300 unrelated 1-2M jpgs), a 'git-repack -a' takes about 10\n> minutes to complete. With the delta cache, subsequent repacks take only\n> 13 seconds. Results are not quite as dramatic for \"normal\" repos, but\n> there is still some speedup. Repacking a fully packed linux-2.6 repo\n> went from 1m12s to 36s. Repacking the git repo goes from 5.6s to 3.0s.\n\nInteresting idea. I think this matters more because for a\nrepository with many unrelated undeltifiable files, we do the\ncomputation for objects that results in _no_ delta. For normal\nnearly fully packed repositories, once an object is deltified\nagainst something else, subsequent repacking of the same set of\nobjects (or a superset thereof) will very likely reuse the delta\nwithout recomputation, so as long as each object _can_ be\ndeltified with at least _one_ other object, you should not see\nimprovement on them.\n\nSo I am curious where the speed-up comes from for \"normal\" repos\nin your experiments. If it turns out that in \"normal\" repos the\nobjects that hit your negative cache are stored undeltified,\nthen that suggests that it might be worthwhile to consider using\na cache of \"inherently undeltifiable objects\", In other words, a\nnegative cache of O(N) entries, instead of O(N^2) entries,\n\nAnother interpretation of your result is that we may be using a\ndelta window that is unnecessarily too deep, and your negative\ncache is collecting less optimum candidates that we attempt to\ndeltify against \"just in case\". Can you easily instrument your\ncode to see where in the sorted delta candidate list the pairs\nthat hit your the negative cache are? That is, in find_deltas()\nfunction, we have \"while (--j > 0)\" loop that attempts to delta\nwith the entry that is j (modulo window size) entries away from\nthe current one, then j-1, j-2, ...; I am interested in the\ndistribution of \"j\" value for the pair \"n,m\" that hits your\nnegative cache for normal repositories, and I am speculating\nthat the value would probably be small relative to the delta\nwindow size.\n\nAnother idea is to have a cache of \"paths at which inherently\nundeltifiable objects live in\". For example, we currently do\nnot delta OpenOffice documents (*.odt, *.odp, etc) very well.\nIf one has a repository that tracks the history of \"file.odp\",\nwe know each revision of \"file.odp\" would not delta against any\nother version anyway, and could skip attempting to deltify them.\n\nYour message contained string \"*pt-in\" in the commentary part\n(replace asterisk with lowercase o) and was discarded by vger\nmailing list software because that was a taboo word. If you\nwould want to pursue this I would suggest to resend your\noriginal patch after rephrasing that part.\n\n> - size. The cache is a packed sequence of binary sha1 pairs. I was\n> concerned that it would grow too large (obviously for n blobs you can\n> end up with n^2/2 entries), but it doesn't seem unreasonable for most\n> repos (either you don't have a lot of files, or if you do, they delta\n> reasonably well). My test repo's cache is only 144K. The git cache is\n> about 2.7M. The linux-2.6 cache is 22M.\n\nThe fully-packed object database is 6.2M pack so you are talking\nabout 40% bloat; the kernel is 115M so the overhead is 19%.\n"},{"id":"22768","messageId":"20060629035002.GA29486@coredump.intra.peff.net","threadId":"4703","inReplyTo":"7v4py4y7wo.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-06-29T03:50:03Z","receivedAt":"2006-06-29T03:50:03Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 28, 2006 at 08:09:43PM -0700, Junio C Hamano wrote:\n\n> Interesting idea. I think this matters more because for a\n> repository with many unrelated undeltifiable files, we do the\n> computation for objects that results in _no_ delta. For normal\n\nYes, precisely.\n\n> So I am curious where the speed-up comes from for \"normal\" repos\n> in your experiments. If it turns out that in \"normal\" repos the\n\nI assumed they were either:\n - blobs of files with only a single revision\n - blobs with one \"island\" revision which is so different from previous\n revisions that it isn't worth a delta\nYou can get a (very rough) estimate on the former:\n $ cd linux-2.6 && git-rev-list --objects --all \\\n | grep / | cut -d' ' -f2 | sort | uniq -u | wc -l\n 8364\n\nAs I said, we may also be catching possible deltas at the edge of the\npack depth. I should maybe put the cache check closer to the\ncreate_delta call.\n\n> objects that hit your negative cache are stored undeltified,\n> then that suggests that it might be worthwhile to consider using\n> a cache of \"inherently undeltifiable objects\", In other words, a\n> negative cache of O(N) entries, instead of O(N^2) entries,\n\nThat would certainly be preferable, though I'm not convinced there\naren't objects which are deltifiable, but not right now (e.g., a file\nwith only one revision, but which will later get a revision).\n\nI'm not sure what would make a file inherently undeltifiable. But you\ncould put the O(N) cache in front of the other cache, and reduce the\nsize of N for the O(N^2) cache. \n\n> deltify against \"just in case\". Can you easily instrument your\n> code to see where in the sorted delta candidate list the pairs\n> that hit your the negative cache are? That is, in find_deltas()\n\nI'll look into that...\n\n> Another idea is to have a cache of \"paths at which inherently\n> undeltifiable objects live in\". For example, we currently do\n> not delta OpenOffice documents (*.odt, *.odp, etc) very well.\n> If one has a repository that tracks the history of \"file.odp\",\n> we know each revision of \"file.odp\" would not delta against any\n> other version anyway, and could skip attempting to deltify them.\n\nI thought about that, but I was trying to avoid \"clever\" heuristics that\ncan often be wrong. Case in point: my repo consists mainly of jpegs,\nmost of which will not delta. But for a few, I edited the exif header\nand they delta'd nicely against their previous revision.\n\n> Your message contained string \"*pt-in\" in the commentary part\n> (replace asterisk with lowercase o) and was discarded by vger\n> mailing list software because that was a taboo word. If you\n\nOops, I didn't know we were filtering. I'll resend in a moment.\n\n> > reasonably well). My test repo's cache is only 144K. The git cache is\n> > about 2.7M. The linux-2.6 cache is 22M.\n> The fully-packed object database is 6.2M pack so you are talking\n> about 40% bloat; the kernel is 115M so the overhead is 19%.\n\nYes, obviously if you're interested in maximal space saving, this is\nstupid for the classic git repo case (though it makes sense for repos\nwith few but very large blobs). However, if you assume that:\n 1. Packing is inherently space-saving and more-or-less required on\n large repos like linux-2.6 (which is 1.8G unpacked and 115M packed)\n 2. It saves time (36 seconds per repack on linux-2.6)\nthen a more reasonable question is \"do you want to spend 22M to save 30\nseconds every time you repack -a?\". Or, to really cook the numbers, you\ncan say that the cache is only wasting 1% versus an unpacked repo. :)\n\nI think it's reasonable that this should be an optional feature. For\nsome repos, it turns them from almost unusable to very fast. For others,\nit's a questionable space-time tradeoff (and for some pathological\ncases, it would probably turn the repo from usable to unusable).\n\n-Peff\n"},{"id":"22769","messageId":"20060629035849.GA30749@coredump.intra.peff.net","threadId":"4703","inReplyTo":"7v4py4y7wo.fsf@assigned-by-dhcp.cox.net","subject":"[RFC] Cache negative delta pairs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-06-29T03:58:49Z","receivedAt":"2006-06-29T03:58:49Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":">From repack to repack, we end up trying to delta many of the same object\npairs, which is computationally expensive. This patch makes a\npersistent cache, $GIT_DIR/delta-cache, which contains pairs of sha1\nhashes (the presence of a pair indicates that it's not worth trying to\ndelta those two objects).\n\nSigned-off-by: Jeff King \n---\n\n[This is a repost, since the original got caught by the list filter.]\n\nI found this especially to be a problem with repos that consist of many\nlarge, unrelated files (e.g., photos). For example, on my test repo\n(about 300 unrelated 1-2M jpgs), a 'git-repack -a' takes about 10\nminutes to complete. With the delta cache, subsequent repacks take only\n13 seconds. Results are not quite as dramatic for \"normal\" repos, but\nthere is still some speedup. Repacking a fully packed linux-2.6 repo\nwent from 1m12s to 36s. Repacking the git repo goes from 5.6s to 3.0s.\n\nHere are some of my thoughts:\n\n - speed. The implementation is quite fast. The sha1 pairs are stored\n sorted, and we mmap and binary search them. Certainly the extra time\n spent in lookup is justified by avoiding the delta attempts.\n\n - size. The cache is a packed sequence of binary sha1 pairs. I was\n concerned that it would grow too large (obviously for n blobs you can\n end up with n^2/2 entries), but it doesn't seem unreasonable for most\n repos (either you don't have a lot of files, or if you do, they delta\n reasonably well). My test repo's cache is only 144K. The git cache is\n about 2.7M. The linux-2.6 cache is 22M.\n\n Theoretically, I could bound the cache size and boot old entries.\n However, that means storing age information, which increases the\n required size. I think keeping it simple is best.\n\n - correctness. Currently the code uses the output of try_delta for\n negative caching. Should the cache checking be moved inside try_delta\n instead? This would give more control over which reasons to mark a\n delta negative (I believe right now hitting the depth limit will\n cause a negative mark; we should perhaps only do so if the content\n itself makes the delta unpalatable).\n \n - optionalness. Currently the delta-cache is always used. Since it is a\n space-time tradeoff, maybe it should be optional (it will have\n negligible performance and horrible size impact on a repo that\n consists of many very small but unrelated objects). Possible methods\n include:\n - enable cache saves only if .git/delta-cache is present; turn it\n on initially with 'touch .git/delta-cache'\n - config variable\n\n Makefile | 4 +-\n delta-cache.c | 119 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n delta-cache.h | 11 +++++\n pack-objects.c | 11 +++++\n 4 files changed, 142 insertions(+), 3 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex cde619c..39c4308 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -202,7 +202,7 @@ LIB_H = \\\n \tblob.h cache.h commit.h csum-file.h delta.h \\\n \tdiff.h object.h pack.h pkt-line.h quote.h refs.h \\\n \trun-command.h strbuf.h tag.h tree.h git-compat-util.h revision.h \\\n-\ttree-walk.h log-tree.h dir.h\n+\ttree-walk.h log-tree.h dir.h delta-cache.h\n \n DIFF_OBJS = \\\n \tdiff.o diff-lib.o diffcore-break.o diffcore-order.o \\\n@@ -217,7 +217,7 @@ LIB_OBJS = \\\n \tserver-info.o setup.o sha1_file.o sha1_name.o strbuf.o \\\n \ttag.o tree.o usage.o config.o environment.o ctype.o copy.o \\\n \tfetch-clone.o revision.o pager.o tree-walk.o xdiff-interface.o \\\n-\talloc.o $(DIFF_OBJS)\n+\talloc.o delta-cache.o $(DIFF_OBJS)\n \n BUILTIN_OBJS = \\\n \tbuiltin-log.o builtin-help.o builtin-count.o builtin-diff.o builtin-push.o \\\ndiff --git a/delta-cache.c b/delta-cache.c\nnew file mode 100644\nindex 0000000..d132867\n--- /dev/null\n+++ b/delta-cache.c\n@@ -0,0 +1,119 @@\n+#include \"delta-cache.h\"\n+#include \"cache.h\"\n+\n+static const unsigned char* disk_cache = 0;\n+static unsigned disk_cache_len = 0;\n+static unsigned char* mem_cache = 0;\n+static unsigned mem_cache_len = 0;\n+static unsigned mem_cache_alloc = 0;\n+\n+#define GETCACHE(c, n) (c+(40*n))\n+\n+static void disk_cache_init()\n+{\n+\tstatic int done = 0;\n+\tint fd;\n+\tstruct stat st;\n+\n+\tif (done) return;\n+\tdone = 1;\n+\n+\tfd = open(git_path(\"delta-cache\"), O_RDONLY);\n+\tif (fd < 0)\n+\t\treturn;\n+\tif (fstat(fd, &st) || (st.st_size == 0)) {\n+\t\tclose(fd);\n+\t\treturn;\n+\t}\n+\tdisk_cache = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tclose(fd);\n+\tif (disk_cache != MAP_FAILED)\n+\t\tdisk_cache_len = st.st_size / 40;\n+}\n+\n+static int\n+check_cache(const unsigned char* c, unsigned len, const unsigned char s[40])\n+{\n+\tint left, right, mid, cmp;\n+\n+\tleft = 0;\n+\tright = len - 1;\n+\twhile (left <= right) {\n+\t\tmid = left + (right - left) / 2;\n+\t\tcmp = memcmp(s, GETCACHE(c, mid), 40);\n+\t\tif(cmp == 0) return 1;\n+\t\telse if(cmp < 0) right = mid - 1;\n+\t\telse left = mid + 1;\n+\t}\n+\treturn 0;\n+}\n+\n+extern int\n+delta_cache_check(const unsigned char a[20], const unsigned char b[20])\n+{\n+\tunsigned char search[40];\n+\n+\tdisk_cache_init();\n+\tmemcpy(search, a, 20);\n+\tmemcpy(search+20, b, 20);\n+\treturn check_cache(disk_cache, disk_cache_len, search);\n+}\n+\n+extern void\n+delta_cache_mark(const unsigned char a[20], const unsigned char b[20])\n+{\n+\tif (mem_cache_len == mem_cache_alloc) {\n+\t\tmem_cache_alloc = mem_cache_alloc ? mem_cache_alloc * 2 : 16;\n+\t\tmem_cache = xrealloc(mem_cache, mem_cache_alloc * 40);\n+\t}\n+\tmemcpy(GETCACHE(mem_cache, mem_cache_len), a, 20);\n+\tmemcpy(GETCACHE(mem_cache, mem_cache_len)+20, b, 20);\n+\tmem_cache_len++;\n+}\n+\n+static int\n+compare_sha1pair(const void *a, const void *b)\n+{\n+\treturn memcmp(a, b, 40);\n+}\n+\n+static int\n+merge_write(int fd, const unsigned char* p1, unsigned n1,\n+\t\t const unsigned char* p2, unsigned n2)\n+{\n+#define EMIT(p, x) do { \\\n+\tif (xwrite(fd, GETCACHE(p, x), 40) < 0) return -1; x++; \\\n+\t} while(0)\n+\n+\tint i = 0, j = 0, cmp;\n+\twhile (i < n1 && j < n2) {\n+\t\tcmp = memcmp(GETCACHE(p1, i), GETCACHE(p2, j), 40);\n+\t\tif (cmp < 0) EMIT(p1, i);\n+\t\telse EMIT(p2, j);\n+\t}\n+\twhile (i < n1) EMIT(p1, i);\n+\twhile (j < n2) EMIT(p2, j);\n+#undef EMIT\n+\treturn 0;\n+}\n+\n+extern void\n+delta_cache_save(void)\n+{\n+\tint fd;\n+\tchar tmpfile[PATH_MAX];\n+\n+\tstrcpy(tmpfile, git_path(\"delta-cache.%u\", getpid()));\n+\tfd = open(tmpfile, O_WRONLY|O_EXCL|O_CREAT, 0666);\n+\tif (fd < 0)\n+\t\treturn;\n+\n+\tqsort(mem_cache, mem_cache_len, 40, compare_sha1pair);\n+\tif (merge_write(fd, mem_cache, mem_cache_len,\n+\t\t\t disk_cache, disk_cache_len) < 0) {\n+\t\tclose(fd);\n+\t\treturn;\n+\t}\n+\n+\trename(tmpfile, git_path(\"delta-cache\"));\n+}\ndiff --git a/delta-cache.h b/delta-cache.h\nnew file mode 100644\nindex 0000000..19201be\n--- /dev/null\n+++ b/delta-cache.h\n@@ -0,0 +1,11 @@\n+#ifndef DELTA_CACHE_H\n+#define DELTA_CACHE_H\n+\n+extern int\n+delta_cache_check(const unsigned char a[20], const unsigned char b[20]);\n+extern void\n+delta_cache_mark(const unsigned char a[20], const unsigned char b[20]);\n+extern void\n+delta_cache_save(void);\n+\n+#endif /* DELTA_CACHE_H */\ndiff --git a/pack-objects.c b/pack-objects.c\nindex bed2497..46b9775 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -8,6 +8,7 @@ #include \"delta.h\"\n #include \"pack.h\"\n #include \"csum-file.h\"\n #include \"tree-walk.h\"\n+#include \"delta-cache.h\"\n #include \n #include \n \n@@ -1083,14 +1084,21 @@ static void find_deltas(struct object_en\n \t\tj = window;\n \t\twhile (--j > 0) {\n \t\t\tunsigned int other_idx = idx + j;\n+\t\t\tint r;\n \t\t\tstruct unpacked *m;\n \t\t\tif (other_idx >= window)\n \t\t\t\tother_idx -= window;\n \t\t\tm = array + other_idx;\n \t\t\tif (!m->entry)\n \t\t\t\tbreak;\n-\t\t\tif (try_delta(n, m, m->index, depth) < 0)\n+\t\t\tif (delta_cache_check(n->entry->sha1, m->entry->sha1))\n+\t\t\t\tcontinue;\n+\t\t\tr = try_delta(n, m, m->index, depth);\n+\t\t\tif (r < 0)\n \t\t\t\tbreak;\n+\t\t\tif (r == 0)\n+\t\t\t\tdelta_cache_mark(n->entry->sha1,\n+\t\t\t\t\t\t m->entry->sha1);\n \t\t}\n \t\t/* if we made n a delta, and if n is already at max\n \t\t * depth, leaving it in the window is pointless. we\n@@ -1342,5 +1350,6 @@ int main(int argc, char **argv)\n \tif (progress)\n \t\tfprintf(stderr, \"Total %d, written %d (delta %d), reused %d (delta %d)\\n\",\n \t\t\tnr_result, written, written_delta, reused, reused_delta);\n+\tdelta_cache_save();\n \treturn 0;\n }\n-- \n1.4.1.rc1.g3000\n"},{"id":"22770","messageId":"20060629040959.GA32156@coredump.intra.peff.net","threadId":"4703","inReplyTo":"7v4py4y7wo.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-06-29T04:09:59Z","receivedAt":"2006-06-29T04:09:59Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 28, 2006 at 08:09:43PM -0700, Junio C Hamano wrote:\n\n> that hit your the negative cache are? That is, in find_deltas()\n> function, we have \"while (--j > 0)\" loop that attempts to delta\n> with the entry that is j (modulo window size) entries away from\n> the current one, then j-1, j-2, ...; I am interested in the\n> distribution of \"j\" value for the pair \"n,m\" that hits your\n> negative cache for normal repositories, and I am speculating\n> that the value would probably be small relative to the delta\n> window size.\n\nJust to make sure I am understanding you correctly, you're interested in\nthe distribution of 'j' each time we skip a delta for being negative\n(or each time we mark a negative, but that should simply equal the\nlookup times for the next run). The instrumentation I added simply\nprints the value of j each time we skip a delta. The counts are\nsurprisingly uniform (this is for linux-2.6):\n 57209 j=1\n 57213 j=2\n 57217 j=3\n 57221 j=4\n 57225 j=5\n 57229 j=6\n 57233 j=7\n 57237 j=8\n 57241 j=9\n 57245 j=10\nThey're so uniform (and in order by j!) that I feel like I must have done\nsomething wrong...\n\n-Peff\n"},{"id":"22771","messageId":"20060629043053.GA32630@coredump.intra.peff.net","threadId":"4703","inReplyTo":"20060629035849.GA30749@coredump.intra.peff.net","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-06-29T04:30:53Z","receivedAt":"2006-06-29T04:30:53Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 28, 2006 at 11:58:49PM -0400, Jeff King wrote:\n\n> about 2.7M. The linux-2.6 cache is 22M.\n> [...]\n> - correctness. Currently the code uses the output of try_delta for\n> negative caching. Should the cache checking be moved inside try_delta\n> instead? This would give more control over which reasons to mark a\n\nI tried moving the cache check/mark to wrap the call to create_delta in\ntry_delta. The speedup is the same (since all of the CPU time is spent\nin create_delta anyway), and the linux-2.6 cache size dropped to 18M.\nI also think this is probably more correct (it ignores every reason not\nto delta EXCEPT create_delta failing).\n\nThe distribution of the window parameter 'j' is similarly uniform:\n 44900 j=2\n 44907 j=3\n 44943 j=1\n 45001 j=4\n 45014 j=5\n 45023 j=6\n 45063 j=7\n 45158 j=8\n 45288 j=9\n 45466 j=10\n\nPatch on top of my other one is below.\n\n-Peff\n\n-- >8 --\npack-objects: move delta-cache check/mark closer to create_delta\n\nSigned-off-by: Jeff King \n---\n pack-objects.c | 15 ++++++---------\n 1 files changed, 6 insertions(+), 9 deletions(-)\n\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 46b9775..83ccc8a 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -1014,9 +1014,13 @@ static int try_delta(struct unpacked *tr\n \tif (sizediff >= max_size)\n \t\treturn 0;\n \n+\tif (delta_cache_check(src->entry->sha1, trg->entry->sha1))\n+\t\treturn 0;\n \tdelta_buf = create_delta(src_index, trg->data, size, &delta_size, max_size);\n-\tif (!delta_buf)\n+\tif (!delta_buf) {\n+\t\tdelta_cache_mark(src->entry->sha1, trg->entry->sha1);\n \t\treturn 0;\n+\t}\n \n \ttrg_entry->delta = src_entry;\n \ttrg_entry->delta_size = delta_size;\n@@ -1084,21 +1088,14 @@ static void find_deltas(struct object_en\n \t\tj = window;\n \t\twhile (--j > 0) {\n \t\t\tunsigned int other_idx = idx + j;\n-\t\t\tint r;\n \t\t\tstruct unpacked *m;\n \t\t\tif (other_idx >= window)\n \t\t\t\tother_idx -= window;\n \t\t\tm = array + other_idx;\n \t\t\tif (!m->entry)\n \t\t\t\tbreak;\n-\t\t\tif (delta_cache_check(n->entry->sha1, m->entry->sha1))\n-\t\t\t\tcontinue;\n-\t\t\tr = try_delta(n, m, m->index, depth);\n-\t\t\tif (r < 0)\n+\t\t\tif (try_delta(n, m, m->index, depth) < 0)\n \t\t\t\tbreak;\n-\t\t\tif (r == 0)\n-\t\t\t\tdelta_cache_mark(n->entry->sha1,\n-\t\t\t\t\t\t m->entry->sha1);\n \t\t}\n \t\t/* if we made n a delta, and if n is already at max\n \t\t * depth, leaving it in the window is pointless. we\n-- \n1.4.1.rc1.g0458-dirty\n"},{"id":"22800","messageId":"Pine.LNX.4.64.0606291053280.1213@localhost.localdomain","threadId":"4703","inReplyTo":"7v4py4y7wo.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-06-29T15:42:14Z","receivedAt":"2006-06-29T15:42:14Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 28 Jun 2006, Junio C Hamano wrote:\n\n> Interesting idea. I think this matters more because for a\n> repository with many unrelated undeltifiable files, we do the\n> computation for objects that results in _no_ delta. For normal\n> nearly fully packed repositories, once an object is deltified\n> against something else, subsequent repacking of the same set of\n> objects (or a superset thereof) will very likely reuse the delta\n> without recomputation, so as long as each object _can_ be\n> deltified with at least _one_ other object, you should not see\n> improvement on them.\n> \n> So I am curious where the speed-up comes from for \"normal\" repos\n> in your experiments.\n\nMy GIT repo currently has 23622 objects and 7610 of them are currently \nundeltified. Those objects are of course candidates for delta matching \neach time git-repack is run.\n\n> If it turns out that in \"normal\" repos the\n> objects that hit your negative cache are stored undeltified,\n> then that suggests that it might be worthwhile to consider using\n> a cache of \"inherently undeltifiable objects\", In other words, a\n> negative cache of O(N) entries, instead of O(N^2) entries,\n\nActually... I'm not so sure. Those objects are not \"inherently \nundeltifiable\". They just happen to not have other objects to easily \ndelta against in the given set of objects. Think of a file with only \none revision for example. As soon as there is a second revision of that \nfile added to the set of objects then the former revision would have a \nhigh probability of being deltifiable.\n\nSo the negative cache should not be O(N^2) either. It just has to be \nO(N*window).\n\n> Another interpretation of your result is that we may be using a\n> delta window that is unnecessarily too deep, and your negative\n> cache is collecting less optimum candidates that we attempt to\n> deltify against \"just in case\". Can you easily instrument your\n> code to see where in the sorted delta candidate list the pairs\n> that hit your the negative cache are? That is, in find_deltas()\n> function, we have \"while (--j > 0)\" loop that attempts to delta\n> with the entry that is j (modulo window size) entries away from\n> the current one, then j-1, j-2, ...; I am interested in the\n> distribution of \"j\" value for the pair \"n,m\" that hits your\n> negative cache for normal repositories, and I am speculating\n> that the value would probably be small relative to the delta\n> window size.\n\nMy past experiments showed that the best window size for compression is \na bit larger than the current default of 10. It was rather around 15 \nfor the kernel repository, with higher values than 15 not providing \nsignificant improvements anymore. But that is clearly a function of the \nrepository nature (the average number of revisions for each file). But \nthe window size is directly connected to the computational cost.\n\n> Another idea is to have a cache of \"paths at which inherently\n> undeltifiable objects live in\". For example, we currently do\n> not delta OpenOffice documents (*.odt, *.odp, etc) very well.\n> If one has a repository that tracks the history of \"file.odp\",\n> we know each revision of \"file.odp\" would not delta against any\n> other version anyway, and could skip attempting to deltify them.\n\nI'm afraid this could lead to bad behavior eventually. Better to just \nattempt a delta once, and when an object has not found any delta \nbase candidate then just write its sha1 and corresponding window to the \ncache. This would imply an initial cost to create the cache the first \ntime, but after that the created cache could be relied upon as hard \ninformation and not just as guess heuristics.\n\n> > - size. The cache is a packed sequence of binary sha1 pairs. I was\n> > concerned that it would grow too large (obviously for n blobs you can\n> > end up with n^2/2 entries), but it doesn't seem unreasonable for most\n> > repos (either you don't have a lot of files, or if you do, they delta\n> > reasonably well). My test repo's cache is only 144K. The git cache is\n> > about 2.7M. The linux-2.6 cache is 22M.\n\nThis is way suboptimal. First there is no reason for the cache to ever \ngrow to N^2. At worst it should be N*10 where 10 is the current window \nsize.\n\nNext I think this can be made just N*2. Consider that the criteria for \nskipping over delta matching for a given object is the fact \nthat we already know that such object doesn't delta against \nnone of the objects found in a given window. Therefore we only have to \ncompute a hash for the object names found in that window and store that \nin the cache. So the cache entries would then be a pair of sha1: first \nthe sha1 of the victim object, and the sha1 of all sha1 names for the \nobjects against which the victim object was found not to delta well \nagainst.\n\nAnd this can be pushed even further by just including the sha1 of the \nvictim object inside the list of objects therefore computing a hash of \nall objects (the victim and the window) for which no delta results. The \ncache is therefore a list of hash values corresponding to bad \nvictim+window combinations.\n\nSo given my GIT repository such a cache would be 7610 * 40 = 304400 \nbytes if we stick to the full 40 bytes of sha1 to hash bad combinations.\n\n\nNicolas\n"},{"id":"22803","messageId":"Pine.LNX.4.64.0606291233120.1213@localhost.localdomain","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291053280.1213@localhost.localdomain","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-06-29T16:35:36Z","receivedAt":"2006-06-29T16:35:36Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 29 Jun 2006, Nicolas Pitre wrote:\n\n> And this can be pushed even further by just including the sha1 of the \n> victim object inside the list of objects therefore computing a hash of \n> all objects (the victim and the window) for which no delta results. The \n> cache is therefore a list of hash values corresponding to bad \n> victim+window combinations.\n> \n> So given my GIT repository such a cache would be 7610 * 40 = 304400 \n> bytes if we stick to the full 40 bytes of sha1 to hash bad combinations.\n\nCorrection: the 40 bytes figure is for _ascii_ representation of sha1 \nvalues. The cache doesn't need ascii and therefore this number can be \nreduced by half.\n\n\nNicolas\n"},{"id":"22805","messageId":"Pine.LNX.4.64.0606291154510.1213@localhost.localdomain","threadId":"4703","inReplyTo":"20060629035849.GA30749@coredump.intra.peff.net","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-06-29T16:39:31Z","receivedAt":"2006-06-29T16:39:31Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 28 Jun 2006, Jeff King wrote:\n\n> >From repack to repack, we end up trying to delta many of the same object\n> pairs, which is computationally expensive. This patch makes a\n> persistent cache, $GIT_DIR/delta-cache, which contains pairs of sha1\n> hashes (the presence of a pair indicates that it's not worth trying to\n> delta those two objects).\n\nI think this could be done differently to be even more space efficient \nas I suggested earlier.\n\n> Here are some of my thoughts:\n> \n> - speed. The implementation is quite fast. The sha1 pairs are stored\n> sorted, and we mmap and binary search them. Certainly the extra time\n> spent in lookup is justified by avoiding the delta attempts.\n\nYou do that lookup for every delta match attempt. Instead it could be \ndone once for the whole window attempt, potentially reducing the cache \nsize by a factor of 20, and it might be faster too.\n\n> - size. The cache is a packed sequence of binary sha1 pairs. I was\n> concerned that it would grow too large (obviously for n blobs you can\n> end up with n^2/2 entries), but it doesn't seem unreasonable for most\n> repos (either you don't have a lot of files, or if you do, they delta\n> reasonably well). My test repo's cache is only 144K. The git cache is\n> about 2.7M. The linux-2.6 cache is 22M.\n\nSee my previous email for comments about this.\n\n> Theoretically, I could bound the cache size and boot old entries.\n> However, that means storing age information, which increases the\n> required size. I think keeping it simple is best.\n\nYou could simply recreate the cache on each run. Or just keep a bitmap \nof referenced cache entries, and a list of new entries. At the end if \nthe new entry list is empty and the bitmap is all set (or clear) then \nyou just keep the current cache. ONce, say, more than 10% of cache \nentries are not used anymore then you regenerate the cache. But since \nyou need to regenerate it when new entries are added then the 10% unused \nentry criteria might not be used that often anyway, unless packs shrink \nwith time which might not be the case really often.\n\n> - correctness. Currently the code uses the output of try_delta for\n> negative caching. Should the cache checking be moved inside try_delta\n> instead? This would give more control over which reasons to mark a\n> delta negative (I believe right now hitting the depth limit will\n> cause a negative mark; we should perhaps only do so if the content\n> itself makes the delta unpalatable).\n\nLike I said earlier I think this should be moved up a bit i.e. outside \nthe delta loop. In find_deltas() right before the ...\n\n\t\tj = window;\n\t\twhile (--j > 0) {\n\nloop, just insert another loop that compute the sha1 of the current \ntarget object and window:\n\n\t\tSHA1_Init(&c);\n\t\tj = window;\n\t\twhile (j-- > 0) { /* postdec include the current object as well */\n\t\t\tunsigned int other_idx = idx + j;\n\t\t\tstruct unpacked *m;\n\t\t\tif (other_idx >= window)\n\t\t\t\tother_idx -= window;\n\t\t\tm = array + other_idx;\n\t\t\tif (!m->entry)\n\t\t\t\tbreak;\n\t\t\tSHA1_Update(&c, m->entry.sha1, 20);\n\t\t}\n\t\tSHA1_Final(negative_delta_hash, &c);\t\t\t\n\nThen you can skip over the whole of the delta loop right away if that \nnegative_delta_hash matches one entry in the cache since you already \nknow that this object with this window doesn't produce any delta result.\n\nOtherwise, after the delta loop has proceeded, if there is no delta \nfound then you can add negative_delta_hash to the cache.\n\n> - optionalness. Currently the delta-cache is always used. Since it is a\n> space-time tradeoff, maybe it should be optional (it will have\n> negligible performance and horrible size impact on a repo that\n> consists of many very small but unrelated objects). Possible methods\n> include:\n> - enable cache saves only if .git/delta-cache is present; turn it\n> on initially with 'touch .git/delta-cache'\n> - config variable\n\nFirst, I think it should be ignored (but still created) when \n--no-reuse-delta is passed. Then, it should not be created (but still \nlooked up if it exists and --no-reuse-delta is not provided) when the \npack index file is also not created. I don't think it is worth making \nthis further configurable, and given the suggested strategy above the \ncache should remain fairly small.\n\n\nNicolas\n"},{"id":"22808","messageId":"20060629180011.GA4392@coredump.intra.peff.net","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291053280.1213@localhost.localdomain","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-06-29T18:00:11Z","receivedAt":"2006-06-29T18:00:11Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 29, 2006 at 11:42:14AM -0400, Nicolas Pitre wrote:\n\n> So the negative cache should not be O(N^2) either. It just has to be \n> O(N*window).\n\nYes, unless we use the cache information to change the window (but I\ndon't think that's worth it, unless our window heuristics are bad).\nThe implementation I posted should already grow to O(N*window), since it\nonly saves what we try (and fail at).\n\n> My past experiments showed that the best window size for compression is \n> a bit larger than the current default of 10. It was rather around 15 \n> for the kernel repository, with higher values than 15 not providing \n> significant improvements anymore. But that is clearly a function of the \n> repository nature (the average number of revisions for each file). But \n> the window size is directly connected to the computational cost.\n\nIncreasing the window, of course, has virtually no speed impact on later\nrepacks with the cache in effect. Packing with a window of 15 drops my\nlinux-2.6 pack to 108M from 122M. That helps offset the cache size\n(though of course it takes longer on the initial pack).\n\n> This is way suboptimal. First there is no reason for the cache to ever \n> grow to N^2. At worst it should be N*10 where 10 is the current window \n> size.\n\nI assumed the window would change over time (though our total is still\nlikely to hang around N*10 rather than N^2).\n\n> none of the objects found in a given window. Therefore we only have to \n> compute a hash for the object names found in that window and store that \n> in the cache. So the cache entries would then be a pair of sha1: first \n> the sha1 of the victim object, and the sha1 of all sha1 names for the \n> objects against which the victim object was found not to delta well \n> against.\n\nThis will fail to hit the cache anytime the window changes. How often\ndoes the window change? In my test case, I would think anytime I added a\nbunch of new photos, it would be likely that one of them would make it\ninto the window, thus invalidating the cache entry and forcing me to try\nagainst every object in the window (even though I've already tried\n9/10).\n\nAlso, is it true to say \"if this object did not delta against this\nwindow, it will never delta?\" What about interactions with the depth\nparameter?\n\n> So given my GIT repository such a cache would be 7610 * 40 = 304400 \n> bytes if we stick to the full 40 bytes of sha1 to hash bad combinations.\n\nKeep in mind that it will grow every time the window changes.\n\n-Peff\n"},{"id":"22809","messageId":"20060629180719.GB4392@coredump.intra.peff.net","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291154510.1213@localhost.localdomain","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-06-29T18:07:19Z","receivedAt":"2006-06-29T18:07:19Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 29, 2006 at 12:39:31PM -0400, Nicolas Pitre wrote:\n\n> You do that lookup for every delta match attempt. Instead it could be \n> done once for the whole window attempt, potentially reducing the cache \n> size by a factor of 20, and it might be faster too.\n\nI'm not convinced this will provide good cache hit characteristics, and\nI'm not convinced it's semantically correct (see my other mail).\n\n> You could simply recreate the cache on each run. Or just keep a bitmap \n\nYes, that would probably work and would be quite easy to do with the\nexisting code.\n\n> First, I think it should be ignored (but still created) when \n> --no-reuse-delta is passed. Then, it should not be created (but still \n> looked up if it exists and --no-reuse-delta is not provided) when the \n> pack index file is also not created. I don't think it is worth making \n> this further configurable, and given the suggested strategy above the \n> cache should remain fairly small.\n\nThose suggestions make sense to me.\n\n-Peff\n"},{"id":"22815","messageId":"Pine.LNX.4.64.0606291410420.1213@localhost.localdomain","threadId":"4703","inReplyTo":"20060629180011.GA4392@coredump.intra.peff.net","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-06-29T18:24:57Z","receivedAt":"2006-06-29T18:24:57Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 29 Jun 2006, Jeff King wrote:\n\n> > This is way suboptimal. First there is no reason for the cache to ever \n> > grow to N^2. At worst it should be N*10 where 10 is the current window \n> > size.\n> \n> I assumed the window would change over time (though our total is still\n> likely to hang around N*10 rather than N^2).\n\nIt doesn't change unless you force a different window size.\n\n> > none of the objects found in a given window. Therefore we only have to \n> > compute a hash for the object names found in that window and store that \n> > in the cache. So the cache entries would then be a pair of sha1: first \n> > the sha1 of the victim object, and the sha1 of all sha1 names for the \n> > objects against which the victim object was found not to delta well \n> > against.\n> \n> This will fail to hit the cache anytime the window changes. How often\n> does the window change? In my test case, I would think anytime I added a\n> bunch of new photos, it would be likely that one of them would make it\n> into the window, thus invalidating the cache entry and forcing me to try\n> against every object in the window (even though I've already tried\n> 9/10).\n\nSure. But on the lot how often will that happen?\nThis trades a bit of CPU for much smaller cache which might be worth it.\n\nAnd even then, since my suggested method implies only one cache lookup \nin a much smaller cache instead of 10 lookups in a larger cache for each \nobjects it might end up faster overall even if sometimes some windows \ndon't match and deltas are recomputed needlessly.\n\n> Also, is it true to say \"if this object did not delta against this\n> window, it will never delta?\" What about interactions with the depth\n> parameter?\n\nOf course a greater depth might allow for a hit where there isn't any \notherwise. But changing the delta depth is not something someone does \nthat often, and when the depth is changed then you better use -f with \ngit-repack as well which like I said should also ignore the cache.\n\n> > So given my GIT repository such a cache would be 7610 * 40 = 304400 \n> > bytes if we stick to the full 40 bytes of sha1 to hash bad combinations.\n> \n> Keep in mind that it will grow every time the window changes.\n\nWhat do you mean by window change?\n\n\nNicolas\n"},{"id":"22819","messageId":"Pine.LNX.4.64.0606291444370.1213@localhost.localdomain","threadId":"4703","inReplyTo":"20060629180719.GB4392@coredump.intra.peff.net","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-06-29T18:48:23Z","receivedAt":"2006-06-29T18:48:23Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 29 Jun 2006, Jeff King wrote:\n\n> On Thu, Jun 29, 2006 at 12:39:31PM -0400, Nicolas Pitre wrote:\n> \n> > You do that lookup for every delta match attempt. Instead it could be \n> > done once for the whole window attempt, potentially reducing the cache \n> > size by a factor of 20, and it might be faster too.\n> \n> I'm not convinced this will provide good cache hit characteristics, and\n> I'm not convinced it's semantically correct (see my other mail).\n\nDare to test it? I provided you with most of the code difference \nalready.\n\nAnd what do you mean by \"semantically correct\"?\n\n\nNicolas\n"},{"id":"22820","messageId":"20060629185335.GA6704@coredump.intra.peff.net","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291410420.1213@localhost.localdomain","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-06-29T18:53:35Z","receivedAt":"2006-06-29T18:53:35Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 29, 2006 at 02:24:57PM -0400, Nicolas Pitre wrote:\n\n> > I assumed the window would change over time (though our total is still\n> > likely to hang around N*10 rather than N^2).\n> It doesn't change unless you force a different window size.\n\nSorry, I meant \"the items in the window for a given object would change\nover time.\" \n\n> > This will fail to hit the cache anytime the window changes. How often\n> > does the window change? In my test case, I would think anytime I added a\n> > bunch of new photos, it would be likely that one of them would make it\n> > into the window, thus invalidating the cache entry and forcing me to try\n> > against every object in the window (even though I've already tried\n> > 9/10).\n> Sure. But on the lot how often will that happen?\n\nReasonably often, according to my test. I did this to simulate usage\nover time:\n - create an empty repo\n - from my test repo of 515 images, grab 20 at a time and add/commit\n them\n - after each commit, record the SHA1 of (object, window[0..n]) for\n each object to be delta'd\nIf doing the cache on the sha1 of the whole window is a good idea, then\nwe should see many of the same hashes from commit to commit. If we\ndon't, that means the newly added files are being placed in the old\nwindows, thus disrupting their hashes.\n\nThe results were that there was typically only 1 reusable window each\ntime I added 20 files. At that point, caching is largely pointless.\n\n> And even then, since my suggested method implies only one cache lookup \n> in a much smaller cache instead of 10 lookups in a larger cache for each \n> objects it might end up faster overall even if sometimes some windows \n> don't match and deltas are recomputed needlessly.\n\nI didn't benchmark, but I doubt it will have significant impact.\nEspecially on my photo test repo, the lookups are dominated by the\ncreate_delta time by several orders of magnitude.\n\n> Of course a greater depth might allow for a hit where there isn't any \n> otherwise. But changing the delta depth is not something someone does \n> that often, and when the depth is changed then you better use -f with \n> git-repack as well which like I said should also ignore the cache.\n\nThat sounds reasonable to me for depth. What about other reasons for\ntry_delta to fail? Preferred base?\n\n> > > So given my GIT repository such a cache would be 7610 * 40 = 304400 \n> > > bytes if we stick to the full 40 bytes of sha1 to hash bad combinations.\n> > Keep in mind that it will grow every time the window changes.\n> What do you mean by window change?\n\nI meant that when the window we use for a given object changes, it will\ninsert a new cache entry. But if we deal with invalidating unused cache\nentries as you suggested before, it won't matter.\n\n-Peff\n"},{"id":"22821","messageId":"20060629185759.GB6704@coredump.intra.peff.net","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291444370.1213@localhost.localdomain","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-06-29T18:58:00Z","receivedAt":"2006-06-29T18:58:00Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 29, 2006 at 02:48:23PM -0400, Nicolas Pitre wrote:\n\n> Dare to test it? I provided you with most of the code difference \n> already.\n\nSee my other mail. Unless I did something horribly wrong, caching full\nwindows is largely useless.\n\n> And what do you mean by \"semantically correct\"?\n\nI mean that right now the cache means \"calling create_delta on content\nthat has sha1_a against content that has sha1_b will not produce a\nuseful delta.\" That makes sense since the content is never going to\nchange for a given sha1. However, covering the whole window takes into\naccount depth and preferred base. We just need to be sure that it is\ncorrect to be including those in our cache calculation (I don't know,\nand I'll defer to your judgement on that, since you clearly know more\nabout the delta logic than I do).\n\n-Peff\n"},{"id":"22822","messageId":"Pine.LNX.4.64.0606291458110.1213@localhost.localdomain","threadId":"4703","inReplyTo":"20060629185335.GA6704@coredump.intra.peff.net","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-06-29T19:04:15Z","receivedAt":"2006-06-29T19:04:15Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 29 Jun 2006, Jeff King wrote:\n\n> On Thu, Jun 29, 2006 at 02:24:57PM -0400, Nicolas Pitre wrote:\n> \n> > > I assumed the window would change over time (though our total is still\n> > > likely to hang around N*10 rather than N^2).\n> > It doesn't change unless you force a different window size.\n> \n> Sorry, I meant \"the items in the window for a given object would change\n> over time.\" \n> \n> > > This will fail to hit the cache anytime the window changes. How often\n> > > does the window change? In my test case, I would think anytime I added a\n> > > bunch of new photos, it would be likely that one of them would make it\n> > > into the window, thus invalidating the cache entry and forcing me to try\n> > > against every object in the window (even though I've already tried\n> > > 9/10).\n> > Sure. But on the lot how often will that happen?\n> \n> Reasonably often, according to my test. I did this to simulate usage\n> over time:\n> - create an empty repo\n> - from my test repo of 515 images, grab 20 at a time and add/commit\n> them\n> - after each commit, record the SHA1 of (object, window[0..n]) for\n> each object to be delta'd\n> If doing the cache on the sha1 of the whole window is a good idea, then\n> we should see many of the same hashes from commit to commit. If we\n> don't, that means the newly added files are being placed in the old\n> windows, thus disrupting their hashes.\n> \n> The results were that there was typically only 1 reusable window each\n> time I added 20 files. At that point, caching is largely pointless.\n\nRight. Your use pattern is a special case that doesn't work well with \nthe whole window hash approach. I'd expect it to work beautifully with \nthe kernel repository though.\n\n> > And even then, since my suggested method implies only one cache lookup \n> > in a much smaller cache instead of 10 lookups in a larger cache for each \n> > objects it might end up faster overall even if sometimes some windows \n> > don't match and deltas are recomputed needlessly.\n> \n> I didn't benchmark, but I doubt it will have significant impact.\n> Especially on my photo test repo, the lookups are dominated by the\n> create_delta time by several orders of magnitude.\n\nAgain I think it is a repo like the linux kernel that would benefit \nmore.\n\n> > Of course a greater depth might allow for a hit where there isn't any \n> > otherwise. But changing the delta depth is not something someone does \n> > that often, and when the depth is changed then you better use -f with \n> > git-repack as well which like I said should also ignore the cache.\n> \n> That sounds reasonable to me for depth. What about other reasons for\n> try_delta to fail? Preferred base?\n\nHmmm. That might need to be dealth with (easily but still).\n\n\nNicolas\n"},{"id":"22823","messageId":"Pine.LNX.4.64.0606291505070.1213@localhost.localdomain","threadId":"4703","inReplyTo":"20060629185759.GB6704@coredump.intra.peff.net","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-06-29T19:06:31Z","receivedAt":"2006-06-29T19:06:31Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 29 Jun 2006, Jeff King wrote:\n\n> On Thu, Jun 29, 2006 at 02:48:23PM -0400, Nicolas Pitre wrote:\n> \n> > Dare to test it? I provided you with most of the code difference \n> > already.\n> \n> See my other mail. Unless I did something horribly wrong, caching full\n> windows is largely useless.\n\n... on your special photo repository I agree.\n\nI'm still unconvinced for large repos though.\n\n\nNicolas\n"},{"id":"22826","messageId":"20060629195201.GA10786@coredump.intra.peff.net","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291458110.1213@localhost.localdomain","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-06-29T19:52:01Z","receivedAt":"2006-06-29T19:52:01Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 29, 2006 at 03:04:15PM -0400, Nicolas Pitre wrote:\n\n> Right. Your use pattern is a special case that doesn't work well with \n> the whole window hash approach. I'd expect it to work beautifully with \n> the kernel repository though.\n\nI don't necessarily care about the kernel repository. It packs fine as\nit is, and you only waste 30 seconds on a repack checking deltas that\ncould be avoided. I do care on my special repository where packing is\nvirtually unusable and I can achieve a 45x speedup. Maybe my original\ncaching is not worth it for the kernel and should be configurable,\nbut obviously this window caching cannot REPLACE mine since it fails\nutterly for the one thing I wanted it for.\n\nThat being said, I'm not sure that window caching is all that great for\n\"normal\" repos.\n\nSame test as before, but instead of simulating the commits, I merely\nlooked at the window hashes produced by \n git-rev-list --objects master~$x\n\nFor the git repo:\nx=0 tries 6698 windows\nx=0 and x=50 contain 5197 identical windows\nx=0 and x=100 contain 2484 identical windows\nx=0 and x=500 contain 455 identical windows\n\nFor linux-2.6 repo:\nx=0 tries 57208 windows\nx=0 and x=50 contain 53677 identical windows\nx=0 and x=100 contain 52886 identical windows\nx=0 and x=500 contain 41196 identical windows\n\nObviously the kernel repo is doing better, but x=500 is only 4 days ago.\nTrying with --before=2.weeks.ago yields only 31505 matches.\n\nSo the windows do clearly experience a fair bit of churn, but whether or\nnot this is worth it depends on how long you think is reasonable before\nsomething gets \"churned out\" .\n\n-Peff\n"},{"id":"22833","messageId":"Pine.LNX.4.64.0606291616480.1213@localhost.localdomain","threadId":"4703","inReplyTo":"20060629195201.GA10786@coredump.intra.peff.net","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-06-29T20:24:01Z","receivedAt":"2006-06-29T20:24:01Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 29 Jun 2006, Jeff King wrote:\n\n> On Thu, Jun 29, 2006 at 03:04:15PM -0400, Nicolas Pitre wrote:\n> \n> > Right. Your use pattern is a special case that doesn't work well with \n> > the whole window hash approach. I'd expect it to work beautifully with \n> > the kernel repository though.\n> \n> I don't necessarily care about the kernel repository. It packs fine as\n> it is, and you only waste 30 seconds on a repack checking deltas that\n> could be avoided. I do care on my special repository where packing is\n> virtually unusable and I can achieve a 45x speedup. Maybe my original\n> caching is not worth it for the kernel and should be configurable,\n> but obviously this window caching cannot REPLACE mine since it fails\n> utterly for the one thing I wanted it for.\n\nAnd I agreed with you already.\n\n> That being said, I'm not sure that window caching is all that great for\n> \"normal\" repos.\n> \n> Same test as before, but instead of simulating the commits, I merely\n> looked at the window hashes produced by \n> git-rev-list --objects master~$x\n> \n> For the git repo:\n> x=0 tries 6698 windows\n> x=0 and x=50 contain 5197 identical windows\n> x=0 and x=100 contain 2484 identical windows\n> x=0 and x=500 contain 455 identical windows\n> \n> For linux-2.6 repo:\n> x=0 tries 57208 windows\n> x=0 and x=50 contain 53677 identical windows\n> x=0 and x=100 contain 52886 identical windows\n> x=0 and x=500 contain 41196 identical windows\n> \n> Obviously the kernel repo is doing better, but x=500 is only 4 days ago.\n> Trying with --before=2.weeks.ago yields only 31505 matches.\n\nWhat does this prove? I fail to see the relation between those results \nand a possible git-pack-objects improvement.\n\nThe negative delta cache concept is certainly attractive even for normal \nrepositories, especially for public servers, since when used in \nconjonction with delta reuse it makes the creation of a pack basically \nfree. So I think this idea really has merits, as long as the cache \nremains small.\n\n\nNicolas\n"},{"id":"22836","messageId":"Pine.LNX.4.64.0606291352110.12404@g5.osdl.org","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291616480.1213@localhost.localdomain","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-29T21:04:01Z","receivedAt":"2006-06-29T21:04:01Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOn Thu, 29 Jun 2006, Nicolas Pitre wrote:\n> \n> The negative delta cache concept is certainly attractive even for normal \n> repositories, especially for public servers, since when used in \n> conjonction with delta reuse it makes the creation of a pack basically \n> free. So I think this idea really has merits, as long as the cache \n> remains small.\n\nI don't really see much of a point of this all.\n\nInstead of having a separate cache, wouldn't it be much better to just \ntake the hint from the previous pack-file?\n\nIn the repacking window, if both objects we are looking at already came \nfrom the same (old) pack-file, don't bother delta'ing them against each \nother. \n\nThat means that we'll still always check for better deltas for (and \nagainst!) _unpacked_ objects, but assuming incremental repacks, you'll \navoid the delta creation 99% of the time.\n\nIe somethng really simple like the appended.\n\n\t\tLinus\n---\ndiff --git a/pack-objects.c b/pack-objects.c\nindex bed2497..cea63e7 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -988,6 +988,13 @@ static int try_delta(struct unpacked *tr\n \t\treturn -1;\n \n \t/*\n+\t * We do not bother to try a delta that we discarded\n+\t * on an earlier try\n+\t */\n+\tif (trg_entry->in_pack && trg_entry->in_pack == src_entry->in_pack)\n+\t\treturn -1;\n+\n+\t/*\n \t * If the current object is at pack edge, take the depth the\n \t * objects that depend on the current object into account --\n \t * otherwise they would become too deep.\n"},{"id":"22837","messageId":"Pine.LNX.4.64.0606291723060.1213@localhost.localdomain","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291352110.12404@g5.osdl.org","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-06-29T21:24:23Z","receivedAt":"2006-06-29T21:24:23Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 29 Jun 2006, Linus Torvalds wrote:\n\n> Instead of having a separate cache, wouldn't it be much better to just \n> take the hint from the previous pack-file?\n\nDOH! ;-)\n\n\nNicolas\n"},{"id":"22838","messageId":"7vbqsbpsaa.fsf@assigned-by-dhcp.cox.net","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291616480.1213@localhost.localdomain","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-29T21:26:37Z","receivedAt":"2006-06-29T21:26:37Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> The negative delta cache concept is certainly attractive even for normal \n> repositories, especially for public servers, since when used in \n> conjonction with delta reuse it makes the creation of a pack basically \n> free. So I think this idea really has merits, as long as the cache \n> remains small.\n\nYes, I agree it is very attractive.\n\nOne thing to watch out for is that we probably would not want to\nlet git-daemon write into public repositories. Which means that\nuse of negative cache should be strict \"opt-in\".\n\n - \"$GIT_DIR/delta-cache\" is read but not necessarily is written\n back when it exists; git-daemon uses it that way.\n\n - The owner of the repository shouldn't have to tell the tool\n to update the negative cache every time repack happens.\n\nWhich suggests that pack-objects.c can learn an option that\ntells it to call delta_cache_save(), and we use it in\ngit-repack, perhaps like this:\n\ndiff --git a/git-repack.sh b/git-repack.sh\nindex 640ad8d..b07ed9b 100755\n--- a/git-repack.sh\n+++ b/git-repack.sh\n@@ -44,7 +44,7 @@ case \",$all_into_one,\" in\n esac\n pack_objects=\"$pack_objects $local $quiet $no_reuse_delta$extra\"\n name=$(git-rev-list --objects --all $rev_list 2>&1 |\n-\tgit-pack-objects --non-empty $pack_objects .tmp-pack) ||\n+\tgit-pack-objects --update-delta-cache --non-empty $pack_objects .tmp-pack) ||\n \texit 1\n if [ -z \"$name\" ]; then\n \techo Nothing new to pack.\n \ndiff --git a/pack-objects.c b/pack-objects.c\nindex bed2497..46b9775 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n...\n@@ -1342,5 +1350,7 @@ int main(int argc, char **argv)\n \tif (progress)\n \t\tfprintf(stderr, \"Total %d, written %d (delta %d), reused %d (delta %d)\\n\",\n \t\t\tnr_result, written, written_delta, reused, reused_delta);\n+\tif (update_delta_cache)\n+\t\tdelta_cache_save();\n \treturn 0;\n }\n"},{"id":"22840","messageId":"Pine.LNX.4.64.0606291428150.12404@g5.osdl.org","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291723060.1213@localhost.localdomain","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-29T21:30:11Z","receivedAt":"2006-06-29T21:30:11Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 29 Jun 2006, Nicolas Pitre wrote:\n>\n> On Thu, 29 Jun 2006, Linus Torvalds wrote:\n> \n> > Instead of having a separate cache, wouldn't it be much better to just \n> > take the hint from the previous pack-file?\n> \n> DOH! ;-)\n\nBtw, I think this could do with a flag to turn it on/off (but probably \ndefault to on).\n\nThe advantage of this patch is that it should guarantee that if everything \nis already packed, a repack will basically keep the pack identical. \n\nHowever, that is obviously also the dis-advantage, since it means that \nrepacking cannot improve packing. So adding a flag to say \"please try to \nincrementally improve the pack\" might well be worth it, even if this new \nbehaviour would be the _default_.\n\nHmm? Jeff, does this work for your load?\n\n\t\tLinus\n"},{"id":"22841","messageId":"20060629213503.GA15604@coredump.intra.peff.net","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291352110.12404@g5.osdl.org","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-06-29T21:35:03Z","receivedAt":"2006-06-29T21:35:03Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 29, 2006 at 02:04:01PM -0700, Linus Torvalds wrote:\n\n> Instead of having a separate cache, wouldn't it be much better to just \n> take the hint from the previous pack-file?\n\nI'd like to second Nicolas' \"DOH!\".\n\nThis drops my nasty load with roughly the same effect as the delta\ncache, and it does the same for the kernel repo. And it doesn't consume\nany extra disk space. Junio, please drop my delta-cache patch in favor\nof Linus' patch.\n\n-Peff\n"},{"id":"22842","messageId":"20060629213728.GB15604@coredump.intra.peff.net","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291616480.1213@localhost.localdomain","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-06-29T21:37:28Z","receivedAt":"2006-06-29T21:37:28Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 29, 2006 at 04:24:01PM -0400, Nicolas Pitre wrote:\n\n> > Obviously the kernel repo is doing better, but x=500 is only 4 days ago.\n> > Trying with --before=2.weeks.ago yields only 31505 matches.\n> \n> What does this prove? I fail to see the relation between those results \n> and a possible git-pack-objects improvement.\n\nMy point is that the window cache gets invalidated over time, whereas a\nsha1 by sha1 cache doesn't. However, the point is moot, as I think\nLinus has come up with a much better solution.\n\n> The negative delta cache concept is certainly attractive even for normal \n> repositories, especially for public servers, since when used in \n> conjonction with delta reuse it makes the creation of a pack basically \n> free. So I think this idea really has merits, as long as the cache \n> remains small.\n\nYes, if you're talking about a situation in which you make many packs\nfor a given set of commits, then it does make more sense (what I was\nreally trying to eliminate was a 10 minute repack followed by another 10\nminute repack to push to the server).\n\n-Peff\n"},{"id":"22843","messageId":"20060629213929.GC15604@coredump.intra.peff.net","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291428150.12404@g5.osdl.org","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-06-29T21:39:29Z","receivedAt":"2006-06-29T21:39:29Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jun 29, 2006 at 02:30:11PM -0700, Linus Torvalds wrote:\n\n> However, that is obviously also the dis-advantage, since it means that \n> repacking cannot improve packing. So adding a flag to say \"please try to \n> incrementally improve the pack\" might well be worth it, even if this new \n> behaviour would be the _default_.\n\nWe could tie the on/off to --no-reuse-delta, since you would mostly\nwant them at the same time. This disallows repacking over and over to\ntry to incrementally improve size. Do people actually do that?\n\n> Hmm? Jeff, does this work for your load?\n\nYes, just as well as my original patch.\n\n-Peff\n"},{"id":"22848","messageId":"20060629214349.GA11640@ca-server1.us.oracle.com","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291428150.12404@g5.osdl.org","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Joel Becker","fromEmail":"joel.becker@oracle.com","sentAt":"2006-06-29T21:43:49Z","receivedAt":"2006-06-29T21:43:49Z","isPatch":false,"sender":{"key":"joel.becker@oracle.com","avatar":null},"body":"On Thu, Jun 29, 2006 at 02:30:11PM -0700, Linus Torvalds wrote:\n> However, that is obviously also the dis-advantage, since it means that \n> repacking cannot improve packing. So adding a flag to say \"please try to \n> incrementally improve the pack\" might well be worth it, even if this new \n> behaviour would be the _default_.\n\n\tI nominate \"--pack-me-harder\".\n\nJoel\n\n-- \n\n\"Behind every successful man there's a lot of unsuccessful years.\"\n - Bob Brown\n\nJoel Becker\nPrincipal Software Developer\nOracle\nE-mail: joel.becker@oracle.com\nPhone: (650) 506-8127\n"},{"id":"22844","messageId":"Pine.LNX.4.64.0606291743010.1213@localhost.localdomain","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291428150.12404@g5.osdl.org","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-06-29T21:47:09Z","receivedAt":"2006-06-29T21:47:09Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 29 Jun 2006, Linus Torvalds wrote:\n\n> \n> \n> On Thu, 29 Jun 2006, Nicolas Pitre wrote:\n> >\n> > On Thu, 29 Jun 2006, Linus Torvalds wrote:\n> > \n> > > Instead of having a separate cache, wouldn't it be much better to just \n> > > take the hint from the previous pack-file?\n> > \n> > DOH! ;-)\n> \n> Btw, I think this could do with a flag to turn it on/off (but probably \n> default to on).\n\nI think it should simply be coupled with the --no-reuse-delta flag.\n\n> The advantage of this patch is that it should guarantee that if everything \n> is already packed, a repack will basically keep the pack identical. \n> \n> However, that is obviously also the dis-advantage, since it means that \n> repacking cannot improve packing. So adding a flag to say \"please try to \n> incrementally improve the pack\" might well be worth it, even if this new \n> behaviour would be the _default_.\n\nActually, the delta reusing already prevents those deltas from being \nimproved. So your patch only extend this notion to the non-deltified \nobjects as well. And the way out is to provide the --no-reuse-delta \nflag.\n\n\nNicolas\n"},{"id":"22846","messageId":"7v1wt7pqz5.fsf@assigned-by-dhcp.cox.net","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291352110.12404@g5.osdl.org","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-29T21:54:54Z","receivedAt":"2006-06-29T21:54:54Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Instead of having a separate cache, wouldn't it be much better to just \n> take the hint from the previous pack-file?\n>\n> In the repacking window, if both objects we are looking at already came \n> from the same (old) pack-file, don't bother delta'ing them against each \n> other. \n>\n> That means that we'll still always check for better deltas for (and \n> against!) _unpacked_ objects, but assuming incremental repacks, you'll \n> avoid the delta creation 99% of the time.\n\nI bow down before you.\n\nNo ugly special-case caching, just automatically \"the right\nthing\", with very little overhead.\n\nIt just makes sense.\n\nWe have a winner.\n\n;-)\n"},{"id":"22849","messageId":"7vwtazobkw.fsf@assigned-by-dhcp.cox.net","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291743010.1213@localhost.localdomain","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-29T22:12:47Z","receivedAt":"2006-06-29T22:12:47Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> On Thu, 29 Jun 2006, Linus Torvalds wrote:\n>\n>> \n>> \n>> On Thu, 29 Jun 2006, Nicolas Pitre wrote:\n>> >\n>> > On Thu, 29 Jun 2006, Linus Torvalds wrote:\n>> > \n>> > > Instead of having a separate cache, wouldn't it be much better to just \n>> > > take the hint from the previous pack-file?\n>> > \n>> > DOH! ;-)\n>> \n>> Btw, I think this could do with a flag to turn it on/off (but probably \n>> default to on).\n>\n> I think it should simply be coupled with the --no-reuse-delta flag.\n\nI agree that makes sense.\n"},{"id":"22852","messageId":"7vsllnob3w.fsf@assigned-by-dhcp.cox.net","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606291352110.12404@g5.osdl.org","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-29T22:22:59Z","receivedAt":"2006-06-29T22:22:59Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Thu, 29 Jun 2006, Nicolas Pitre wrote:\n>> \n>> The negative delta cache concept is certainly attractive even for normal \n>> repositories, especially for public servers, since when used in \n>> conjonction with delta reuse it makes the creation of a pack basically \n>> free. So I think this idea really has merits, as long as the cache \n>> remains small.\n>\n> I don't really see much of a point of this all.\n>\n> Instead of having a separate cache, wouldn't it be much better to just \n> take the hint from the previous pack-file?\n>\n> In the repacking window, if both objects we are looking at already came \n> from the same (old) pack-file, don't bother delta'ing them against each \n> other. \n>\n> That means that we'll still always check for better deltas for (and \n> against!) _unpacked_ objects, but assuming incremental repacks, you'll \n> avoid the delta creation 99% of the time.\n>\n> Ie somethng really simple like the appended.\n>\n> \t\tLinus\n> ---\n> diff --git a/pack-objects.c b/pack-objects.c\n> index bed2497..cea63e7 100644\n> --- a/pack-objects.c\n> +++ b/pack-objects.c\n> @@ -988,6 +988,13 @@ static int try_delta(struct unpacked *tr\n> \t\treturn -1;\n> \n> \t/*\n> +\t * We do not bother to try a delta that we discarded\n> +\t * on an earlier try\n> +\t */\n> +\tif (trg_entry->in_pack && trg_entry->in_pack == src_entry->in_pack)\n> +\t\treturn -1;\n> +\n> +\t/*\n\nI think you meant to return 0 from here though. -1 means \"do\nnot use this pair and do not bother try improving it with the\nremaining candidates\".\n"},{"id":"22853","messageId":"e81kcm$p3c$1@sea.gmane.org","threadId":"4703","inReplyTo":"7v4py4y7wo.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFC] Cache negative delta pairs","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-06-29T22:31:59Z","receivedAt":"2006-06-29T22:31:59Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Junio C Hamano wrote:\n\n> [...] For example, we currently do\n> not delta OpenOffice documents (*.odt, *.odp, etc) very well.\n> If one has a repository that tracks the history of \"file.odp\",\n> we know each revision of \"file.odp\" would not delta against any\n> other version anyway, and could skip attempting to deltify them.\n\nPerhaps we should steal Mercurial idea of EncodeDecodeFilter, and store\nOpenOffice documents, Mozilla extensions, Java packages in object store as\nuncompressed archive, and checkout them to working area in original format.\nAll diff should be of course done on in-repository (after-filter) format.\n\nThe original example at \n http://www.selenic.com/mercurial/wiki/index.cgi/EncodeDecodeFilter\ntalks about archives (zip files) and unix2dos endline convention conversion.\n\nPerhaps for OpenOffice and Mozilla we would need to use [external] XML-aware\ndiff, too...\n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"22882","messageId":"Pine.LNX.4.64.0606292335190.1213@localhost.localdomain","threadId":"4703","inReplyTo":"7vwtazobkw.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH] consider previous pack undeltified object state only when reusing delta data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-06-30T03:44:52Z","receivedAt":"2006-06-30T03:44:52Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Without this there would never be a chance to improve packing for \npreviously undeltified objects.\n\nSigned-off-by: Nicolas Pitre \n\n---\n\nOn Thu, 29 Jun 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > On Thu, 29 Jun 2006, Linus Torvalds wrote:\n> >\n> >> \n> >> \n> >> On Thu, 29 Jun 2006, Nicolas Pitre wrote:\n> >> >\n> >> > On Thu, 29 Jun 2006, Linus Torvalds wrote:\n> >> > \n> >> > > Instead of having a separate cache, wouldn't it be much better to just \n> >> > > take the hint from the previous pack-file?\n> >> > \n> >> > DOH! ;-)\n> >> \n> >> Btw, I think this could do with a flag to turn it on/off (but probably \n> >> default to on).\n> >\n> > I think it should simply be coupled with the --no-reuse-delta flag.\n> \n> I agree that makes sense.\n\nSo here it is.\n\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 6e17676..47da33b 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -989,9 +989,10 @@ static int try_delta(struct unpacked *tr\n \n \t/*\n \t * We do not bother to try a delta that we discarded\n-\t * on an earlier try.\n+\t * on an earlier try, but only when reusing delta data.\n \t */\n-\tif (trg_entry->in_pack && trg_entry->in_pack == src_entry->in_pack)\n+\tif (!no_reuse_delta && trg_entry->in_pack &&\n+\t trg_entry->in_pack == src_entry->in_pack)\n \t\treturn 0;\n \n \t/*\n"},{"id":"22903","messageId":"Pine.LNX.4.63.0606301144450.29667@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606292335190.1213@localhost.localdomain","subject":"Re: [PATCH] consider previous pack undeltified object state only when reusing delta data","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-30T09:45:55Z","receivedAt":"2006-06-30T09:45:55Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 29 Jun 2006, Nicolas Pitre wrote:\n\n> Without this there would never be a chance to improve packing for \n> previously undeltified objects.\n\nEarlier this year, I was quite surprised to learn that multiple repackings \nactually improved packing. Does that patch mean this feature is gone?\n\nCiao,\nDscho\n"},{"id":"22914","messageId":"44A518D6.8040901@op5.se","threadId":"4703","inReplyTo":"Pine.LNX.4.63.0606301144450.29667@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] consider previous pack undeltified object state only when reusing delta data","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2006-06-30T12:28:06Z","receivedAt":"2006-06-30T12:28:06Z","isPatch":true,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Johannes Schindelin wrote:\n> Hi,\n> \n> On Thu, 29 Jun 2006, Nicolas Pitre wrote:\n> \n> \n>>Without this there would never be a chance to improve packing for \n>>previously undeltified objects.\n> \n> \n> Earlier this year, I was quite surprised to learn that multiple repackings \n> actually improved packing. Does that patch mean this feature is gone?\n> \n\nThe patch Linus sent removes that feature. This one re-introduces it.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"22928","messageId":"Pine.LNX.4.64.0606301132510.1213@localhost.localdomain","threadId":"4703","inReplyTo":"44A518D6.8040901@op5.se","subject":"Re: [PATCH] consider previous pack undeltified object state only when reusing delta data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-06-30T16:55:44Z","receivedAt":"2006-06-30T16:55:44Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 30 Jun 2006, Andreas Ericsson wrote:\n\n> Johannes Schindelin wrote:\n> > Hi,\n> > \n> > On Thu, 29 Jun 2006, Nicolas Pitre wrote:\n> > \n> > \n> > > Without this there would never be a chance to improve packing for\n> > > previously undeltified objects.\n> > \n> > \n> > Earlier this year, I was quite surprised to learn that multiple repackings\n> > actually improved packing. Does that patch mean this feature is gone?\n> > \n> \n> The patch Linus sent removes that feature. This one re-introduces it.\n\nNot really.\n\nActually that multiple repacking \"feature\" was rather an artifact of the \ndelta data reuse code and not really by design. Here's what happened \nbefore:\n\nConsider the first repack where no delta exists, or \"git-repack -a -f\" \nwhere the -f argument makes it ignores existing delta data. In that \ncase all objects are sorted and delta attempted on them within a window.\n\nSo to simplify things let's assume objects are numbered from 1 upwards. \nFirst obj #1 is added to the window. Obj #2 attempts a delta against \nobj #1. Obj #3 attempts a delta against objs #2 and #1. Obj #4 \nattempts a delta against objs #3, #2 and #1. And so on for all object: \neach new object attempts a delta against the last 10 objects (the \ndefault window size is 10) and the best delta, if any, is kept.\n\nIn the end, some objects get deltified, some don't, and a new pack is \nproduced.\n\nWhen repacking without -f to git-repack, then already deltified objects \nare simply copied as is from the existing pack(s) avoiding costly delta \nre-computation. Still, without Linus' patch, non-deltified objects were \nconsidered for deltification and deltas attempted on them.\n\nSo supposing that objects #1 through #10 were not deltified, and objects \n#11 through #50 were deltified, then those deltified objects were \nskipped over for the purpose of delta matching and therefore object #51 \nended up attempting a delta against objs #1 to 10 instead of #41 to #50 \nlike in the previous run. The net effect was similar to a larger window \nfor some objects providing more opportunities for successful deltas, and \ntherefore a smaller pack.\n\nWith Linus' patch those objects already known to be undeltified are, \ntoo, skipped. That means that successive git-repack without the -f \nargument are now producing identical packs all the time and the artifact \nabove is gone.\n\nI think this is a good thing since now the packing behavior is more \npredictable. But nothing is lost since if you want to have better \npacking like before you simply have to specify a slightly larger window \nsize on the first git-repack. It'll take a bit more time but running \ngit-repack many times also took more time in the end anyway.\n\n\nNicolas\n"},{"id":"23092","messageId":"44A8D116.5070709@op5.se","threadId":"4703","inReplyTo":"Pine.LNX.4.64.0606301132510.1213@localhost.localdomain","subject":"Re: [PATCH] consider previous pack undeltified object state only when reusing delta data","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2006-07-03T08:11:02Z","receivedAt":"2006-07-03T08:11:02Z","isPatch":true,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Nicolas Pitre wrote:\n> On Fri, 30 Jun 2006, Andreas Ericsson wrote:\n> \n>>Johannes Schindelin wrote:\n>>>\n>>>>Without this there would never be a chance to improve packing for\n>>>>previously undeltified objects.\n>>>\n>>>\n>>>Earlier this year, I was quite surprised to learn that multiple repackings\n>>>actually improved packing. Does that patch mean this feature is gone?\n>>>\n>>\n>>The patch Linus sent removes that feature. This one re-introduces it.\n> \n> \n> Not really.\n> \n> Actually that multiple repacking \"feature\" was rather an artifact of the \n> delta data reuse code and not really by design. Here's what happened \n> before:\n> \n\nThanks for the extensive and very clear info. Lovely to see a competent \nprogrammer who can also explain how things work. :)\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"}]}