Re: [PATCH v2 18/24] pack-bitmap-write: build fewer intermediate bitmaps

[Jonathan Tan <jonathantanmy@google.com>]

I've reviewed the commit message already [1]; now let's look at the code.

[1] https://lore.kernel.org/git/20201124060738.762751-1-jonathantanmy@google.com/

>  struct bb_commit {
>  	struct commit_list *reverse_edges;
> +	struct bitmap *commit_mask;
>  	struct bitmap *bitmap;
> -	unsigned selected:1;
> +	unsigned selected:1,
> +		 maximal:1;

The code itself probably should contain comments about the algorithm,
but I'm not sure of the best way to do it. (E.g. I would say that
"maximal" should be "When iteration in bitmap_builder_init() reaches
this bb_commit, this is true iff none of its descendants has or will
ever have the exact same commit_mask" - but then when do we explain why
the commit_mask matters?)

>  	unsigned idx; /* within selected array */
>  };
>  
> @@ -198,7 +200,7 @@ static void bitmap_builder_init(struct bitmap_builder *bb,
>  {
>  	struct rev_info revs;
>  	struct commit *commit;
> -	unsigned int i;
> +	unsigned int i, num_maximal;
>  
>  	memset(bb, 0, sizeof(*bb));
>  	init_bb_data(&bb->data);
> @@ -210,27 +212,85 @@ static void bitmap_builder_init(struct bitmap_builder *bb,
>  	for (i = 0; i < writer->selected_nr; i++) {
>  		struct commit *c = writer->selected[i].commit;
>  		struct bb_commit *ent = bb_data_at(&bb->data, c);
> +
>  		ent->selected = 1;
> +		ent->maximal = 1;
>  		ent->idx = i;
> +
> +		ent->commit_mask = bitmap_new();
> +		bitmap_set(ent->commit_mask, i);
> +
>  		add_pending_object(&revs, &c->object, "");
>  	}
> +	num_maximal = writer->selected_nr;
>  
>  	if (prepare_revision_walk(&revs))
>  		die("revision walk setup failed");
>  
>  	while ((commit = get_revision(&revs))) {
>  		struct commit_list *p;
> +		struct bb_commit *c_ent;
>  
>  		parse_commit_or_die(commit);
>  
> -		ALLOC_GROW(bb->commits, bb->commits_nr + 1, bb->commits_alloc);
> -		bb->commits[bb->commits_nr++] = commit;
> +		c_ent = bb_data_at(&bb->data, commit);
> +
> +		if (c_ent->maximal) {
> +			if (!c_ent->selected) {
> +				bitmap_set(c_ent->commit_mask, num_maximal);
> +				num_maximal++;
> +			}
> +
> +			ALLOC_GROW(bb->commits, bb->commits_nr + 1, bb->commits_alloc);
> +			bb->commits[bb->commits_nr++] = commit;

So the order of bit assignments in the commit_mask and the order of
commits in bb->commits are not the same. In the commit_mask, bits are
first assigned for selected commits and then the rest for commits we
discover to be maximal. But in bb->commits, the order follows the
topologically-sorted iteration. This is fine, but might be worth a
comment (to add to the already big comment burden...)

> +		}
>  
>  		for (p = commit->parents; p; p = p->next) {
> -			struct bb_commit *ent = bb_data_at(&bb->data, p->item);
> -			commit_list_insert(commit, &ent->reverse_edges);
> +			struct bb_commit *p_ent = bb_data_at(&bb->data, p->item);
> +			int c_not_p, p_not_c;
> +
> +			if (!p_ent->commit_mask) {
> +				p_ent->commit_mask = bitmap_new();
> +				c_not_p = 1;
> +				p_not_c = 0;
> +			} else {
> +				c_not_p = bitmap_diff_nonzero(c_ent->commit_mask, p_ent->commit_mask);
> +				p_not_c = bitmap_diff_nonzero(p_ent->commit_mask, c_ent->commit_mask);
> +			}
> +
> +			if (!c_not_p)
> +				continue;
> +
> +			bitmap_or(p_ent->commit_mask, c_ent->commit_mask);
> +
> +			if (p_not_c)
> +				p_ent->maximal = 1;
> +			else {
> +				p_ent->maximal = 0;
> +				free_commit_list(p_ent->reverse_edges);
> +				p_ent->reverse_edges = NULL;
> +			}
> +
> +			if (c_ent->maximal) {
> +				commit_list_insert(commit, &p_ent->reverse_edges);
> +			} else {
> +				struct commit_list *cc = c_ent->reverse_edges;
> +
> +				for (; cc; cc = cc->next) {
> +					if (!commit_list_contains(cc->item, p_ent->reverse_edges))
> +						commit_list_insert(cc->item, &p_ent->reverse_edges);
> +				}
> +			}
>  		}
> +
> +		bitmap_free(c_ent->commit_mask);
> +		c_ent->commit_mask = NULL;
>  	}
> +
> +	trace2_data_intmax("pack-bitmap-write", the_repository,
> +			   "num_selected_commits", writer->selected_nr);
> +	trace2_data_intmax("pack-bitmap-write", the_repository,
> +			   "num_maximal_commits", num_maximal);
>  }

The rest looks like a faithful implementation of the algorithm.

Now let's look at the tests.

> +# To ensure the logic for "maximal commits" is exercised, make
> +# the repository a bit more complicated.
> +#
> +#    other                         master
> +#      *                             *
> +# (99 commits)                  (99 commits)
> +#      *                             *
> +#      |\                           /|
> +#      | * octo-other  octo-master * |
> +#      |/|\_________  ____________/|\|
> +#      | \          \/  __________/  |
> +#      |  | ________/\ /             |
> +#      *  |/          * merge-right  *
> +#      | _|__________/ \____________ |
> +#      |/ |                         \|
> +# (l1) *  * merge-left               * (r1)
> +#      | / \________________________ |
> +#      |/                           \|
> +# (l2) *                             * (r2)
> +#       \____________...____________ |

What does the ... represent? If a certain number of commits, it would be
clearer to write that there.

> +#                                   \|
> +#                                    * (base)

OK - some of the crosses are unclear, but from the bitmask given below,
I know where the lines should go.

> +#
> +# The important part for the maximal commit algorithm is how
> +# the bitmasks are extended. Assuming starting bit positions
> +# for master (bit 0) and other (bit 1), and some flexibility
> +# in the order that merge bases are visited, the bitmasks at
> +# the end should be:
> +#
> +#      master: 1       (maximal, selected)
> +#       other: 01      (maximal, selected)
> +# octo-master: 1
> +#  octo-other: 01
> +# merge-right: 111     (maximal)
> +#        (l1): 111
> +#        (r1): 111
> +#  merge-left: 1101    (maximal)
> +#        (l2): 11111   (maximal)
> +#        (r2): 111101  (maximal)
> +#      (base): 1111111 (maximal)

This makes sense. (l1) and (r1) are not maximal because everything that
can reach merge-right can also reach them.

[snip]

>  test_expect_success 'full repack creates bitmaps' '
> -	git repack -ad &&
> +	GIT_TRACE2_EVENT_NESTING=4 GIT_TRACE2_EVENT="$(pwd)/trace" \
> +		git repack -ad &&
>  	ls .git/objects/pack/ | grep bitmap >output &&
> -	test_line_count = 1 output
> +	test_line_count = 1 output &&
> +	grep "\"key\":\"num_selected_commits\",\"value\":\"106\"" trace &&
> +	grep "\"key\":\"num_maximal_commits\",\"value\":\"111\"" trace

From the diagram and bit masks, I see that the important number for
"maximal" is 7. Could this test be run twice - one without the crosses
and one with, and we can verify that the difference between the maximal
commits is 7? As it is, this 111 number is hard to verify.