Re: [PATCH v6] show-branch: convert per-branch flags to commit-slab

[Junio C Hamano <gitster@pobox.com>]

Gatla Vishweshwar Reddy <gatlavishweshwarreddy26@gmail.com> writes:

> show-branch uses commit->object.flags to store per-branch
> reachability bits, one bit per branch starting at REV_SHIFT.
> The flags word has only a fixed number of available bits, limiting
> the number of branches that can be shown simultaneously to MAX_REVS.
>
> Convert the per-branch bits to a dedicated commit-slab using uint64_t
> as the element type, initialized with a stride via
> init_commit_rev_flags_with_stride(). Keep the UNINTERESTING bit in
> object.flags where it belongs, as it is used for revision walking and
> does not need to be in the per-branch slab. With UNINTERESTING removed
> from the slab, REV_SHIFT becomes 0 and all 64 bits of uint64_t are
> available for branch tracking, lifting MAX_REVS from 27 to 64 branches.

Thanks.  This version looks much cleaner.  I appreciate your
addressing the correctness issues around UNINTERESTING
propagation that we spotted in the previous round.

I do have a slight worry about a potential performance regression,
though.  We might run the risk of slowing down the traversal in
how we skip parents.

> @@ -226,39 +285,43 @@ static void join_revs(struct prio_queue *queue,
> ...

In the original code, we avoided parsing and re-queueing the parent 'p'
if we knew it already had all the flags we were trying to propagate.

> -			int this_flag = p->object.flags;
> -			parents = parents->next;
> -			if ((this_flag & flags) == flags)
> -				continue;
> -			repo_parse_commit(the_repository, p);
> ...
> +		{
> +			int commit_is_merge_base = has_all_rev_flags(commit, num_rev);
> +			parents = commit->parents;
> +
> +			while (parents) {
> +				struct commit *p = parents->item;
> +				parents = parents->next;
> +				if (has_all_rev_flags(p, num_rev) &&
> +				    (!commit_is_merge_base || (p->object.flags & UNINTERESTING)))
> +					continue;

With the new slab-based approach, we skip only when 'p' already has
all possible revision flags, num_rev.  If 'p' already carries all
the flags that the current 'commit' has (even if it lacks some of
the other num_rev flags), the traversal could be pruned early, but
the proposed change fails to do so.

Consequently, we proceed to propagate the flags (which amounts to a
no-op on the slab anyway) and, worse, re-queue 'p' for further
processing.  In a densely tangled history with many merges, this
would lead to significant redundant work and queue thrashing.  We
instead should check whether the flags of 'commit' are a subset of
those of 'p'.  Since the flags_stride is known, introducing a
helper, perhaps has_subset_rev_flags(commit, p), to perform this
check should be a straightforward exercise.

Also, looking at the bigger picture ...

> -#define REV_SHIFT	 2
> -#define MAX_REVS	(FLAG_BITS - REV_SHIFT) /* should not exceed bits_per_int - REV_SHIFT */
> -
> +#define REV_SHIFT	 0
> +#define MAX_REVS	(sizeof(uint64_t) * 8)

While lifting the limit from 27 to 64 is a welcome improvement, I
wonder why we stop there and still tolerate a hardcoded MAX_REVS
limit.

The introduction of flags_stride and init_commit_rev_flags_with_stride
already lays the groundwork for supporting an arbitrary number of
flags.  The only remaining blockages that keep MAX_REVS alive are:

 - The static ref_name[] array; and

 - The stack-allocated arrays rev[] and reflog_msg[] in the
   cmd_show_branch() function.

If we

 - dynamically grow the ref_name[] array (perhaps using the
   ALLOC_GROW macro),

 - dynamically allocate rev[] and reflog_msg[] in cmd_show_branch()
   once options are parsed (and thus ref_name_cnt and the reflog
   flag are known), and

 - calculate flags_stride at runtime as (ref_name_cnt + 63) / 64,

then we can get rid of MAX_REVS and the associated boundary checks
entirely.  Since the proposed patch already does 90% of the work
needed to support an arbitrary stride, it feels like a missed
opportunity not to take that final step.

Thoughts?