Changed Paths Bloom Filters

Documentation/git-commit-graph.txt

It is nice to have option documented.

All right, the 'write' subcommand has the following synopsis:

'git commit-graph write' <options> [--object-dir <dir>] [--[no-]progress]

so the is no need to adjust it when adding a new option.

Documentation/git-commit-graph.txt or `--stdin-packs`.) · line 60

       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This might be not entirely clear for someone that is not familiar with Git jargon. Perhaps it would better read as "for getting history of a directory or a file with git log <path>", or something like that.

Side note: the sentence is missing its finishing full stop.

builtin/commit-graph.c static const char * const builtin_commit_graph_verify_usage[] = { · line 24

I was at first wondering why the duplication (not caused by your patch, though), and then realized that it is to have usage for command, and for individual subcommands, separately.

builtin/commit-graph.c static struct opts_commit_graph { · line 35

Why the field is called enable_bloom_filters, while option is called --changed-paths? I know it is not user-visible thing, so it would be easy to change if we ever go beyond Bloom filters, though...

So I am not against keeping it as it is currently.

builtin/commit-graph.c static int graph_write(int argc, const char **argv) · line 150

Minor nitpick: are we all right having this ordering of options (not for example having opt.progress last)?

Disregarding this, it looks all right.

commit-graph.h enum commit_graph_write_flags { · line 80

I wonder if we should add comment describing the flag, like for the one above...

commit-graph.h enum commit_graph_write_flags { · line 83

Best,

Jakub Narębski

Makefile LIB_OBJS += base85.o · line 844

I'll put bloom.h first, to make it easier to review.

bloom.h line 5

This would probably be missing if this patch was split in two:
introducing Bloom filter and saving Bloom filter in the repository metadata (in commit-graphh file).

bloom.h line 6

O.K., the names of fields are descriptive enough so that this struct doesn't need detailed description in comment (like the next one).

bloom.h line 8

Do we need full half-word for hash version?

bloom.h line 9

Do we need full 32-bits for number of hashes? The "Bloom Filters in Probabilistic Verification" paper mentioned in Stolee blog states that no one should need number of hashes greater than k=32 - the accuracy is so high that it doesn't matter that it is not optimal.

"Notice one last thing about Bloom filters in verification, if $m$ is
several gigabytes or less and $m/n$ calls for more than about 32 index functions, the accuracy is going to be so high that there is not much reason to use more than 32—for the next several years at least. In response to this, 3SPIN currently limits the user to $k = 32$. The point of this observation is that we do not have to worry about the runtime cost of $k$ being on the order of 64 or 100, because those choices do not really buy us anything over 32."

Here 'm' is the number of bits in Bloom filter, and m/n is number of bits per element added to filter.

bloom.h line 10

All right, we wouldn't really want large Bloom filters, as we use one filter per commit to match againts one key, not single Bloom filter to match againts many keys.

bloom.h line 24

O.K., so it is single variable-sized (in 64-bit increments) Bloom filter bit vector (bitmap).

bloom.h line 34

That is smart. I wonder however if it wouldn't be a good idea to 'typedef' a hash function return type.

I repeat myself: in Git case we have one key that we try to match against many Bloom filters which are never updated, while in an ordinary case many keys are matched against single Bloom filter - in many cases updated (with keys inserted to Bloom filter).

I wonder if somebody from academia have examined such situation. I couldn't find a good search query.

Sidenote: perhaps Xor or Xor+ filters from Graf & Lemire (2019)
https://arxiv.org/abs/1912.08258 would be better solution - they also assume unchanging filter. Though they are a very fresh proposal; also construction time might be important for Git.
https://github.com/FastFilter/xor_singleheader

bloom.h line 39

Those two functions really need API documentation on how they are used, if they are to be used in any other role, especially what is their calling convention? Why load_bloom_filters() doesn't take any parameters?

Anyway, if this patch would be split into pure Bloom filter implementation and Git use^W store of Bloom filters, then this would be left for the latter patch.

bloom.h line 44

It is a bit strange that two basic Bloom filter operations, namely adding element to Bloom filter (and constructing Bloom filter), and testing whether element is in Bloom filter are not part of a public API...

This function should probably be documented, in particular the fact that *key is an in/out parameter. This could also be a good place to document the mechanism itself (i.e. our implementation of Bloom filter, with references), though it might be better to keep the details of how it works in the bloom.c - close to the actual source (while keeping description of API in bloom.h comments).

bloom.c line 14

All right, so the Bloom filter data would be on slab. This should probably be mentioned in the commit message, like in
https://lore.kernel.org/git/[email protected]/

Sidenote: If I remember correctly one of the unmet prerequisites for switching to generation numbers v2 (corrected commit date with monotonic offsets) was moving 'generation' field out of 'struct commit' and on to slab (possibly also 'graph_pos'), and certainly having 'corrected_date' on slab (Inside-Out Object style). Which probably could be done with Coccinelle script...

bloom.c line 19

Hmmm... I wonder why use hashmap and not string_list. This is for adding path with leading directories to the Bloom filter, isn't it?

bloom.c line 26

Does it actually work with count being negative? Shouldn't 'count' be of unsigned type, and if int32_t is needed, perhaps add an assertion (if needed)? I think it does not.

It looks like it is John Regehr [2] safe and compiler-friendly implementation, with explicit 8 in place of CHAR_BIT from <limits.h>, which should compile to "rotate" assembly instruction... it looks like it is the case, see https://godbolt.org/z/5JP1Jb (at least for C++ compiler).

[2]: https://en.wikipedia.org/wiki/Circular_shift

I wonder if this should, in the future, be a part of 'compat/', maybe even using compiler intrinsics for "rotate right" if available (see
https://stackoverflow.com/a/776523/46058). But that might be outside of the scope of this patch (perhaps outside of choosing function name).

bloom.c line 27

It would be nice to have reference to the source of algorithm, or to the code that was borrowed for this in the header comment for the following function.

I will be comparing the algorithm itself in Wikipedia
https://en.wikipedia.org/wiki/MurmurHash#Algorithm
and its implementation in C in qLibc library (BSD licensed)
https://github.com/wolkykim/qlibc/blob/03a8ce035391adf88d6d755f9a26967c16a1a567/src/utilities/qhash.c#L258

bloom.c line 33

Those two: r1 and r1, probably should be both uint32_t type.

bloom.c line 38

*tail should probably be 'uint8_t', not 'char', isn't it?

bloom.c line 40

All length variables and parameters, i.e. len, len4, i, could possibly be size_t and not int type.

bloom.c line 43

Some implementations copy seed (or assume seed=0) to the local variable named h or hash.

bloom.c line 49

Shouldn't it be *rotate_left* (ROL), not rotate_right (ROR)??? This affects all cases / uses.

bloom.c line 57

We could have reused variable k, like the implementation in qLibc does, instead of introducing new k1 variable, but this way it is more clean. Or name it remainingBytes instead of k1

bloom.c line 84

It would be nice to have header comment describing what this function is intended to actually do.

bloom.c line 88

Sidenote: I wonder if ewah/bitmap.c implements something similar. Certainly possible consolidation, if any possible exists, should be left for the future.

bloom.c line 97

Where did those constants came from? It would be nice to have a reference either in header comment (in bloom.h or bloom.c), or in a commit message, or both.

Note that above *constants* are each used only once.

bloom.c line 100

Those are constant values, so perhaps they should be const uint32_t.

bloom.c line 104

It looks like this code implements the double hashing technique given in Eq. (4) in http://www.ccs.neu.edu/home/pete/pub/bloom-filters-verification.pdf
that is "Bloom Filters in Probabilistic Verification".

Note that Dillinger and Manolios in this paper propose also _enhanced_ double hashing algorithm (Algorithm 2 on page 11), which has closed form given by Eq. (6) - with better science-theoretical properties at similar cost.

It might be a good idea to explicitly state in the header comment that all arithmetic is performed with unsigned 32-bit integers, which means that operations are performed modulo 2^32. Or it might not be needed.

bloom.c line 116

All right. Because Bloom filters for different commits (and the same key) may have different lengths, we can perform modulo operation only here. hash_mod is i-th hash modulo size of filter, and block_pos is the block the '1' bit would go into.

bloom.c line 118

I'm not quite convinced that get_bitmask() is a good name: this function returns bitmap with hash_mod's bit set to 1. On the other hand it doesn't matter, because it is static (file-local) helper function.

Never mind then.

bloom.c line 125

Why *load* if all it does is initialize?

bloom.c line 128

I will not comment on this function; see Jeff King reply and Derrick Stolee reply.

commit-graph.c struct write_commit_graph_context { · line 799

Very minor nitpick: why bloom and not bloom_filter?

commit-graph.c struct write_commit_graph_context { · line 802

All right, I guess size of all Bloom filters would fit in uint32_t, no need for size_t, is it?

Shouldn't it be total_bloom_filters_size -- it is not a single Bloom filter, but many (minor nitpick)?

commit-graph.c static void compute_generation_numbers(struct write_commit_graph_context *ctx) · line 1160

Wouldn't it be more future proof instead of using sizeof(uint64_t) to use sizeof(filter->data[0]) here? This may be not worth it, and be less readable (we have hard-coded use of 64-bits blocks in other places).

commit-graph.c int write_commit_graph(const char *obj_dir, · line 1819

All right, this flag was defined in [PATCH 1/9].

The ordering of setting ctx members looks a bit strange. Now it is neither check flags firsts, neither keep related stuff together (see ctx->split vs ctx->split_opts). This is a very minor nitpick.

commit-graph.c int write_commit_graph(const char *obj_dir, · line 1920

Regards,

Jakub Narębski

commit-graph.c line 27

Minor nit: MAX_NUM_CHUNKS or MAX_CHUNKS?

commit-graph.c static int write_commit_graph_file(struct write_commit_graph_context *ctx) · line 1386

Looks good. I guess we won't ever have more chunks than 5:
OIDF, OIDL, CDAT, EDGE, BASE (and they cannot repeat, and last two are optional).

commit-graph.c static int write_commit_graph_file(struct write_commit_graph_context *ctx) · line 1389

Good.

Looks good to me.

Jakub Narębski

Documentation/technical/commit-graph-format.txt metadata, including: · line 21

s/bloom/Bloom/ and s/it's/its/

I am not sure about exact wording, but I could at this time think of a better but concise way of stating it.

Documentation/technical/commit-graph-format.txt CHUNK DATA: · line 103

I think it would be better for consistency and ease of reading to follow the example of OID Fanout (OIDF) chunk description:

+ Bloom Filter Index (ID: {'B', 'I', 'D', 'X'}) (N * 4 bytes) [Optional]

 +      The ith entry, BIDX[i], stores the number of 8-byte word blocks
 +      in all Bloom filters from commit 0 up to commit i (inclusive)
 +      in lexicographical order.

Maybe even add the following to make implementing it easier:

+ Data for Bloom filter for i-th commit spans from BIDX[i-1] to
+ BIDX[i] (plus header length), where we take BIDX[-1] to be 0.

Is it possible for (BIDX[i] - BIDX[i-1]) to be zero (no Bloom filter), for example for commits with more than 512 changes? Or is this case handled by 1 8-byte word Bloom filter of all bits sets to '1', i.e. 0xffffffffffffffff?

How the case of too many changes is distingushed from the case of no changes (git commit --allow-empty, or git merge --ours)? Is the case of no changes uninteresting, i.e. Bloom filter consisting of zero, that is with all bits set to '0'?

Documentation/technical/commit-graph-format.txt CHUNK DATA: · line 106

I would say "It starts with the header consisting of three unsigned 32-bit integers:" (but current version is not bad).

I wonder if this metadata should perhaps be put in a separate chunk, BMET... (Bloom filter METadata).

Documentation/technical/commit-graph-format.txt CHUNK DATA: · line 107

This number not only encodes that the base hash algorithm being used is 32-bit Murmur3 hash, but that 'k' hashes used in the computation are created out of Murmur3 hash using double hashing technique, and specifies two specific seed values for this double hashing technique.

[Maybe we should store those two seed values here too?]

It might be important to say that the currently supported version is '1', and if Git encounters unknown hashing algorithm version it should not use Bloom filter data.

Unless we store encoded _name_ of the hash algorithm, e.g. bytes 'm','u','r','3' for MurmurHash3_32... though it is about more than a base hash.

Do we need whole 4 bytes for hash version, or is it for ease of use and alignment?

Documentation/technical/commit-graph-format.txt CHUNK DATA: · line 108

All right. Perhaps we should test in the future patches that the value different from the default of 7 would also work.

Also 8-bits / 1 byte for number of hashes (hash functions) should be
enough: as I have written in prevous reply there is no need for k > 32.

Documentation/technical/commit-graph-format.txt CHUNK DATA: · line 109

This is important for construction of Bloom filter, but I think it is not necessary to use it -- so it may not be necessary to store it.

Would also fit in a single byte: we don't need exceedingly low false positive probability.

We could use it to estimate the false positive probability, and...

Documentation/technical/commit-graph-format.txt CHUNK DATA: · line 111

+ * The rest of the chunk is the concatenation of all the computed Bloom
+ filters for the commits in lexicographic order.

It would be, I think, a good idea to make it explicit that BDAT is present iff BIDX is present (iff == if and only if), i.e. that either both or neither of those chunks should be present.

Documentation/technical/commit-graph-format.txt CHUNK DATA: · line 115

Best,

Jakub Narębski

commit-graph.c line 29

Very minor nitpick: shouldn't we follow the order in the commit-graph-format.txt document (i.e. "BASE" as last chunk and last preprocessor constant)?

commit-graph.c struct commit_graph *parse_commit_graph(void *graph_map, int fd, · line 294

All right.

commit-graph.c struct commit_graph *parse_commit_graph(void *graph_map, int fd, · line 302

All right, now I see why all those header values for BDAT chunk are defined to be 32-bit integers. For code simplicity.

commit-graph.c struct commit_graph *parse_commit_graph(void *graph_map, int fd, · line 305

What does it mean for Git? Behave as if there were no Bloom filter data?

commit-graph.c struct commit_graph *parse_commit_graph(void *graph_map, int fd, · line 310

All right, looks O.K.

commit-graph.c static void write_graph_chunk_extra_edges(struct hashfile *f, · line 1039

Why not follow the write_graph_chunk_oids() example, instead of write_graph_chunk_data(), that is use simply:

  +	struct commit **list = ctx->commits.list;
  +	uint32_t cur_pos = 0;
  +
  +	for (count = 0; count < ctx->commits.nr; count++, list++) {
  +		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
  +		cur_pos += filter->len;
  +		hashwrite_be32(f, cur_pos);
  +	}

I guess using here

  +		cur_pos += get_bloom_filter(ctx->r, *list)->len;

would be too cryptic, and hard to debug?

Also, wouldn't we need

  +		display_progress(ctx->progress, ++ctx->progress_cnt);

before hashwrite_be32()?

commit-graph.c static void write_graph_chunk_extra_edges(struct hashfile *f, · line 1046

Even if we decide to use while loop, like write_graph_chunk_data(), and not for loop, like write_graph_chunk_oids(), why the change from struct commit **list = ... to struct commit **first = ...?

commit-graph.c static void write_graph_chunk_extra_edges(struct hashfile *f, · line 1051

All right, simple.

commit-graph.c static void write_graph_chunk_extra_edges(struct hashfile *f, · line 1054

Hmmm... wouldn't this compute Bloom filter second time? get_bloom_filter() does work unconditionally.

Wouldn't

  +		struct bloom_filter *filter = bloom_filter_slab_at(&bloom_filters, *first);

be enough?

Or make get_bloom_filter() use *_peek() to check if Bloom filter for given commit was already computed, and only if it returns NULL do the work.

commit-graph.c static void write_graph_chunk_extra_edges(struct hashfile *f, · line 1055

Might need display_progress() before hashwrote().

commit-graph.c static int write_commit_graph_file(struct write_commit_graph_context *ctx) · line 1502

Looks all right.

commit-graph.c static int write_commit_graph_file(struct write_commit_graph_context *ctx) · line 1527

Better wrap those long lines, like above:

  +	if (ctx->bloom) {
  +		chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] +
  +						sizeof(uint32_t) * ctx->commits.nr;
  +		num_chunks++;
  +
  +		chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] +
  +						sizeof(uint32_t) * 3 + ctx->total_bloom_filter_size;
  +		num_chunks++;
  +	}

commit-graph.c static int write_commit_graph_file(struct write_commit_graph_context *ctx) · line 1568

All right.

commit-graph.h struct commit_graph { · line 65

Should this be part of struct commit_graph? Shouldn't we free() this data, or is it a pointer into xmmap-ped file... no it isn't -- we xalloc() it, so we should free() it.

I think it should be done in 'cleanup:' section of write_commit_graph(), but I am not entirely sure.

commit-graph.h struct commit_graph { · line 68

Best,

Jakub Narębski

t/helper/test-read-graph.c int cmd__read_graph(int argc, const char **argv) · line 51

All right, though it is very basic information.

t/t5325-commit-graph-bloom.sh line 15

Style: space between function name and parentheses, i.e.

  +graph_read_expect () {

t/t5325-commit-graph-bloom.sh line 16

Not used anywhere.

t/t5325-commit-graph-bloom.sh line 18

It might be good idea to add names to those parameters by setting some local variables to $1 and $2; or, alternatively add comment describing this function.

t/t5325-commit-graph-bloom.sh line 30

No comments below this point...

Best,

Jakub Narębski

bloom.c static void add_key_to_filter(struct bloom_key *key, · line 134

This part shares common code with load_oid_from_graph(), only without some of error checking; perhaps it might be good to extract it into a separate helper function, e.g. lex_index(&g, c->graph_pos).

Minor nitpick about the consistency of function names: why load_oid_from_graph(), but fill_filter_from_graph(), and not load_filter_from_graph() / load_bloom_from_graph()?

bloom.c static void add_key_to_filter(struct bloom_key *key, · line 136

I think using

+ if (lex_pos > 0)

or

+ if (lex_pos >= 0)

might be easier to reason about.

bloom.c static void add_key_to_filter(struct bloom_key *key, · line 141

The above command reads a bit strange: next - prev? not next - curr, or curr - prev? Wouldn't it be better to name it begin_index and end_index, or beg_index and end_index for brevity?

bloom.c static void add_key_to_filter(struct bloom_key *key, · line 142

Please do not use magic constants; use instead something like:

+ filter->data = (uint64_t *)(g->chunk_bloom_data +
+ sizeof(uint64_t) * prev_index +
+ BLOOMDATA_CHUNK_HEADER_SIZE);

Perhaps using 3*sizeof(unit32_t) instead of magic value 12 would be enough; but having symbolic name for BDAT chunk header size is better, I think.

bloom.c static void add_key_to_filter(struct bloom_key *key, · line 152

I'm not sure about compute_if_null name...

bloom.c struct bloom_filter *get_bloom_filter(struct repository *r, · line 160

Note that the documentation for slab_at(slab, commit) is documented in commit-slab.h as

 *   This function locates the data associated with the given commit in
 *   the indegree slab, and returns the pointer to it.  The location to
 *   store the data is allocated as necessary.
                       ~~~~~~~~~~~~~~~~~~~~~~

Should we worry about this possibly unnecessary allocation (if there is no Bloom filter chunk in the commit-graph, and we are not recomputing it)?

There is slab_peek(slab_commit) with the following properties:

* This function is similar to indegree_at(), but it will return NULL
* until a call to indegree_at() was made for the commit.

bloom.c struct bloom_filter *get_bloom_filter(struct repository *r, · line 162

What does the Bloom filter for a commit with no changes looks like? What about for a commit with more than 512 changes? Do, in either of those cases, filter->len is 0? If yes, what about filter->data?

bloom.c struct bloom_filter *get_bloom_filter(struct repository *r, · line 164

Please wrap overly long lines (109 characters seems too long; the CodingGuidelines states:

- We try to keep to at most 80 characters per line.

  +		if (c->graph_pos != COMMIT_NOT_FROM_GRAPH &&
  +		    r->objects->commit_graph->chunk_bloom_indexes) {

You seem to assume here that in the chain of commit-graph files either all of them would have Bloom filters, or all of them would be missing Bloom filters. Isn't it however possible for only some of the commit-graph files in chain to include Bloom filter data chunks?

In such case, the top commit-graph file may have BIDX chunk (bloom_indexes), but the commit-graph with the commit 'c' might not have it. Or the top commit-graph file may be missing BIDX chunk, so Git would recompute it even if the commit-graph file for commit 'c' includes it.

If such situation is forbidden, how the restriction is managed?

Note: in any case, this needs to be tested!

bloom.c struct bloom_filter *get_bloom_filter(struct repository *r, · line 168

All right, if it is not in slab, we try to read if from the commit graph. Looks all right.

bloom.c struct bloom_filter *get_bloom_filter(struct repository *r, · line 171

                ^^^^^^^^
                 |
                 \- one tab too many

If we have found existing filter (on slab or in the commit-graph), or if we won't be recomputing it, return it. O.K.

bloom.c struct bloom_filter *get_bloom_filter(struct repository *r, · line 237

Accidental change.

bloom.h struct bloom_key { · line 41

All right, this is just update of the function signature.

commit-graph.c static void write_graph_chunk_bloom_data(struct hashfile *f, · line 1057

O.K., so those two do not compute Bloom filters, but they are called from write_commit_graph_file(), which in turn is called in write_commit_graph() *after* running compute_bloom_filters().

Looks good to me, then.

commit-graph.c static void compute_bloom_filters(struct write_commit_graph_context *ctx) · line 1224

All right, so compute_bloom_filters() ensures that it is actually computed (if needed).

Looks good to me.

Regards,

Jakub Narębski

bloom.c struct bloom_filter *get_bloom_filter(struct repository *r, · line 247

Ah, so filter->len equal to zero denotes too many changes for a Bloom filter, and this conditional is a short-circuit test: always return "maybe".

I wonder if we should explicitly check for filter->len = 1 and filter->data[0] = 0, which should be empty Bloom filter -- for commit with no changes with respect to first parent, and short-circuit returning 0 (no file would ever belong).

bloom.c struct bloom_filter *get_bloom_filter(struct repository *r, · line 251

I have seen this code before... ;-) The add_key_to_filter() function includes almost identical code, but I am not sure if it is feasible to eliminate this (slight) code duplication. Probably not.

bloom.c struct bloom_filter *get_bloom_filter(struct repository *r, · line 253

All right, if at least one hash function does not match, return "no"...

bloom.c struct bloom_filter *get_bloom_filter(struct repository *r, · line 256

... else return "maybe".

bloom.c struct bloom_filter *get_bloom_filter(struct repository *r, · line 257

I am wondering however if this code should not be moved earlier in the series, so that commit 2/9 in series actually adds fully functional [semi-generic] Bloom filter implementation.

revision.c static void file_change(struct diff_options *options, · line 631

All right, this function name is certainly descriptive. I wonder if it wouldn't be better to use a shorter name, like maybe_different(), or maybe_not_treesame(), so that the conditional using this function would read naturally:

if (!maybe_different(revs, commit, revs->bloom_key,
revs->bloom_filter_settings))
return REV_TREE_SAME;

But this might be just a matter of taste.

revision.c static void file_change(struct diff_options *options, · line 638

O.K., so we check that there is loaded commit graph, and that given commit is in a commit graph, otherwise we return "no data".

I agree with distinguishing between "no data" value (which is <0, a convention for denoting errors), and "maybe" value. Currently this distinction is not utilized, but it would help in the case of more than one path given -- in "no data" case there is no need to check other paths against non-existing Bloom filter.

revision.c static void file_change(struct diff_options *options, · line 640

Why the check for non-NULL 'key' and 'settings' is the last check?

BTW. when it is possible for key or settings to be NULL? Or is it just defensive programming?

revision.c static void file_change(struct diff_options *options, · line 642

O.K., we won't be recomputing Bloom filter if it is not present either on slab (as "inside-out" auxiliary data for a commit), or in the commit-graph (in Bloom filter chunks).

revision.c static void file_change(struct diff_options *options, · line 645

Sidenote: bloom_filter_contains() would also indirectly check for filter->len being zero. Though this doesn't cost much.

Shouldn't !filter case return value of -1 i.e. "no data", rather than return value of 1 i.e. "maybe"?

revision.c static void file_change(struct diff_options *options, · line 648

All right.

revision.c static int rev_compare_tree(struct rev_info *revs, · line 680

All right, Bloom filter stores information about changed paths with respect to first-parent changes only, so if we are asking about is not a first parent (where nth_parent == 0), we cannot use Bloom filter.

Currently we limit the check to single pathspec only; that is a good start and a good simplification.

revision.c static int rev_compare_tree(struct rev_info *revs, · line 687

Pretty straightforward.

revision.c static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit) · line 892

All right, we need to pass information about the index of the parent; and we have just done that. Good.

revision.c static void expand_topo_walk(struct rev_info *revs, struct commit *commit) · line 3379

All right, I see that pointers to bloom_key and bloom_filter_settings were added to the rev_info struct. I understand why the former is here, but the latter seems to be there just as a shortcut (to not owned data), which is fine but a bit strange.

Or is the latter here to allow for Bloom filter settings to possibly change from commit-graph file in the chain to commit-graph file, and thus from commit to commit?

revision.c static void expand_topo_walk(struct rev_info *revs, struct commit *commit) · line 3381

Maybe 'pathspec' (or the like) instead of short and cryptic 'pi' would be better a better name... unless 'pi' is used in other places already.

revision.c static void expand_topo_walk(struct rev_info *revs, struct commit *commit) · line 3386

When revs->commits may be NULL? I understand that we need to have this check because we use revs->commits->item next (sidenote: can revs ever be NULL?).

Would git log --all -- <path> use Bloom filters (as it theoretically could)?

revision.c static void expand_topo_walk(struct rev_info *revs, struct commit *commit) · line 3388

Why parsing first commit on the list of starting commits is needed here? Please help me understand this line.

And shouldn't we use repo_parse_commit() here?

revision.c static void expand_topo_walk(struct rev_info *revs, struct commit *commit) · line 3395

All right, so if there is no commit graph, or the commit graph does not include Bloom filter data, there is nothing to do.

Though I worry that it would make Git do not use Bloom filter if the top commit-graph in the chain does not include Bloom filter data, while other commit-graph files do (and Git could have used that information to speed up the file history query).

revision.c static void expand_topo_walk(struct rev_info *revs, struct commit *commit) · line 3399

Why not the following, if we do not do any checks for 'pi' value:

  +	path = &revs->pruning.pathspec.items[0]->match;

A question: is the path in the match field in struct pathspec normalized with respect to trailing slash (for directories)? Bloom filter stores pathnames for directories without trailing slash.

What I mean is if, for example, both of those would use Bloom filter data:

  $ git log -- Documentation/
  $ git log -- Documentation

revision.c static void expand_topo_walk(struct rev_info *revs, struct commit *commit) · line 3403

All right, looks good.

Though... do we leak revs->bloom_key, as should we worry about it?

revision.c int prepare_revision_walk(struct rev_info *revs) · line 3456

Looks good.

Minor nitpick: 4 spaces instead of tab are used for indentation (or, to be more exact a tab followed by 4 space, instead of two tabs):

  +	if (revs->pruning.pathspec.nr == 1)
  +		prepare_to_use_bloom_filter(revs);

revision.h struct rev_info { · line 298

It might be a good idea to add one-line comment above those newly introduced fields. The struct rev_info has many subsections of fields described by such comments (or even block comments), like e.g.

/* Starting list */
/* Parents of shown commits */
/* The end-points specified by the end user */ /* excluding from --branches, --refs, etc. expansion */ /* Traversal flags */
/* diff info for patches and for paths limiting */

/*
* Whether the arguments parsed by setup_revisions() included any
* "input" revisions that might still have yielded an empty pending
* list (e.g., patterns like "--all" or "--glob").
*/

t/t4216-log-bloom.sh line 12

Why do you use test_oid_init, when you are *not* using test_oid? I guess it is because t5318-commit-graph.sh uses it, isn't it?

The graphdir shell variable is not used either.

t/t4216-log-bloom.sh line 25

Wouldn't it be better for this step to be a part of 'setup repo' step? Anyway, the test name says '... and repack', but git repack is missing (it should be done after last test_commit).

I think it would be good idea to test behavior of Bloom filters with respect to directories, so at least one file should be in a subdirectory (maybe even deeper in hierarchy).

We should also test the behavior with respect to merges, and when we are not following the first parent. But that might be a separate part of this test.

t/t4216-log-bloom.sh line 27

Doing things outside test is discouraged. We can create a separate test that creates those expect_file* files, or it can be a part of 'create commits' test.

Anyway, instead of doing test without Bloom filters (something that should have been tested already by other parts of testsuite), and then doing the same test with Bloom filter, why not compare that the result without and with Bloom filter is the same. The t5318-commit-graph.sh test does this with help of graph_git_two_modes() function:

  graph_git_two_modes () {
  	git -c core.commitGraph=true  $1 >output
  	git -c core.commitGraph=false $1 >expect
  	test_cmp expect output
  }

Sidenote: I wonder if it is high time to create t/lib-commit-graph.sh helper with, among others, this common function.

t/t4216-log-bloom.sh line 30

CodingGuidelines:57: Redirection operators should be written with space before, but no space after them. (Minor nitpick)

  +	git log --pretty="format:%s"  -- file1 >actual &&

t/t4216-log-bloom.sh line 34

+printf "c8\nc7\nc5\nc4\nc2\nc1" >expect_file1_file2

t/t4216-log-bloom.sh line 37

  +	git log --pretty="format:%s"  -- file1 file2 >actual &&

t/t4216-log-bloom.sh line 41

CodingGuidelines:144: We prefer a space between the function name and the parentheses, and no space inside the parentheses. (Minor nitpick)

  +graph_read_expect () {

t/t4216-log-bloom.sh line 47

This should be either

  +		NUM_CHUNKS=$((5 + $(echo "$2" | wc -w)))

or more future proof

  +		NUM_CHUNKS=$(($NUM_CHUNKS + $(echo "$2" | wc -w)))

We got away with this bug because we were not using octopus merges, and there were no optional core chunks, that is we never call graph_read_expect with second parameter in this test.

t/t4216-log-bloom.sh line 49

Why there is space between "<<-" and "EOF"?

t/t4216-log-bloom.sh line 62

All right, this is preparatory step for further tests.

t/t4216-log-bloom.sh line 72

With graph_git_two_modes() it would be much simpler:

  +test_expect_success 'single-path log' '
  +	git_graph_two_modes "git log --pretty=format:%s -- file1"
  +'

  +test_expect_success 'multi-path log' '
  +	git_graph_two_modes "git log --pretty=format:%s -- file1 file2"
  +'

What is missing is:
1. checking that Git is actually _using_ Bloom filters (which might be difficult to do)
2. testing that Bloom filters work also for history of subdirectories e.g. "git log -- subdir/" and "git log -- subdir"; this would of course require adjusting setup step
3. testing specific behaviors, like "git log --all -- file1"
4. merges with history following second parent
5. commits with no changes and/or merges with no first-parent changes
6. commit with more than 512 changed files (marked as slow test, and perhaps created with fast-import interface, like bulk commit creation in test_commit_bulk)

t/t4216-log-bloom.sh line 74

Best regards,

Jakub Narębski

builtin/commit-graph.c static int graph_write(int argc, const char **argv) · line 151

Very minor nitpick: not to make this line long, I would break it at the boolean operator, that is write

  -	if (opts.enable_bloom_filters)
  +	if (opts.enable_bloom_filters ||
  +	    git_env_bool(GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS, 0))  
   		flags |= COMMIT_GRAPH_WRITE_BLOOM_FILTERS;

I agree that this is a good place to put this check, by pretending that --changed-paths option was given on command line. Looks good.

ci/run-build-and-tests.sh linux-gcc) · line 25

All right, adding this to CI would certainly exercise this feature.

commit-graph.h line 12

All right (the ordering is a mater of taste).

t/README GIT_TEST_COMMIT_GRAPH=<boolean>, when true, forces the commit-graph to · line 383

Thanks for documenting this.

Missing full stop '.' at the end of the sentence. (Minor nit).

We might want to add ", as if '--changed-paths' option was given.", but it is not strictly necessary.

t/t4216-log-bloom.sh line 8

OK, neither of those setting increase the coverage for this test.

On the other hand they won't make tests fail (or at least they shouldn't, I think). The t5318-commit-graph.sh doesn't include GIT_TEST_COMMIT_GRAPH=0, after all.

t/t5318-commit-graph.sh line 7

All right, adding Bloom filters to commit-graph file would make test cases utilizing graph_read_expect() fail.

t/t5324-split-commit-graph.sh test_description='split commit graph' · line 7

All right, same here: adding Bloom filters to commit-graph would make test cases utilizing graph_read_expect() fail.

Sidenote: Here without GIT_TEST_COMMIT_GRAPH=0 tests that rely on precise timing of writing commit-graph to create split commit-graph would fail.

t/t5325-commit-graph-bloom.sh line 8

This test also includes some split commit-graph test cases, so the above is necessary.

All right.

t/t5325-commit-graph-bloom.sh line 11

Best,

Jakub Narębski