From: Ezekiel Newren Date: Wed, 22 Oct 2025 21:31:57 GMT Subject: Re: [PATCH 5/9] xdiff: split xrecord_t.ha into line_hash and minimal_perfect_hash Message-ID: In-Reply-To: On Tue, Oct 21, 2025 at 4:03 AM Phillip Wood wrote: > > Hi Ezekiel > > On 21/10/2025 00:29, Ezekiel Newren wrote: > > On Wed, Oct 15, 2025 at 3:18 PM Ezekiel Newren via GitGitGadget > > wrote: > >> > >> From: Ezekiel Newren > >> > >> 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 > > > > 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.