From: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
Date: Mon, 16 Jul 2012 19:31:57 GMT
Subject: Re: [PATCH 4/8] git-remote-mediawiki: get rid of O(N^2) loop
Message-ID: <vpqhat7v6xe.fsf@bauges.imag.fr>
In-Reply-To: <7v394r36ws.fsf@alter.siamese.dyndns.org>

Junio C Hamano <gitster@pobox.com> writes:

> Matthieu Moy <Matthieu.Moy@imag.fr> writes:
>
>> The algorithm to find a path from the local revision to the remote one
>> was calling "git rev-list" and parsing its output N times. Run rev-list
>> only once, and fill a hashtable with the result to optimize the body of
>> the loop.
>
> Good thinking.  I wonder if it would further reduce the overhead if
> you stop using --children and do this using --parents instead, as
> you will be reading the parsed_sha1..local range either way yourself
> anyway.

It is possible, yes. I'll resend a version with --parents, but this
probably doesn't change the performance much: what we really need is for
Git to prune dead-ends in the subgraph, to make sure we find a path
without having to backtrack (i.e. we need parent rewriting history
simplification), so Git has to do something a bit clever anyway.

-- 
Matthieu Moy
http://www-verimag.imag.fr/~moy/