[PATCH v6 0/5] bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal

[Lidong Yan <yldhome2d2@gmail.com>]

The revision traversal limited by pathspec has optimization when
the pathspec has only one element, it does not use any pathspec
magic (other than literal), and there is no wildcard. The absence
of optimization for multiple pathspec elements in revision traversal
cause an issue raised by Kai Koponen at
  https://lore.kernel.org/git/CADYQcGqaMC=4jgbmnF9Q11oC11jfrqyvH8EuiRRHytpMXd4wYA@mail.gmail.com/

While it is much harder to lift the latter two limitations,
supporting a pathspec with multiple elements is relatively easy.
Just make sure we hash each of them separately and ask the bloom
filter about them, and if we see none of them can possibly be
affected by the commit, we can skip without tree comparison.

The difference from v5 is:
  - extract convert pathspec item to bloom_keyvec logic to
    a separate function, which simplifies the prepare_to_use_bloom_filter()
    function.
  - fix few bugs in v5.

Below is a comparison of the time taken to run git log on Git and
LLVM repositories before and after applying this patch. These statistics
are given by Derrick Stolee at
  https://lore.kernel.org/git/afb68948-218b-4b56-9faa-29578ef9c73c@gmail.com/

Setup commit-graph:
  $ cd ~/src/git && git commit-graph write --split --reachable --changed-paths
  $ cd ~/src/llvm && git commit-graph write --split --reachable --changed-paths

Running hyperfine [1] on Git repository:

  $ hyperfine --warmup=3 \
  > -n 'old' '~/_git/git-sparse-checkout-clean/git log -100 -- commit.c commit-graph.c' \
  > -n 'new' '~/_git/git/git log -100 -- commit.c commit-graph.c'

Benchmark 1: old
  Time (mean ± σ):      73.1 ms ±   2.9 ms    [User: 48.8 ms, System: 23.9 ms]
  Range (min … max):    69.9 ms …  84.5 ms    42 runs

Benchmark 2: new
  Time (mean ± σ):      55.1 ms ±   2.9 ms    [User: 30.5 ms, System: 24.4 ms]
  Range (min … max):    51.1 ms …  61.2 ms    52 runs

Summary
  'new' ran
    1.33 ± 0.09 times faster than 'old'

And for LLVM:

  $ hyperfine --warmup=3 \
  > -n 'old' '~/_git/git-sparse-checkout-clean/git log -100 -- llvm/lib/Support/CommandLine.cpp llvm/lib/Support/CommandLine.h' \
  > -n 'new' '~/_git/git/git log -100 -- llvm/lib/Support/CommandLine.cpp llvm/lib/Support/CommandLine.h'

Benchmark 1: old
  Time (mean ± σ):      1.974 s ±  0.006 s    [User: 1.877 s, System: 0.097 s]
  Range (min … max):    1.960 s …  1.983 s    10 runs

Benchmark 2: new
  Time (mean ± σ):     262.9 ms ±   2.4 ms    [User: 214.2 ms, System: 48.4 ms]
  Range (min … max):   257.7 ms … 266.2 ms    11 runs

Summary
  'new' ran
    7.51 ± 0.07 times faster than 'old'

[1] https://github.com/sharkdp/hyperfine

Lidong Yan (5):
  bloom: add test helper to return murmur3 hash
  bloom: rename function operates on bloom_key
  bloom: replace struct bloom_key * with struct bloom_keyvec
  revision: make helper for pathspec to bloom keyvec
  To enable optimize multiple pathspec items in revision traversal,
    return 0 if all pathspec item is literal in forbid_bloom_filters().
    Add for loops to initialize and check each pathspec item's
    bloom_keyvec when optimization is possible.

 blame.c               |   2 +-
 bloom.c               |  84 ++++++++++++++++++++++++++---
 bloom.h               |  54 ++++++++++++++-----
 line-log.c            |   5 +-
 revision.c            | 122 +++++++++++++++++++++---------------------
 revision.h            |   6 +--
 t/helper/test-bloom.c |   8 +--
 t/t4216-log-bloom.sh  |  23 ++++----
 8 files changed, 204 insertions(+), 100 deletions(-)

Range-diff against v5:
1:  4d8f60e5ff = 1:  f5ab19063d bloom: add test helper to return murmur3 hash
2:  acee03e397 = 2:  51a180daa6 bloom: rename function operates on bloom_key
3:  d7690bd02c ! 3:  e17249ab4b bloom: replace struct bloom_key * with struct bloom_keyvec
    @@ bloom.h: void bloom_key_fill(struct bloom_key *key, const char *data, size_t len
      void bloom_key_clear(struct bloom_key *key);
      
     +/*
    -+ * bloom_keyvec_fill - Allocate and populate a bloom_keyvec with keys for the
    ++ * bloom_keyvec_new - Allocate and populate a bloom_keyvec with keys for the
     + * given path.
     + *
     + * This function splits the input path by '/' and generates a bloom key for each
    @@ revision.c: static int forbid_bloom_filters(struct pathspec *spec)
      static void prepare_to_use_bloom_filter(struct rev_info *revs)
      {
      	struct pathspec_item *pi;
    -+	struct bloom_keyvec *bloom_keyvec;
      	char *path_alloc = NULL;
    - 	const char *path, *p;
    +-	const char *path, *p;
    ++	const char *path;
      	size_t len;
     -	int path_component_nr = 1;
      
-:  ---------- > 4:  b3c1f5bcd1 revision: make helper for pathspec to bloom keyvec
4:  e577aa1bfd ! 5:  785bd43674 bloom: optimize multiple pathspec items in revision traversal
    @@ Metadata
     Author: Lidong Yan <yldhome2d2@gmail.com>
     
      ## Commit message ##
    -    bloom: optimize multiple pathspec items in revision traversal
    -
         To enable optimize multiple pathspec items in revision traversal,
         return 0 if all pathspec item is literal in forbid_bloom_filters().
         Add for loops to initialize and check each pathspec item's bloom_keyvec
         when optimization is possible.
     
         Add new test cases in t/t4216-log-bloom.sh to ensure
    -      - consistent results between the optimization for multiple pathspec
    -        items using bloom filter and the case without bloom filter
    -        optimization.
    -      - does not use bloom filter if any pathspec item is not literal.
    +     - consistent results between the optimization for multiple pathspec
    +       items using bloom filter and the case without bloom filter
    +       optimization.
    +     - does not use bloom filter if any pathspec item is not literal.
    +
    +    With these optimizations, we get some improvements for multi-pathspec runs
    +    of 'git log'. First, in the Git repository we see these modest results:
    +
    +    Benchmark 1: old
    +     Time (mean ± σ):      73.1 ms ±   2.9 ms
    +     Range (min … max):    69.9 ms …  84.5 ms    42 runs
    +
    +    Benchmark 2: new
    +     Time (mean ± σ):      55.1 ms ±   2.9 ms
    +     Range (min … max):    51.1 ms …  61.2 ms    52 runs
    +
    +    Summary
    +     'new' ran
    +       1.33 ± 0.09 times faster than 'old'
    +
    +    But in a larger repo, such as the LLVM project repo below, we get even
    +    better results:
    +
    +    Benchmark 1: old
    +     Time (mean ± σ):      1.974 s ±  0.006 s
    +     Range (min … max):    1.960 s …  1.983 s    10 runs
    +
    +    Benchmark 2: new
    +     Time (mean ± σ):     262.9 ms ±   2.4 ms
    +     Range (min … max):   257.7 ms … 266.2 ms    11 runs
    +
    +    Summary
    +     'new' ran
    +       7.51 ± 0.07 times faster than 'old'
     
         Signed-off-by: Lidong Yan <502024330056@smail.nju.edu.cn>
    +    Signed-off-by: Derrick Stolee <stolee@gmail.com>
     
      ## revision.c ##
     @@ revision.c: static int forbid_bloom_filters(struct pathspec *spec)
    @@ revision.c: static void prepare_to_use_bloom_filter(struct rev_info *revs)
      
     -	revs->bloom_keyvecs_nr = 1;
     -	CALLOC_ARRAY(revs->bloom_keyvecs, 1);
    --	pi = &revs->pruning.pathspec.items[0];
     +	revs->bloom_keyvecs_nr = revs->pruning.pathspec.nr;
     +	CALLOC_ARRAY(revs->bloom_keyvecs, revs->bloom_keyvecs_nr);
    -+	for (int i = 0; i < revs->pruning.pathspec.nr; i++) {
    -+		pi = &revs->pruning.pathspec.items[i];
      
    --	/* remove single trailing slash from path, if needed */
    --	if (pi->len > 0 && pi->match[pi->len - 1] == '/') {
    --		path_alloc = xmemdupz(pi->match, pi->len - 1);
    --		path = path_alloc;
    --	} else
    --		path = pi->match;
    -+		/* remove single trailing slash from path, if needed */
    -+		if (pi->len > 0 && pi->match[pi->len - 1] == '/') {
    -+			path_alloc = xmemdupz(pi->match, pi->len - 1);
    -+			path = path_alloc;
    -+		} else
    -+			path = pi->match;
    - 
    --	len = strlen(path);
    --	if (!len)
    +-	if (convert_pathspec_to_bloom_keyvec(&revs->bloom_keyvecs[0],
    +-					     &revs->pruning.pathspec.items[0],
    +-					     revs->bloom_filter_settings))
     -		goto fail;
    -+		len = strlen(path);
    -+		if (!len)
    ++	for (int i = 0; i < revs->pruning.pathspec.nr; i++) {
    ++		if (convert_pathspec_to_bloom_keyvec(&revs->bloom_keyvecs[i],
    ++						     &revs->pruning.pathspec.items[i],
    ++						     revs->bloom_filter_settings))
     +			goto fail;
    - 
    --	revs->bloom_keyvecs[0] =
    --		bloom_keyvec_new(path, len, revs->bloom_filter_settings);
    -+		revs->bloom_keyvecs[i] =
    -+			bloom_keyvec_new(path, len, revs->bloom_filter_settings);
    -+		FREE_AND_NULL(path_alloc);
     +	}
      
      	if (trace2_is_enabled() && !bloom_filter_atexit_registered) {
-- 
2.39.5 (Apple Git-154)