From: Jeff King <peff@peff.net>
Date: Wed, 29 Aug 2012 11:08:12 GMT
Subject: Re: [PATCH 5/5] (BROKEN) get_merge_bases_many(): walk from many tips in parallel
Message-ID: <20120829110812.GA14069@sigill.intra.peff.net>
In-Reply-To: <7vvcg2y4bk.fsf@alter.siamese.dyndns.org>

On Tue, Aug 28, 2012 at 04:39:11PM -0700, Junio C Hamano wrote:

> > git rev-list --committer=torvalds@linux-foundation.org \
> >     --max-parents=2 --min-parents=2 --parents v3.5..v3.6-rc2 >RL
> >
> > cmd='
> > 	while read result parent1 parent2
> > 	do
> > 		$GIT merge-base $parent1 $parent2
> > 	done <RL
> > '
> 
> I have this suspicion that it is spending most of its time in
> insert-by-date.  Luckily, merge_bases_many() is totally outside of
> the usual revision traversal and its use of the commit list is
> pretty well isolated.
> 
> Peff, can I interest you into resurrecting your $gmane/174007 and
> $gmane/174008 (we do not need pop_commit_from_queue() in the latter;
> everything can stay as static to commit.c for now) to see how well
> priority queue based approach would perform?

I did a quick port of merge_bases_many and get_merge_bases_many to use
priority queues, but I didn't see any speedup at all on the above test
case.  According to perf, we spend most of our time in zlib, inflating
commits. Only 1% is spent on commit_list_insert_by_date, which is about
the same amount spent on queue insertion after my patches.

Patches follow, just for reference.

  [1/2]: basic priority queue implementation
  [2/2]: commit: use a priority queue in merge base functions

-Peff