From: Phillip Wood <phillip.wood123@gmail•com>
To: Ezekiel Newren <ezekielnewren@gmail•com>,
Ezekiel Newren via GitGitGadget <gitgitgadget@gmail•com>
Cc: git@vger•kernel.org, Patrick Steinhardt <ps@pks•im>,
Junio C Hamano <gitster@pobox•com>
Subject: Re: [PATCH 5/9] xdiff: split xrecord_t.ha into line_hash and minimal_perfect_hash
Date: Tue, 21 Oct 2025 11:03:37 +0100 [thread overview]
Message-ID: <a0711cfe-6e44-44d6-b66b-84a296e113d2@gmail.com> (raw)
In-Reply-To: <CAH=ZcbAjX=V_VvJsRzvQEA+CMM7dWQx6E5=d4FL5CD3s+ozjBg@mail.gmail.com>
Hi Ezekiel
On 21/10/2025 00:29, Ezekiel Newren wrote:
> On Wed, Oct 15, 2025 at 3:18 PM Ezekiel Newren via GitGitGadget
> <gitgitgadget@gmail•com> wrote:
>>
>> 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: The straightforward hash of a line, requiring no
>> additional context.
>> * 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.
>>
>> Signed-off-by: Ezekiel Newren <ezekielnewren@gmail•com>
>
> I'm a bit surprised that nobody has commented on this patch.
I've been off the list and I haven't caught up with this series yet.
> I thought
> that someone would have criticized the length of the name
> "minimal_perfect_hash" or asked me why I was splitting one field into
> two.
I think "perfect_hash" would be fine if we want a shorter name. More
importantly it would be helpful to explain why the two fields have
different types. I assume it is because the perfect_hash is used as an
array index and therefore size_t is a better match for rust's usize than
uint64_t. How much more memory do we end up using by adding second hash
member to the struct? If the aim is to show that only one of them is
used at a time then a union might be more appropriate but I doubt that
plays well with rust.
I'll try and have a look at the other patches later this week. I think
the type changes are going to need careful review.
Thanks
Phillip
next prev parent reply other threads:[~2025-10-21 10:03 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 [this message]
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 ` [PATCH v5 06/10] xdiff: split xrecord_t.ha into line_hash and minimal_perfect_hash Ezekiel Newren via GitGitGadget
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=a0711cfe-6e44-44d6-b66b-84a296e113d2@gmail.com \
--to=phillip.wood123@gmail$(echo .)com \
--cc=ezekielnewren@gmail$(echo .)com \
--cc=git@vger$(echo .)kernel.org \
--cc=gitgitgadget@gmail$(echo .)com \
--cc=gitster@pobox$(echo .)com \
--cc=phillip.wood@dunelm$(echo .)org.uk \
--cc=ps@pks$(echo .)im \
/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