Re: [PATCH v3 6/8] commit-reach: implement ahead_behind() logic

From: Jonathan Tan <jonathantanmy@google.com>
Date: Mar 15, 2023, 23:28 UTC
Message-ID: <20230315232835.173584-1-jonathantanmy@google.com>
In-Reply-To: <0fb3913810b7d4731707a0129df7f5d57c8ab39f.1678902343.git.gitgitgadget@gmail.com>

First of all, thanks to Taylor and Stolee for this algorithm and code
- it is straightforwardly written and looks correct to me. I have some
commit message and code comment suggestions that if taken, would have
helped me on my first reading, but these are subjective so feel free
to ignore them if you think they would add unnecessary detail (I did
understand the algorithm in the end, after all).

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

> The second array, using the
> new ahead_behind_count struct, indicates which commits from that initial
> array form the base/tip pair for the ahead/behind count it will store.

I would have preferred: The second array contains base/tip pairs designating pairs of commits for which ahead/behind counts need to be computed, each pair being a pair of indexes into the first array.

> Each commit in the input commit list is associated with a bit position
> indicating "the ith commit can reach this commit". Each of these commits
> is associated with a bitmap with its position flipped on and then
> placed in a queue for walking commit history.

"this commit" is not necessarily a commit in the input commit list (it is actually the commit that we're currently at in our iteration) and I think that the association of bitmaps with commits in the input commit list could be more clearly described. So I would have preferred: Each commit in the priority queue is associated with a bitmap of width N (N being the count of commits in the first array), in which a bit is set iff the commit can be reached by the corresponding commit in the first array. This is different from packfile or MIDX bitmaps in that a commit's bitmap stores what can reach it, not what it can reach. The priority queue is initialized with N commits, each commit being associated with a bitmap in which a single bit is set (indicating that the commit can be reached by itself).

Show 6 quoted lines

> +void ahead_behind(struct repository *r,
> +		  struct commit **commits, size_t commits_nr,
> +		  struct ahead_behind_count *counts, size_t counts_nr)
> +{
> +	struct prio_queue queue = { .compare = compare_commits_by_gen_then_commit_date };
> +	size_t width = (commits_nr + BITS_IN_EWORD - 1) / BITS_IN_EWORD;

As we discussed in our Review Club, DIV_ROUND_UP can be used for this.

(For those reading who do not know what Review Club is, search the archives and/or look out for future announcements!)

> +			if (bitmap_popcount(bitmap_p) == commits_nr)
> +				p->item->object.flags |= STALE;

Might be worth adding a comment above the STALE line: this parent commit and all its ancestors can be reached by every commit in the commits list and thus can never be "ahead" or "behind" in any pair; mark this STALE so that, as an optimization, we can stop iteration if only STALE commits remain (since further iteration would never change any "ahead" or "behind" value).