Re: [PATCH v4 09/16] refs/packed-backend.c: implement jump lists to avoid excluded pattern(s)

> On Tue, Jun 20, 2023 at 10:21:42AM -0400, Taylor Blau wrote:
>
> > Second, note that the jump list is best-effort, since we do not handle
> > loose references, and because of the meta-character issue above. The
> > jump list may not skip past all references which won't appear in the
> > results, but will never skip over a reference which does appear in the
> > result set.
>
> I wonder if we should be advertising this in a docstring comment above
> the relevant function. The problem may be that there are several such
> functions. I just think that it's a gotcha that may affect somebody who
> wants to call the function, and they're not going to think to dig up
> this commit message.

> >     $ hyperfine \
> >       'git for-each-ref --format="%(objectname) %(refname)" | grep -vE "^[0-9a-f]{40} refs/pull/"' \
> >       'git.compile for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"'
> >     Benchmark 1: git for-each-ref --format="%(objectname) %(refname)" | grep -vE "^[0-9a-f]{40} refs/pull/"
> >       Time (mean ± σ):     802.7 ms ±   2.1 ms    [User: 691.6 ms, System: 147.0 ms]
> >       Range (min … max):   800.0 ms … 807.7 ms    10 runs
> >
> >     Benchmark 2: git.compile for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"
> >       Time (mean ± σ):       4.7 ms ±   0.3 ms    [User: 0.7 ms, System: 4.0 ms]
> >       Range (min … max):     4.3 ms …   6.7 ms    422 runs
> >
> >     Summary
> >       'git.compile for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"' ran
> >       172.03 ± 9.60 times faster than 'git for-each-ref --format="%(objectname) %(refname)" | grep -vE "^[0-9a-f]{40} refs/pull/"'
>
> This measurement is cheating a little, I think, because the earlier
> patch to implement --exclude sped that up from ~800ms to ~100ms (because
> we avoid writing and all of the ref-filter malloc slowness for the
> excluded entries). So the better comparison is between two invocations
> with "--exclude", but before/after this patch. You should still see a
> 20x speedup (100ms down to 5).

> > @@ -802,14 +826,34 @@ struct packed_ref_iterator {
> >   */
> >  static int next_record(struct packed_ref_iterator *iter)
> >  {
> > -	const char *p = iter->pos, *eol;
> > +	const char *p, *eol;
> >
> >  	strbuf_reset(&iter->refname_buf);
> >
> > +	/*
> > +	 * If iter->pos is contained within a skipped region, jump past
> > +	 * it.
> > +	 *
> > +	 * Note that each skipped region is considered at most once,
> > +	 * since they are ordered based on their starting position.
> > +	 */
> > +	while (iter->jump_cur < iter->jump_nr) {
> > +		struct jump_list_entry *curr = &iter->jump[iter->jump_cur];
> > +		if (iter->pos < curr->start)
> > +			break; /* not to the next jump yet */
> > +
> > +		iter->jump_cur++;
> > +		if (iter->pos < curr->end) {
> > +			iter->pos = curr->end;
> > +			break;
> > +		}
> > +	}
>
> It took me a minute to convince myself that this second "break" was
> right. If we get to it, we know that iter->pos (the current record we
> are looking at) is in the current jump region. So it makes sense to
> advance to curr->end. But might we hit another jump region immediately?
>
> I guess not, because earlier we would have coalesced the jump regions.
> So either there is a non-excluded entry there _or_ we would have
> coalesced the later region into a single larger region. So breaking is
> the right thing to do.

> > +	for (pattern = excluded_patterns; *pattern; pattern++) {
> > +		struct jump_list_entry *e;
> > +
> > +		/*
> > +		 * We can't feed any excludes with globs in them to the
> > +		 * refs machinery.  It only understands prefix matching.
> > +		 * We likewise can't even feed the string leading up to
> > +		 * the first meta-character, as something like "foo[a]"
> > +		 * should not exclude "foobar" (but the prefix "foo"
> > +		 * would match that and mark it for exclusion).
> > +		 */
> > +		if (has_glob_special(*pattern))
> > +			continue;
>
> OK, and here's where we could split "foo[ac]" into "fooa" and "foob" if
> we wanted. But I think it is a very good idea to leave that out of this
> initial patch. :)

> > +	/*
> > +	 * As an optimization, merge adjacent entries in the jump list
> > +	 * to jump forwards as far as possible when entering a skipped
> > +	 * region.
> > +	 *
> > +	 * For example, if we have two skipped regions:
> > +	 *
> > +	 *	[[A, B], [B, C]]
> > +	 *
> > +	 * we want to combine that into a single entry jumping from A to
> > +	 * C.
> > +	 */
> > +	last_disjoint = iter->jump;
> > +
> > +	for (i = 1, j = 1; i < iter->jump_nr; i++) {
> > +		struct jump_list_entry *ours = &iter->jump[i];
> > +
> > +		if (ours->start == ours->end) {
> > +			/* ignore empty regions (no matching entries) */
> > +			continue;
>
> Dropping empty regions makes sense, but our iteration starts at "1"
> (because the rest of the checks are inherently looking at last_disjoint
> before deciding if each region is worth keeping). So we'd fail to throw
> away iter->jump[0] if it is empty, I think.
>
> That could be fixed here by iterating from 0 and checking for a NULL
> last_disjoint, but maybe it would be easier to avoid allocating at all
> in the earlier loop, when we find that start == end?