Re: [PATCH v2 18/24] pack-bitmap-write: build fewer intermediate bitmaps
- From
- Jonathan Tan <jonathantanmy@google.com>
- Date
- Nov 25, 2020, 01:46 UTC
- Message-ID
- <20201125014633.951649-1-jonathantanmy@google.com>
- In-Reply-To
- <5262daa3300114fbaccdbc7393882c5435f95f4f.1605649533.git.me@ttaylorr.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/
Show 7 quoted lines
> 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?)
Show 49 quoted lines
> 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...)
Show 51 quoted lines
> + }
>
> 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.
Show 20 quoted lines
> +# 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.
Show 18 quoted lines
> +# > +# 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]
Show 9 quoted lines
> 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.