Re: [PATCH 1/2] patience diff: remove unnecessary string comparisons

On 05/05/2021 01:31, Junio C Hamano wrote:

"Phillip Wood via GitGitGadget" [off-list ref] writes:

quoted

From: Phillip Wood <redacted>

xdl_prepare_env() calls xdl_classify_record() which arranges for the
hashes of non-matching lines to be different so lines can be tested
for equality by comparing just their hashes.

Hmph, that is a bit different from what I read from the comment in
the post context of the first hunk, though.

	/*
	 * After xdl_prepare_env() (or more precisely, due to
	 * xdl_classify_record()), the "ha" member of the records (AKA lines)
	 * is _not_ the hash anymore, but a linearized version of it.  In
	 * other words, the "ha" member is guaranteed to start with 0 and
	 * the second record's ha can only be 0 or 1, etc.
	 *
	 * So we multiply ha by 2 in the hope that the hashing was
	 * "unique enough".
	 */

The words "home" and "enough" hints to me that the "ha" member is
not hash, but "lineralized version of it" (whatever it means) does
not guarantee that two records with the same "ha" are identical, or
does it?

By "hashes" I meant "the value of record->ha". That comment is a bit 
confusing. I think "linearized version of it" is referring to 
xdl_classify_record() assigning a unique integer to each unique input 
line starting from zero and increasing by one for each unique input line 
(the function is fairly easy to follow). I assume "unique enough" is 
referring to the line below the comment which takes the modulus of 
record->ha and record->ha is not evenly distributed over the whole 
integer range but bunched at the lower end.

The Myers implementation calls xdl_classify_record() and then only ever 
compares record->ha, it does not call xdl_recmatch() while computing the 
diff.

Well, I should just go read xdl_classify_record() to see what it
really does, but if it eliminates collisions, then the patch is a
clear and obvious improvement.

Thanks

Phillip

Thanks.

quoted

diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c
index 20699a6f6054..db2d53e89cb0 100644
--- a/xdiff/xpatience.c
+++ b/xdiff/xpatience.c

@@ -90,7 +90,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,
  {
  	xrecord_t **records = pass == 1 ?
  		map->env->xdf1.recs : map->env->xdf2.recs;
-	xrecord_t *record = records[line - 1], *other;
+	xrecord_t *record = records[line - 1];
  	/*
  	 * After xdl_prepare_env() (or more precisely, due to
  	 * xdl_classify_record()), the "ha" member of the records (AKA lines)

@@ -104,11 +104,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,
  	int index = (int)((record->ha << 1) % map->alloc);
  
  	while (map->entries[index].line1) {
-		other = map->env->xdf1.recs[map->entries[index].line1 - 1];
-		if (map->entries[index].hash != record->ha ||
-				!xdl_recmatch(record->ptr, record->size,
-					other->ptr, other->size,
-					map->xpp->flags)) {
+		if (map->entries[index].hash != record->ha) {
  			if (++index >= map->alloc)
  				index = 0;
  			continue;

@@ -253,8 +249,7 @@ static int match(struct hashmap *map, int line1, int line2)
  {
  	xrecord_t *record1 = map->env->xdf1.recs[line1 - 1];
  	xrecord_t *record2 = map->env->xdf2.recs[line2 - 1];
-	return xdl_recmatch(record1->ptr, record1->size,
-		record2->ptr, record2->size, map->xpp->flags);
+	return record1->ha == record2->ha;
  }
  
  static int patience_diff(mmfile_t *file1, mmfile_t *file2,