Re: [PATCH 5/9] xdiff: split xrecord_t.ha into line_hash and minimal_perfect_hash

From: Ezekiel Newren <ezekielnewren@gmail.com>
Date: Oct 22, 2025, 21:31 UTC
Message-ID: <CAH=ZcbD7FeRHtYvN_4=qHApB-AwK18=KRU2SGWNg8ADkrFM-Fw@mail.gmail.com>
In-Reply-To: <a0711cfe-6e44-44d6-b66b-84a296e113d2@gmail.com>

On Tue, Oct 21, 2025 at 4:03 AM Phillip Wood <phillip.wood123@gmail.com> wrote:

Show 39 quoted lines

>
> 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.

Your understanding is correct. line_hash is fixed width while minimal_perfect_hash is meant to be used as an array index into memory. I'll update my commit message to make this more clear.

> 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.

xrecord_t used to be defined with a pointer, so we're at the same size. But more importantly I plan on splitting minimal_perfect_hash out of xrecord_t into its own array. I think the diff algorithms end up being a little bit faster with a separate array because each element is only 8 bytes instead of 32.

In v2.51.0:
typedef struct s_xrecord {
       struct s_xrecord *next;
       char const *ptr;
       long size;
       unsigned long ha;
} xrecord_t;

This patch series:
typedef struct s_xrecord {
       uint8_t const *ptr;
       size_t size;
       uint64_t line_hash;
       size_t minimal_perfect_hash;
} xrecord_t;

> 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.

I appreciate the careful review. I figured it would be best to limit the scope of this patch series to type changes, so that it wasn't bogged down by other stuff.