On Mon, Jul 03, 2023 at 01:56:27AM -0400, Jeff King wrote:
> 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.
Good idea, thanks.
> > $ 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).
I agree. I included a build from the previous commit in this benchmark.
As expected, it's around ~100ms, but at least it gives readers a clearer
picture of how performance changes as a result of this patch.
(
> > @@ -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.
Exactly. I added a short comment to this effect to hopefully avoid any
confusion here.
> > + 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. :)
Oh, definitely ;-).
> > + /*
> > + * 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?
Yeah, I agree with this. I think Patrick made a similar suggestion in an
earlier response, and I decided not to take it since it makes the patch
more verbose.
But I think that avoiding the empty region special case is worth it.
Thanks, both :-).
Thanks,
Taylor
