Re: [PATCH v4 12/13] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators

From: Taylor Blau <me@ttaylorr.com>
Date: Mar 19, 2025, 23:02 UTC
Message-ID: <Z9tNA/2cZI5ssHnr@nand.local>
In-Reply-To: <20250318020526.GB1473033@coredump.intra.peff.net>

On Mon, Mar 17, 2025 at 10:05:26PM -0400, Jeff King wrote:

Show 22 quoted lines

> On Fri, Mar 14, 2025 at 04:18:56PM -0400, Taylor Blau wrote:
>
> > -static void init_type_iterator(struct ewah_iterator *it,
> > +static void init_type_iterator(struct ewah_or_iterator *it,
> >  			       struct bitmap_index *bitmap_git,
> >  			       enum object_type type)
> >  {
> >  	switch (type) {
> >  	case OBJ_COMMIT:
> > -		ewah_iterator_init(it, bitmap_git->commits);
> > +		ewah_or_iterator_init(it, bitmap_git->commits_all,
> > +				      bitmap_git->base_nr + 1);
>
> This certainly makes sense. It looks like we now use the or_iterator
> unconditionally, even for non-layered queries. It's probably a little
> slower in practice, just because it's an extra layer of indirection. But
> I don't know if trying to micro-optimize here is worth it. In general
> I'd say no, but sometimes there are surprising tight loops with bitmaps.
>
> I dunno. I guess it would be easy enough to do a simple before/after
> benchmark on a single packfile with this series. I wouldn't expect it to
> find anything, but might not hurt to double check.

Should be OK. We're adding one extra allocation, and one extra function call on each _next() iteration. So I think we should be OK here, and indeed...

    $ git for-each-ref --format='%(objectname)' refs/heads refs/tags >in
    $ hyperfine -L v ,.compile 'git{v} pack-objects --stdout --delta-base-offset --use-bitmap-index --revs <in >/dev/null'
    Benchmark 1: git pack-objects --stdout --delta-base-offset --use-bitmap-index --revs <in >/dev/null
      Time (mean ± σ):      1.715 s ±  0.026 s    [User: 4.353 s, System: 0.206 s]
      Range (min … max):    1.692 s …  1.785 s    10 runs

    Benchmark 2: git.compile pack-objects --stdout --delta-base-offset --use-bitmap-index --revs <in >/dev/null
      Time (mean ± σ):      1.712 s ±  0.021 s    [User: 4.401 s, System: 0.223 s]
      Range (min … max):    1.676 s …  1.749 s    10 runs

    Summary
      git.compile pack-objects --stdout --delta-base-offset --use-bitmap-index --revs <in >/dev/null ran
        1.00 ± 0.02 times faster than git pack-objects --stdout --delta-base-offset --use-bitmap-index --revs <in >/dev/null

Looks like we're about the same. 'git' here is the latest release, and 'git.compile' is this commit compiled with -O2 for an apples-to-apples comparison.

In this benchmark it looks like this build is maybe ~1ms faster than the stock build, but we're well within the noise range here, so I don't think there's any statistical significance to the results.

Thanks, Taylor