{"thread":{"id":"56926","subject":"[PATCH 0/3] xdiff: speedup histogram diff","startedAt":"2021-11-17T11:20:31Z","lastAt":"2021-11-19T22:19:26Z","messageCount":15,"participants":["Phillip Wood via GitGitGadget","Derrick Stolee","Jeff King","Phillip Wood","Johannes Schindelin","Ævar Arnfjörð Bjarmason"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"441470","messageId":"pull.1079.git.1637148025.gitgitgadget@gmail.com","threadId":"56926","inReplyTo":null,"subject":"[PATCH 0/3] xdiff: speedup histogram diff","fromName":"Phillip Wood via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-11-17T11:20:22Z","receivedAt":"2021-11-17T11:20:31Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Histogram is the only diff algorithm not to call xdl_classify_record().\nCalling xdl_classify_record() means that it is not necessary to use\nxdl_recmatch() when comparing lines, all that is necessary is to compare the\nhash values. This gives a 7% reduction in the runtime of \"git log --patch\"\nwhen using the histogram diff algorithm.\n\nPhillip Wood (3):\n  diff histogram: intern strings\n  xdiff: avoid unnecessary memory allocations\n  xdiff: simplify comparison\n\n xdiff/xdiffi.c     |  5 +----\n xdiff/xhistogram.c |  5 ++---\n xdiff/xprepare.c   | 35 +++++++++++++++--------------------\n 3 files changed, 18 insertions(+), 27 deletions(-)\n\n\nbase-commit: cd3e606211bb1cf8bc57f7d76bab98cc17a150bc\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1079%2Fphillipwood%2Fwip%2Fhistogram-speedup-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1079/phillipwood/wip/histogram-speedup-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1079\n-- \ngitgitgadget\n"},{"id":"441471","messageId":"38c771a74d2a348e6a752555f95b746de029b1d7.1637148025.git.gitgitgadget@gmail.com","threadId":"56926","inReplyTo":"pull.1079.git.1637148025.gitgitgadget@gmail.com","subject":"[PATCH 1/3] diff histogram: intern strings","fromName":"Phillip Wood via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-11-17T11:20:23Z","receivedAt":"2021-11-17T11:20:34Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nHistogram is the only diff algorithm not to call\nxdl_classify_record(). xdl_classify_record() ensures that the hash\nvalues of two strings that are not equal differ which means that it is\nnot necessary to use xdl_recmatch() when comparing lines, all that is\nnecessary is to compare the hash values. This gives a 7% reduction in\nthe runtime of \"git log --patch\" when using the histogram diff\nalgorithm.\n\nTest                                  HEAD^             HEAD\n-----------------------------------------------------------------------------\n4000.1: log -3000 (baseline)          0.18(0.14+0.04)   0.19(0.17+0.02) +5.6%\n4000.2: log --raw -3000 (tree-only)   0.99(0.77+0.21)   0.98(0.78+0.20) -1.0%\n4000.3: log -p -3000 (Myers)          4.84(4.31+0.51)   4.81(4.15+0.64) -0.6%\n4000.4: log -p -3000 --histogram      6.34(5.86+0.46)   5.87(5.19+0.66) -7.4%\n4000.5: log -p -3000 --patience       5.39(4.60+0.76)   5.35(4.60+0.73) -0.7%\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xhistogram.c |  5 ++---\n xdiff/xprepare.c   | 24 ++++++++----------------\n 2 files changed, 10 insertions(+), 19 deletions(-)\n\ndiff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\nindex e694bfd9e31..6c1c88a69a1 100644\n--- a/xdiff/xhistogram.c\n+++ b/xdiff/xhistogram.c\n@@ -91,9 +91,8 @@ struct region {\n static int cmp_recs(xpparam_t const *xpp,\n \txrecord_t *r1, xrecord_t *r2)\n {\n-\treturn r1->ha == r2->ha &&\n-\t\txdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,\n-\t\t\t    xpp->flags);\n+\treturn r1->ha == r2->ha;\n+\n }\n \n #define CMP_ENV(xpp, env, s1, l1, s2, l2) \\\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex abeb8fb84e6..7fae0727a02 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -181,15 +181,11 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_\n \tif (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *))))\n \t\tgoto abort;\n \n-\tif (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF)\n-\t\thbits = hsize = 0;\n-\telse {\n-\t\thbits = xdl_hashbits((unsigned int) narec);\n-\t\thsize = 1 << hbits;\n-\t\tif (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))\n-\t\t\tgoto abort;\n-\t\tmemset(rhash, 0, hsize * sizeof(xrecord_t *));\n-\t}\n+\thbits = xdl_hashbits((unsigned int) narec);\n+\thsize = 1 << hbits;\n+\tif (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))\n+\t\tgoto abort;\n+\tmemset(rhash, 0, hsize * sizeof(xrecord_t *));\n \n \tnrec = 0;\n \tif ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) {\n@@ -208,9 +204,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_\n \t\t\tcrec->size = (long) (cur - prev);\n \t\t\tcrec->ha = hav;\n \t\t\trecs[nrec++] = crec;\n-\n-\t\t\tif ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&\n-\t\t\t    xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)\n+\t\t\tif (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)\n \t\t\t\tgoto abort;\n \t\t}\n \t}\n@@ -279,8 +273,7 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \tenl1 = xdl_guess_lines(mf1, sample) + 1;\n \tenl2 = xdl_guess_lines(mf2, sample) + 1;\n \n-\tif (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF &&\n-\t    xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)\n+\tif (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)\n \t\treturn -1;\n \n \tif (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {\n@@ -305,8 +298,7 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t\treturn -1;\n \t}\n \n-\tif (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)\n-\t\txdl_free_classifier(&cf);\n+\txdl_free_classifier(&cf);\n \n \treturn 0;\n }\n-- \ngitgitgadget\n\n"},{"id":"441472","messageId":"eef46c71840d7f36b503a92b899c95632c023351.1637148025.git.gitgitgadget@gmail.com","threadId":"56926","inReplyTo":"pull.1079.git.1637148025.gitgitgadget@gmail.com","subject":"[PATCH 2/3] xdiff: avoid unnecessary memory allocations","fromName":"Phillip Wood via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-11-17T11:20:24Z","receivedAt":"2021-11-17T11:20:34Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nrindex and ha are only used by xdl_cleanup_records() which is not\ncalled by the histogram or patience algorithms. The perf test results\nshow a small reduction in run time but that is probably within the\nnoise.\n\nTest                                  HEAD^             HEAD\n-----------------------------------------------------------------------------\n4000.1: log -3000 (baseline)          0.19(0.17+0.02)   0.19(0.12+0.07) +0.0%\n4000.2: log --raw -3000 (tree-only)   0.98(0.78+0.20)   0.98(0.81+0.16) +0.0%\n4000.3: log -p -3000 (Myers)          4.81(4.15+0.64)   4.81(4.23+0.56) +0.0%\n4000.4: log -p -3000 --histogram      5.87(5.19+0.66)   5.83(5.11+0.70) -0.7%\n4000.5: log -p -3000 --patience       5.35(4.60+0.73)   5.31(4.61+0.69) -0.7%\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xprepare.c | 11 +++++++----\n 1 file changed, 7 insertions(+), 4 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 7fae0727a02..4527a4a07c4 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -213,10 +213,13 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_\n \t\tgoto abort;\n \tmemset(rchg, 0, (nrec + 2) * sizeof(char));\n \n-\tif (!(rindex = (long *) xdl_malloc((nrec + 1) * sizeof(long))))\n-\t\tgoto abort;\n-\tif (!(ha = (unsigned long *) xdl_malloc((nrec + 1) * sizeof(unsigned long))))\n-\t\tgoto abort;\n+\tif ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&\n+\t    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) {\n+\t\tif (!(rindex = xdl_malloc((nrec + 1) * sizeof(*rindex))))\n+\t\t\tgoto abort;\n+\t\tif (!(ha = xdl_malloc((nrec + 1) * sizeof(*ha))))\n+\t\t\tgoto abort;\n+\t}\n \n \txdf->nrec = nrec;\n \txdf->recs = recs;\n-- \ngitgitgadget\n\n"},{"id":"441473","messageId":"b0bc773f51e114d96ad6efd1ebd03fb6e7646288.1637148025.git.gitgitgadget@gmail.com","threadId":"56926","inReplyTo":"pull.1079.git.1637148025.gitgitgadget@gmail.com","subject":"[PATCH 3/3] xdiff: simplify comparison","fromName":"Phillip Wood via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-11-17T11:20:25Z","receivedAt":"2021-11-17T11:20:35Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nNow that the histogram algorithm calls xdl_classify_record() it is no\nlonger necessary to use xdl_recmatch() to compare lines, it is\nsufficient just to compare the hash values. This has a negligible\neffect on performance.\n\nTest                                  HEAD~1            HEAD\n-----------------------------------------------------------------------------\n4000.1: log -3000 (baseline)          0.19(0.12+0.07)   0.18(0.14+0.04) -5.3%\n4000.2: log --raw -3000 (tree-only)   0.98(0.81+0.16)   0.98(0.79+0.18) +0.0%\n4000.3: log -p -3000 (Myers)          4.81(4.23+0.56)   4.80(4.26+0.53) -0.2%\n4000.4: log -p -3000 --histogram      5.83(5.11+0.70)   5.82(5.15+0.65) -0.2%\n4000.5: log -p -3000 --patience       5.31(4.61+0.69)   5.30(4.54+0.75) -0.2%\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xdiffi.c | 5 +----\n 1 file changed, 1 insertion(+), 4 deletions(-)\n\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex a4542c05b61..6a3b9280beb 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -392,10 +392,7 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,\n \n static int recs_match(xrecord_t *rec1, xrecord_t *rec2, long flags)\n {\n-\treturn (rec1->ha == rec2->ha &&\n-\t\txdl_recmatch(rec1->ptr, rec1->size,\n-\t\t\t     rec2->ptr, rec2->size,\n-\t\t\t     flags));\n+\treturn (rec1->ha == rec2->ha);\n }\n \n /*\n-- \ngitgitgadget\n"},{"id":"441505","messageId":"2b2bd380-540f-959b-b950-cfdc95cbff29@gmail.com","threadId":"56926","inReplyTo":"38c771a74d2a348e6a752555f95b746de029b1d7.1637148025.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] diff histogram: intern strings","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-11-17T15:55:02Z","receivedAt":"2021-11-17T15:55:06Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"\n\nOn 11/17/2021 6:20 AM, Phillip Wood via GitGitGadget wrote:\n> From: Phillip Wood <phillip.wood@dunelm.org.uk>\n> \n> Histogram is the only diff algorithm not to call\n> xdl_classify_record(). xdl_classify_record() ensures that the hash\n> values of two strings that are not equal differ which means that it is\n> not necessary to use xdl_recmatch() when comparing lines, all that is\n> necessary is to compare the hash values. This gives a 7% reduction in\n> the runtime of \"git log --patch\" when using the histogram diff\n> algorithm.\n> \n> Test                                  HEAD^             HEAD\n> -----------------------------------------------------------------------------\n> 4000.1: log -3000 (baseline)          0.18(0.14+0.04)   0.19(0.17+0.02) +5.6%\n> 4000.2: log --raw -3000 (tree-only)   0.99(0.77+0.21)   0.98(0.78+0.20) -1.0%\n> 4000.3: log -p -3000 (Myers)          4.84(4.31+0.51)   4.81(4.15+0.64) -0.6%\n> 4000.4: log -p -3000 --histogram      6.34(5.86+0.46)   5.87(5.19+0.66) -7.4%\n> 4000.5: log -p -3000 --patience       5.39(4.60+0.76)   5.35(4.60+0.73) -0.7%\n> \n> Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n> ---\n>  xdiff/xhistogram.c |  5 ++---\n>  xdiff/xprepare.c   | 24 ++++++++----------------\n>  2 files changed, 10 insertions(+), 19 deletions(-)\n> \n> diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\n> index e694bfd9e31..6c1c88a69a1 100644\n> --- a/xdiff/xhistogram.c\n> +++ b/xdiff/xhistogram.c\n> @@ -91,9 +91,8 @@ struct region {\n>  static int cmp_recs(xpparam_t const *xpp,\n>  \txrecord_t *r1, xrecord_t *r2)\n>  {\n> -\treturn r1->ha == r2->ha &&\n> -\t\txdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,\n> -\t\t\t    xpp->flags);\n> +\treturn r1->ha == r2->ha;\n> +\n\nnit: stray newline.\n\nThe only meaningful change here is that you are relying entirely on\nthe hash and not checking the content again. This means that hash\ncollisions on this 32-bit hash could start introducing different\nresults. Are we worried about that?\n\nI see that a similar hash-comparison is done in xpatience.c without\nfurther checking the contents, but xdiffi.c compares the hashes and\nthen checks with xdl_recmatch(). So, we are still not reaching full\nconsistency across all diff algorithms with how we handle these\ncomparisons. I think it is good to have at least one that can be used\nif/when we hit these hash collisions within a diff, but it can be hard\nto communicate to a user why they need to change a diff algorithm for\nsuch an internal reason.\n\n\nThe following bits looked scary at first, but you are just removing the\nspecial-casing of XDF_HISTOGRAM_DIFF from the preparation stage.\n\n> -\tif (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF)\n> -\t\thbits = hsize = 0;\n> -\telse {\n> -\t\thbits = xdl_hashbits((unsigned int) narec);\n> -\t\thsize = 1 << hbits;\n> -\t\tif (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))\n> -\t\t\tgoto abort;\n> -\t\tmemset(rhash, 0, hsize * sizeof(xrecord_t *));\n> -\t}\n> +\thbits = xdl_hashbits((unsigned int) narec);\n> +\thsize = 1 << hbits;\n> +\tif (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))\n> +\t\tgoto abort;\n> +\tmemset(rhash, 0, hsize * sizeof(xrecord_t *));\n\n> -\t\t\tif ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&\n> -\t\t\t    xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)\n> +\t\t\tif (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)\n\n> -\tif (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF &&\n> -\t    xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)\n> +\tif (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)\n\n> -\tif (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)\n> -\t\txdl_free_classifier(&cf);\n> +\txdl_free_classifier(&cf);\n\nThe existence of these conditions gave me pause, so I went to look for where they\nwere inserted. They were made in 9f37c27 (xdiff/xprepare: skip classification,\n2011-07-12) with the justification that \n\n    We don't need any of that in histogram diff, so we omit calls to these\n    functions. We also skip allocating memory to the hash table, rhash, as\n    it is no longer used.\n\n    This gives us a small boost in performance.\n\nBut you are actually _using_ these preparation steps, which means you are\nre-adding the cost of hashing but overall improving because you use the\ndata correctly. Excellent.\n\nThanks,\n-Stolee\n"},{"id":"441508","messageId":"YZUx+mzaUf/TgXrx@coredump.intra.peff.net","threadId":"56926","inReplyTo":"2b2bd380-540f-959b-b950-cfdc95cbff29@gmail.com","subject":"Re: [PATCH 1/3] diff histogram: intern strings","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-11-17T16:46:50Z","receivedAt":"2021-11-17T16:47:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Nov 17, 2021 at 10:55:02AM -0500, Derrick Stolee wrote:\n\n> > diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\n> > index e694bfd9e31..6c1c88a69a1 100644\n> > --- a/xdiff/xhistogram.c\n> > +++ b/xdiff/xhistogram.c\n> > @@ -91,9 +91,8 @@ struct region {\n> >  static int cmp_recs(xpparam_t const *xpp,\n> >  \txrecord_t *r1, xrecord_t *r2)\n> >  {\n> > -\treturn r1->ha == r2->ha &&\n> > -\t\txdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,\n> > -\t\t\t    xpp->flags);\n> > +\treturn r1->ha == r2->ha;\n> > +\n> \n> nit: stray newline.\n> \n> The only meaningful change here is that you are relying entirely on\n> the hash and not checking the content again. This means that hash\n> collisions on this 32-bit hash could start introducing different\n> results. Are we worried about that?\n\nI had the same thought. But running \"git log --histogram -p\" on git.git\ndoes not seem to produce any differences between the two. So perhaps\ncollisions are removed elsewhere. It would be nice to have a better\nunderstanding of this before proceeding with this change.\n\nCuriously, I got a much smaller improvement in my test, which did:\n\n  git log --no-merges -p --histogram :^po\n\nMy assumption being that \"po/\" diffs are big and uninteresting and so\nbloat the output. But that turned out to be interesting timing-wise.\nExcluding \"po/\" means that patch produces only a 0.6% improvement in\nspeed. But _just_ running the diffs for po shows a 24% speedup!\n\nI guess this is just because those files are much larger than average\n(and changed in fewer commits), meaning that the time spent hashing and\ncomparing lines will show up as a larger percentage of the total work.\n\nBut I wondered...\n\n> The existence of these conditions gave me pause, so I went to look for where they\n> were inserted. They were made in 9f37c27 (xdiff/xprepare: skip classification,\n> 2011-07-12) with the justification that \n> \n>     We don't need any of that in histogram diff, so we omit calls to these\n>     functions. We also skip allocating memory to the hash table, rhash, as\n>     it is no longer used.\n> \n>     This gives us a small boost in performance.\n> \n> But you are actually _using_ these preparation steps, which means you are\n> re-adding the cost of hashing but overall improving because you use the\n> data correctly. Excellent.\n\nAre we making a tradeoff here based on the data patterns? That is, it\nseems like we are spending extra time upfront to do classification in\norder to get quicker comparisons later. Presumably the upfront work is\nO(n) in the length of the file. How many comparisons do we expect to\nsave?  Is it also linear in the number of lines, or could it be\nsuper- or sub-linear depending on the actual diff?\n\n-Peff\n"},{"id":"441510","messageId":"88eaee89-4536-fba4-3aa0-c3693f58eae0@gmail.com","threadId":"56926","inReplyTo":"2b2bd380-540f-959b-b950-cfdc95cbff29@gmail.com","subject":"Re: [PATCH 1/3] diff histogram: intern strings","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2021-11-17T16:52:03Z","receivedAt":"2021-11-17T16:52:10Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Stolee\n\nOn 17/11/2021 15:55, Derrick Stolee wrote:\n> \n> \n> On 11/17/2021 6:20 AM, Phillip Wood via GitGitGadget wrote:\n>> From: Phillip Wood <phillip.wood@dunelm.org.uk>\n>>\n>> Histogram is the only diff algorithm not to call\n>> xdl_classify_record(). xdl_classify_record() ensures that the hash\n>> values of two strings that are not equal differ which means that it is\n>> not necessary to use xdl_recmatch() when comparing lines, all that is\n>> necessary is to compare the hash values. This gives a 7% reduction in\n>> the runtime of \"git log --patch\" when using the histogram diff\n>> algorithm.\n>>\n>> Test                                  HEAD^             HEAD\n>> -----------------------------------------------------------------------------\n>> 4000.1: log -3000 (baseline)          0.18(0.14+0.04)   0.19(0.17+0.02) +5.6%\n>> 4000.2: log --raw -3000 (tree-only)   0.99(0.77+0.21)   0.98(0.78+0.20) -1.0%\n>> 4000.3: log -p -3000 (Myers)          4.84(4.31+0.51)   4.81(4.15+0.64) -0.6%\n>> 4000.4: log -p -3000 --histogram      6.34(5.86+0.46)   5.87(5.19+0.66) -7.4%\n>> 4000.5: log -p -3000 --patience       5.39(4.60+0.76)   5.35(4.60+0.73) -0.7%\n>>\n>> Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n>> ---\n>>   xdiff/xhistogram.c |  5 ++---\n>>   xdiff/xprepare.c   | 24 ++++++++----------------\n>>   2 files changed, 10 insertions(+), 19 deletions(-)\n>>\n>> diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\n>> index e694bfd9e31..6c1c88a69a1 100644\n>> --- a/xdiff/xhistogram.c\n>> +++ b/xdiff/xhistogram.c\n>> @@ -91,9 +91,8 @@ struct region {\n>>   static int cmp_recs(xpparam_t const *xpp,\n>>   \txrecord_t *r1, xrecord_t *r2)\n>>   {\n>> -\treturn r1->ha == r2->ha &&\n>> -\t\txdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,\n>> -\t\t\t    xpp->flags);\n>> +\treturn r1->ha == r2->ha;\n>> +\n> \n> nit: stray newline.\n> \n> The only meaningful change here is that you are relying entirely on\n> the hash and not checking the content again. This means that hash\n> collisions on this 32-bit hash could start introducing different\n> results. Are we worried about that?\n\nxdiff-interface.c limits the size of the file that can be passed to just \nbelow 1GB so we are safe. The other diff algorithms are already using \nthis optimization. (the hash is 64 bits on most platforms, the xdiff \ncode could really benefit from a unsigned long -> size_t cleanup)\n\n> I see that a similar hash-comparison is done in xpatience.c without\n> further checking the contents, but xdiffi.c compares the hashes and\n> then checks with xdl_recmatch(). So, we are still not reaching full\n> consistency across all diff algorithms with how we handle these\n> comparisons. I think it is good to have at least one that can be used\n> if/when we hit these hash collisions within a diff, but it can be hard\n> to communicate to a user why they need to change a diff algorithm for\n> such an internal reason.\n\nI think that code in xdiffi.c is only used by the diff slider code that \nimplements diff.indentHeuristic, the Myers diff implementation just \ncompares the hash values. Before this change the diff slider code needed \nto do the full check to be correct when processing the output of the \nhistogram algorithm.\n\n> The following bits looked scary at first, but you are just removing the\n> special-casing of XDF_HISTOGRAM_DIFF from the preparation stage.\n> \n>> -\tif (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF)\n>> -\t\thbits = hsize = 0;\n>> -\telse {\n>> -\t\thbits = xdl_hashbits((unsigned int) narec);\n>> -\t\thsize = 1 << hbits;\n>> -\t\tif (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))\n>> -\t\t\tgoto abort;\n>> -\t\tmemset(rhash, 0, hsize * sizeof(xrecord_t *));\n>> -\t}\n>> +\thbits = xdl_hashbits((unsigned int) narec);\n>> +\thsize = 1 << hbits;\n>> +\tif (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))\n>> +\t\tgoto abort;\n>> +\tmemset(rhash, 0, hsize * sizeof(xrecord_t *));\n> \n>> -\t\t\tif ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&\n>> -\t\t\t    xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)\n>> +\t\t\tif (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)\n> \n>> -\tif (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF &&\n>> -\t    xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)\n>> +\tif (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)\n> \n>> -\tif (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)\n>> -\t\txdl_free_classifier(&cf);\n>> +\txdl_free_classifier(&cf);\n> \n> The existence of these conditions gave me pause, so I went to look for where they\n> were inserted. They were made in 9f37c27 (xdiff/xprepare: skip classification,\n> 2011-07-12) with the justification that\n> \n>      We don't need any of that in histogram diff, so we omit calls to these\n>      functions. We also skip allocating memory to the hash table, rhash, as\n>      it is no longer used.\n> \n>      This gives us a small boost in performance.\n> \n> But you are actually _using_ these preparation steps, which means you are\n> re-adding the cost of hashing but overall improving because you use the\n> data correctly. Excellent.\n\nThanks for looking at this\n\nBest Wishes\n\nPhillip\n\n> Thanks,\n> -Stolee\n> \n"},{"id":"441610","messageId":"nycvar.QRO.7.76.6.2111181631260.11028@tvgsbejvaqbjf.bet","threadId":"56926","inReplyTo":"88eaee89-4536-fba4-3aa0-c3693f58eae0@gmail.com","subject":"Re: [PATCH 1/3] diff histogram: intern strings","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-11-18T15:35:48Z","receivedAt":"2021-11-18T15:36:28Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 17 Nov 2021, Phillip Wood wrote:\n\n> On 17/11/2021 15:55, Derrick Stolee wrote:\n> >\n> > On 11/17/2021 6:20 AM, Phillip Wood via GitGitGadget wrote:\n> > > From: Phillip Wood <phillip.wood@dunelm.org.uk>\n> > >\n> > > Histogram is the only diff algorithm not to call\n> > > xdl_classify_record(). xdl_classify_record() ensures that the hash\n> > > values of two strings that are not equal differ which means that it is\n> > > not necessary to use xdl_recmatch() when comparing lines, all that is\n> > > necessary is to compare the hash values. This gives a 7% reduction in\n> > > the runtime of \"git log --patch\" when using the histogram diff\n> > > algorithm.\n> > >\n> > > Test                                  HEAD^             HEAD\n> > > -----------------------------------------------------------------------------\n> > > 4000.1: log -3000 (baseline)          0.18(0.14+0.04)   0.19(0.17+0.02)\n> > > +5.6%\n> > > 4000.2: log --raw -3000 (tree-only)   0.99(0.77+0.21)   0.98(0.78+0.20)\n> > > -1.0%\n> > > 4000.3: log -p -3000 (Myers)          4.84(4.31+0.51)   4.81(4.15+0.64)\n> > > -0.6%\n> > > 4000.4: log -p -3000 --histogram      6.34(5.86+0.46)   5.87(5.19+0.66)\n> > > -7.4%\n> > > 4000.5: log -p -3000 --patience       5.39(4.60+0.76)   5.35(4.60+0.73)\n> > > -0.7%\n> > >\n> > > Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n> > > ---\n> > >   xdiff/xhistogram.c |  5 ++---\n> > >   xdiff/xprepare.c   | 24 ++++++++----------------\n> > >   2 files changed, 10 insertions(+), 19 deletions(-)\n> > >\n> > > diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\n> > > index e694bfd9e31..6c1c88a69a1 100644\n> > > --- a/xdiff/xhistogram.c\n> > > +++ b/xdiff/xhistogram.c\n> > > @@ -91,9 +91,8 @@ struct region {\n> > >   static int cmp_recs(xpparam_t const *xpp,\n> > >   \txrecord_t *r1, xrecord_t *r2)\n> > >   {\n> > > -\treturn r1->ha == r2->ha &&\n> > > -\t\txdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,\n> > > -\t\t\t    xpp->flags);\n> > > +\treturn r1->ha == r2->ha;\n> > > +\n> >\n> > nit: stray newline.\n> >\n> > The only meaningful change here is that you are relying entirely on\n> > the hash and not checking the content again. This means that hash\n> > collisions on this 32-bit hash could start introducing different\n> > results. Are we worried about that?\n>\n> xdiff-interface.c limits the size of the file that can be passed to just below\n> 1GB so we are safe. The other diff algorithms are already using this\n> optimization. (the hash is 64 bits on most platforms, the xdiff code could\n> really benefit from a unsigned long -> size_t cleanup)\n\nI think the really important thing to point out is that\n`xdl_classify_record()` ensures that the `ha` attribute is different for\ndifferent text. AFAIR it even \"linearizes\" the `ha` values, i.e. they\nwon't be all over the place but start at 0 (or 1).\n\nSo no, I'm not worried about collisions. That would be a bug in\n`xdl_classify_record()` and I think we would have caught this bug by now.\n\nCiao,\nDscho\n"},{"id":"441611","messageId":"nycvar.QRO.7.76.6.2111181636580.11028@tvgsbejvaqbjf.bet","threadId":"56926","inReplyTo":"pull.1079.git.1637148025.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/3] xdiff: speedup histogram diff","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-11-18T15:40:17Z","receivedAt":"2021-11-18T15:40:24Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Phillip,\n\nOn Wed, 17 Nov 2021, Phillip Wood via GitGitGadget wrote:\n\n> Histogram is the only diff algorithm not to call xdl_classify_record().\n> Calling xdl_classify_record() means that it is not necessary to use\n> xdl_recmatch() when comparing lines, all that is necessary is to compare the\n> hash values. This gives a 7% reduction in the runtime of \"git log --patch\"\n> when using the histogram diff algorithm.\n\nThanks for this! I had a look over the patches (and refreshed my memory of\nwhat `xdl_classify_record()` does), and they look good.\n\nHaving said that, I would love to increase my confidence by backing up the\npatches with a sort of stress test. Do we have anything like that? I guess\nnot, a `git grep histogram t/` did not really turn up anything promising,\np4000 does not even validate the output...\n\nThanks,\nDscho\n"},{"id":"441612","messageId":"YZZ0e7CCGW5QbQlW@coredump.intra.peff.net","threadId":"56926","inReplyTo":"nycvar.QRO.7.76.6.2111181631260.11028@tvgsbejvaqbjf.bet","subject":"Re: [PATCH 1/3] diff histogram: intern strings","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-11-18T15:42:51Z","receivedAt":"2021-11-18T15:42:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Nov 18, 2021 at 04:35:48PM +0100, Johannes Schindelin wrote:\n\n> I think the really important thing to point out is that\n> `xdl_classify_record()` ensures that the `ha` attribute is different for\n> different text. AFAIR it even \"linearizes\" the `ha` values, i.e. they\n> won't be all over the place but start at 0 (or 1).\n> \n> So no, I'm not worried about collisions. That would be a bug in\n> `xdl_classify_record()` and I think we would have caught this bug by now.\n\nAh, thanks for that explanation. That addresses my collision concern from\nearlier in the thread completely.\n\n-Peff\n"},{"id":"441710","messageId":"86d38148-7b97-76aa-148b-346cc179615a@gmail.com","threadId":"56926","inReplyTo":"YZZ0e7CCGW5QbQlW@coredump.intra.peff.net","subject":"Re: [PATCH 1/3] diff histogram: intern strings","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2021-11-19T10:05:32Z","receivedAt":"2021-11-19T10:05:38Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"On 18/11/2021 15:42, Jeff King wrote:\n> On Thu, Nov 18, 2021 at 04:35:48PM +0100, Johannes Schindelin wrote:\n> \n>> I think the really important thing to point out is that\n>> `xdl_classify_record()` ensures that the `ha` attribute is different for\n>> different text. AFAIR it even \"linearizes\" the `ha` values, i.e. they\n>> won't be all over the place but start at 0 (or 1).\n>>\n>> So no, I'm not worried about collisions. That would be a bug in\n>> `xdl_classify_record()` and I think we would have caught this bug by now.\n> \n> Ah, thanks for that explanation. That addresses my collision concern from\n> earlier in the thread completely.\n\nYes, thanks for clarifying I should have been clearer in my reply to \nStolee. The reason I was waffling on about file sizes is that there can \nonly be a collision if there are more than 2^32 unique lines. I think \nthe minimum file size where that happens is just below 10GB when one \nside of the diff has 2^31 lines and the other has 2^31 + 1 lines and all \nthe lines are unique.\n\nBest Wishes\n\nPhillip\n"},{"id":"441740","messageId":"YZe4hqF6Jf14L5tb@coredump.intra.peff.net","threadId":"56926","inReplyTo":"86d38148-7b97-76aa-148b-346cc179615a@gmail.com","subject":"Re: [PATCH 1/3] diff histogram: intern strings","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-11-19T14:45:26Z","receivedAt":"2021-11-19T14:45:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 19, 2021 at 10:05:32AM +0000, Phillip Wood wrote:\n\n> On 18/11/2021 15:42, Jeff King wrote:\n> > On Thu, Nov 18, 2021 at 04:35:48PM +0100, Johannes Schindelin wrote:\n> > \n> > > I think the really important thing to point out is that\n> > > `xdl_classify_record()` ensures that the `ha` attribute is different for\n> > > different text. AFAIR it even \"linearizes\" the `ha` values, i.e. they\n> > > won't be all over the place but start at 0 (or 1).\n> > > \n> > > So no, I'm not worried about collisions. That would be a bug in\n> > > `xdl_classify_record()` and I think we would have caught this bug by now.\n> > \n> > Ah, thanks for that explanation. That addresses my collision concern from\n> > earlier in the thread completely.\n> \n> Yes, thanks for clarifying I should have been clearer in my reply to Stolee.\n> The reason I was waffling on about file sizes is that there can only be a\n> collision if there are more than 2^32 unique lines. I think the minimum file\n> size where that happens is just below 10GB when one side of the diff has\n> 2^31 lines and the other has 2^31 + 1 lines and all the lines are unique.\n\nRight, that makes more sense (and we are not likely to lift the 1GB\nlimit anytime soon; there are tons of 32-bit variables and potential\ninteger overflows all through the xdiff code).\n\nIt's probably worth explaining this a bit in the commit message.\n\nI also, FWIW, found the subject confusing. I expected \"intern\" to refer\nto keeping a single copy of some strings. Maybe:\n\n  Subject: diff histogram: skip xdl_recmatch for comparing records\n\nor something?\n\n-Peff\n"},{"id":"441751","messageId":"nycvar.QRO.7.76.6.2111191647100.63@tvgsbejvaqbjf.bet","threadId":"56926","inReplyTo":"86d38148-7b97-76aa-148b-346cc179615a@gmail.com","subject":"Re: [PATCH 1/3] diff histogram: intern strings","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-11-19T15:49:09Z","receivedAt":"2021-11-19T15:49:22Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Phillip,\n\nOn Fri, 19 Nov 2021, Phillip Wood wrote:\n\n> On 18/11/2021 15:42, Jeff King wrote:\n> > On Thu, Nov 18, 2021 at 04:35:48PM +0100, Johannes Schindelin wrote:\n> >\n> > > I think the really important thing to point out is that\n> > > `xdl_classify_record()` ensures that the `ha` attribute is different\n> > > for different text. AFAIR it even \"linearizes\" the `ha` values, i.e.\n> > > they won't be all over the place but start at 0 (or 1).\n> > >\n> > > So no, I'm not worried about collisions. That would be a bug in\n> > > `xdl_classify_record()` and I think we would have caught this bug by\n> > > now.\n> >\n> > Ah, thanks for that explanation. That addresses my collision concern\n> > from earlier in the thread completely.\n>\n> Yes, thanks for clarifying I should have been clearer in my reply to\n> Stolee. The reason I was waffling on about file sizes is that there can\n> only be a collision if there are more than 2^32 unique lines. I think\n> the minimum file size where that happens is just below 10GB when one\n> side of the diff has 2^31 lines and the other has 2^31 + 1 lines and all\n> the lines are unique.\n\nIndeed, and as you pointed out, we already refuse to generate diffs for\nsuch large amounts of data.\n\n(For what it's worth, I totally agree with punting on such large data, it\nwould also take too long a time to generate diffs on such large data to be\nreasonable.)\n\nCiao,\nDscho\n"},{"id":"441794","messageId":"211119.86v90n25cv.gmgdl@evledraar.gmail.com","threadId":"56926","inReplyTo":"YZe4hqF6Jf14L5tb@coredump.intra.peff.net","subject":"Re: [PATCH 1/3] diff histogram: intern strings","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-11-19T21:22:04Z","receivedAt":"2021-11-19T21:38:45Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Nov 19 2021, Jeff King wrote:\n\n> On Fri, Nov 19, 2021 at 10:05:32AM +0000, Phillip Wood wrote:\n>\n>> On 18/11/2021 15:42, Jeff King wrote:\n>> > On Thu, Nov 18, 2021 at 04:35:48PM +0100, Johannes Schindelin wrote:\n>> > \n>> > > I think the really important thing to point out is that\n>> > > `xdl_classify_record()` ensures that the `ha` attribute is different for\n>> > > different text. AFAIR it even \"linearizes\" the `ha` values, i.e. they\n>> > > won't be all over the place but start at 0 (or 1).\n>> > > \n>> > > So no, I'm not worried about collisions. That would be a bug in\n>> > > `xdl_classify_record()` and I think we would have caught this bug by now.\n>> > \n>> > Ah, thanks for that explanation. That addresses my collision concern from\n>> > earlier in the thread completely.\n>> \n>> Yes, thanks for clarifying I should have been clearer in my reply to Stolee.\n>> The reason I was waffling on about file sizes is that there can only be a\n>> collision if there are more than 2^32 unique lines. I think the minimum file\n>> size where that happens is just below 10GB when one side of the diff has\n>> 2^31 lines and the other has 2^31 + 1 lines and all the lines are unique.\n>\n> Right, that makes more sense (and we are not likely to lift the 1GB\n> limit anytime soon; there are tons of 32-bit variables and potential\n> integer overflows all through the xdiff code).\n\nInterestingly:\n    \n    $ du -sh 8gb*\n    8.1G    8gb\n    8.1G    8gb.cp\n    $ ~/g/git/git -P -c core.bigFileThreshold=10g diff -U0 --no-index --no-color-moved 2gb 2gb.cp\n    diff --git a/8gb b/8gb.cp\n    index a886cdfe5ce..4965a132d44 100644\n    --- a/8gb\n    +++ b/8gb.cp\n    @@ -17,0 +18 @@ more\n    +blah\n\nAnd the only change I made was:\n    \n    diff --git a/xdiff-interface.c b/xdiff-interface.c\n    index 75b32aef51d..cb8ca5f5d0a 100644\n    --- a/xdiff-interface.c\n    +++ b/xdiff-interface.c\n    @@ -117,9 +117,6 @@ int xdi_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdemitconf_t co\n            mmfile_t a = *mf1;\n            mmfile_t b = *mf2;\n     \n    -       if (mf1->size > MAX_XDIFF_SIZE || mf2->size > MAX_XDIFF_SIZE)\n    -               return -1;\n    -\n            if (!xecfg->ctxlen && !(xecfg->flags & XDL_EMIT_FUNCCONTEXT))\n                    trim_common_tail(&a, &b);\n\nPerhaps we're being overly concervative with these hardcoded limits, at\nleast on some platforms? This is Linux x86_64.\n\nI understand from skimming the above that it's about the pathological\ncase, these two files are the same except for a trailer at the end.\n\nI wonder how far you could get with #define int size_t & the like ... :)\n"},{"id":"441799","messageId":"YZgi6ikhX4tqLtj0@coredump.intra.peff.net","threadId":"56926","inReplyTo":"211119.86v90n25cv.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH 1/3] diff histogram: intern strings","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-11-19T22:19:22Z","receivedAt":"2021-11-19T22:19:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 19, 2021 at 10:22:04PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> > Right, that makes more sense (and we are not likely to lift the 1GB\n> > limit anytime soon; there are tons of 32-bit variables and potential\n> > integer overflows all through the xdiff code).\n> \n> Interestingly:\n>     \n>     $ du -sh 8gb*\n>     8.1G    8gb\n>     8.1G    8gb.cp\n>     $ ~/g/git/git -P -c core.bigFileThreshold=10g diff -U0 --no-index --no-color-moved 2gb 2gb.cp\n>     diff --git a/8gb b/8gb.cp\n>     index a886cdfe5ce..4965a132d44 100644\n>     --- a/8gb\n>     +++ b/8gb.cp\n>     @@ -17,0 +18 @@ more\n>     +blah\n> \n> And the only change I made was:\n>     \n>     diff --git a/xdiff-interface.c b/xdiff-interface.c\n>     index 75b32aef51d..cb8ca5f5d0a 100644\n>     --- a/xdiff-interface.c\n>     +++ b/xdiff-interface.c\n>     @@ -117,9 +117,6 @@ int xdi_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdemitconf_t co\n>             mmfile_t a = *mf1;\n>             mmfile_t b = *mf2;\n>      \n>     -       if (mf1->size > MAX_XDIFF_SIZE || mf2->size > MAX_XDIFF_SIZE)\n>     -               return -1;\n>     -\n>             if (!xecfg->ctxlen && !(xecfg->flags & XDL_EMIT_FUNCCONTEXT))\n>                     trim_common_tail(&a, &b);\n> \n> Perhaps we're being overly concervative with these hardcoded limits, at\n> least on some platforms? This is Linux x86_64.\n\nIt's been a couple of years since I looked, but I'm fairly certain there\nare triggerable heap overflows. You probably need fewer than 2^31 lines,\nbut more than 2^30, as that will overflow the size computation of an\narray whose elements are themselves 32-bit integers.\n\nFor instance, this:\n\n  perl -e 'print \"x\\n\" x (2**30 + 10)'  >gigaline\n  cp gigaline gigaline.cp\n  echo foo >>gigaline\n\nresults in:\n\n  $ git.compile -c core.bigfilethreshold=10g --no-pager diff --no-index gigaline gigaline.cp\n  fatal: Out of memory, malloc failed (tried to allocate 18446744056529682432 bytes)\n\nso at some point we went negative with our allocation (and then it was\ncast to size_t when we passed it xmalloc). There's probably a value\nsomewhere in the middle where it wraps but stays positive, and you'd get\na heap overflow.\n\n> I understand from skimming the above that it's about the pathological\n> case, these two files are the same except for a trailer at the end.\n\nThe real danger here is not producing a wrong answer for some dumb\ncases, but introducing an exploitable heap overflow. Switching to\nsize_t, or at the very least using st_mult(), etc, everywhere in xdiff\nwould help. I looked at that long ago, but eventually decided it was\nsafer and less work to just stick the 1GB limit, since it practice\nnobody really cares about diffing beyond that level. (And the limit is\nreally about number of lines, but 1GB of bytes is an easy proxy for\nthat).\n\nIt would be OK for somebody to fix it if they really want bigger diffs,\nbut I think it has to be done carefully.\n\n-Peff\n"}]}