{"thread":{"id":"11187","subject":"[PATCH 1/2] pack-objects: reverse the delta search sort list","startedAt":"2007-12-08T05:00:08Z","lastAt":"2007-12-08T11:10:29Z","messageCount":4,"participants":["Nicolas Pitre","Junio C Hamano","Mike Hommey","Peter Baumann"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"62372","messageId":"alpine.LFD.0.99999.0712072357050.555@xanadu.home","threadId":"11187","inReplyTo":null,"subject":"[PATCH 1/2] pack-objects: reverse the delta search sort list","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-12-08T05:00:08Z","receivedAt":"2007-12-08T05:00:08Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nIt is currently sorted and then walked backward.  Not only this doesn't\nfeel natural for my poor brain, but it would make the next patch less\nobvious as well.\n\nSo reverse the sort order, and reverse the list walking direction,\nwhich effectively produce the exact same end result as before.\n\nAlso bring the relevant comment nearer the actual code and adjust it\naccordingly, with minor additional clarifications.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n builtin-pack-objects.c |   41 +++++++++++++++++++++--------------------\n 1 files changed, 21 insertions(+), 20 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 4f44658..5002cc6 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -1245,28 +1245,37 @@ static void get_object_details(void)\n \tfree(sorted_by_offset);\n }\n \n+/*\n+ * We search for deltas in a list sorted by type, by filename hash, and then\n+ * by size, so that we see progressively smaller and smaller files.\n+ * That's because we prefer deltas to be from the bigger file\n+ * to the smaller -- deletes are potentially cheaper, but perhaps\n+ * more importantly, the bigger file is likely the more recent\n+ * one.  The deepest deltas are therefore the oldest objects which are\n+ * less susceptible to be accessed often.\n+ */\n static int type_size_sort(const void *_a, const void *_b)\n {\n \tconst struct object_entry *a = *(struct object_entry **)_a;\n \tconst struct object_entry *b = *(struct object_entry **)_b;\n \n-\tif (a->type < b->type)\n-\t\treturn -1;\n \tif (a->type > b->type)\n-\t\treturn 1;\n-\tif (a->hash < b->hash)\n \t\treturn -1;\n-\tif (a->hash > b->hash)\n+\tif (a->type < b->type)\n \t\treturn 1;\n-\tif (a->preferred_base < b->preferred_base)\n+\tif (a->hash > b->hash)\n \t\treturn -1;\n-\tif (a->preferred_base > b->preferred_base)\n+\tif (a->hash < b->hash)\n \t\treturn 1;\n-\tif (a->size < b->size)\n+\tif (a->preferred_base > b->preferred_base)\n \t\treturn -1;\n+\tif (a->preferred_base < b->preferred_base)\n+\t\treturn 1;\n \tif (a->size > b->size)\n+\t\treturn -1;\n+\tif (a->size < b->size)\n \t\treturn 1;\n-\treturn a > b ? -1 : (a < b);  /* newest last */\n+\treturn a < b ? -1 : (a > b);  /* newest first */\n }\n \n struct unpacked {\n@@ -1317,14 +1326,6 @@ static pthread_mutex_t progress_mutex = PTHREAD_MUTEX_INITIALIZER;\n \n #endif\n \n-/*\n- * We search for deltas _backwards_ in a list sorted by type and\n- * by size, so that we see progressively smaller and smaller files.\n- * That's because we prefer deltas to be from the bigger file\n- * to the smaller - deletes are potentially cheaper, but perhaps\n- * more importantly, the bigger file is likely the more recent\n- * one.\n- */\n static int try_delta(struct unpacked *trg, struct unpacked *src,\n \t\t     unsigned max_depth, unsigned long *mem_usage)\n {\n@@ -1481,7 +1482,7 @@ static unsigned long free_unpacked(struct unpacked *n)\n static void find_deltas(struct object_entry **list, unsigned list_size,\n \t\t\tint window, int depth, unsigned *processed)\n {\n-\tuint32_t i = list_size, idx = 0, count = 0;\n+\tuint32_t i = 0, idx = 0, count = 0;\n \tunsigned int array_size = window * sizeof(struct unpacked);\n \tstruct unpacked *array;\n \tunsigned long mem_usage = 0;\n@@ -1490,7 +1491,7 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n \tmemset(array, 0, array_size);\n \n \tdo {\n-\t\tstruct object_entry *entry = list[--i];\n+\t\tstruct object_entry *entry = list[i++];\n \t\tstruct unpacked *n = array + idx;\n \t\tint j, max_depth, best_base = -1;\n \n@@ -1575,7 +1576,7 @@ static void find_deltas(struct object_entry **list, unsigned list_size,\n \t\t\tcount++;\n \t\tif (idx >= window)\n \t\t\tidx = 0;\n-\t} while (i > 0);\n+\t} while (i < list_size);\n \n \tfor (i = 0; i < window; ++i) {\n \t\tfree_delta_index(array[i].index);\n-- \n1.5.3.7.2184.ge321d-dirty\n"},{"id":"62388","messageId":"7vmyslwqdr.fsf@gitster.siamese.dyndns.org","threadId":"11187","inReplyTo":"alpine.LFD.0.99999.0712072357050.555@xanadu.home","subject":"[OT] perhaps we want to support copied-context diff output","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-12-08T08:18:56Z","receivedAt":"2007-12-08T08:18:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The patch looks correct, but I have an offtopic comment that does not\nhave anything to do with the problem being discussed right now.\n\nNicolas Pitre <nico@cam.org> writes:\n\n> diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\n> index 4f44658..5002cc6 100644\n> --- a/builtin-pack-objects.c\n> +++ b/builtin-pack-objects.c\n> @@ -1245,28 +1245,37 @@ static void get_object_details(void)\n> ...\n>  static int type_size_sort(const void *_a, const void *_b)\n>  {\n>  \tconst struct object_entry *a = *(struct object_entry **)_a;\n>  \tconst struct object_entry *b = *(struct object_entry **)_b;\n>  \n> -\tif (a->type < b->type)\n> -\t\treturn -1;\n>  \tif (a->type > b->type)\n> -\t\treturn 1;\n> -\tif (a->hash < b->hash)\n>  \t\treturn -1;\n> -\tif (a->hash > b->hash)\n> +\tif (a->type < b->type)\n>  \t\treturn 1;\n> -\tif (a->preferred_base < b->preferred_base)\n> +\tif (a->hash > b->hash)\n>  \t\treturn -1;\n> -\tif (a->preferred_base > b->preferred_base)\n> +\tif (a->hash < b->hash)\n>  \t\treturn 1;\n> -\tif (a->size < b->size)\n> +\tif (a->preferred_base > b->preferred_base)\n>  \t\treturn -1;\n> +\tif (a->preferred_base < b->preferred_base)\n> +\t\treturn 1;\n>  \tif (a->size > b->size)\n> +\t\treturn -1;\n> +\tif (a->size < b->size)\n>  \t\treturn 1;\n> -\treturn a > b ? -1 : (a < b);  /* newest last */\n> +\treturn a < b ? -1 : (a > b);  /* newest first */\n>  }\n\nBefore being able to understand what was going on, I had to shuffle the\nabove patch by duplicating the context lines, prefix them with '-' and\nthen '+', and grouping preimage lines and postimage lines together, to\ncome up with this patch:\n\n static int type_size_sort(const void *_a, const void *_b)\n {\n \tconst struct object_entry *a = *(struct object_entry **)_a;\n \tconst struct object_entry *b = *(struct object_entry **)_b;\n \n-\tif (a->type < b->type)\n-\t\treturn -1;\n-\tif (a->type > b->type)\n-\t\treturn 1;\n-\tif (a->hash < b->hash)\n-\t\treturn -1;\n-\tif (a->hash > b->hash)\n-\t\treturn 1;\n-\tif (a->preferred_base < b->preferred_base)\n-\t\treturn -1;\n-\tif (a->preferred_base > b->preferred_base)\n-\t\treturn 1;\n-\tif (a->size < b->size)\n-\t\treturn -1;\n-\tif (a->size > b->size)\n-\t\treturn 1;\n-\treturn a > b ? -1 : (a < b);  /* newest last */\n+\tif (a->type > b->type)\n+\t\treturn -1;\n+\tif (a->type < b->type)\n+\t\treturn 1;\n+\tif (a->hash > b->hash)\n+\t\treturn -1;\n+\tif (a->hash < b->hash)\n+\t\treturn 1;\n+\tif (a->preferred_base > b->preferred_base)\n+\t\treturn -1;\n+\tif (a->preferred_base < b->preferred_base)\n+\t\treturn 1;\n+\tif (a->size > b->size)\n+\t\treturn -1;\n+\tif (a->size < b->size)\n+\t\treturn 1;\n+\treturn a < b ? -1 : (a > b);  /* newest first */\n }\n\nPerhaps we may want to add \"diff -c\" (copied context) output format as\nan option, which may be easier to read.\n\nA possible alternative with much less impact to our toolset would be to\nstay with unified context format but employ some heuristics (e.g. \"a\nhunk has many small context lines between preimage and postimage pairs\")\nand rewrite the diff output automatically like what I did by hand above.\n\nThe problematic region has 26 lines, among which 9 lines are deleted\nmaterial and 9 lines are added material, and it contains 8 isolated\ngroups of unchanged material, one line each.  A heuristics to notice\nsuch excessively large number of groups of unchanged lines compared to\nthe size of the hunk itself would be reasonably easy to implement.\n"},{"id":"62392","messageId":"20071208085302.GA13432@glandium.org","threadId":"11187","inReplyTo":"7vmyslwqdr.fsf@gitster.siamese.dyndns.org","subject":"Re: [OT] perhaps we want to support copied-context diff output","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2007-12-08T08:53:02Z","receivedAt":"2007-12-08T08:53:02Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"> Perhaps we may want to add \"diff -c\" (copied context) output format as\n> an option, which may be easier to read.\n\nOr maybe use the patience diff.\n\nOn a testcase I had a few months ago, patience diff would give:\n@@ -42,11 +42,10 @@\n\n include $(DEPTH)/config/autoconf.mk\n\n+EXTRA_COMPONENTS = nsKillAll.js\n+\n include $(topsrcdir)/config/rules.mk\n\n-libs::\n-       $(INSTALL) $(srcdir)/nsKillAll.js $(DIST)/bin/components\n-\n clean::\n        rm -f $(DIST)/bin/components/nsKillAll.js\n\nWhere \"normal\" diff would give:\n@@ -42,10 +42,9 @@\n\n include $(DEPTH)/config/autoconf.mk\n\n-include $(topsrcdir)/config/rules.mk\n+EXTRA_COMPONENTS = nsKillAll.js\n\n-libs::\n-       $(INSTALL) $(srcdir)/nsKillAll.js $(DIST)/bin/components\n+include $(topsrcdir)/config/rules.mk\n\n clean::\n        rm -f $(DIST)/bin/components/nsKillAll.js\n\ngit outputs the same as the normal diff, bzr and svn seem to use the\npatience diff. Mercurial outputs almost the same as bzr and svn:\n@@ -42,10 +42,9 @@\n\n include $(DEPTH)/config/autoconf.mk\n\n+EXTRA_COMPONENTS = nsKillAll.js\n+\n include $(topsrcdir)/config/rules.mk\n-\n-libs::\n-       $(INSTALL) $(srcdir)/nsKillAll.js $(DIST)/bin/components\n\n clean::\n        rm -f $(DIST)/bin/components/nsKillAll.js\n\nMike\n"},{"id":"62401","messageId":"20071208111029.GB2844@xp.machine.xx","threadId":"11187","inReplyTo":"20071208085302.GA13432@glandium.org","subject":"Re: [OT] perhaps we want to support copied-context diff output","fromName":"Peter Baumann","fromEmail":"waste.manager@gmx.de","sentAt":"2007-12-08T11:10:29Z","receivedAt":"2007-12-08T11:10:29Z","isPatch":false,"sender":{"key":"waste.manager@gmx.de","avatar":null},"body":"On Sat, Dec 08, 2007 at 09:53:02AM +0100, Mike Hommey wrote:\n> > Perhaps we may want to add \"diff -c\" (copied context) output format as\n> > an option, which may be easier to read.\n> \n> Or maybe use the patience diff.\n> \n\n[... skip testcase showing a much nicer diff for human consumption ...]\n\nAFAIR bzr uses the patience diff already. I don't actually use bzr\n(obviously, because git is so much better:-) but it produces much nicer\ndiffs than git if you have many small changes nearby.\n\n-Peter\n"}]}