From: "Ezekiel Newren via GitGitGadget" <gitgitgadget@gmail•com>
To: git@vger•kernel.org
Cc: Kristoffer Haugsbakk <kristofferhaugsbakk@fastmail•com>,
Patrick Steinhardt <ps@pks•im>,
Phillip Wood <phillip.wood123@gmail•com>,
Chris Torek <chris.torek@gmail•com>,
Ramsay Jones <ramsay@ramsayjones•plus.com>,
Ben Knoble <ben.knoble@gmail•com>,
Ezekiel Newren <ezekielnewren@gmail•com>,
Ezekiel Newren <ezekielnewren@gmail•com>
Subject: [PATCH v5 06/10] xdiff: split xrecord_t.ha into line_hash and minimal_perfect_hash
Date: Tue, 18 Nov 2025 22:34:18 +0000 [thread overview]
Message-ID: <78af0f16f4a1c3af0b8474169ceb75bda2b94b49.1763505262.git.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.2070.v5.git.git.1763505262.gitgitgadget@gmail.com>
From: Ezekiel Newren <ezekielnewren@gmail•com>
The ha field is serving two different purposes, which makes the code
harder to read. At first glance, it looks like many places assume
there could never be hash collisions between lines of the two input
files. In reality, line_hash is used together with xdl_recmatch() to
ensure correct comparisons of lines, even when collisions occur.
To make this clearer, the old ha field has been split:
* line_hash: a straightforward hash of a line, independent of any
external context. Its type is uint64_t, as it comes from a fixed
width hash function.
* minimal_perfect_hash: Not a new concept, but now a separate
field. It comes from the classifier's general-purpose hash table,
which assigns each line a unique and minimal hash across the two
files. A size_t is used here because it's meant to be used to
index an array. This also avoids ` as usize` casts on the Rust
side when using it to index a slice.
Signed-off-by: Ezekiel Newren <ezekielnewren@gmail•com>
---
xdiff/xdiffi.c | 6 +++---
xdiff/xhistogram.c | 4 ++--
xdiff/xpatience.c | 10 +++++-----
xdiff/xprepare.c | 18 +++++++++---------
xdiff/xtypes.h | 3 ++-
5 files changed, 21 insertions(+), 20 deletions(-)
diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
index cb8e412c7b..8d96074414 100644
--- a/xdiff/xdiffi.c
+++ b/xdiff/xdiffi.c
@@ -22,9 +22,9 @@
#include "xinclude.h"
-static unsigned long get_hash(xdfile_t *xdf, long index)
+static size_t get_hash(xdfile_t *xdf, long index)
{
- return xdf->recs[xdf->rindex[index]].ha;
+ return xdf->recs[xdf->rindex[index]].minimal_perfect_hash;
}
#define XDL_MAX_COST_MIN 256
@@ -385,7 +385,7 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1,
static int recs_match(xrecord_t *rec1, xrecord_t *rec2)
{
- return (rec1->ha == rec2->ha);
+ return rec1->minimal_perfect_hash == rec2->minimal_perfect_hash;
}
/*
diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c
index 6dc450b1fe..5ae1282c27 100644
--- a/xdiff/xhistogram.c
+++ b/xdiff/xhistogram.c
@@ -90,7 +90,7 @@ struct region {
static int cmp_recs(xrecord_t *r1, xrecord_t *r2)
{
- return r1->ha == r2->ha;
+ return r1->minimal_perfect_hash == r2->minimal_perfect_hash;
}
@@ -98,7 +98,7 @@ static int cmp_recs(xrecord_t *r1, xrecord_t *r2)
(cmp_recs(REC(i->env, s1, l1), REC(i->env, s2, l2)))
#define TABLE_HASH(index, side, line) \
- XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits)
+ XDL_HASHLONG((REC(index->env, side, line))->minimal_perfect_hash, index->table_bits)
static int scanA(struct histindex *index, int line1, int count1)
{
diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c
index bb61354f22..cc53266f3b 100644
--- a/xdiff/xpatience.c
+++ b/xdiff/xpatience.c
@@ -48,7 +48,7 @@
struct hashmap {
int nr, alloc;
struct entry {
- unsigned long hash;
+ size_t minimal_perfect_hash;
/*
* 0 = unused entry, 1 = first line, 2 = second, etc.
* line2 is NON_UNIQUE if the line is not unique
@@ -101,10 +101,10 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,
* So we multiply ha by 2 in the hope that the hashing was
* "unique enough".
*/
- int index = (int)((record->ha << 1) % map->alloc);
+ int index = (int)((record->minimal_perfect_hash << 1) % map->alloc);
while (map->entries[index].line1) {
- if (map->entries[index].hash != record->ha) {
+ if (map->entries[index].minimal_perfect_hash != record->minimal_perfect_hash) {
if (++index >= map->alloc)
index = 0;
continue;
@@ -120,7 +120,7 @@ static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,
if (pass == 2)
return;
map->entries[index].line1 = line;
- map->entries[index].hash = record->ha;
+ map->entries[index].minimal_perfect_hash = record->minimal_perfect_hash;
map->entries[index].anchor = is_anchor(xpp, (const char *)map->env->xdf1.recs[line - 1].ptr);
if (!map->first)
map->first = map->entries + index;
@@ -248,7 +248,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 record1->ha == record2->ha;
+ return record1->minimal_perfect_hash == record2->minimal_perfect_hash;
}
static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,
diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
index 85e56021da..bea0992b5e 100644
--- a/xdiff/xprepare.c
+++ b/xdiff/xprepare.c
@@ -93,12 +93,12 @@ static void xdl_free_classifier(xdlclassifier_t *cf) {
static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t *rec) {
- long hi;
+ size_t hi;
xdlclass_t *rcrec;
- hi = (long) XDL_HASHLONG(rec->ha, cf->hbits);
+ hi = XDL_HASHLONG(rec->line_hash, cf->hbits);
for (rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next)
- if (rcrec->rec.ha == rec->ha &&
+ if (rcrec->rec.line_hash == rec->line_hash &&
xdl_recmatch((const char *)rcrec->rec.ptr, (long)rcrec->rec.size,
(const char *)rec->ptr, (long)rec->size, cf->flags))
break;
@@ -120,7 +120,7 @@ static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t
(pass == 1) ? rcrec->len1++ : rcrec->len2++;
- rec->ha = (unsigned long) rcrec->idx;
+ rec->minimal_perfect_hash = (size_t)rcrec->idx;
return 0;
}
@@ -158,7 +158,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_
crec = &xdf->recs[xdf->nrec++];
crec->ptr = prev;
crec->size = cur - prev;
- crec->ha = hav;
+ crec->line_hash = hav;
if (xdl_classify_record(pass, cf, crec) < 0)
goto abort;
}
@@ -290,7 +290,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)
mlim = XDL_MAX_EQLIMIT;
for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {
- rcrec = cf->rcrecs[recs->ha];
+ rcrec = cf->rcrecs[recs->minimal_perfect_hash];
nm = rcrec ? rcrec->len2 : 0;
action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
}
@@ -298,7 +298,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)
mlim = XDL_MAX_EQLIMIT;
for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {
- rcrec = cf->rcrecs[recs->ha];
+ rcrec = cf->rcrecs[recs->minimal_perfect_hash];
nm = rcrec ? rcrec->len1 : 0;
action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
}
@@ -350,7 +350,7 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {
recs2 = xdf2->recs;
for (i = 0, lim = XDL_MIN(xdf1->nrec, xdf2->nrec); i < lim;
i++, recs1++, recs2++)
- if (recs1->ha != recs2->ha)
+ if (recs1->minimal_perfect_hash != recs2->minimal_perfect_hash)
break;
xdf1->dstart = xdf2->dstart = i;
@@ -358,7 +358,7 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {
recs1 = xdf1->recs + xdf1->nrec - 1;
recs2 = xdf2->recs + xdf2->nrec - 1;
for (lim -= i, i = 0; i < lim; i++, recs1--, recs2--)
- if (recs1->ha != recs2->ha)
+ if (recs1->minimal_perfect_hash != recs2->minimal_perfect_hash)
break;
xdf1->dend = xdf1->nrec - i - 1;
diff --git a/xdiff/xtypes.h b/xdiff/xtypes.h
index 354349b523..d4e9cd2e76 100644
--- a/xdiff/xtypes.h
+++ b/xdiff/xtypes.h
@@ -41,7 +41,8 @@ typedef struct s_chastore {
typedef struct s_xrecord {
uint8_t const *ptr;
size_t size;
- unsigned long ha;
+ uint64_t line_hash;
+ size_t minimal_perfect_hash;
} xrecord_t;
typedef struct s_xdfile {
--
gitgitgadget
next prev parent reply other threads:[~2025-11-18 22:34 UTC|newest]
Thread overview: 118+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-10-15 21:18 [PATCH 0/9] Xdiff cleanup part2 Ezekiel Newren via GitGitGadget
2025-10-15 21:18 ` [PATCH 1/9] xdiff: use ssize_t for dstart/dend, make them last in xdfile_t Ezekiel Newren via GitGitGadget
2025-10-21 11:32 ` Phillip Wood
2025-10-21 17:18 ` Junio C Hamano
2025-10-22 21:07 ` Ezekiel Newren
2025-10-22 21:38 ` Junio C Hamano
2025-10-22 21:51 ` Ezekiel Newren
2025-10-15 21:18 ` [PATCH 2/9] xdiff: make xrecord_t.ptr a uint8_t instead of char Ezekiel Newren via GitGitGadget
2025-10-16 21:51 ` Kristoffer Haugsbakk
2025-10-21 8:33 ` Patrick Steinhardt
2025-10-22 21:12 ` Ezekiel Newren
2025-10-21 13:13 ` Phillip Wood
2025-10-21 18:15 ` Junio C Hamano
2025-10-22 13:27 ` Phillip Wood
2025-10-22 20:55 ` Ezekiel Newren
2025-10-15 21:18 ` [PATCH 3/9] xdiff: use size_t for xrecord_t.size Ezekiel Newren via GitGitGadget
2025-10-15 21:18 ` [PATCH 4/9] xdiff: use unambiguous types in xdl_hash_record() Ezekiel Newren via GitGitGadget
2025-10-21 8:33 ` Patrick Steinhardt
2025-10-22 21:20 ` Ezekiel Newren
2025-10-23 5:49 ` Patrick Steinhardt
2025-10-15 21:18 ` [PATCH 5/9] xdiff: split xrecord_t.ha into line_hash and minimal_perfect_hash Ezekiel Newren via GitGitGadget
2025-10-20 23:29 ` Ezekiel Newren
2025-10-21 5:10 ` Junio C Hamano
2025-10-21 8:33 ` Patrick Steinhardt
2025-10-21 10:03 ` Phillip Wood
2025-10-21 11:16 ` Chris Torek
2025-10-22 21:31 ` Ezekiel Newren
2025-10-15 21:18 ` [PATCH 6/9] xdiff: make xdfile_t.nrec a size_t instead of long Ezekiel Newren via GitGitGadget
2025-10-15 21:18 ` [PATCH 7/9] xdiff: make xdfile_t.nreff " Ezekiel Newren via GitGitGadget
2025-10-15 21:18 ` [PATCH 8/9] xdiff: change rindex from long to size_t in xdfile_t Ezekiel Newren via GitGitGadget
2025-10-21 8:34 ` Patrick Steinhardt
2025-10-22 22:14 ` Ezekiel Newren
2025-10-23 5:49 ` Patrick Steinhardt
2025-10-15 21:18 ` [PATCH 9/9] xdiff: rename rindex -> reference_index Ezekiel Newren via GitGitGadget
2025-10-15 21:28 ` [PATCH 0/9] Xdiff cleanup part2 Junio C Hamano
2025-10-21 13:28 ` Phillip Wood
2025-10-21 13:41 ` Junio C Hamano
2025-10-29 22:19 ` [PATCH v2 00/10] " Ezekiel Newren via GitGitGadget
2025-10-29 22:19 ` [PATCH v2 01/10] doc: define unambiguous type mappings across C and Rust Ezekiel Newren via GitGitGadget
2025-11-06 9:55 ` Phillip Wood
2025-11-06 22:52 ` Ezekiel Newren
2025-11-09 14:14 ` Phillip Wood
2025-10-29 22:19 ` [PATCH v2 02/10] xdiff: use ssize_t for dstart/dend, make them last in xdfile_t Ezekiel Newren via GitGitGadget
2025-11-06 9:55 ` Phillip Wood
2025-11-06 22:56 ` Ezekiel Newren
2025-10-29 22:19 ` [PATCH v2 03/10] xdiff: make xrecord_t.ptr a uint8_t instead of char Ezekiel Newren via GitGitGadget
2025-11-06 10:49 ` Phillip Wood
2025-11-06 23:13 ` Ezekiel Newren
2025-11-06 10:55 ` Phillip Wood
2025-11-06 23:14 ` Ezekiel Newren
2025-10-29 22:19 ` [PATCH v2 04/10] xdiff: use size_t for xrecord_t.size Ezekiel Newren via GitGitGadget
2025-10-29 22:19 ` [PATCH v2 05/10] xdiff: use unambiguous types in xdl_hash_record() Ezekiel Newren via GitGitGadget
2025-10-29 22:19 ` [PATCH v2 06/10] xdiff: split xrecord_t.ha into line_hash and minimal_perfect_hash Ezekiel Newren via GitGitGadget
2025-11-06 11:00 ` Phillip Wood
2025-11-06 23:20 ` Ezekiel Newren
2025-10-29 22:19 ` [PATCH v2 07/10] xdiff: make xdfile_t.nrec a size_t instead of long Ezekiel Newren via GitGitGadget
2025-10-29 22:19 ` [PATCH v2 08/10] xdiff: make xdfile_t.nreff " Ezekiel Newren via GitGitGadget
2025-10-29 22:19 ` [PATCH v2 09/10] xdiff: change rindex from long to size_t in xdfile_t Ezekiel Newren via GitGitGadget
2025-10-29 22:19 ` [PATCH v2 10/10] xdiff: rename rindex -> reference_index Ezekiel Newren via GitGitGadget
2025-10-30 14:26 ` [PATCH v2 00/10] Xdiff cleanup part2 Junio C Hamano
2025-11-11 19:42 ` [PATCH v3 " Ezekiel Newren via GitGitGadget
2025-11-11 19:42 ` [PATCH v3 01/10] doc: define unambiguous type mappings across C and Rust Ezekiel Newren via GitGitGadget
2025-11-11 20:52 ` Junio C Hamano
2025-11-11 21:05 ` Junio C Hamano
2025-11-11 19:42 ` [PATCH v3 02/10] xdiff: use ptrdiff_t for dstart/dend Ezekiel Newren via GitGitGadget
2025-11-11 22:23 ` Junio C Hamano
2025-11-11 19:42 ` [PATCH v3 03/10] xdiff: make xrecord_t.ptr a uint8_t instead of char Ezekiel Newren via GitGitGadget
2025-11-11 22:53 ` Junio C Hamano
2025-11-11 19:42 ` [PATCH v3 04/10] xdiff: use size_t for xrecord_t.size Ezekiel Newren via GitGitGadget
2025-11-11 23:08 ` Junio C Hamano
2025-11-14 6:02 ` Ezekiel Newren
2025-11-14 16:31 ` Junio C Hamano
2025-11-11 19:42 ` [PATCH v3 05/10] xdiff: use unambiguous types in xdl_hash_record() Ezekiel Newren via GitGitGadget
2025-11-11 19:42 ` [PATCH v3 06/10] xdiff: split xrecord_t.ha into line_hash and minimal_perfect_hash Ezekiel Newren via GitGitGadget
2025-11-11 23:21 ` Junio C Hamano
2025-11-14 5:41 ` Ezekiel Newren
2025-11-14 20:06 ` Junio C Hamano
2025-11-11 19:42 ` [PATCH v3 07/10] xdiff: make xdfile_t.nrec a size_t instead of long Ezekiel Newren via GitGitGadget
2025-11-11 19:42 ` [PATCH v3 08/10] xdiff: make xdfile_t.nreff " Ezekiel Newren via GitGitGadget
2025-11-11 19:42 ` [PATCH v3 09/10] xdiff: change rindex from long to size_t in xdfile_t Ezekiel Newren via GitGitGadget
2025-11-11 19:42 ` [PATCH v3 10/10] xdiff: rename rindex -> reference_index Ezekiel Newren via GitGitGadget
2025-11-11 23:40 ` [PATCH v3 00/10] Xdiff cleanup part2 Junio C Hamano
2025-11-14 5:52 ` Ezekiel Newren
2025-11-14 22:36 ` [PATCH v4 " Ezekiel Newren via GitGitGadget
2025-11-14 22:36 ` [PATCH v4 01/10] doc: define unambiguous type mappings across C and Rust Ezekiel Newren via GitGitGadget
2025-11-15 3:06 ` Ramsay Jones
2025-11-15 3:41 ` Ben Knoble
2025-11-15 14:55 ` Ramsay Jones
2025-11-15 16:42 ` Junio C Hamano
2025-11-15 16:59 ` D. Ben Knoble
2025-11-15 20:03 ` Junio C Hamano
2025-11-17 1:20 ` Junio C Hamano
2025-11-17 2:08 ` Ramsay Jones
2025-11-14 22:36 ` [PATCH v4 02/10] xdiff: use ptrdiff_t for dstart/dend Ezekiel Newren via GitGitGadget
2025-11-14 22:36 ` [PATCH v4 03/10] xdiff: make xrecord_t.ptr a uint8_t instead of char Ezekiel Newren via GitGitGadget
2025-11-15 8:26 ` Junio C Hamano
2025-11-18 20:55 ` Ezekiel Newren
2025-11-14 22:36 ` [PATCH v4 04/10] xdiff: use size_t for xrecord_t.size Ezekiel Newren via GitGitGadget
2025-11-14 22:36 ` [PATCH v4 05/10] xdiff: use unambiguous types in xdl_hash_record() Ezekiel Newren via GitGitGadget
2025-11-14 22:36 ` [PATCH v4 06/10] xdiff: split xrecord_t.ha into line_hash and minimal_perfect_hash Ezekiel Newren via GitGitGadget
2025-11-14 22:36 ` [PATCH v4 07/10] xdiff: make xdfile_t.nrec a size_t instead of long Ezekiel Newren via GitGitGadget
2025-11-14 22:36 ` [PATCH v4 08/10] xdiff: make xdfile_t.nreff " Ezekiel Newren via GitGitGadget
2025-11-14 22:36 ` [PATCH v4 09/10] xdiff: change rindex from long to size_t in xdfile_t Ezekiel Newren via GitGitGadget
2025-11-14 22:36 ` [PATCH v4 10/10] xdiff: rename rindex -> reference_index Ezekiel Newren via GitGitGadget
2025-11-18 22:34 ` [PATCH v5 00/10] Xdiff cleanup part2 Ezekiel Newren via GitGitGadget
2025-11-18 22:34 ` [PATCH v5 01/10] doc: define unambiguous type mappings across C and Rust Ezekiel Newren via GitGitGadget
2025-11-18 23:46 ` Ramsay Jones
2025-11-19 4:14 ` Junio C Hamano
2025-11-18 22:34 ` [PATCH v5 02/10] xdiff: use ptrdiff_t for dstart/dend Ezekiel Newren via GitGitGadget
2025-11-18 22:34 ` [PATCH v5 03/10] xdiff: make xrecord_t.ptr a uint8_t instead of char Ezekiel Newren via GitGitGadget
2025-11-18 22:34 ` [PATCH v5 04/10] xdiff: use size_t for xrecord_t.size Ezekiel Newren via GitGitGadget
2025-11-18 22:34 ` [PATCH v5 05/10] xdiff: use unambiguous types in xdl_hash_record() Ezekiel Newren via GitGitGadget
2025-11-18 22:34 ` Ezekiel Newren via GitGitGadget [this message]
2025-11-18 22:34 ` [PATCH v5 07/10] xdiff: make xdfile_t.nrec a size_t instead of long Ezekiel Newren via GitGitGadget
2025-11-18 22:34 ` [PATCH v5 08/10] xdiff: make xdfile_t.nreff " Ezekiel Newren via GitGitGadget
2025-11-18 22:34 ` [PATCH v5 09/10] xdiff: change rindex from long to size_t in xdfile_t Ezekiel Newren via GitGitGadget
2025-11-18 22:34 ` [PATCH v5 10/10] xdiff: rename rindex -> reference_index Ezekiel Newren via GitGitGadget
2025-11-18 23:11 ` [PATCH v5 00/10] Xdiff cleanup part2 Junio C Hamano
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=78af0f16f4a1c3af0b8474169ceb75bda2b94b49.1763505262.git.gitgitgadget@gmail.com \
--to=gitgitgadget@gmail$(echo .)com \
--cc=ben.knoble@gmail$(echo .)com \
--cc=chris.torek@gmail$(echo .)com \
--cc=ezekielnewren@gmail$(echo .)com \
--cc=git@vger$(echo .)kernel.org \
--cc=kristofferhaugsbakk@fastmail$(echo .)com \
--cc=phillip.wood123@gmail$(echo .)com \
--cc=ps@pks$(echo .)im \
--cc=ramsay@ramsayjones$(echo .)plus.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox