{"thread":{"id":"9663","subject":"[PATCH] Keep last used delta base in the delta window","startedAt":"2007-08-26T20:56:33Z","lastAt":"2007-08-29T21:02:06Z","messageCount":9,"participants":["Martin Koegler","Junio C Hamano","David Kastrup","Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"51604","messageId":"11881617934179-git-send-email-mkoegler@auto.tuwien.ac.at","threadId":"9663","inReplyTo":null,"subject":"[PATCH] Keep last used delta base in the delta window","fromName":"Martin Koegler","fromEmail":"mkoegler@auto.tuwien.ac.at","sentAt":"2007-08-26T20:56:33Z","receivedAt":"2007-08-26T20:56:33Z","isPatch":true,"sender":{"key":"mkoegler@auto.tuwien.ac.at","avatar":null},"body":"Keeping the last used delta base object, if it would be dropped,\nsupports creating smaller packs with shorter delta chains.\n\nThe runtime impact is minimal, as it only skips slots in the delta window.\n\nOriginal (for git.git repository):\n$ echo | time /data/git/bin/git-pack-objects --non-empty --all --reflog --unpacked=pack-a19e665cf563f4ca8ce2306eeb4bfb78815882a5.pack --no-reuse-object .git/objects/.tmp-29631-pack\nGenerating pack...\nCounting objects: 9846\nDone counting 56224 objects.\nDeltifying 56224 objects...\n 100% (56224/56224) done\nWriting 56224 objects...\n1d3d374f6b9f9f8882ce3a47bab6976702aca35d\n\nTotal 56224 (delta 37798), reused 0 (delta 0)\n57.19user 0.90system 1:00.39elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (6major+33878minor)pagefaults 0swaps\n\nPack size: 14655528\nPack stat:\n      all sizes: count 56224 total 26029188 min 0 max 220191 mean 462.96 median 59 std_dev 3065.89\n all path sizes: count 56224 total 756044939 min 0 max 254816 mean 13447.01 median 6291 std_dev 26983.93\n     tree sizes: count 18426 total 26029188 min 0 max 279666 mean 1412.63 median 451 std_dev 7242.15\ntree path sizes: count 18426 total 756044939 min 0 max 30327513 mean 41031.42 median 457 std_dev 563089.70\n         depths: count 56224 total 713895 min 0 max 50 mean 12.70 median 5 std_dev 15.85\n\nchain length >= 40: 6271 objects\nchain length = 1: 2615 objects\nchain length = 2: 2350 objects\nchain length = 3: 2073 objects\nchain length = 4: 1809 objects\nchain length = 5: 1578 objects\nchain length = 6: 1384 objects\nchain length = 7: 1242 objects\nchain length = 8: 1119 objects\nchain length = 9: 1060 objects\nchain length = 10: 975 objects\nchain length = 11: 904 objects\nchain length = 12: 816 objects\nchain length = 13: 778 objects\nchain length = 14: 776 objects\nchain length = 15: 709 objects\nchain length = 16: 671 objects\nchain length = 17: 651 objects\nchain length = 18: 645 objects\nchain length = 19: 674 objects\nchain length = 20: 603 objects\nchain length = 21: 563 objects\nchain length = 22: 537 objects\nchain length = 23: 530 objects\nchain length = 24: 485 objects\nchain length = 25: 473 objects\nchain length = 26: 452 objects\nchain length = 27: 427 objects\nchain length = 28: 439 objects\nchain length = 29: 420 objects\nchain length = 30: 416 objects\nchain length = 31: 387 objects\nchain length = 32: 407 objects\nchain length = 33: 387 objects\nchain length = 34: 377 objects\nchain length = 35: 354 objects\nchain length = 36: 367 objects\nchain length = 37: 364 objects\nchain length = 38: 359 objects\nchain length = 39: 351 objects\n\nWith the patch:\n$ echo | time ./git-pack-objects --non-empty --all --reflog --unpacked=pack-a19e665cf563f4ca8ce2306eeb4bfb78815882a5.pack --no-reuse-object .git/objects/.tmp-29638-pack\nGenerating pack...\nCounting objects: 9806\nDone counting 56224 objects.\nDeltifying 56224 objects...\n 100% (56224/56224) done\nWriting 56224 objects...\n1d3d374f6b9f9f8882ce3a47bab6976702aca35d\n\nTotal 56224 (delta 37871), reused 0 (delta 0)\n57.67user 1.08system 1:00.73elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+32236minor)pagefaults 0swaps\n\nPack size: 14306798\nPack stat:\n      all sizes: count 56224 total 25299924 min 0 max 220191 mean 449.98 median 58 std_dev 2968.96\n all path sizes: count 56224 total 773260074 min 0 max 272126 mean 13753.20 median 6320 std_dev 27370.12\n     tree sizes: count 18353 total 25299924 min 0 max 279899 mean 1378.52 median 450 std_dev 7097.53\ntree path sizes: count 18353 total 773260074 min 0 max 28995033 mean 42132.63 median 455 std_dev 594290.34\n         depths: count 56224 total 664005 min 0 max 50 mean 11.81 median 4 std_dev 14.85\n\nchain length >= 40: 5056 objects\nchain length = 1: 3174 objects\nchain length = 2: 2613 objects\nchain length = 3: 2209 objects\nchain length = 4: 1918 objects\nchain length = 5: 1565 objects\nchain length = 6: 1412 objects\nchain length = 7: 1211 objects\nchain length = 8: 1090 objects\nchain length = 9: 1001 objects\nchain length = 10: 950 objects\nchain length = 11: 893 objects\nchain length = 12: 803 objects\nchain length = 13: 772 objects\nchain length = 14: 787 objects\nchain length = 15: 691 objects\nchain length = 16: 656 objects\nchain length = 17: 624 objects\nchain length = 18: 619 objects\nchain length = 19: 591 objects\nchain length = 20: 569 objects\nchain length = 21: 552 objects\nchain length = 22: 525 objects\nchain length = 23: 509 objects\nchain length = 24: 506 objects\nchain length = 25: 479 objects\nchain length = 26: 462 objects\nchain length = 27: 472 objects\nchain length = 28: 479 objects\nchain length = 29: 475 objects\nchain length = 30: 464 objects\nchain length = 31: 446 objects\nchain length = 32: 426 objects\nchain length = 33: 433 objects\nchain length = 34: 427 objects\nchain length = 35: 412 objects\nchain length = 36: 405 objects\nchain length = 37: 393 objects\nchain length = 38: 394 objects\nchain length = 39: 408 objects\n\nSigned-off-by: Martin Koegler <mkoegler@auto.tuwien.ac.at>\n---\n builtin-pack-objects.c |    9 +++++++++\n 1 files changed, 9 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 77481df..24e8719 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1438,6 +1438,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \tuint32_t i = nr_objects, idx = 0, count = 0, processed = 0;\n \tunsigned int array_size = window * sizeof(struct unpacked);\n \tstruct unpacked *array;\n+\tstruct object_entry *last_base = 0;\n \tint max_depth;\n \n \tif (!nr_objects)\n@@ -1470,6 +1471,13 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \t\tif (entry->no_try_delta)\n \t\t\tcontinue;\n \n+\t\tif (last_base && n->entry == last_base) {\n+\t\t\tidx ++;\n+\t\t\tif (idx >= window)\n+\t\t\t\tidx = 0;\n+\t\t\tn = array + idx;\n+\t\t}\n+\n \t\tfree_unpacked(n);\n \t\tn->entry = entry;\n \n@@ -1513,6 +1521,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \t\tif (entry->delta && depth <= n->depth)\n \t\t\tcontinue;\n \n+\t\tlast_base = entry->delta;\n \t\tnext:\n \t\tidx++;\n \t\tif (count + 1 < window)\n-- \n1.4.4.4\n"},{"id":"51659","messageId":"7v3ay5l5wq.fsf@gitster.siamese.dyndns.org","threadId":"9663","inReplyTo":"11881617934179-git-send-email-mkoegler@auto.tuwien.ac.at","subject":"Re: [PATCH] Keep last used delta base in the delta window","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-27T08:48:21Z","receivedAt":"2007-08-27T08:48:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin Koegler <mkoegler@auto.tuwien.ac.at> writes:\n\n> Keeping the last used delta base object, if it would be dropped,\n> supports creating smaller packs with shorter delta chains.\n\nInstead of treating the \"the last used one happened to be on the\nhorizon -- try not to drop it\" special case, I wonder if it\nmakes sense to float the last used delta base object early in\nthe window _after_ it is used.  Wouldn't we keep more than one\nvery recently used delta base objects in the window that way?\n"},{"id":"51675","messageId":"86veb1thmp.fsf@lola.quinscape.zz","threadId":"9663","inReplyTo":"7v3ay5l5wq.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] Keep last used delta base in the delta window","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-08-27T10:07:58Z","receivedAt":"2007-08-27T10:07:58Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Martin Koegler <mkoegler@auto.tuwien.ac.at> writes:\n>\n>> Keeping the last used delta base object, if it would be dropped,\n>> supports creating smaller packs with shorter delta chains.\n>\n> Instead of treating the \"the last used one happened to be on the\n> horizon -- try not to drop it\" special case, I wonder if it\n> makes sense to float the last used delta base object early in\n> the window _after_ it is used.  Wouldn't we keep more than one\n> very recently used delta base objects in the window that way?\n\nWell, given the little amount of spare time I have for personal\nprojects, I should not go flaunting them too much, but anyway...\n\nI am just drafting implementing a delta-diff size estimator: for every\nhash value it does not store hash chains or pointers to memory images,\nbut just a bit map of at most 32 (possibly 64 where ulong delivers it,\npossibly even just 16 bits when one restricts oneself to 16 element\nwindows in order to save memory) delta window files, telling which of\nthe files show such a hash value anywhere.  When a file is considered\nfor deltaing, it is run once against this delta-diff estimator which\ndoes not even look at the files again.  This delivers a lower bound\nfor the size a delta towards each of the delta candidates can take.\nThe candidates are then sorted in increasing size of expected delta\nsize and are considered in turn.  Once a delta has a lower size than\nthe lowest bound for further delta candidates, no further candidates\nneed to get considered.\n\nAlso the calculation of a delta can get aborted once it exceeds the\nsize of a previous delta.  Somewhat more complex and error-prone would\nbe to abort based on continually correcting the estimated lower bound\nfrom the estimator while one is creating a delta and dropping out as\nsoon as it becomes impossible to beat a previous delta.\n\nThe nice thing about this is that one can start out with a simplistic\nestimator as long as it is guaranteed never to deliver an estimate\nthat is too high.  As long as that is the case, the packs will never\nget worse than they are now: a bad estimator will just mean that more\nelements of the window need to be considered before the conclusion is\nreached.\n\nSince the estimator data structure does not point into any\nmemory-mapped files or hash chains scattered through memory, it should\nbe comparatively light (in comparison to an actual delta) on page\nthrashing which appears to me one of the main performance problems,\nwhile delivering a reasonably useful lower bound for all deltas in the\nwindow at once.\n\nIts size needs to be large enough so that the bit maps will be\ndominated by zeros: hash collisions not actually corresponding to\nmatching data lead to underestimates.  If those become too many, the\npruning of comparisons will become ineffective:\n\nA match implies that the next 2*RABIN_SIZE-1 (31) bytes at least could\npossibly be expressed as a delta, and every match after another\nRABIN_SIZE implies another RABIN_SIZE bytes might get folded into the\nprevious delta.\n\nSo false positives seriously distort the estimate.  There is still a\ngood chance that a good candidate will land early in the sort order\ndue to such an estimate and thus other candidates will have their\ndeltaing cut off early, but of course it is quite more effective if\ntheir deltaing does not even have to start.\n\n-- \nDavid Kastrup\n"},{"id":"51693","messageId":"7vy7fxyy52.fsf@gitster.siamese.dyndns.org","threadId":"9663","inReplyTo":"7v3ay5l5wq.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] Keep last used delta base in the delta window","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-27T12:12:25Z","receivedAt":"2007-08-27T12:12:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Martin Koegler <mkoegler@auto.tuwien.ac.at> writes:\n>\n>> Keeping the last used delta base object, if it would be dropped,\n>> supports creating smaller packs with shorter delta chains.\n>\n> Instead of treating the \"the last used one happened to be on the\n> horizon -- try not to drop it\" special case, I wonder if it\n> makes sense to float the last used delta base object early in\n> the window _after_ it is used.  Wouldn't we keep more than one\n> very recently used delta base objects in the window that way?\n\nThe attached is my quick-and-dirty one.  \n\nI had a bit more objects (59140) than you did in my repository.\nThe runtime from three versions were comparable.  It seems to\nmake the resulting chain even shorter, which can only be good.\n\n(stock \"master\") 15782196 bytes\nchain length = 1: 2972 objects\nchain length = 2: 2651 objects\nchain length = 3: 2369 objects\nchain length = 4: 2121 objects\nchain length = 5: 1877 objects\nchain length = 6: 1715 objects\nchain length = 7: 1469 objects\nchain length = 8: 1296 objects\nchain length = 9: 1185 objects\nchain length = 10: 1111 objects\n...\nchain length = 46: 490 objects\nchain length = 47: 515 objects\nchain length = 48: 527 objects\nchain length = 49: 570 objects\nchain length = 50: 408 objects\n\n(with your patch) 15745736 bytes (0.23% smaller)\nchain length = 1: 3137 objects\nchain length = 2: 2688 objects\nchain length = 3: 2322 objects\nchain length = 4: 2146 objects\nchain length = 5: 1824 objects\nchain length = 6: 1664 objects\nchain length = 7: 1462 objects\nchain length = 8: 1329 objects\nchain length = 9: 1201 objects\nchain length = 10: 1126 objects\n...\nchain length = 46: 503 objects\nchain length = 47: 509 objects\nchain length = 48: 536 objects\nchain length = 49: 588 objects\nchain length = 50: 357 objects\n\n(with this patch) 15612086 bytes (1.08% smaller)\nchain length = 1: 4831 objects\nchain length = 2: 3811 objects\nchain length = 3: 2964 objects\nchain length = 4: 2352 objects\nchain length = 5: 1944 objects\nchain length = 6: 1667 objects\nchain length = 7: 1465 objects\nchain length = 8: 1267 objects\nchain length = 9: 1210 objects\nchain length = 10: 1050 objects\n...\nchain length = 46: 327 objects\nchain length = 47: 353 objects\nchain length = 48: 304 objects\nchain length = 49: 298 objects\nchain length = 50: 135 objects\n\n---\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 9b3ef94..2a5ea29 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1439,6 +1439,61 @@ static void free_unpacked(struct unpacked *n)\n \tn->depth = 0;\n }\n \n+static void shift_base(int idx, int window, struct unpacked *array, struct object_entry *delta_base)\n+{\n+\t/*\n+\t * The delta_base was a useful one to deltify the object at\n+\t * idx (circular).  Shift the contents of array (circular\n+\t * buffer) so that it will be evicted last.\n+\t */\n+\tint good_base, good_at;\n+\tstruct unpacked swap;\n+\n+\tfor (good_base = 0; good_base < window; good_base++)\n+\t\tif (array[good_base].entry == delta_base)\n+\t\t\tbreak;\n+\tif (window <= good_base)\n+\t\tdie(\"Junio is an idiot\");\n+\n+\tif (window <= ++idx)\n+\t\tidx = 0;\n+\t/*\n+\t * The entry at idx modulo window will be evicted first during\n+\t * the next round.  Where in the next window is the good_base\n+\t * found?\n+\t */\n+\tgood_at = (good_base + window - idx) % window;\n+\n+\t/*\n+\t * If it is already at the furthest edge, nothing needs to be done.\n+\t */\n+\tif (good_at == window - 1)\n+\t\treturn;\n+\n+\t/*\n+\t * Otherwise, stash it away, shift the others down and swap it in.\n+\t */\n+\tswap = array[good_base];\n+\n+\twhile (good_at < window) {\n+\t\tint dst, src;\n+\n+\t\tdst = good_at + idx;\n+\t\tif (window <= dst)\n+\t\t\tdst -= window;\n+\t\tsrc = dst + 1;\n+\t\tif (window <= src)\n+\t\t\tsrc -= window;\n+\t\tarray[dst] = array[src];\n+\t\tgood_at++;\n+\t}\n+\n+\tgood_at = idx + window - 1;\n+\tif (window <= good_at)\n+\t\tgood_at -= window;\n+\tarray[good_at] = swap;\n+}\n+\n static void find_deltas(struct object_entry **list, int window, int depth)\n {\n \tuint32_t i = nr_objects, idx = 0, count = 0, processed = 0;\n@@ -1519,6 +1574,13 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \t\tif (entry->delta && depth <= n->depth)\n \t\t\tcontinue;\n \n+\t\t/*\n+\t\t * The delta base was a useful one.  Move it up in the\n+\t\t * window to keep it longer.\n+\t\t */\n+\t\tif (entry->delta)\n+\t\t\tshift_base(idx, window, array, entry->delta);\n+\n \t\tnext:\n \t\tidx++;\n \t\tif (count + 1 < window)\n"},{"id":"51753","messageId":"20070827204320.GA17126@auto.tuwien.ac.at","threadId":"9663","inReplyTo":"86veb1thmp.fsf@lola.quinscape.zz","subject":"Re: [PATCH] Keep last used delta base in the delta window","fromName":"Martin Koegler","fromEmail":"mkoegler@auto.tuwien.ac.at","sentAt":"2007-08-27T20:43:20Z","receivedAt":"2007-08-27T20:43:20Z","isPatch":true,"sender":{"key":"mkoegler@auto.tuwien.ac.at","avatar":null},"body":"On Mon, Aug 27, 2007 at 12:07:58PM +0200, David Kastrup wrote:\n> Well, given the little amount of spare time I have for personal\n> projects, I should not go flaunting them too much, but anyway...\n> \n> I am just drafting implementing a delta-diff size estimator: for every\n> hash value it does not store hash chains or pointers to memory images,\n> but just a bit map of at most 32 (possibly 64 where ulong delivers it,\n> possibly even just 16 bits when one restricts oneself to 16 element\n> windows in order to save memory) delta window files, telling which of\n> the files show such a hash value anywhere. \n\nHow do you want to select these few hash values? \n\nI eg. dump database tables as SQL statements in per table files and\ncommit all changes. All lines in each file share a common prefix\n(INSERT INTO tablename (COL1, COL2, ...) VALUES). Statistics showed, that up\nto 50% of the hash elements of the delta index were dropped, because\nthey had eqal has values.\n\nWith you apropach:\n\nIf rare used values are selected as the 32 hash values, you will\nprobably regard files, which contain different tables (and therefore a\ndifferent prefix), as \"similar\", although the files have not very much\nsimilarity otherwise.\n\nIf you select the hash values of the prefixes, you will create for each\ntable one cluster (if the table count is < 32/64). This already happens\nby using the hash value of the path name in the sorting.\n\nI don't belive, that your idea will improve very much in this case.\nI fear, that it will be even worser than the current algorithm.\n\n> When a file is considered\n> for deltaing, it is run once against this delta-diff estimator which\n> does not even look at the files again.  This delivers a lower bound\n> for the size a delta towards each of the delta candidates can take.\n> The candidates are then sorted in increasing size of expected delta\n> size and are considered in turn.  Once a delta has a lower size than\n> the lowest bound for further delta candidates, no further candidates\n> need to get considered.\n\nSo this means, that we have to hash the target entry too (which could\nbe merged with creating the delta index). We currently only hash an\nentry, if it is really needed as source in a delta-diff.\n\nOn bigger blobs, this could slow the process down.\n\n> Also the calculation of a delta can get aborted once it exceeds the\n> size of a previous delta. \n\nThis already happens.\n\n> Somewhat more complex and error-prone would\n> be to abort based on continually correcting the estimated lower bound\n> from the estimator while one is creating a delta and dropping out as\n> soon as it becomes impossible to beat a previous delta.\n> \n> The nice thing about this is that one can start out with a simplistic\n> estimator as long as it is guaranteed never to deliver an estimate\n> that is too high.  As long as that is the case, the packs will never\n> get worse than they are now: a bad estimator will just mean that more\n> elements of the window need to be considered before the conclusion is\n> reached.\n> \n> Since the estimator data structure does not point into any\n> memory-mapped files or hash chains scattered through memory, it should\n> be comparatively light (in comparison to an actual delta) on page\n> thrashing which appears to me one of the main performance problems,\n> while delivering a reasonably useful lower bound for all deltas in the\n> window at once.\n\nDo you want to do your estimations only against a small window of objects\nor all objects?\n\nmfg Martin Kögler\n"},{"id":"51754","messageId":"8564308zaj.fsf@lola.goethe.zz","threadId":"9663","inReplyTo":"20070827204320.GA17126@auto.tuwien.ac.at","subject":"Re: [PATCH] Keep last used delta base in the delta window","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-08-27T21:04:20Z","receivedAt":"2007-08-27T21:04:20Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"mkoegler@auto.tuwien.ac.at (Martin Koegler) writes:\n\n> On Mon, Aug 27, 2007 at 12:07:58PM +0200, David Kastrup wrote:\n>> Well, given the little amount of spare time I have for personal\n>> projects, I should not go flaunting them too much, but anyway...\n>> \n>> I am just drafting implementing a delta-diff size estimator: for every\n>> hash value it does not store hash chains or pointers to memory images,\n>> but just a bit map of at most 32 (possibly 64 where ulong delivers it,\n>> possibly even just 16 bits when one restricts oneself to 16 element\n>> windows in order to save memory) delta window files, telling which of\n>> the files show such a hash value anywhere. \n>\n> How do you want to select these few hash values?\n\nHm?  Are you familiar with diff-delta.c?  I was not going to change\nthe hash value computation in there.  It is a 32bit CRC over 16byte\npassages: the delta source is checksummed with a stride of 16 bytes\nand the resulting CRC values are masked to a convenient number of bits\nand used as index into a hash table with disambiguation to actual code\npassages using linked lists.  Then the destination delta is\nchecksummed in the same manner but with a stride of 1, and the sums\nare looked up in the hash until a matching prefix is found.\n\nSo I was going to do the same calculation, but look up a bit mask\nrather than a linked list (namely calculating under the assumption\nthat a hash hit implies an actual match).\n\n> I eg. dump database tables as SQL statements in per table files and\n> commit all changes. All lines in each file share a common prefix\n> (INSERT INTO tablename (COL1, COL2, ...) VALUES). Statistics showed,\n> that up to 50% of the hash elements of the delta index were dropped,\n> because they had equal hash values.\n\nYes, I am aware of that.  One somewhat crazy consequence of that is\nthat git's deltaing works better on Linux style indentation than on\nGNU style indentation.\n\n> With you apropach:\n>\n> If rare used values are selected as the 32 hash values, you will\n> probably regard files, which contain different tables (and therefore\n> a different prefix), as \"similar\", although the files have not very\n> much similarity otherwise.\n\nIt's statistics.  Random matches will tend to level out.\n\n> If you select the hash values of the prefixes, you will create for\n> each table one cluster (if the table count is < 32/64). This already\n> happens by using the hash value of the path name in the sorting.\n>\n> I don't belive, that your idea will improve very much in this case.\n> I fear, that it will be even worser than the current algorithm.\n\nHuh?  I am not replacing the current algorithm.  I am doing some\nupfront estimates for getting a good order for doing the current\nalgorithm, so that I might abort parts of it early when I know they\ncan't improve things.  If the estimates are completely random and/or\nuseless, it will mean that you get a slowdown by a comparatively small\nconstant factor.\n\n>> When a file is considered for deltaing, it is run once against this\n>> delta-diff estimator which does not even look at the files again.\n>> This delivers a lower bound for the size a delta towards each of\n>> the delta candidates can take.  The candidates are then sorted in\n>> increasing size of expected delta size and are considered in turn.\n>> Once a delta has a lower size than the lowest bound for further\n>> delta candidates, no further candidates need to get considered.\n>\n> So this means, that we have to hash the target entry too (which\n> could be merged with creating the delta index).\n\nHuh?  I don't see what you are getting at.\n\n> We currently only hash an entry, if it is really needed as source in\n> a delta-diff.\n\nWhy would you want to hash a non-candidate?\n\n>> Also the calculation of a delta can get aborted once it exceeds the\n>> size of a previous delta.\n>\n> This already happens.\n\nAh yes.  Overlooked this.  Presorting the candidates should be helpful\nright away then.\n\n> Do you want to do your estimations only against a small window of\n> objects or all objects?\n\nThe estimates are made against the candidates in the window.  When a\ncandidate leaves the window, its bit in the bit masks gets reused for\nthe next candidate entering the window.\n\n-- \nDavid Kastrup, Kriemhildstr. 15, 44793 Bochum\n"},{"id":"51842","messageId":"alpine.LFD.0.999.0708291339580.16727@xanadu.home","threadId":"9663","inReplyTo":"7vy7fxyy52.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] Keep last used delta base in the delta window","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-08-29T18:21:33Z","receivedAt":"2007-08-29T18:21:33Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 27 Aug 2007, Junio C Hamano wrote:\n\n> Junio C Hamano <gitster@pobox.com> writes:\n> \n> > Instead of treating the \"the last used one happened to be on the\n> > horizon -- try not to drop it\" special case, I wonder if it\n> > makes sense to float the last used delta base object early in\n> > the window _after_ it is used.  Wouldn't we keep more than one\n> > very recently used delta base objects in the window that way?\n> \n> The attached is my quick-and-dirty one.  \n\n\nI like this.  A LRU sorting of base objects is obviously a good thing to \ndo.  Some comments below.\n\n[...]\n\n> diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\n> index 9b3ef94..2a5ea29 100644\n> --- a/builtin-pack-objects.c\n> +++ b/builtin-pack-objects.c\n> @@ -1439,6 +1439,61 @@ static void free_unpacked(struct unpacked *n)\n>  \tn->depth = 0;\n>  }\n>  \n> +static void shift_base(int idx, int window, struct unpacked *array, struct object_entry *delta_base)\n> +{\n> +\t/*\n> +\t * The delta_base was a useful one to deltify the object at\n> +\t * idx (circular).  Shift the contents of array (circular\n> +\t * buffer) so that it will be evicted last.\n> +\t */\n> +\tint good_base, good_at;\n> +\tstruct unpacked swap;\n> +\n> +\tfor (good_base = 0; good_base < window; good_base++)\n> +\t\tif (array[good_base].entry == delta_base)\n> +\t\t\tbreak;\n> +\tif (window <= good_base)\n> +\t\tdie(\"Junio is an idiot\");\n> +\n> +\tif (window <= ++idx)\n> +\t\tidx = 0;\n\n<ranting again>\nI cannot do otherwise but hate this notation.  Just for this one I had \nto spend at least 5 seconds thinking about it before I could convince \nmyself it is OK.  It annoyed me so much that I switched the condition \naround in my local copy.  I acknowledge your maintainer priviledges, but \nI couldn't stop myself making noise about this again anyway.\n</ranting again>\n\n> +\t/*\n> +\t * The entry at idx modulo window will be evicted first during\n> +\t * the next round.  Where in the next window is the good_base\n> +\t * found?\n> +\t */\n> +\tgood_at = (good_base + window - idx) % window;\n> +\n> +\t/*\n> +\t * If it is already at the furthest edge, nothing needs to be done.\n> +\t */\n> +\tif (good_at == window - 1)\n> +\t\treturn;\n\nThis condition will never occur because, upon entering this function, \nidx points to the _current_ \nobject which is never considered as a base (can't deltify against self).  \nSo you probably should avoid increasing idx.\n\nYet I think it would be clearer if you had this instead (assuming idx \nunchanged):\n\n\t/* How far is the good base from the front of the window? */\n\tgood_dist = (window + idx - good_base) % window;\n\n\t/* If it is already at the furthest edge, nothing needs to be done. */\n\tif (good_dist <= 1)\n\t\treturn;\n\n\t/* Otherwise, stash it away, shift the others down and swap it in. */\n\tswap = array[good_base];\n\tdst = good_base;\n\twhile (--good_dist > 0) {\n\t\tsrc = (dst + 1) % window;\n\t\tarray[dst] = array[src];\n\t\tdst = src;\n\t}\n\tarray[dst] = swap;\n\n> +\tswap = array[good_base];\n> +\n> +\twhile (good_at < window) {\n\nThis also had the effect of moving down the current object, i.e. the one \nthat was just deltified.  Maybe this is a good thing, in which case the \n\"if (good_dist <= 1)\" above can be deleted and \"while (good_dist-- > 0)\" \nused instead.\n\n\nNicolas\n"},{"id":"51843","messageId":"7vsl62p2gg.fsf@gitster.siamese.dyndns.org","threadId":"9663","inReplyTo":"alpine.LFD.0.999.0708291339580.16727@xanadu.home","subject":"Re: [PATCH] Keep last used delta base in the delta window","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-29T19:26:07Z","receivedAt":"2007-08-29T19:26:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n>> > Instead of treating the \"the last used one happened to be on the\n>> > horizon -- try not to drop it\" special case, I wonder if it\n>> > makes sense to float the last used delta base object early in\n>> > the window _after_ it is used.  Wouldn't we keep more than one\n>> > very recently used delta base objects in the window that way?\n>> \n>> The attached is my quick-and-dirty one.  \n>\n> I like this.  A LRU sorting of base objects is obviously a good thing to \n> do.  Some comments below.\n\nWell, I said it is Q&D, because _I_ didn't like what I did ;-).\n\nThe original implementation of window as a plain array of\n\"struct unpacked\" made perfect sense because its use was strict\nFIFO.  Adding new element and expiring oldest element was just\nan increment of the \"idx\" integer, and there was no memmove\noverhead.\n\nIf we are to make this into LRU (which I _do_ like), however,\nthe data structure's circular FIFO origin makes the code\nunnecessary complex and inefficient, I think.\n\n - We can always say 0 is the bottom and (window-1) is the top.\n   Then ((idx+1)%window) becomes unnecessary.  As a bonus, we do\n   not have to disagree if it should be (window <= idx) or (idx\n   >= window).\n\n - Shifting elements down to make room can become a single\n   memmove() if we remove the circular FIFO origin from the\n   window implementation.  The Q&D one has tons of structure\n   assignments in each iteration.  It might even make sense to\n   change the window itself an array of \"struct unpacked *\" and\n   make LRU management into just memmove() of bunch of pointers.\n"},{"id":"51853","messageId":"alpine.LFD.0.999.0708291656410.16727@xanadu.home","threadId":"9663","inReplyTo":"7vsl62p2gg.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] Keep last used delta base in the delta window","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-08-29T21:02:06Z","receivedAt":"2007-08-29T21:02:06Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 29 Aug 2007, Junio C Hamano wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> >> > Instead of treating the \"the last used one happened to be on the\n> >> > horizon -- try not to drop it\" special case, I wonder if it\n> >> > makes sense to float the last used delta base object early in\n> >> > the window _after_ it is used.  Wouldn't we keep more than one\n> >> > very recently used delta base objects in the window that way?\n> >> \n> >> The attached is my quick-and-dirty one.  \n> >\n> > I like this.  A LRU sorting of base objects is obviously a good thing to \n> > do.  Some comments below.\n> \n> Well, I said it is Q&D, because _I_ didn't like what I did ;-).\n> \n> The original implementation of window as a plain array of\n> \"struct unpacked\" made perfect sense because its use was strict\n> FIFO.  Adding new element and expiring oldest element was just\n> an increment of the \"idx\" integer, and there was no memmove\n> overhead.\n> \n> If we are to make this into LRU (which I _do_ like), however,\n> the data structure's circular FIFO origin makes the code\n> unnecessary complex and inefficient, I think.\n> \n>  - We can always say 0 is the bottom and (window-1) is the top.\n>    Then ((idx+1)%window) becomes unnecessary.  As a bonus, we do\n>    not have to disagree if it should be (window <= idx) or (idx\n>    >= window).\n> \n>  - Shifting elements down to make room can become a single\n>    memmove() if we remove the circular FIFO origin from the\n>    window implementation.  The Q&D one has tons of structure\n>    assignments in each iteration.  It might even make sense to\n>    change the window itself an array of \"struct unpacked *\" and\n>    make LRU management into just memmove() of bunch of pointers.\n\nRight.\n\nIn the mean time, here's a simplification of your code.  Given that \nruntime appears to be unchanged, this could be used as is and a separate \npatch to clean LRU handling.\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 9b3ef94..c33d00f 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1456,7 +1456,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \tdo {\n \t\tstruct object_entry *entry = list[--i];\n \t\tstruct unpacked *n = array + idx;\n-\t\tint j;\n+\t\tint j, best_base = -1;\n \n \t\tif (!entry->preferred_base)\n \t\t\tprocessed++;\n@@ -1501,6 +1501,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \n \t\tj = window;\n \t\twhile (--j > 0) {\n+\t\t\tint ret;\n \t\t\tuint32_t other_idx = idx + j;\n \t\t\tstruct unpacked *m;\n \t\t\tif (other_idx >= window)\n@@ -1508,8 +1509,11 @@ static void find_deltas(struct object_entry **list, int window, int depth)\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, max_depth) < 0)\n+\t\t\tret = try_delta(n, m, max_depth);\n+\t\t\tif (ret < 0)\n \t\t\t\tbreak;\n+\t\t\telse if (ret > 0)\n+\t\t\t\tbest_base = other_idx;\n \t\t}\n \n \t\t/* if we made n a delta, and if n is already at max\n@@ -1519,6 +1523,23 @@ static void find_deltas(struct object_entry **list, int window, int depth)\n \t\tif (entry->delta && depth <= n->depth)\n \t\t\tcontinue;\n \n+\t\t/*\n+\t\t * Move the best delta base up in the window, after the\n+\t\t * currently deltified object, to keep it longer.  It will\n+\t\t * be the first base object to be attempted next.\n+\t\t */\n+\t\tif (entry->delta) {\n+\t\t\tstruct unpacked swap = array[best_base];\n+\t\t\tint dist = (window + idx - best_base) % window;\n+\t\t\tint dst = best_base;\n+\t\t\twhile (dist--) {\n+\t\t\t\tint src = (dst + 1) % window;\n+\t\t\t\tarray[dst] = array[src];\n+\t\t\t\tdst = src;\n+\t\t\t}\n+\t\t\tarray[dst] = swap;\n+\t\t}\n+\n \t\tnext:\n \t\tidx++;\n \t\tif (count + 1 < window)\n"}]}