{"thread":{"id":"48801","subject":"fast-import slowness when importing large files with small differences","startedAt":"2018-06-29T10:18:49Z","lastAt":"2018-07-27T22:24:10Z","messageCount":17,"participants":["Mike Hommey","Stefan Beller","Jeff King","Junio C Hamano","Ævar Arnfjörð Bjarmason","Jun Wu","Michael Haggerty"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"351326","messageId":"20180629094413.bgltep6ntlza6vhz@glandium.org","threadId":"48801","inReplyTo":null,"subject":"fast-import slowness when importing large files with small differences","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2018-06-29T09:44:13Z","receivedAt":"2018-06-29T10:18:49Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"Hi,\n\nI noticed some slowness when fast-importing data from the Firefox mercurial\nrepository, where fast-import spends more than 5 minutes importing ~2000\nrevisions of one particular file. I reduced a testcase while still\nusing real data. One could synthesize data with kind of the same\nproperties, but I figured real data could be useful.\n\nTo reproduce:\n$ git clone https://gist.github.com/b6b8edcff2005cc482cf84972adfbba9.git foo\n$ git init bar\n$ cd bar\n$ python ../foo/import.py ../foo/data.gz | git fast-import --depth=2000\n\n(--depth=2000 to minimize the pack size)\n\nThe python script doesn't have much overhead:\n$ time python ../foo/import.py ../foo/data.gz > /dev/null\n\nreal\t0m14.564s\nuser\t0m9.813s\nsys\t0m4.703s\n\nIt generates about 26GB of data from that 4.2MB data.gz.\n\n$ python ../foo/import.py ../foo/data.gz | time git fast-import --depth=2000\ngit-fast-import statistics:\n---------------------------------------------------------------------\nAlloc'd objects:       5000\nTotal objects:         1868 (       133 duplicates                  )\n      blobs  :         1868 (       133 duplicates       1867 deltas of       1868 attempts)\n      trees  :            0 (         0 duplicates          0 deltas of          0 attempts)\n      commits:            0 (         0 duplicates          0 deltas of          0 attempts)\n      tags   :            0 (         0 duplicates          0 deltas of          0 attempts)\nTotal branches:           0 (         0 loads     )\n      marks:           1024 (         0 unique    )\n      atoms:              0\nMemory total:          2282 KiB\n       pools:          2048 KiB\n     objects:           234 KiB\n---------------------------------------------------------------------\npack_report: getpagesize()            =       4096\npack_report: core.packedGitWindowSize = 1073741824\npack_report: core.packedGitLimit      = 35184372088832\npack_report: pack_used_ctr            =          0\npack_report: pack_mmap_calls          =          0\npack_report: pack_open_windows        =          0 /          0\npack_report: pack_mapped              =          0 /          0\n---------------------------------------------------------------------\n\n321.61user 6.60system 5:50.08elapsed 93%CPU (0avgtext+0avgdata 83192maxresident)k\n0inputs+10568outputs (0major+38689minor)pagefaults 0swaps\n\n(The resulting pack is 5.3MB, fwiw)\n\nObviously, sha1'ing 26GB is not going to be free, but it's also not the\ndominating cost, according to perf:\n\n    63.52%  git-fast-import  git-fast-import     [.] create_delta_index\n    17.46%  git-fast-import  git-fast-import     [.] sha1_compression_states\n     9.89%  git-fast-import  git-fast-import     [.] ubc_check\n     6.23%  git-fast-import  git-fast-import     [.] create_delta\n     2.49%  git-fast-import  git-fast-import     [.] sha1_process\n\nThat's a whole lot of time spent on create_delta_index.\n\nFWIW, if delta was 100% free (yes, I tested that), the fast-import would\ntake 1:40 with the following profile:\n\n    58.74%  git-fast-import  git-fast-import     [.] sha1_compression_states\n    32.45%  git-fast-import  git-fast-import     [.] ubc_check\n     8.25%  git-fast-import  git-fast-import     [.] sha1_process\n\nI toyed with the idea of eliminating common head and tail before\ncreating the delta, and got some promising result: a fast-import taking\n3:22 instead of 5:50, with the following profile:\n\n    34.67%  git-fast-import  git-fast-import     [.] create_delta_index\n    30.88%  git-fast-import  git-fast-import     [.] sha1_compression_states\n    17.15%  git-fast-import  git-fast-import     [.] ubc_check\n     7.25%  git-fast-import  git-fast-import     [.] store_object\n     4.47%  git-fast-import  git-fast-import     [.] sha1_process\n     2.72%  git-fast-import  git-fast-import     [.] create_delta2\n\nThe resulting pack is however much larger (for some reason, many objects\nare left non-deltaed), and the deltas are partly broken (they don't\napply cleanly), but that just tells the code is not ready to be sent. I\ndon't expect working code would be much slower than this. The remaining\nquestion is whether this is beneficial for more normal cases.\n\nI also seemed to remember when I tested a while ago, that somehow xdiff\nhandles those files faster than diff-delta, and I'm wondering if it\nwould make sense to to make the pack code use xdiff. So I tested\nreplacing diff_delta with a call to xdi_diff_outf with a callback that\ndoes nothing and zeroed out xpparam_t and xdemitconf_t (not sure that's\nbest, though, I haven't looked very deeply), and that finished in 5:15\nwith the following profile (without common head trimming,\nxdiff-interface apparently does common tail trimming):\n\n    32.99%  git-fast-import  git-fast-import     [.] xdl_prepare_ctx.isra.0\n    20.42%  git-fast-import  git-fast-import     [.] sha1_compression_states\n    15.26%  git-fast-import  git-fast-import     [.] xdl_hash_record\n    11.65%  git-fast-import  git-fast-import     [.] ubc_check\n     3.09%  git-fast-import  git-fast-import     [.] xdl_recs_cmp\n     3.03%  git-fast-import  git-fast-import     [.] sha1_process\n     2.91%  git-fast-import  git-fast-import     [.] xdl_prepare_env\n\nSo maybe it would make sense to consolidate the diff code (after all,\ndiff-delta.c is an old specialized fork of xdiff). With manual trimming\nof common head and tail, this gets down to 3:33.\n\nI'll also note that Facebook has imported xdiff from the git code base\ninto mercurial and improved performance on it, so it might also be worth\nlooking at what's worth taking from there.\n\nCheers,\n\nMike\n"},{"id":"351374","messageId":"CAGZ79kb0FOafEsuXU7c_BTwPtcujFeyWVhzSuzFHRFtQHp9weQ@mail.gmail.com","threadId":"48801","inReplyTo":"20180629094413.bgltep6ntlza6vhz@glandium.org","subject":"Re: fast-import slowness when importing large files with small differences","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-06-29T20:14:52Z","receivedAt":"2018-06-29T20:15:08Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Jun 29, 2018 at 3:18 AM Mike Hommey <mh@glandium.org> wrote:\n>\n> Hi,\n>\n> I noticed some slowness when fast-importing data from the Firefox mercurial\n> repository, where fast-import spends more than 5 minutes importing ~2000\n> revisions of one particular file. I reduced a testcase while still\n> using real data. One could synthesize data with kind of the same\n> properties, but I figured real data could be useful.\n\nI cc'd Jameson, who refactored memory allocation in fast-import recently.\n(I am not aware of other refactorings in the area of fast-import)\n\n> To reproduce:\n[...]\n> Memory total:          2282 KiB\n>        pools:          2048 KiB\n>      objects:           234 KiB\n>\n[...]\n> Obviously, sha1'ing 26GB is not going to be free, but it's also not the\n> dominating cost, according to perf:\n>\n>     63.52%  git-fast-import  git-fast-import     [.] create_delta_index\n\nSo this doesn't sound like a memory issue, but a diffing/deltaing issue.\n\n> So maybe it would make sense to consolidate the diff code (after all,\n> diff-delta.c is an old specialized fork of xdiff). With manual trimming\n> of common head and tail, this gets down to 3:33.\n\nThis sounds interesting. I'd love to see that code to be unified.\n\n> I'll also note that Facebook has imported xdiff from the git code base\n> into mercurial and improved performance on it, so it might also be worth\n> looking at what's worth taking from there.\n\nSo starting with\nhttps://www.mercurial-scm.org/repo/hg/rev/34e2ff1f9cd8\n(\"xdiff: vendor xdiff library from git\")\nthey adapted it slightly:\n$ hg log --template '{node|short} {desc|firstline}\\n' --\nmercurial/thirdparty/xdiff/\na2baa61bbb14 xdiff: move stdint.h to xdiff.h\nd40b9e29c114 xdiff: fix a hard crash on Windows\n651c80720eed xdiff: silence a 32-bit shift warning on Windows\nd255744de97a xdiff: backport int64_t and uint64_t types to Windows\ne5b14f5b8b94 xdiff: resolve signed unsigned comparison warning\nf1ef0e53e628 xdiff: use int64 for hash table size\nf0d9811dda8e xdiff: remove unused xpp and xecfg parameters\n49fe6249937a xdiff: remove unused flags parameter\n882657a9f768 xdiff: replace {unsigned ,}long with {u,}int64_t\n0c7350656f93 xdiff: add comments for fields in xdfile_t\nf33a87cf60cc xdiff: add a preprocessing step that trims files\n3cf40112efb7 xdiff: remove xmerge related logic\n90f8fe72446c xdiff: remove xemit related logic\nb5bb0f99064d xdiff: remove unused structure, functions, and constants\n09f320067591 xdiff: remove whitespace related feature\n1f9bbd1d6b8a xdiff: fix builds on Windows\nc420792217c8 xdiff: reduce indent heuristic overhead\nb3c9c483cac9 xdiff: add a bdiff hunk mode\n9e7b14caf67f xdiff: remove patience and histogram diff algorithms\n34e2ff1f9cd8 xdiff: vendor xdiff library from git\n\nInteresting pieces regarding performance:\n\nc420792217c8 xdiff: reduce indent heuristic overhead\nhttps://phab.mercurial-scm.org/rHGc420792217c89622482005c99e959b9071c109c5\n\nf33a87cf60cc xdiff: add a preprocessing step that trims files\nhttps://phab.mercurial-scm.org/rHGf33a87cf60ccb8b46e06b85e60bc5031420707d6\n\nI'll see if I can make that into patches.\n\nThanks,\nStefan\n"},{"id":"351375","messageId":"20180629202811.131265-1-sbeller@google.com","threadId":"48801","inReplyTo":"CAGZ79kb0FOafEsuXU7c_BTwPtcujFeyWVhzSuzFHRFtQHp9weQ@mail.gmail.com","subject":"[PATCH] xdiff: reduce indent heuristic overhead","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-06-29T20:28:11Z","receivedAt":"2018-06-29T20:28:19Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"This patch was written originally for mercurial at\nhttps://phab.mercurial-scm.org/rHGc420792217c89622482005c99e959b9071c109c5\n\n    changeset:   36674:c420792217c8\n    user:        Jun Wu <quark@fb.com>\n    date:        Sat Mar 03 12:39:11 2018 -0800\n    files:       mercurial/thirdparty/xdiff/xdiffi.c\n    description:\n    xdiff: reduce indent heuristic overhead\n\n    Adds some threshold to avoid expensive cases, like:\n\n    ```\n    #!python\n    open('a', 'w').write(\" \\n\" * 1000000)\n    open('b', 'w').write(\" \\n\" * 1000001)\n    ```\n\n    The indent heuristic is O(N * 20) (N = 1000000) for the above case, and\n    makes diff much slower.\n\n    Before this patch (system git 2.14.2):\n\n    ```\n    git diff --no-indent-heuristic a b  0.21s user 0.03s system 100% cpu 0.239 total\n    git diff --indent-heuristic a b     0.77s user 0.02s system 99% cpu 0.785 total\n    ```\n\n    After this patch (git 2fc74f41, with xdiffi.c patched):\n\n    ```\n    # with the changed xdiffi.c\n    git diff --indent-heuristic a b      0.16s user 0.01s system 90% cpu 0.188 total\n    git diff --no-indent-heuristic a b   0.18s user 0.01s system 99% cpu 0.192 total\n    ```\n\n    Now turning on indent-heuristic has no visible impact on performance.\n\n    Differential Revision: https://phab.mercurial-scm.org/D2601\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n\nThis applies on our master branch, I have not thought of a\ngood commit message or if we need to test it.\n\nThanks,\nStefan\n\n xdiff/xdiffi.c | 38 +++++++++++++++++++++++++++++++++++---\n 1 file changed, 35 insertions(+), 3 deletions(-)\n\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 0de1ef463bf..c74ec77da58 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -807,6 +807,14 @@ static void xdl_bug(const char *msg)\n \texit(1);\n }\n \n+/*\n+ * For indentation heuristic, skip searching for better slide position after\n+ * checking MAX_BORING lines without finding an improvement. This defends the\n+ * indentation heuristic logic against pathological cases. The value is not\n+ * picked scientifically but should be good enough.\n+ */\n+#define MAX_BORING 100\n+\n /*\n  * Move back and forward change groups for a consistent and pretty diff output.\n  * This also helps in finding joinable change groups and reducing the diff\n@@ -903,19 +911,43 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \t\t\tlong shift, best_shift = -1;\n \t\t\tstruct split_score best_score;\n \n-\t\t\tfor (shift = earliest_end; shift <= g.end; shift++) {\n+\t\t\t/*\n+\t\t\t * This is O(N * MAX_BLANKS) (N = shift-able lines).\n+\t\t\t * Even with MAX_BLANKS bounded to a small value, a\n+\t\t\t * large N could still make this loop take several\n+\t\t\t * times longer than the main diff algorithm. The\n+\t\t\t * \"boring\" value is to help cut down N to something\n+\t\t\t * like (MAX_BORING + groupsize).\n+\t\t\t *\n+\t\t\t * Scan from bottom to top. So we can exit the loop\n+\t\t\t * without compromising the assumption \"for a same best\n+\t\t\t * score, pick the bottommost shift\".\n+\t\t\t */\n+\t\t\tint boring = 0;\n+\t\t\tfor (shift = g.end; shift >= earliest_end; shift--) {\n \t\t\t\tstruct split_measurement m;\n \t\t\t\tstruct split_score score = {0, 0};\n+\t\t\t\tint cmp;\n \n \t\t\t\tmeasure_split(xdf, shift, &m);\n \t\t\t\tscore_add_split(&m, &score);\n \t\t\t\tmeasure_split(xdf, shift - groupsize, &m);\n \t\t\t\tscore_add_split(&m, &score);\n-\t\t\t\tif (best_shift == -1 ||\n-\t\t\t\t    score_cmp(&score, &best_score) <= 0) {\n+\n+\t\t\t\tif (best_shift == -1) {\n+\t\t\t\t\tcmp = -1;\n+\t\t\t\t} else {\n+\t\t\t\t\tcmp = score_cmp(&score, &best_score);\n+\t\t\t\t}\n+\t\t\t\tif (cmp < 0) {\n+\t\t\t\t\tboring = 0;\n \t\t\t\t\tbest_score.effective_indent = score.effective_indent;\n \t\t\t\t\tbest_score.penalty = score.penalty;\n \t\t\t\t\tbest_shift = shift;\n+\t\t\t\t} else {\n+\t\t\t\t\tboring += 1;\n+\t\t\t\t\tif (boring >= MAX_BORING)\n+\t\t\t\t\t\tbreak;\n \t\t\t\t}\n \t\t\t}\n \n-- \n2.18.0.399.gad0ab374a1-goog\n\n"},{"id":"351376","messageId":"20180629203904.GA27566@sigill.intra.peff.net","threadId":"48801","inReplyTo":"CAGZ79kb0FOafEsuXU7c_BTwPtcujFeyWVhzSuzFHRFtQHp9weQ@mail.gmail.com","subject":"Re: fast-import slowness when importing large files with small differences","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-06-29T20:39:04Z","receivedAt":"2018-06-29T20:39:09Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 29, 2018 at 01:14:52PM -0700, Stefan Beller wrote:\n\n> Interesting pieces regarding performance:\n> \n> c420792217c8 xdiff: reduce indent heuristic overhead\n> https://phab.mercurial-scm.org/rHGc420792217c89622482005c99e959b9071c109c5\n> \n> f33a87cf60cc xdiff: add a preprocessing step that trims files\n> https://phab.mercurial-scm.org/rHGf33a87cf60ccb8b46e06b85e60bc5031420707d6\n> \n> I'll see if I can make that into patches.\n\nApparently the second one is not so trivial as you might hope; see\nhttps://public-inbox.org/git/1520337165-sup-4504@x1c/.\n\n-Peff\n"},{"id":"351377","messageId":"CAGZ79kYSFnKhMPi3J=C-XHMuAg90J76Vir6ocv0uKWoKts4P-w@mail.gmail.com","threadId":"48801","inReplyTo":"20180629203904.GA27566@sigill.intra.peff.net","subject":"Re: fast-import slowness when importing large files with small differences","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-06-29T20:51:21Z","receivedAt":"2018-06-29T20:51:37Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"+cc Jun Wu, original author of these patches\n\nOn Fri, Jun 29, 2018 at 1:39 PM Jeff King <peff@peff.net> wrote:\n\n> > Interesting pieces regarding performance:\n> >\n> > c420792217c8 xdiff: reduce indent heuristic overhead\n> > https://phab.mercurial-scm.org/rHGc420792217c89622482005c99e959b9071c109c5\n\nGoing by the mailing list, the first patch was not brought over yet,\nso sending it here was warranted.\n\nJun, you may want to take ownership of\nhttps://public-inbox.org/git/20180629202811.131265-1-sbeller@google.com/\nas I merely resend it to the git mailing list?\nIf not, that is fine, too.\n\n> >\n> > f33a87cf60cc xdiff: add a preprocessing step that trims files\n> > https://phab.mercurial-scm.org/rHGf33a87cf60ccb8b46e06b85e60bc5031420707d6\n> >\n> > I'll see if I can make that into patches.\n>\n> Apparently the second one is not so trivial as you might hope; see\n> https://public-inbox.org/git/1520337165-sup-4504@x1c/.\n\nThanks so much, this saves me further effort to dig there.\nSo I'll just stop porting this.\n\nThanks,\nStefan\n"},{"id":"351379","messageId":"xmqqfu15thr8.fsf@gitster-ct.c.googlers.com","threadId":"48801","inReplyTo":"20180629202811.131265-1-sbeller@google.com","subject":"Re: [PATCH] xdiff: reduce indent heuristic overhead","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-29T21:17:15Z","receivedAt":"2018-06-29T21:17:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> This patch was written originally for mercurial at\n> https://phab.mercurial-scm.org/rHGc420792217c89622482005c99e959b9071c109c5\n>\n>     changeset:   36674:c420792217c8\n>     user:        Jun Wu <quark@fb.com>\n>     date:        Sat Mar 03 12:39:11 2018 -0800\n>     files:       mercurial/thirdparty/xdiff/xdiffi.c\n>     description:\n>     xdiff: reduce indent heuristic overhead\n\n... This should come with in-body header to credit the original\nauthor as the author, I think.\n\n"},{"id":"351389","messageId":"87o9ftckhb.fsf@evledraar.gmail.com","threadId":"48801","inReplyTo":"20180629094413.bgltep6ntlza6vhz@glandium.org","subject":"Re: fast-import slowness when importing large files with small differences","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-06-29T22:10:24Z","receivedAt":"2018-06-29T22:10:30Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Jun 29 2018, Mike Hommey wrote:\n\n> I noticed some slowness when fast-importing data from the Firefox mercurial\n> repository, where fast-import spends more than 5 minutes importing ~2000\n> revisions of one particular file. I reduced a testcase while still\n> using real data. One could synthesize data with kind of the same\n> properties, but I figured real data could be useful.\n>\n> To reproduce:\n> $ git clone https://gist.github.com/b6b8edcff2005cc482cf84972adfbba9.git foo\n> $ git init bar\n> $ cd bar\n> $ python ../foo/import.py ../foo/data.gz | git fast-import --depth=2000\n>\n> [...]\n> So maybe it would make sense to consolidate the diff code (after all,\n> diff-delta.c is an old specialized fork of xdiff). With manual trimming\n> of common head and tail, this gets down to 3:33.\n>\n> I'll also note that Facebook has imported xdiff from the git code base\n> into mercurial and improved performance on it, so it might also be worth\n> looking at what's worth taking from there.\n\nIt would be interesting to see how does this compares with a more naïve\napproach of committing every version of this file one-at-a-time into a\nnew repository (with & without gc.auto=0). Perhaps deltaing as we go is\nsuboptimal compared to just writing out a lot of redundant data and\nrepacking it all at once later.\n"},{"id":"351394","messageId":"20180629233538.7zxxrvou4twqyd6d@glandium.org","threadId":"48801","inReplyTo":"87o9ftckhb.fsf@evledraar.gmail.com","subject":"Re: fast-import slowness when importing large files with small differences","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2018-06-29T23:35:38Z","receivedAt":"2018-06-29T23:35:45Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Sat, Jun 30, 2018 at 12:10:24AM +0200, Ævar Arnfjörð Bjarmason wrote:\n> \n> On Fri, Jun 29 2018, Mike Hommey wrote:\n> \n> > I noticed some slowness when fast-importing data from the Firefox mercurial\n> > repository, where fast-import spends more than 5 minutes importing ~2000\n> > revisions of one particular file. I reduced a testcase while still\n> > using real data. One could synthesize data with kind of the same\n> > properties, but I figured real data could be useful.\n> >\n> > To reproduce:\n> > $ git clone https://gist.github.com/b6b8edcff2005cc482cf84972adfbba9.git foo\n> > $ git init bar\n> > $ cd bar\n> > $ python ../foo/import.py ../foo/data.gz | git fast-import --depth=2000\n> >\n> > [...]\n> > So maybe it would make sense to consolidate the diff code (after all,\n> > diff-delta.c is an old specialized fork of xdiff). With manual trimming\n> > of common head and tail, this gets down to 3:33.\n> >\n> > I'll also note that Facebook has imported xdiff from the git code base\n> > into mercurial and improved performance on it, so it might also be worth\n> > looking at what's worth taking from there.\n> \n> It would be interesting to see how does this compares with a more naïve\n> approach of committing every version of this file one-at-a-time into a\n> new repository (with & without gc.auto=0). Perhaps deltaing as we go is\n> suboptimal compared to just writing out a lot of redundant data and\n> repacking it all at once later.\n\n\"Just\" writing 26GB? And that's only one file. If I were to do that for\nthe whole repository, it would yield a > 100GB pack. Instead of < 2GB\ncurrently.\n\nMike\n"},{"id":"351395","messageId":"20180629233741.173309-1-sbeller@google.com","threadId":"48801","inReplyTo":"xmqqfu15thr8.fsf@gitster-ct.c.googlers.com","subject":"[PATCH] xdiff: reduce indent heuristic overhead","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-06-29T23:37:41Z","receivedAt":"2018-06-29T23:37:48Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"From: Jun Wu <quark@fb.com>\n\nThis patch was written originally for mercurial at [1],\nadding a limit on how long we'd be looking for an\noptimal indent heuristic. Choose the limit high enough\nto only limit edge cases.\n\n    Adds some threshold to avoid expensive cases, like:\n\n    ```\n    #!python\n    open('a', 'w').write(\" \\n\" * 1000000)\n    open('b', 'w').write(\" \\n\" * 1000001)\n    ```\n\n    The indent heuristic is O(N * 20) (N = 1000000) for the above case, and\n    makes diff much slower.\n\n    Before this patch (system git 2.14.2):\n\n    ```\n    git diff --no-indent-heuristic a b  0.21s user 0.03s system 100% cpu 0.239 total\n    git diff --indent-heuristic a b     0.77s user 0.02s system 99% cpu 0.785 total\n    ```\n\n    After this patch (git 2fc74f41, with xdiffi.c patched):\n\n    ```\n    # with the changed xdiffi.c\n    git diff --indent-heuristic a b      0.16s user 0.01s system 90% cpu 0.188 total\n    git diff --no-indent-heuristic a b   0.18s user 0.01s system 99% cpu 0.192 total\n    ```\n\n    Now turning on indent-heuristic has no visible impact on performance.\n\n    Differential Revision: https://phab.mercurial-scm.org/D2601\n\n[1] https://phab.mercurial-scm.org/rHGc420792217c89622482005c99e959b9071c109c5\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n\nJun, Junio\n\nBy changing the authorship we'd want to have a sign off from the original author,\nbefore applying; in the previous attempt, I was merely taking the code from\nmercurial as their copy of xdiff is also LGPLv2 so we are free to use that.\n\nThanks,\nStefan\n\n xdiff/xdiffi.c | 38 +++++++++++++++++++++++++++++++++++---\n 1 file changed, 35 insertions(+), 3 deletions(-)\n\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 0de1ef463bf..c74ec77da58 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -807,6 +807,14 @@ static void xdl_bug(const char *msg)\n \texit(1);\n }\n \n+/*\n+ * For indentation heuristic, skip searching for better slide position after\n+ * checking MAX_BORING lines without finding an improvement. This defends the\n+ * indentation heuristic logic against pathological cases. The value is not\n+ * picked scientifically but should be good enough.\n+ */\n+#define MAX_BORING 100\n+\n /*\n  * Move back and forward change groups for a consistent and pretty diff output.\n  * This also helps in finding joinable change groups and reducing the diff\n@@ -903,19 +911,43 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \t\t\tlong shift, best_shift = -1;\n \t\t\tstruct split_score best_score;\n \n-\t\t\tfor (shift = earliest_end; shift <= g.end; shift++) {\n+\t\t\t/*\n+\t\t\t * This is O(N * MAX_BLANKS) (N = shift-able lines).\n+\t\t\t * Even with MAX_BLANKS bounded to a small value, a\n+\t\t\t * large N could still make this loop take several\n+\t\t\t * times longer than the main diff algorithm. The\n+\t\t\t * \"boring\" value is to help cut down N to something\n+\t\t\t * like (MAX_BORING + groupsize).\n+\t\t\t *\n+\t\t\t * Scan from bottom to top. So we can exit the loop\n+\t\t\t * without compromising the assumption \"for a same best\n+\t\t\t * score, pick the bottommost shift\".\n+\t\t\t */\n+\t\t\tint boring = 0;\n+\t\t\tfor (shift = g.end; shift >= earliest_end; shift--) {\n \t\t\t\tstruct split_measurement m;\n \t\t\t\tstruct split_score score = {0, 0};\n+\t\t\t\tint cmp;\n \n \t\t\t\tmeasure_split(xdf, shift, &m);\n \t\t\t\tscore_add_split(&m, &score);\n \t\t\t\tmeasure_split(xdf, shift - groupsize, &m);\n \t\t\t\tscore_add_split(&m, &score);\n-\t\t\t\tif (best_shift == -1 ||\n-\t\t\t\t    score_cmp(&score, &best_score) <= 0) {\n+\n+\t\t\t\tif (best_shift == -1) {\n+\t\t\t\t\tcmp = -1;\n+\t\t\t\t} else {\n+\t\t\t\t\tcmp = score_cmp(&score, &best_score);\n+\t\t\t\t}\n+\t\t\t\tif (cmp < 0) {\n+\t\t\t\t\tboring = 0;\n \t\t\t\t\tbest_score.effective_indent = score.effective_indent;\n \t\t\t\t\tbest_score.penalty = score.penalty;\n \t\t\t\t\tbest_shift = shift;\n+\t\t\t\t} else {\n+\t\t\t\t\tboring += 1;\n+\t\t\t\t\tif (boring >= MAX_BORING)\n+\t\t\t\t\t\tbreak;\n \t\t\t\t}\n \t\t\t}\n \n-- \n2.18.0.399.gad0ab374a1-goog\n\n"},{"id":"351396","messageId":"1530320014-sup-1592@x1c","threadId":"48801","inReplyTo":"20180629233741.173309-1-sbeller@google.com","subject":"Re: [PATCH] xdiff: reduce indent heuristic overhead","fromName":"Jun Wu","fromEmail":"quark@fb.com","sentAt":"2018-06-30T01:11:16Z","receivedAt":"2018-06-30T01:12:12Z","isPatch":true,"sender":{"key":"quark@fb.com","avatar":null},"body":"Excerpts from Stefan Beller's message of 2018-06-29 16:37:41 -0700:\n> [...]\n> Jun, Junio\n> \n> By changing the authorship we'd want to have a sign off from the original author,\n> before applying; in the previous attempt, I was merely taking the code from\n> mercurial as their copy of xdiff is also LGPLv2 so we are free to use that.\n\nI'm fine with signing off the patch. I didn't send this one here mainly\nbecause indent heuristic was default off at the time I made the changes, and\nI wasn't sure about how to test this properly according to the git community\nstandard. If this change is fine without additional tests, I can send it\nmyself, too.\n\n> Thanks,\n> Stefan\n> \n> [...]\n"},{"id":"351476","messageId":"72ac1ac2-f567-f241-41d6-d0f83072e0b3@alum.mit.edu","threadId":"48801","inReplyTo":"20180629202811.131265-1-sbeller@google.com","subject":"Re: [PATCH] xdiff: reduce indent heuristic overhead","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-07-01T15:57:35Z","receivedAt":"2018-07-01T15:58:06Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/29/2018 10:28 PM, Stefan Beller wrote:\n> [...]\n>     Adds some threshold to avoid expensive cases, like:\n> \n>     ```\n>     #!python\n>     open('a', 'w').write(\" \\n\" * 1000000)\n>     open('b', 'w').write(\" \\n\" * 1000001)\n>     ```\n> \n>     The indent heuristic is O(N * 20) (N = 1000000) for the above case, and\n>     makes diff much slower.\n> [...]\n> +/*\n> + * For indentation heuristic, skip searching for better slide position after\n> + * checking MAX_BORING lines without finding an improvement. This defends the\n> + * indentation heuristic logic against pathological cases. The value is not\n> + * picked scientifically but should be good enough.\n> + */\n> +#define MAX_BORING 100\n\nThis is an interesting case, and a speed difference of almost a factor\nof five seems impressive. But this is a pretty pathological case, isn't\nit? And I'm pretty sure that the algorithm is `O(N)` both before and\nafter this change. Remember that to find `earliest_end` and `g.end`,\nthere has already been a scan through all 1000000 lines. In other words,\nyou're not improving how the overall algorithm scales with `N`; you're\nonly changing the constant factor in front. So it's a little bit\nquestionable whether it is worth complicating the code for this unusual\ncase.\n\nBut *if* we want to improve this case, I think that we could be smarter\nabout it.\n\nBy the time we get to this point in the code, we already know that there\nis a \"slider\" hunk of length `M` (`groupsize`) that can be slid up or\ndown within a range of `N` (`g.end - earliest_end + 1`) possible\npositions. The interesting case here is `N ≫ M`, because then naively\nthe number of positions to try out is a lot bigger than the size of the\nhunk itself. (In the case described above, `N` is 1000000 and `M` is 1.)\n\nBut how can that situation even arise? Remember, a hunk can only be slid\ndown by a line if the first line *after* the hunk is identical to the\nfirst line *of* the hunk. It follows that if you shift a hunk down `M`\nlines, then it has the same contents as when you started—you've just\nrotated all of the hunk lines around once.\n\nSo if `N ≫ M`, there is necessarily a lot of repetition among the `N +\nM` lines that the hunk could possibly overlay. Specifically, it must\nconsist of `floor((N + M)/M)` identical copies of the hunk, plus\npossibly a few leftover lines constituting the start of another repetition.\n\nGiven this large amount of repetition, it seems to me that there is\nnever a need to scan more than the bottom `M + 1` possible positions [1]\nplus the highest possible position [2] to be sure of finding the very\nbest one. In the pathological case that you described above, where `M`\nis 1, only three positions have to be evaluated, not 100.\n\nIn fact, it *could* be that there is even more repetition, namely if the\nhunk itself contains multiple copies of an even shorter block of `K`\nlines. In that case, you would only have to scan `K + 1` positions at\nthe bottom plus one at the top to be sure to find the best hunk\nposition. This would be an interesting optimization for a case like\n\n>     open('a', 'w').write(\" \\n\" * 1000000)\n>     open('b', 'w').write(\" \\n\" * 1100000)\n\n(`N = 1000000`, `M = 100000`, `K = 1`) or\n\n>     open('a', 'w').write(\"<item>\\nMISSING\\n</item>\\n\" * 1000000)\n>     open('b', 'w').write(\"<item>\\nMISSING\\n</item>\\n\" * 1100000)\n\n(`N = 3000000`, `M = 300000`, `K = 3`). On the other hand, it's not\nentirely trivial to find periodicity in a group of lines (i.e., to find\n`K`), and I don't know offhand how that task scales with `M`.\n\nMichael\n\n[1] Actually, to be rigorously correct it might be necessary to check\neven a bit more than `M + 1` positions at the bottom because the\nheuristic looks a bit beyond the lines of the hunk.\n\n[2] The position at the top has different predecessor lines than the\nother positions, so it could have a lower score than all of the others.\nIt's worth checking it. Here too, to be rigorously correct it might be\nnecessary to check more than one position at the top because the\nheuristic looks a bit beyond the lines of the hunk.\n"},{"id":"351533","messageId":"CAGZ79kZzrdswds4ejCJrhJD1UcJeODdhifX5-UREuK5wPUM-rg@mail.gmail.com","threadId":"48801","inReplyTo":"72ac1ac2-f567-f241-41d6-d0f83072e0b3@alum.mit.edu","subject":"Re: [PATCH] xdiff: reduce indent heuristic overhead","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-07-02T17:27:31Z","receivedAt":"2018-07-02T17:27:47Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Sun, Jul 1, 2018 at 8:57 AM Michael Haggerty <mhagger@alum.mit.edu> wrote:\n>\n> On 06/29/2018 10:28 PM, Stefan Beller wrote:\n> > [...]\n> >     Adds some threshold to avoid expensive cases, like:\n> >\n> >     ```\n> >     #!python\n> >     open('a', 'w').write(\" \\n\" * 1000000)\n> >     open('b', 'w').write(\" \\n\" * 1000001)\n> >     ```\n> >\n> >     The indent heuristic is O(N * 20) (N = 1000000) for the above case, and\n> >     makes diff much slower.\n> > [...]\n> > +/*\n> > + * For indentation heuristic, skip searching for better slide position after\n> > + * checking MAX_BORING lines without finding an improvement. This defends the\n> > + * indentation heuristic logic against pathological cases. The value is not\n> > + * picked scientifically but should be good enough.\n> > + */\n> > +#define MAX_BORING 100\n>\n> This is an interesting case, and a speed difference of almost a factor\n> of five seems impressive. But this is a pretty pathological case, isn't\n> it? And I'm pretty sure that the algorithm is `O(N)` both before and\n> after this change. Remember that to find `earliest_end` and `g.end`,\n> there has already been a scan through all 1000000 lines. In other words,\n> you're not improving how the overall algorithm scales with `N`; you're\n> only changing the constant factor in front. So it's a little bit\n> questionable whether it is worth complicating the code for this unusual\n> case.\n>\n> But *if* we want to improve this case, I think that we could be smarter\n> about it.\n>\n> By the time we get to this point in the code, we already know that there\n> is a \"slider\" hunk of length `M` (`groupsize`) that can be slid up or\n> down within a range of `N` (`g.end - earliest_end + 1`) possible\n> positions. The interesting case here is `N ≫ M`, because then naively\n> the number of positions to try out is a lot bigger than the size of the\n> hunk itself. (In the case described above, `N` is 1000000 and `M` is 1.)\n>\n> But how can that situation even arise? Remember, a hunk can only be slid\n> down by a line if the first line *after* the hunk is identical to the\n> first line *of* the hunk. It follows that if you shift a hunk down `M`\n> lines, then it has the same contents as when you started—you've just\n> rotated all of the hunk lines around once.\n>\n> So if `N ≫ M`, there is necessarily a lot of repetition among the `N +\n> M` lines that the hunk could possibly overlay. Specifically, it must\n> consist of `floor((N + M)/M)` identical copies of the hunk, plus\n> possibly a few leftover lines constituting the start of another repetition.\n>\n> Given this large amount of repetition, it seems to me that there is\n> never a need to scan more than the bottom `M + 1` possible positions [1]\n> plus the highest possible position [2] to be sure of finding the very\n> best one. In the pathological case that you described above, where `M`\n> is 1, only three positions have to be evaluated, not 100.\n>\n> In fact, it *could* be that there is even more repetition, namely if the\n> hunk itself contains multiple copies of an even shorter block of `K`\n> lines. In that case, you would only have to scan `K + 1` positions at\n> the bottom plus one at the top to be sure to find the best hunk\n> position. This would be an interesting optimization for a case like\n>\n> >     open('a', 'w').write(\" \\n\" * 1000000)\n> >     open('b', 'w').write(\" \\n\" * 1100000)\n>\n> (`N = 1000000`, `M = 100000`, `K = 1`) or\n>\n> >     open('a', 'w').write(\"<item>\\nMISSING\\n</item>\\n\" * 1000000)\n> >     open('b', 'w').write(\"<item>\\nMISSING\\n</item>\\n\" * 1100000)\n>\n> (`N = 3000000`, `M = 300000`, `K = 3`). On the other hand, it's not\n> entirely trivial to find periodicity in a group of lines (i.e., to find\n> `K`), and I don't know offhand how that task scales with `M`.\n>\n> Michael\n>\n> [1] Actually, to be rigorously correct it might be necessary to check\n> even a bit more than `M + 1` positions at the bottom because the\n> heuristic looks a bit beyond the lines of the hunk.\n>\n> [2] The position at the top has different predecessor lines than the\n> other positions, so it could have a lower score than all of the others.\n> It's worth checking it. Here too, to be rigorously correct it might be\n> necessary to check more than one position at the top because the\n> heuristic looks a bit beyond the lines of the hunk.\n\nSo this suggests to have MAX_BORING to be\n\"hunk size + some small constant offset\" ?\n\nStefan\n"},{"id":"351584","messageId":"CAMy9T_HUdszkq8c545puzCpjvh1pKAL7MWtnrZFagNndyyxK7A@mail.gmail.com","threadId":"48801","inReplyTo":"CAGZ79kZzrdswds4ejCJrhJD1UcJeODdhifX5-UREuK5wPUM-rg@mail.gmail.com","subject":"Re: [PATCH] xdiff: reduce indent heuristic overhead","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2018-07-03T09:15:00Z","receivedAt":"2018-07-03T09:15:18Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On Mon, Jul 2, 2018 at 7:27 PM Stefan Beller <sbeller@google.com> wrote:\n> On Sun, Jul 1, 2018 at 8:57 AM Michael Haggerty <mhagger@alum.mit.edu> wrote:\n> [...]\n> So this suggests to have MAX_BORING to be\n> \"hunk size + some small constant offset\" ?\n\nThat would be my suggestion, yes. There are cases where it will be\nmore expensive than a fixed `MAX_BORING`, but I bet on average it will\nbe faster. Plus, it should always give the right answer.\n\nMichael\n"},{"id":"351628","messageId":"87muv8cnk3.fsf@evledraar.gmail.com","threadId":"48801","inReplyTo":"20180629233538.7zxxrvou4twqyd6d@glandium.org","subject":"Re: fast-import slowness when importing large files with small differences","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2018-07-03T16:05:16Z","receivedAt":"2018-07-03T16:05:22Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Jun 29 2018, Mike Hommey wrote:\n\n> On Sat, Jun 30, 2018 at 12:10:24AM +0200, Ævar Arnfjörð Bjarmason wrote:\n>>\n>> On Fri, Jun 29 2018, Mike Hommey wrote:\n>>\n>> > I noticed some slowness when fast-importing data from the Firefox mercurial\n>> > repository, where fast-import spends more than 5 minutes importing ~2000\n>> > revisions of one particular file. I reduced a testcase while still\n>> > using real data. One could synthesize data with kind of the same\n>> > properties, but I figured real data could be useful.\n>> >\n>> > To reproduce:\n>> > $ git clone https://gist.github.com/b6b8edcff2005cc482cf84972adfbba9.git foo\n>> > $ git init bar\n>> > $ cd bar\n>> > $ python ../foo/import.py ../foo/data.gz | git fast-import --depth=2000\n>> >\n>> > [...]\n>> > So maybe it would make sense to consolidate the diff code (after all,\n>> > diff-delta.c is an old specialized fork of xdiff). With manual trimming\n>> > of common head and tail, this gets down to 3:33.\n>> >\n>> > I'll also note that Facebook has imported xdiff from the git code base\n>> > into mercurial and improved performance on it, so it might also be worth\n>> > looking at what's worth taking from there.\n>>\n>> It would be interesting to see how does this compares with a more naïve\n>> approach of committing every version of this file one-at-a-time into a\n>> new repository (with & without gc.auto=0). Perhaps deltaing as we go is\n>> suboptimal compared to just writing out a lot of redundant data and\n>> repacking it all at once later.\n>\n> \"Just\" writing 26GB? And that's only one file. If I were to do that for\n> the whole repository, it would yield a > 100GB pack. Instead of < 2GB\n> currently.\n\nTo clarify on my terse response. I mean to try this on an isolated test\ncase to see to what extent the problem you're describing is unique to\nfast-import, and to what extent it's encountered during \"normal\" git use\nwhen you commit all the revisions of that file in succession.\n\nPerhaps the difference between the two would give some hint as to how to\nproceed, or not.\n"},{"id":"351633","messageId":"xmqq1sckrxtp.fsf@gitster-ct.c.googlers.com","threadId":"48801","inReplyTo":"72ac1ac2-f567-f241-41d6-d0f83072e0b3@alum.mit.edu","subject":"Re: [PATCH] xdiff: reduce indent heuristic overhead","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-07-03T18:14:26Z","receivedAt":"2018-07-03T18:14:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> So if `N ≫ M`, there is necessarily a lot of repetition among the `N +\n> M` lines that the hunk could possibly overlay. Specifically, it must\n> consist of `floor((N + M)/M)` identical copies of the hunk, plus\n> possibly a few leftover lines constituting the start of another repetition.\n>\n> Given this large amount of repetition, it seems to me that there is\n> never a need to scan more than the bottom `M + 1` possible positions [1]\n> plus the highest possible position [2] to be sure of finding the very\n> best one. In the pathological case that you described above, where `M`\n> is 1, only three positions have to be evaluated, not 100.\n\nNicely analysed.\n"},{"id":"351670","messageId":"20180703223823.qedmoy2imp4dcvkp@glandium.org","threadId":"48801","inReplyTo":"87muv8cnk3.fsf@evledraar.gmail.com","subject":"Re: fast-import slowness when importing large files with small differences","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2018-07-03T22:38:23Z","receivedAt":"2018-07-03T22:38:29Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Tue, Jul 03, 2018 at 06:05:16PM +0200, Ævar Arnfjörð Bjarmason wrote:\n> \n> On Fri, Jun 29 2018, Mike Hommey wrote:\n> \n> > On Sat, Jun 30, 2018 at 12:10:24AM +0200, Ævar Arnfjörð Bjarmason wrote:\n> >>\n> >> On Fri, Jun 29 2018, Mike Hommey wrote:\n> >>\n> >> > I noticed some slowness when fast-importing data from the Firefox mercurial\n> >> > repository, where fast-import spends more than 5 minutes importing ~2000\n> >> > revisions of one particular file. I reduced a testcase while still\n> >> > using real data. One could synthesize data with kind of the same\n> >> > properties, but I figured real data could be useful.\n> >> >\n> >> > To reproduce:\n> >> > $ git clone https://gist.github.com/b6b8edcff2005cc482cf84972adfbba9.git foo\n> >> > $ git init bar\n> >> > $ cd bar\n> >> > $ python ../foo/import.py ../foo/data.gz | git fast-import --depth=2000\n> >> >\n> >> > [...]\n> >> > So maybe it would make sense to consolidate the diff code (after all,\n> >> > diff-delta.c is an old specialized fork of xdiff). With manual trimming\n> >> > of common head and tail, this gets down to 3:33.\n> >> >\n> >> > I'll also note that Facebook has imported xdiff from the git code base\n> >> > into mercurial and improved performance on it, so it might also be worth\n> >> > looking at what's worth taking from there.\n> >>\n> >> It would be interesting to see how does this compares with a more naïve\n> >> approach of committing every version of this file one-at-a-time into a\n> >> new repository (with & without gc.auto=0). Perhaps deltaing as we go is\n> >> suboptimal compared to just writing out a lot of redundant data and\n> >> repacking it all at once later.\n> >\n> > \"Just\" writing 26GB? And that's only one file. If I were to do that for\n> > the whole repository, it would yield a > 100GB pack. Instead of < 2GB\n> > currently.\n> \n> To clarify on my terse response. I mean to try this on an isolated test\n> case to see to what extent the problem you're describing is unique to\n> fast-import, and to what extent it's encountered during \"normal\" git use\n> when you commit all the revisions of that file in succession.\n> \n> Perhaps the difference between the two would give some hint as to how to\n> proceed, or not.\n\nAIUI, git repack will end up creating delta indexes for every blob, so the\nproblem should exist there, but because it will be comparing \"random\"\nblobs, it can't take the same kinds of shortcuts as fast-import could,\nbecause fast-import only cares about diffing with the last imported\nblob. So while fast-import can reduce the amount of work it does by not\ncreating an index for common heads and tails of the compared blobs, git\nrepack can't.\n\nMike\n"},{"id":"353766","messageId":"20180727222356.96396-1-sbeller@google.com","threadId":"48801","inReplyTo":"CAMy9T_HUdszkq8c545puzCpjvh1pKAL7MWtnrZFagNndyyxK7A@mail.gmail.com","subject":"[PATCH] xdiff: reduce indent heuristic overhead","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-07-27T22:23:56Z","receivedAt":"2018-07-27T22:24:10Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"Skip searching for better indentation heuristics if we'd slide a hunk more\nthan its size. This is the easiest fix proposed in the analysis[1] in\nresponse to a patch that mercurial took for xdiff to limit searching\nby a constant. Using a performance test as:\n\n     #!python\n     open('a', 'w').write(\" \\n\" * 1000000)\n     open('b', 'w').write(\" \\n\" * 1000001)\n\nThis patch reduces the execution of \"git diff --no-index a b\" from\n0.70s to 0.31s. However limiting the sliding to the size of the diff hunk,\nwhich was proposed as a solution (that I found easiest to implement for\nnow) is not optimal for cases like\n\n     open('a', 'w').write(\" \\n\" * 1000000)\n     open('b', 'w').write(\" \\n\" * 2000000)\n\nas then we'd still slide 1000000 times.\n\nIn addition to limiting the sliding to size of the hunk, also limit by a\nconstant. Choose 100 lines as the constant as that fits more than a screen,\nwhich really means that the diff sliding is probably not providing a lot\nof benefit anyway.\n\n[1] https://public-inbox.org/git/72ac1ac2-f567-f241-41d6-d0f83072e0b3@alum.mit.edu/\n\nReported-by: Jun Wu <quark@fb.com>\nAnalysis-by: Michael Haggerty <mhagger@alum.mit.edu>\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n\n> Plus, it should always give the right answer.\n\nI was tempted to do just that, but I caved. The diff is correct,\nand the hunk sliding is purely to appease the visual aspect of\nhumans looking at diffs. If your diff can slide more than a\nmonitor height, you're not interested in the best slided diff,\nbut something else is going on.\n\n> There are cases where it will be\n> more expensive than a fixed `MAX_BORING`, but I bet on average it will\n> be faster.\n\nSo I did both, settling for performance as the utmost desire. ;-)\n\n xdiff/xdiffi.c | 12 +++++++++++-\n 1 file changed, 11 insertions(+), 1 deletion(-)\n\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 0de1ef463bf..91e98ee9869 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -591,6 +591,11 @@ static void measure_split(const xdfile_t *xdf, long split,\n  */\n #define INDENT_WEIGHT 60\n \n+/*\n+ * How far do we slide a hunk at most?\n+ */\n+#define INDENT_HEURISTIC_MAX_SLIDING 100\n+\n /*\n  * Compute a badness score for the hypothetical split whose measurements are\n  * stored in m. The weight factors were determined empirically using the tools and\n@@ -903,7 +908,12 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {\n \t\t\tlong shift, best_shift = -1;\n \t\t\tstruct split_score best_score;\n \n-\t\t\tfor (shift = earliest_end; shift <= g.end; shift++) {\n+\t\t\tshift = earliest_end;\n+\t\t\tif (g.end - groupsize - 1 > shift)\n+\t\t\t\tshift = g.end - groupsize - 1;\n+\t\t\tif (g.end - INDENT_HEURISTIC_MAX_SLIDING > shift)\n+\t\t\t\tshift = g.end - INDENT_HEURISTIC_MAX_SLIDING;\n+\t\t\tfor (; shift <= g.end; shift++) {\n \t\t\t\tstruct split_measurement m;\n \t\t\t\tstruct split_score score = {0, 0};\n \n-- \n2.18.0.345.g5c9ce644c3-goog\n\n"}]}