Re: [PATCH v2 1/3] Eliminate recursion in setting/clearing marks in commit list

From: Junio C Hamano <gitster@pobox.com>
Date: Jan 9, 2012, 22:09 UTC
Message-ID: <7v4nw4edeu.fsf@alter.siamese.dyndns.org>
In-Reply-To: <1326081546-29320-2-git-send-email-pclouds@gmail.com>

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

Show 6 quoted lines

> Recursion in a DAG is generally a bad idea because it could be very
> deep. Be defensive and avoid recursion in mark_parents_uninteresting()
> and clear_commit_marks().
>
> mark_parents_uninteresting() learns a trick from clear_commit_marks()
> to avoid malloc() in (dorminant) single-parent case.

Looks cleanly done.

This retains the depth-firstness of the (supposedly less common case) recursion in mark_parents_uninteresting() from the original code, by adding the already parsed parent at the beginning of the queue. I suspect that the original went depth-first primarily because that was the most straightforward way to code it, but now you have more flexibility, I wonder if there is a difference if we made it width-first, and if so, if the difference is positive or detrimental.

Thanks.