From: Junio C Hamano <gitster@pobox.com>
Date: Mon, 09 Jan 2012 22:09:29 GMT
Subject: Re: [PATCH v2 1/3] Eliminate recursion in setting/clearing marks in commit list
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:

> 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.