{"thread":{"id":"55615","subject":"[PATCH 1/2] patience diff: remove unnecessary string comparisons","startedAt":"2021-05-04T09:25:51Z","lastAt":"2021-05-06T01:32:21Z","messageCount":8,"participants":["Phillip Wood via GitGitGadget","Junio C Hamano","Phillip Wood","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"423564","messageId":"a339d1cf9b9ffd6365fca3efda8fb7e10346dda4.1620120345.git.gitgitgadget@gmail.com","threadId":"55615","inReplyTo":"pull.948.git.1620120345.gitgitgadget@gmail.com","subject":"[PATCH 1/2] patience diff: remove unnecessary string comparisons","fromName":"Phillip Wood via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-05-04T09:25:44Z","receivedAt":"2021-05-04T09:25:51Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nxdl_prepare_env() calls xdl_classify_record() which arranges for the\nhashes of non-matching lines to be different so lines can be tested\nfor equality by comparing just their hashes.\n\nThis reduces the time taken to calculate the diff of v2.28.0 to\nv2.29.0 by ~3-4%.\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xpatience.c | 11 +++--------\n 1 file changed, 3 insertions(+), 8 deletions(-)\n\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nindex 20699a6f6054..db2d53e89cb0 100644\n--- a/xdiff/xpatience.c\n+++ b/xdiff/xpatience.c\n@@ -90,7 +90,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,\n {\n \txrecord_t **records = pass == 1 ?\n \t\tmap->env->xdf1.recs : map->env->xdf2.recs;\n-\txrecord_t *record = records[line - 1], *other;\n+\txrecord_t *record = records[line - 1];\n \t/*\n \t * After xdl_prepare_env() (or more precisely, due to\n \t * xdl_classify_record()), the \"ha\" member of the records (AKA lines)\n@@ -104,11 +104,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,\n \tint index = (int)((record->ha << 1) % map->alloc);\n \n \twhile (map->entries[index].line1) {\n-\t\tother = map->env->xdf1.recs[map->entries[index].line1 - 1];\n-\t\tif (map->entries[index].hash != record->ha ||\n-\t\t\t\t!xdl_recmatch(record->ptr, record->size,\n-\t\t\t\t\tother->ptr, other->size,\n-\t\t\t\t\tmap->xpp->flags)) {\n+\t\tif (map->entries[index].hash != record->ha) {\n \t\t\tif (++index >= map->alloc)\n \t\t\t\tindex = 0;\n \t\t\tcontinue;\n@@ -253,8 +249,7 @@ static int match(struct hashmap *map, int line1, int line2)\n {\n \txrecord_t *record1 = map->env->xdf1.recs[line1 - 1];\n \txrecord_t *record2 = map->env->xdf2.recs[line2 - 1];\n-\treturn xdl_recmatch(record1->ptr, record1->size,\n-\t\trecord2->ptr, record2->size, map->xpp->flags);\n+\treturn record1->ha == record2->ha;\n }\n \n static int patience_diff(mmfile_t *file1, mmfile_t *file2,\n-- \ngitgitgadget\n\n"},{"id":"423565","messageId":"pull.948.git.1620120345.gitgitgadget@gmail.com","threadId":"55615","inReplyTo":null,"subject":"[PATCH 0/2] A couple of small patience diff cleanups","fromName":"Phillip Wood via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-05-04T09:25:43Z","receivedAt":"2021-05-04T09:25:52Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Remove some unnecessary string comparisons and an unused variable\n\nPhillip Wood (2):\n  patience diff: remove unnecessary string comparisons\n  patience diff: remove unused variable\n\n xdiff/xpatience.c | 14 +++-----------\n 1 file changed, 3 insertions(+), 11 deletions(-)\n\n\nbase-commit: 7e391989789db82983665667013a46eabc6fc570\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-948%2Fphillipwood%2Fwip%2Fpatience-diff-cleanup-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-948/phillipwood/wip/patience-diff-cleanup-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/948\n-- \ngitgitgadget\n"},{"id":"423566","messageId":"b38a4e02d4f1c8e77bbc8ed1e4e8507d41ab9fd8.1620120345.git.gitgitgadget@gmail.com","threadId":"55615","inReplyTo":"pull.948.git.1620120345.gitgitgadget@gmail.com","subject":"[PATCH 2/2] patience diff: remove unused variable","fromName":"Phillip Wood via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-05-04T09:25:45Z","receivedAt":"2021-05-04T09:25:56Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"From: Phillip Wood <phillip.wood@dunelm.org.uk>\n\nSigned-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>\n---\n xdiff/xpatience.c | 3 ---\n 1 file changed, 3 deletions(-)\n\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nindex db2d53e89cb0..c5d48e80aefb 100644\n--- a/xdiff/xpatience.c\n+++ b/xdiff/xpatience.c\n@@ -284,9 +284,6 @@ static int walk_common_sequence(struct hashmap *map, struct entry *first,\n \n \t\t/* Recurse */\n \t\tif (next1 > line1 || next2 > line2) {\n-\t\t\tstruct hashmap submap;\n-\n-\t\t\tmemset(&submap, 0, sizeof(submap));\n \t\t\tif (patience_diff(map->file1, map->file2,\n \t\t\t\t\tmap->xpp, map->env,\n \t\t\t\t\tline1, next1 - line1,\n-- \ngitgitgadget\n"},{"id":"423627","messageId":"xmqqpmy658e1.fsf@gitster.g","threadId":"55615","inReplyTo":"a339d1cf9b9ffd6365fca3efda8fb7e10346dda4.1620120345.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/2] patience diff: remove unnecessary string comparisons","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-05-05T00:31:02Z","receivedAt":"2021-05-05T00:31:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Phillip Wood via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> From: Phillip Wood <phillip.wood@dunelm.org.uk>\n>\n> xdl_prepare_env() calls xdl_classify_record() which arranges for the\n> hashes of non-matching lines to be different so lines can be tested\n> for equality by comparing just their hashes.\n\nHmph, that is a bit different from what I read from the comment in\nthe post context of the first hunk, though.\n\n\t/*\n\t * After xdl_prepare_env() (or more precisely, due to\n\t * xdl_classify_record()), the \"ha\" member of the records (AKA lines)\n\t * is _not_ the hash anymore, but a linearized version of it.  In\n\t * other words, the \"ha\" member is guaranteed to start with 0 and\n\t * the second record's ha can only be 0 or 1, etc.\n\t *\n\t * So we multiply ha by 2 in the hope that the hashing was\n\t * \"unique enough\".\n\t */\n\nThe words \"home\" and \"enough\" hints to me that the \"ha\" member is\nnot hash, but \"lineralized version of it\" (whatever it means) does\nnot guarantee that two records with the same \"ha\" are identical, or\ndoes it?\n\nWell, I should just go read xdl_classify_record() to see what it\nreally does, but if it eliminates collisions, then the patch is a\nclear and obvious improvement.\n\nThanks.\n\n> diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\n> index 20699a6f6054..db2d53e89cb0 100644\n> --- a/xdiff/xpatience.c\n> +++ b/xdiff/xpatience.c\n> @@ -90,7 +90,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,\n>  {\n>  \txrecord_t **records = pass == 1 ?\n>  \t\tmap->env->xdf1.recs : map->env->xdf2.recs;\n> -\txrecord_t *record = records[line - 1], *other;\n> +\txrecord_t *record = records[line - 1];\n>  \t/*\n>  \t * After xdl_prepare_env() (or more precisely, due to\n>  \t * xdl_classify_record()), the \"ha\" member of the records (AKA lines)\n> @@ -104,11 +104,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,\n>  \tint index = (int)((record->ha << 1) % map->alloc);\n>  \n>  \twhile (map->entries[index].line1) {\n> -\t\tother = map->env->xdf1.recs[map->entries[index].line1 - 1];\n> -\t\tif (map->entries[index].hash != record->ha ||\n> -\t\t\t\t!xdl_recmatch(record->ptr, record->size,\n> -\t\t\t\t\tother->ptr, other->size,\n> -\t\t\t\t\tmap->xpp->flags)) {\n> +\t\tif (map->entries[index].hash != record->ha) {\n>  \t\t\tif (++index >= map->alloc)\n>  \t\t\t\tindex = 0;\n>  \t\t\tcontinue;\n> @@ -253,8 +249,7 @@ static int match(struct hashmap *map, int line1, int line2)\n>  {\n>  \txrecord_t *record1 = map->env->xdf1.recs[line1 - 1];\n>  \txrecord_t *record2 = map->env->xdf2.recs[line2 - 1];\n> -\treturn xdl_recmatch(record1->ptr, record1->size,\n> -\t\trecord2->ptr, record2->size, map->xpp->flags);\n> +\treturn record1->ha == record2->ha;\n>  }\n>  \n>  static int patience_diff(mmfile_t *file1, mmfile_t *file2,\n"},{"id":"423649","messageId":"87001425-8043-4c66-dbc2-637f05a7229f@gmail.com","threadId":"55615","inReplyTo":"xmqqpmy658e1.fsf@gitster.g","subject":"Re: [PATCH 1/2] patience diff: remove unnecessary string comparisons","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2021-05-05T09:34:29Z","receivedAt":"2021-05-05T09:34:36Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"On 05/05/2021 01:31, Junio C Hamano wrote:\n> \"Phillip Wood via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n> \n>> From: Phillip Wood <phillip.wood@dunelm.org.uk>\n>>\n>> xdl_prepare_env() calls xdl_classify_record() which arranges for the\n>> hashes of non-matching lines to be different so lines can be tested\n>> for equality by comparing just their hashes.\n> \n> Hmph, that is a bit different from what I read from the comment in\n> the post context of the first hunk, though.\n> \n> \t/*\n> \t * After xdl_prepare_env() (or more precisely, due to\n> \t * xdl_classify_record()), the \"ha\" member of the records (AKA lines)\n> \t * is _not_ the hash anymore, but a linearized version of it.  In\n> \t * other words, the \"ha\" member is guaranteed to start with 0 and\n> \t * the second record's ha can only be 0 or 1, etc.\n> \t *\n> \t * So we multiply ha by 2 in the hope that the hashing was\n> \t * \"unique enough\".\n> \t */\n> \n> The words \"home\" and \"enough\" hints to me that the \"ha\" member is\n> not hash, but \"lineralized version of it\" (whatever it means) does\n> not guarantee that two records with the same \"ha\" are identical, or\n> does it?\n\nBy \"hashes\" I meant \"the value of record->ha\". That comment is a bit \nconfusing. I think \"linearized version of it\" is referring to \nxdl_classify_record() assigning a unique integer to each unique input \nline starting from zero and increasing by one for each unique input line \n(the function is fairly easy to follow). I assume \"unique enough\" is \nreferring to the line below the comment which takes the modulus of \nrecord->ha and record->ha is not evenly distributed over the whole \ninteger range but bunched at the lower end.\n\nThe Myers implementation calls xdl_classify_record() and then only ever \ncompares record->ha, it does not call xdl_recmatch() while computing the \ndiff.\n\n> Well, I should just go read xdl_classify_record() to see what it\n> really does, but if it eliminates collisions, then the patch is a\n> clear and obvious improvement.\n\nThanks\n\nPhillip\n\n\n> Thanks.\n> \n>> diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\n>> index 20699a6f6054..db2d53e89cb0 100644\n>> --- a/xdiff/xpatience.c\n>> +++ b/xdiff/xpatience.c\n>> @@ -90,7 +90,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,\n>>   {\n>>   \txrecord_t **records = pass == 1 ?\n>>   \t\tmap->env->xdf1.recs : map->env->xdf2.recs;\n>> -\txrecord_t *record = records[line - 1], *other;\n>> +\txrecord_t *record = records[line - 1];\n>>   \t/*\n>>   \t * After xdl_prepare_env() (or more precisely, due to\n>>   \t * xdl_classify_record()), the \"ha\" member of the records (AKA lines)\n>> @@ -104,11 +104,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,\n>>   \tint index = (int)((record->ha << 1) % map->alloc);\n>>   \n>>   \twhile (map->entries[index].line1) {\n>> -\t\tother = map->env->xdf1.recs[map->entries[index].line1 - 1];\n>> -\t\tif (map->entries[index].hash != record->ha ||\n>> -\t\t\t\t!xdl_recmatch(record->ptr, record->size,\n>> -\t\t\t\t\tother->ptr, other->size,\n>> -\t\t\t\t\tmap->xpp->flags)) {\n>> +\t\tif (map->entries[index].hash != record->ha) {\n>>   \t\t\tif (++index >= map->alloc)\n>>   \t\t\t\tindex = 0;\n>>   \t\t\tcontinue;\n>> @@ -253,8 +249,7 @@ static int match(struct hashmap *map, int line1, int line2)\n>>   {\n>>   \txrecord_t *record1 = map->env->xdf1.recs[line1 - 1];\n>>   \txrecord_t *record2 = map->env->xdf2.recs[line2 - 1];\n>> -\treturn xdl_recmatch(record1->ptr, record1->size,\n>> -\t\trecord2->ptr, record2->size, map->xpp->flags);\n>> +\treturn record1->ha == record2->ha;\n>>   }\n>>   \n>>   static int patience_diff(mmfile_t *file1, mmfile_t *file2,\n"},{"id":"423692","messageId":"nycvar.QRO.7.76.6.2105051649280.50@tvgsbejvaqbjf.bet","threadId":"55615","inReplyTo":"xmqqpmy658e1.fsf@gitster.g","subject":"Re: [PATCH 1/2] patience diff: remove unnecessary string comparisons","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-05-05T14:58:38Z","receivedAt":"2021-05-05T14:58:49Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nOn Wed, 5 May 2021, Junio C Hamano wrote:\n\n> \"Phillip Wood via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n>\n> > From: Phillip Wood <phillip.wood@dunelm.org.uk>\n> >\n> > xdl_prepare_env() calls xdl_classify_record() which arranges for the\n> > hashes of non-matching lines to be different so lines can be tested\n> > for equality by comparing just their hashes.\n>\n> Hmph, that is a bit different from what I read from the comment in\n> the post context of the first hunk, though.\n>\n> \t/*\n> \t * After xdl_prepare_env() (or more precisely, due to\n> \t * xdl_classify_record()), the \"ha\" member of the records (AKA lines)\n> \t * is _not_ the hash anymore, but a linearized version of it.  In\n> \t * other words, the \"ha\" member is guaranteed to start with 0 and\n> \t * the second record's ha can only be 0 or 1, etc.\n> \t *\n> \t * So we multiply ha by 2 in the hope that the hashing was\n> \t * \"unique enough\".\n> \t */\n>\n> The words \"home\" and \"enough\" hints to me that the \"ha\" member is\n> not hash, but \"lineralized version of it\" (whatever it means) does\n> not guarantee that two records with the same \"ha\" are identical, or\n> does it?\n>\n> Well, I should just go read xdl_classify_record() to see what it\n> really does, but if it eliminates collisions, then the patch is a\n> clear and obvious improvement.\n\nRight. I had the same concern. But it does look as if\n`xdl_classify_record()` replaced the possibly non-unique hash values to\nunique sequential identifiers.\n\nI have to admit that the code is unnecessarily hard to read for me:\nhttps://github.com/git/git/blob/v2.31.1/xdiff/xprepare.c#L110-L157\n\nBut I do gather that the loop at\nhttps://github.com/git/git/blob/v2.31.1/xdiff/xprepare.c#L119-L123\nis called for every line, that it does compare it to every seen line with\nthe same hash, and that it exits the loop early if the contents disagree:\n\n\tfor (rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next)\n\t\tif (rcrec->ha == rec->ha &&\n\t\t\t\txdl_recmatch(rcrec->line, rcrec->size,\n\t\t\t\t\trec->ptr, rec->size, cf->flags))\n\t\t\tbreak;\n\nSince naming is hard (and you can easily err on saving space at the\nexpense of costing readers' time, as libxdiff proves), and since I am\nrunning out of review time, I'll have to assume that\nhttps://github.com/git/git/blob/v2.31.1/xdiff/xprepare.c#L150-L154 means\nthat indeed, the `ha` field is set to a counter that uniquely identifies\nthe line contents:\n\n\trec->ha = (unsigned long) rcrec->idx;\n\n\n\thi = (long) XDL_HASHLONG(rec->ha, hbits);\n\trec->next = rhash[hi];\n\trhash[hi] = rec;\n\nSo I am fairly confident that the patch is good, and the performance win\nis nice.\n\nThanks!\nDscho\n\n>\n> Thanks.\n>\n> > diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\n> > index 20699a6f6054..db2d53e89cb0 100644\n> > --- a/xdiff/xpatience.c\n> > +++ b/xdiff/xpatience.c\n> > @@ -90,7 +90,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,\n> >  {\n> >  \txrecord_t **records = pass == 1 ?\n> >  \t\tmap->env->xdf1.recs : map->env->xdf2.recs;\n> > -\txrecord_t *record = records[line - 1], *other;\n> > +\txrecord_t *record = records[line - 1];\n> >  \t/*\n> >  \t * After xdl_prepare_env() (or more precisely, due to\n> >  \t * xdl_classify_record()), the \"ha\" member of the records (AKA lines)\n> > @@ -104,11 +104,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,\n> >  \tint index = (int)((record->ha << 1) % map->alloc);\n> >\n> >  \twhile (map->entries[index].line1) {\n> > -\t\tother = map->env->xdf1.recs[map->entries[index].line1 - 1];\n> > -\t\tif (map->entries[index].hash != record->ha ||\n> > -\t\t\t\t!xdl_recmatch(record->ptr, record->size,\n> > -\t\t\t\t\tother->ptr, other->size,\n> > -\t\t\t\t\tmap->xpp->flags)) {\n> > +\t\tif (map->entries[index].hash != record->ha) {\n> >  \t\t\tif (++index >= map->alloc)\n> >  \t\t\t\tindex = 0;\n> >  \t\t\tcontinue;\n> > @@ -253,8 +249,7 @@ static int match(struct hashmap *map, int line1, int line2)\n> >  {\n> >  \txrecord_t *record1 = map->env->xdf1.recs[line1 - 1];\n> >  \txrecord_t *record2 = map->env->xdf2.recs[line2 - 1];\n> > -\treturn xdl_recmatch(record1->ptr, record1->size,\n> > -\t\trecord2->ptr, record2->size, map->xpp->flags);\n> > +\treturn record1->ha == record2->ha;\n> >  }\n> >\n> >  static int patience_diff(mmfile_t *file1, mmfile_t *file2,\n>\n"},{"id":"423702","messageId":"67b46d8c-6a84-d2f7-dadf-e63050149e93@gmail.com","threadId":"55615","inReplyTo":"nycvar.QRO.7.76.6.2105051649280.50@tvgsbejvaqbjf.bet","subject":"Re: [PATCH 1/2] patience diff: remove unnecessary string comparisons","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2021-05-05T18:00:57Z","receivedAt":"2021-05-05T18:04:17Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Dscho\n\nOn 05/05/2021 15:58, Johannes Schindelin wrote:\n> Hi Junio,\n> \n> On Wed, 5 May 2021, Junio C Hamano wrote:\n> \n>> \"Phillip Wood via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n>>\n>>> From: Phillip Wood <phillip.wood@dunelm.org.uk>\n>>>\n>>> xdl_prepare_env() calls xdl_classify_record() which arranges for the\n>>> hashes of non-matching lines to be different so lines can be tested\n>>> for equality by comparing just their hashes.\n>>\n>> Hmph, that is a bit different from what I read from the comment in\n>> the post context of the first hunk, though.\n>>\n>> \t/*\n>> \t * After xdl_prepare_env() (or more precisely, due to\n>> \t * xdl_classify_record()), the \"ha\" member of the records (AKA lines)\n>> \t * is _not_ the hash anymore, but a linearized version of it.  In\n>> \t * other words, the \"ha\" member is guaranteed to start with 0 and\n>> \t * the second record's ha can only be 0 or 1, etc.\n>> \t *\n>> \t * So we multiply ha by 2 in the hope that the hashing was\n>> \t * \"unique enough\".\n>> \t */\n>>\n>> The words \"home\" and \"enough\" hints to me that the \"ha\" member is\n>> not hash, but \"lineralized version of it\" (whatever it means) does\n>> not guarantee that two records with the same \"ha\" are identical, or\n>> does it?\n>>\n>> Well, I should just go read xdl_classify_record() to see what it\n>> really does, but if it eliminates collisions, then the patch is a\n>> clear and obvious improvement.\n> \n> Right. I had the same concern. But it does look as if\n> `xdl_classify_record()` replaced the possibly non-unique hash values to\n> unique sequential identifiers.\n> \n> I have to admit that the code is unnecessarily hard to read for me:\n> https://github.com/git/git/blob/v2.31.1/xdiff/xprepare.c#L110-L157\n> \n> But I do gather that the loop at\n> https://github.com/git/git/blob/v2.31.1/xdiff/xprepare.c#L119-L123\n> is called for every line, that it does compare it to every seen line with\n> the same hash, and that it exits the loop early if the contents disagree:\n> \n> \tfor (rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next)\n> \t\tif (rcrec->ha == rec->ha &&\n> \t\t\t\txdl_recmatch(rcrec->line, rcrec->size,\n> \t\t\t\t\trec->ptr, rec->size, cf->flags))\n> \t\t\tbreak;\n> \n> Since naming is hard (and you can easily err on saving space at the\n> expense of costing readers' time, as libxdiff proves), and since I am\n> running out of review time, I'll have to assume that\n> https://github.com/git/git/blob/v2.31.1/xdiff/xprepare.c#L150-L154 means\n> that indeed, the `ha` field is set to a counter that uniquely identifies\n> the line contents:\n> \n> \trec->ha = (unsigned long) rcrec->idx;\n> \n> \n> \thi = (long) XDL_HASHLONG(rec->ha, hbits);\n> \trec->next = rhash[hi];\n> \trhash[hi] = rec;\n> \n> So I am fairly confident that the patch is good, and the performance win\n> is nice.\n\nThanks for taking the time to review this patch, I agree with your \nanalysis. The output of `git log -p --diff-algorithm=patience \norigin/master` for the whole history of git.git is unchanged by this patch.\n\nBest Wishes\n\nPhillip\n\n> \n> Thanks!\n> Dscho\n> \n>>\n>> Thanks.\n>>\n>>> diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\n>>> index 20699a6f6054..db2d53e89cb0 100644\n>>> --- a/xdiff/xpatience.c\n>>> +++ b/xdiff/xpatience.c\n>>> @@ -90,7 +90,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,\n>>>   {\n>>>   \txrecord_t **records = pass == 1 ?\n>>>   \t\tmap->env->xdf1.recs : map->env->xdf2.recs;\n>>> -\txrecord_t *record = records[line - 1], *other;\n>>> +\txrecord_t *record = records[line - 1];\n>>>   \t/*\n>>>   \t * After xdl_prepare_env() (or more precisely, due to\n>>>   \t * xdl_classify_record()), the \"ha\" member of the records (AKA lines)\n>>> @@ -104,11 +104,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,\n>>>   \tint index = (int)((record->ha << 1) % map->alloc);\n>>>\n>>>   \twhile (map->entries[index].line1) {\n>>> -\t\tother = map->env->xdf1.recs[map->entries[index].line1 - 1];\n>>> -\t\tif (map->entries[index].hash != record->ha ||\n>>> -\t\t\t\t!xdl_recmatch(record->ptr, record->size,\n>>> -\t\t\t\t\tother->ptr, other->size,\n>>> -\t\t\t\t\tmap->xpp->flags)) {\n>>> +\t\tif (map->entries[index].hash != record->ha) {\n>>>   \t\t\tif (++index >= map->alloc)\n>>>   \t\t\t\tindex = 0;\n>>>   \t\t\tcontinue;\n>>> @@ -253,8 +249,7 @@ static int match(struct hashmap *map, int line1, int line2)\n>>>   {\n>>>   \txrecord_t *record1 = map->env->xdf1.recs[line1 - 1];\n>>>   \txrecord_t *record2 = map->env->xdf2.recs[line2 - 1];\n>>> -\treturn xdl_recmatch(record1->ptr, record1->size,\n>>> -\t\trecord2->ptr, record2->size, map->xpp->flags);\n>>> +\treturn record1->ha == record2->ha;\n>>>   }\n>>>\n>>>   static int patience_diff(mmfile_t *file1, mmfile_t *file2,\n>>\n\n"},{"id":"423729","messageId":"xmqqo8do1wbh.fsf@gitster.g","threadId":"55615","inReplyTo":"nycvar.QRO.7.76.6.2105051649280.50@tvgsbejvaqbjf.bet","subject":"Re: [PATCH 1/2] patience diff: remove unnecessary string comparisons","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-05-06T01:32:18Z","receivedAt":"2021-05-06T01:32:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> Right. I had the same concern. But it does look as if\n> `xdl_classify_record()` replaced the possibly non-unique hash values to\n> unique sequential identifiers.\n>\n> I have to admit that the code is unnecessarily hard to read for me:\n> https://github.com/git/git/blob/v2.31.1/xdiff/xprepare.c#L110-L157\n>\n> But I do gather that the loop at\n> https://github.com/git/git/blob/v2.31.1/xdiff/xprepare.c#L119-L123\n> is called for every line, that it does compare it to every seen line with\n> the same hash, and that it exits the loop early if the contents disagree:\n>\n> \tfor (rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next)\n> \t\tif (rcrec->ha == rec->ha &&\n> \t\t\t\txdl_recmatch(rcrec->line, rcrec->size,\n> \t\t\t\t\trec->ptr, rec->size, cf->flags))\n> \t\t\tbreak;\n\nYeah, I arrived at the same conclusion.  Also as Phillip said in a\nseparate message, Myers side already takes advantage of this same\nfact, so I am fine with this change.\n\nThanks, both.\n"}]}