Re: [PATCH 1/3] commit-reach: use one walk in remove_redundant()
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Jan 28, 2021, 20:51 UTC
- Message-ID
- <xmqqtur0vl7i.fsf@gitster.c.googlers.com>
- In-Reply-To
- <3fe74e339fc5b7083398f2df51baae5a4a008060.1611851095.git.gitgitgadget@gmail.com>
"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
Show 42 quoted lines
> + /* Mark all parents of the input as STALE */
> + for (i = 0; i < cnt; i++) {
> + struct commit_list *parents;
> + timestamp_t generation;
>
> repo_parse_commit(r, array[i]);
> + parents = array[i]->parents;
> +
> + while (parents) {
> + repo_parse_commit(r, parents->item);
> + if (!(parents->item->object.flags & STALE)) {
> + parents->item->object.flags |= STALE;
> + prio_queue_put(&queue, parents->item);
> + }
> + parents = parents->next;
> + }
> +
> + generation = commit_graph_generation(array[i]);
> +
> + if (generation < min_generation)
> + min_generation = generation;
> + }
> +
> + /* push the STALE bits up to min generation */
> + while (queue.nr) {
> + struct commit_list *parents;
> + struct commit *c = prio_queue_get(&queue);
> +
> + repo_parse_commit(r, c);
>
> + if (commit_graph_generation(c) < min_generation)
> continue;
>
> + parents = c->parents;
> + while (parents) {
> + if (!(parents->item->object.flags & STALE)) {
> + parents->item->object.flags |= STALE;
> + prio_queue_put(&queue, parents->item);
> + }
> + parents = parents->next;
> + }
> + }So, the inner loop makes sure we won't revisit STALE parent, but keep digging parents we haven't seen, and stop when the generation is old enough. What happens when there is no generation number computed yet, I wonder... We'll keep getting infinity and dig all the way down to root?
Show 13 quoted lines
> + /* rearrange array */
> + dup = xcalloc(cnt, sizeof(struct commit *));
> + COPY_ARRAY(dup, array, cnt);
> + for (i = 0; i < cnt; i++) {
> + if (dup[i]->object.flags & STALE) {
> + int insert = cnt - 1 - (i - count_non_stale);
> + array[insert] = dup[i];
> + } else {
> + array[count_non_stale] = dup[i];
> + count_non_stale++;
> + }
> + }
> + free(dup);The "fill stale ones from the end, non-stale ones from the beginning" in the loop looks unnecessarily complex to me. I wonder if we can do only the "fill non-stale ones from the beginning" half, i.e.
for (i = count_non_stale = 0; i < cnt; i++) {
if (dup[i] is not stale)
array[count_non_stale++] = dup[i];
}without the "keep the stale one at the end of array[]", and clear marks using what is in dup[] as starting points before discarding dup[]?
Or do the callers still look at the entries beyond count_non_stale?
Other than that, nicely done.
Show 37 quoted lines
> + /* clear marks */
> + for (i = 0; i < cnt; i++) {
> + struct commit_list *parents;
> + parents = array[i]->parents;
> +
> + while (parents) {
> + clear_commit_marks(parents->item, STALE);
> + parents = parents->next;
> }
> - common = paint_down_to_common(r, array[i], filled,
> - work, min_generation);
> - if (array[i]->object.flags & PARENT2)
> - redundant[i] = 1;
> - for (j = 0; j < filled; j++)
> - if (work[j]->object.flags & PARENT1)
> - redundant[filled_index[j]] = 1;
> - clear_commit_marks(array[i], all_flags);
> - clear_commit_marks_many(filled, work, all_flags);
> - free_commit_list(common);
> }
>
> - /* Now collect the result */
> - COPY_ARRAY(work, array, cnt);
> - for (i = filled = 0; i < cnt; i++)
> - if (!redundant[i])
> - array[filled++] = work[i];
> - for (j = filled, i = 0; i < cnt; i++)
> - if (redundant[i])
> - array[j++] = work[i];
> - free(work);
> - free(redundant);
> - free(filled_index);
> - return filled;
> + return count_non_stale;
> }
>
> static struct commit_list *get_merge_bases_many_0(struct repository *r,