Subject: Re: [PATCH 09/10] xdiff: remove dependence on xdlclassifier from xdl_cleanup_records()

From: René Scharfe <[email-masked]>
Date: Sun, 18 Jan 2026 19:23:48 +0100

On 1/17/26 5:34 PM, Ezekiel Newren wrote:
> On Fri, Jan 16, 2026 at 1:19 PM René Scharfe <[email-masked]> wrote:
>>
>> On 1/2/26 7:52 PM, Ezekiel Newren via GitGitGadget wrote:
>>> @@ -253,22 +250,44 @@ static bool xdl_clean_mmatch(uint8_t const *action, long i, long s, long e) {
>>>       return rpdis1 * XDL_KPDIS_RUN < (rpdis1 + rdis1);
>>>  }
>>>
>>> +struct xoccurrence
>>> +{
>>> +     size_t file1, file2;
>>> +};
>>> +
>>> +
>>> +DEFINE_IVEC_TYPE(struct xoccurrence, xoccurrence);
>>> +
>>>
>>>  /*
>>>   * Try to reduce the problem complexity, discard records that have no
>>>   * matches on the other file. Also, lines that have multiple matches
>>>   * might be potentially discarded if they appear in a run of discardable.
>>>   */
>>> -static int xdl_cleanup_records(xdlclassifier_t *cf, xdfenv_t *xe) {
>>> -     long i, nm, mlim;
>>> +static int xdl_cleanup_records(xdfenv_t *xe, uint64_t flags) {
>>> +     long i;
>>> +     size_t nm, mlim;
>>>       xrecord_t *recs;
>>> -     xdlclass_t *rcrec;
>>>       uint8_t *action1 = NULL, *action2 = NULL;
>>> -     bool need_min = !!(cf->flags & XDF_NEED_MINIMAL);
>>> +     struct IVec_xoccurrence occ;
>>> +     bool need_min = !!(flags & XDF_NEED_MINIMAL);
>>>       int ret = 0;
>>>       ptrdiff_t dend1 = xe->xdf1.nrec - 1 - xe->delta_end;
>>>       ptrdiff_t dend2 = xe->xdf2.nrec - 1 - xe->delta_end;
>>>
>>> +     IVEC_INIT(occ);
>>> +     ivec_zero(&occ, xe->mph_size);
>>
>> This array is presized here.  It is neither grown nor shrunken.
>> CALLOC_ARRAY would work just as well, at least at this point, no?
>>
>>> +
>>> +     for (size_t j = 0; j < xe->xdf1.nrec; j++) {
>>> +             size_t mph1 = xe->xdf1.recs[j].minimal_perfect_hash;
>>> +             occ.ptr[mph1].file1 += 1;
>>> +     }
>>> +
>>> +     for (size_t j = 0; j < xe->xdf2.nrec; j++) {
>>> +             size_t mph2 = xe->xdf2.recs[j].minimal_perfect_hash;
>>> +             occ.ptr[mph2].file2 += 1;
>>> +     }
>>> +
>>>       /*
>>>        * Create temporary arrays that will help us decide if
>>>        * changed[i] should remain false, or become true.
>>> @@ -288,16 +307,14 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfenv_t *xe) {
>>>       if ((mlim = xdl_bogosqrt((long)xe->xdf1.nrec)) > XDL_MAX_EQLIMIT)
>>>               mlim = XDL_MAX_EQLIMIT;
>>>       for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start]; i <= dend1; i++, recs++) {
>>> -             rcrec = cf->rcrecs[recs->minimal_perfect_hash];
>>> -             nm = rcrec ? rcrec->len2 : 0;
>>> +             nm = occ.ptr[recs->minimal_perfect_hash].file2;
>>>               action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
>>>       }
>>>
>>>       if ((mlim = xdl_bogosqrt((long)xe->xdf2.nrec)) > XDL_MAX_EQLIMIT)
>>>               mlim = XDL_MAX_EQLIMIT;
>>>       for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start]; i <= dend2; i++, recs++) {
>>> -             rcrec = cf->rcrecs[recs->minimal_perfect_hash];
>>> -             nm = rcrec ? rcrec->len1 : 0;
>>> +             nm = occ.ptr[recs->minimal_perfect_hash].file1;
>>>               action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
>>>       }
>>>
>>> @@ -332,6 +349,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfenv_t *xe) {
>>>  cleanup:
>>>       xdl_free(action1);
>>>       xdl_free(action2);
>>> +     ivec_free(&occ);
>>>
>>>       return ret;
>>>  }
> 
> In Rust the memory management macros defined in git-compat-util.h will
> not be available. ivec was built expressly to bridge the gap between C
> and Rust. I'm avoiding using those macros because I'm trying to get C
> programmers familiar with how Rust's Vec operates without forcing them
> to read and write in Rust. Also, it makes converting from IVec to Vec
> super easy.
> 
> ivec_zero() also sets length and capacity. Also CALLOC_ARRAY needs to
> know the type of the pointer which ivec_zero() does not have access
> to. This is one of the few ivec functions that does not have a direct
> equivalent in Rust's Vec, but is faster than what is logically
> equivalent in Rust.
> 
> In Rust the closest safe equivalent would look like:
> 
> let size = 35;
> let mut vec = Vec::<u64>::new();
> vec.reserve_exact(size);
> vec.fill(0);  // requires that T implements the `Copy` trait
> 
> The unsafe version would look like:
> let size = 35;
> let mut vec = Vec::<u64>::new();
> vec.reserve_exact(size);
> unsafe {
>     std::ptr::write_bytes(vec.as_mut_ptr(), 0, size * size_of::<u64>());
> }

I was being unclear and made a few assumptions here.  My point was just
that this is a fixed-size array and doesn't need to be stored in a
variable-sized container.  This is the first Ivec user, and I would have
expected it to exercise the push function.  I assume accessing a
fixed-size array via FFI would be a lot easier since allocation and
growth are out of the picture.

René