Re: [PATCH 1/1] ref-filter.c: find disjoint pattern prefixes

> [ ... ]
>
> > Instead, we want to partition the patterns into disjoint sets, where we
> > know that no ref will be matched by any two patterns in different sets.
> > In the above, these are:
> >
> >   - {'refs/heads/a/*', 'refs/heads/a/b/c'}, and
> >   - {'refs/tags/v1.0.0'}
>
> Is this disjoint set calculation already existing, or did you have to
> add it in this patch?

> >   4. Otherwise, recurse on step (3) with the slice of the list
> >      corresponding to our current prefix (i.e., the subset of patterns
> >      that have our prefix as a literal string prefix.)
> >
> > This algorithm is 'O(kn + n log(n))', where 'k' is max(len(pattern)) for
> > each pattern in the list, and 'n' is len(patterns).
> >
>
> ok, so if we can assume that k is some relatively small constant
> number (since the maximum pattern length isn't likely to grow without
> bounds), this is O(n*log(n)) on the number of patterns, so we don't
> even approach n^2 even when we are given a large number of patterns.
> Nice!
>
> > By discovering this set of interesting patterns, we reduce the runtime
> > of multi-pattern 'git for-each-ref' (and other ref traversals) from
> > O(N) to O(n log(N)), where 'N' is the total number of packed references.
>
> So here, n is the number of patterns still? This seems like a pretty
> significant gane when we have a large number of packed references.

> >
> > Running 'git for-each-ref refs/tags/a refs/tags/b' on a repository with
> > 10,000,000 refs in 'refs/tags/huge-N', my best-of-five times drop from:
> >
> >   real    0m5.805s
> >   user    0m5.188s
> >   sys     0m0.468s
> >
> > to:
> >
> >   real    0m0.001s
> >   user    0m0.000s
> >   sys     0m0.000s
> >
>
> That's a pretty significant decrease!

> > On linux.git, the times to dig out two of the latest -rc tags drops from
> > 0.002s to 0.001s, so the change on repositories with fewer tags is much
> > less noticeable.
> >
>
> This explains why it might not have been done before.. many
> repositories wouldn't benefit much.
>
> That said, the patch description doesn't make it seem very
> complicated. I did run out of time reading the message, so I'll have
> to follow up reviewing the actual change below later. I think the
> description of the goal and solution is sound though.