Re: [PATCH v2 06/25] reachable: use traverse_commit_list instead of custom walk

From: Junio C Hamano <gitster@pobox.com>
Date: Oct 16, 2014, 17:53 UTC
Message-ID: <xmqqmw8vuci7.fsf@gitster.dls.corp.google.com>
In-Reply-To: <20141015223728.GF25630@peff.net>

Jeff King <peff@peff.net> writes:

Show 16 quoted lines

> To find the set of reachable objects, we add a bunch of
> possible sources to our rev_info, call prepare_revision_walk,
> and then launch into a custom walker that handles each
> object top. This is a subset of what traverse_commit_list
> does, so we can just reuse that code (it can also handle
> more complex cases like UNINTERESTING commits and pathspecs,
> but we don't use those features).
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> I was concerned this would be slower because traverse_commit_list is
> more featureful. To my surprise, it was consistently about 3-4% faster!
> The major difference is that traverse_commit_list will hit all of the
> commits first, and then the trees. For reachability that doesn't matter
> either way, but I suspect the new way has slightly better cache
> locality, leading to the minor speedup.

I am not very surprised, as "custom walk" hasn't changed much ever since it was done in ba84a797 (builtin "git prune", 2006-07-06), while the generic traversal code has been worked heavily while it was still in builtin-rev-list.c and then later moved to list-objects.c.

>  reachable.c | 130 ++++++++----------------------------------------------------
>  1 file changed, 17 insertions(+), 113 deletions(-)

;-) ;-) ;-) ;-) ;-)