Commits on Jun 27, 2019

1. ref-filter.c: find disjoint pattern prefixes …

   Since cfe004a (ref-filter: limit traversal to prefix, 2017-05-22),
   the ref-filter code has sought to limit the traversals to a prefix of
   the given patterns.
   
   That code stopped short of handling more than one pattern, because it
   means invoking 'for_each_ref_in' multiple times. If we're not careful
   about which patterns overlap, we will output the same refs multiple
   times.
   
   For instance, consider the set of patterns 'refs/heads/a/*',
   'refs/heads/a/b/c', and 'refs/tags/v1.0.0'. If we naïvely ran:
   
     for_each_ref_in("refs/heads/a/*", ...);
     for_each_ref_in("refs/heads/a/b/c", ...);
     for_each_ref_in("refs/tags/v1.0.0", ...);
   
   we would see 'refs/heads/a/b/c' (and everything underneath it) twice.
   
   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'}
   
   Given one of these disjoint sets, what is a suitable pattern to pass to
   'for_each_ref_in'? One approach is to compute the longest common prefix
   over all elements in that disjoint set, and let the caller cull out the
   refs they didn't want. Computing the longest prefix means that in most
   cases, we won't match too many things the caller would like to ignore.
   
   The longest common prefixes of the above are:
   
     - {'refs/heads/a/*', 'refs/heads/a/b/c'} -> refs/heads/a/*
     - {'refs/tags/v1.0.0'}                   -> refs/tags/v1.0.0
   
   We instead invoke:
   
     for_each_ref_in("refs/heads/a/*", ...);
     for_each_ref_in("refs/tags/v1.0.0", ...);
   
   Which provides us with the refs we were looking for with a minimal
   amount of extra cruft, but never a duplicate of the ref we asked for.
   
   Implemented here is an algorithm which accomplishes the above, which
   works as follows:
   
     1. Lexicographically sort the given list of patterns.
   
     2. Initialize 'prefix' to the empty string, where our goal is to
        build each element in the above set of longest common prefixes.
   
     3. Consider each pattern in the given set, and emit 'prefix' if it
        reaches the end of a pattern, or touches a wildcard character. The
        end of a string is treated as if it precedes a wildcard. (Note that
        there is some room for future work to detect that, e.g., 'a?b' and
        'abc' are disjoint).
   
     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).
   
   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.
   
   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
   
   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.
   
   Co-authored-by: Jeff King <peff@peff.net>
   Signed-off-by: Jeff King <peff@peff.net>
   Signed-off-by: Taylor Blau <me@ttaylorr.com>
   Signed-off-by: Junio C Hamano <gitster@pobox.com>

   

   2 people authored and gitster committed Jun 27, 2019
   Configuration menu

   • View commit details
   • Copy full SHA for b31e268
   • Browse repository at this point

   Copy the full SHA

   b31e268 View commit details

   Browse the repository at this point in the history