git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
PGPhillip Wood via GitGitGadget <gitgitgadget@gmail.com>
Date
May 4, 2021, 09:25 UTC
Message-ID
<a339d1cf9b9ffd6365fca3efda8fb7e10346dda4.1620120345.git.gitgitgadget@gmail.com>
In-Reply-To
<pull.948.git.1620120345.gitgitgadget@gmail.com>
From: Phillip Wood <phillip.wood@dunelm.org.uk>

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.

This reduces the time taken to calculate the diff of v2.28.0 to v2.29.0 by ~3-4%.

Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
---
 xdiff/xpatience.c | 11 +++--------
 1 file changed, 3 insertions(+), 8 deletions(-)
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,
-- 
gitgitgadget
Previous: Phillip Wood via GitGitGadgetNext: Junio C Hamano
Message 2 of 8 in “A couple of small patience diff cleanups”
  1. 0/2 A couple of small patience diff cleanupsPhillip Wood via GitGitGadget, May 4, 2021
  2. 1/2 patience diff: remove unnecessary string comparisonsPhillip Wood via GitGitGadget, May 4, 2021
  3. Junio C HamanoMay 5, 2021
  4. Phillip WoodMay 5, 2021
  5. Johannes SchindelinMay 5, 2021
  6. Phillip WoodMay 5, 2021
  7. Junio C HamanoMay 6, 2021
  8. 2/2 patience diff: remove unused variablePhillip Wood via GitGitGadget, May 4, 2021

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.