Re: [PATCH] last-modified: implement faster algorithm

[Taylor Blau <me@ttaylorr.com>]

On Tue, Oct 21, 2025 at 11:04:05AM +0200, Toon Claes wrote:
> > Taylor Blau <me@ttaylorr.com> writes:
>
> >> Nice, I am glad to see that we are using a bitmap here rather than the
> >> hacky 'char *' that we had originally written. I seem to remember that
> >> there was a tiny slow-down when using bitmaps, but can't find the
> >> discussion anymore. (It wasn't in the internal PR that I originally
> >> opened, and I no longer can read messages that far back in history.)
> >>
> >> It might be worth benchmarking here to see if using a 'char *' is
> >> faster. Of course, that's 8x worse in terms of memory usage, but not a
> >> huge deal given both the magnitude and typical number of directory
> >> elements (you'd need 1024^2 entries in a single tree to occupy even a
> >> single MiB of heap).
>
> Using ewah bitmaps is slightly faster, although the difference is almost
> neglible.
>
>     Benchmark 1: bitmap-ewah
>       Time (mean ± σ):     793.1 ms ±   6.2 ms    [User: 755.1 ms, System: 35.2 ms]
>       Range (min … max):   784.7 ms … 804.8 ms    10 runs
>
>     Benchmark 2: bitmap-chars
>       Time (mean ± σ):     808.9 ms ±  11.2 ms    [User: 770.8 ms, System: 35.4 ms]
>       Range (min … max):   800.2 ms … 830.5 ms    10 runs
>
>     Summary
>       bitmap-ewah ran
>         1.02 ± 0.02 times faster than bitmap-chars

OK, makes sense, though just to clarify, "bitmap-ewah" is just a
bog-standard "struct bitmap", right? That happens to come from the EWAH
implementation, but the bitmap itself is not being EWAH compressed,
right?

> And ewah bitmap being more memory efficient, it makes more sense to keep
> using those.
>
> >> Likewise, I wonder if we should have elemtype here be just 'struct
> >> bitmap'. Unfortunately I don't think the EWAH code has a function like:
> >>
> >>     void bitmap_init(struct bitmap *);
> >>
> >> and only has ones that allocate for us. So we may consider adding one,
> >> or creating a dummy bitmap and copying its contents, or otherwise.
>
> I've done some testing, and to do so I've made bitmap_grow() public.
>
>     Benchmark 1: bitmap-as-pointers
>       Time (mean ± σ):     783.7 ms ±   8.9 ms    [User: 744.1 ms, System: 37.5 ms]
>       Range (min … max):   774.4 ms … 803.4 ms    10 runs
>
>     Benchmark 2: bitmap-as-values
>       Time (mean ± σ):     856.7 ms ±  10.5 ms    [User: 816.0 ms, System: 38.1 ms]
>       Range (min … max):   845.7 ms … 872.5 ms    10 runs
>
>     Summary
>       bitmap-as-pointers ran
>         1.09 ± 0.02 times faster than bitmap-as-values
>
> It seems using ewah bitmaps as pointers is faster than using bitmaps as
> values. I must admit I'm surprised as well, but in case you want to
> double check, here's the patch:

I think this makes sense; the pointers are half as wide as a struct
bitmap. Even though we're going through another layer of indirection, I
think that the smaller slab footprint results in better cache locality,
and ultimately faster code. Thanks for testing it out.

Thanks,
Taylor