Re: [PATCH v5 0/4] bloom: enable bloom filter optimization for multiple pathspec elements in revision traversal

> The difference from v4 is:
>   - for the bloom_key_* functions, we now pass struct bloom_key *
>     as the first parameter.
>   - bloom_keyvec_fill_key() and bloom_keyvec_new() have been merged
>     into a single function, so that each key is filled during the
>     creation of the bloom_keyvec.
> 
> Below is a comparison of the time taken to run git log on Git and
> LLVM repositories before and after applying this patch.
> 
> 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
> 
> Run git log on Git repository
>   $ cd ~/src/git
>   $ hash -p /usr/bin/git git # my system git binary is 2.43.0
>   $ time git log -100 -- commit.c commit-graph.c >/dev/null
>   real	0m0.055s
>   user	0m0.040s
>   sys	  0m0.015s
>   $ hash -p ~/bin/git/bin/git git
>   $ time git log -100 -- commit.c commit-graph.c >/dev/null
>   real	0m0.039s
>   user	0m0.020s
>   sys	  0m0.020s
> 
> Run git log in LLVM repository
>   $ cd ~/src/llvm
>   $ hash -p /usr/bin/git git # my system git binary is 2.43.0
>   $ time git log -100 -- llvm/lib/Support/CommandLine.cpp llvm/lib/Support/CommandLine.h >/dev/null
>   real	0m2.365s
>   user	0m2.252s
>   sys	  0m0.113s
>   $ hash -p ~/bin/git/bin/git git
>   $ time git log -100 -- llvm/lib/Support/CommandLine.cpp llvm/lib/Support/CommandLine.h >/dev/null
>   real	0m0.240s
>   user	0m0.158s
>   sys	  0m0.064s

>     -+struct bloom_keyvec *bloom_keyvec_new(size_t count)
>     ++struct bloom_keyvec *bloom_keyvec_new(const char *path, size_t len,
>     ++				      const struct bloom_filter_settings *settings)
>      +{
>      +	struct bloom_keyvec *vec;
>     -+	size_t sz = sizeof(struct bloom_keyvec);
>     -+	sz += count * sizeof(struct bloom_key);
>     ++	const char *p;
>     ++	size_t sz;
>     ++	size_t nr = 1;
>     ++
>     ++	p = path;
>     ++	while (*p) {
>     ++		/*
>     ++		 * At this point, the path is normalized to use Unix-style
>     ++		 * path separators. This is required due to how the
>     ++		 * changed-path Bloom filters store the paths.
>     ++		 */
>     ++		if (*p == '/')
>     ++			nr++;
>     ++		p++;
>     ++	}
>     ++
>     ++	sz = sizeof(struct bloom_keyvec);
>     ++	sz += nr * sizeof(struct bloom_key);
>      +	vec = (struct bloom_keyvec *)xcalloc(1, sz);
>     -+	vec->count = count;
>     ++	if (!vec)
>     ++		return NULL;
>     ++	vec->count = nr;
>     ++
>     ++	bloom_key_fill(&vec->key[0], path, len, settings);
>     ++	nr = 1;
>     ++	p = path + len - 1;
>     ++	while (p > path) {
>     ++		if (*p == '/') {
>     ++			bloom_key_fill(&vec->key[nr++], path, p - path, settings);
>     ++		}
>     ++		p--;
>     ++	}
>     ++	assert(nr == vec->count);
>      +	return vec;
>      +}