From: Junio C Hamano <gitster@pobox.com>
Date: Thu, 30 Aug 2012 23:13:04 GMT
Subject: [PATCH 0/4] "merge-base" updates
Message-ID: <1346368388-23576-1-git-send-email-gitster@pobox.com>

This replaces the topmost commit from the earlier series that tried
to optimize N*(N-1) loop with N traversals.  With this, running the
following script in the kernel repository:

-- >8 --
#!/bin/sh

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
'

GIT="rungit master" time sh -c "$cmd" >:stock
GIT=../git.git/git time sh -c "$cmd" >:optim
cmp :stock :optim
-- 8< --

shows a slight but measurable boost in the performance of
merge-base itself.

42.45user 3.79system 0:46.62elapsed 99%CPU (0avgtext+0avgdata 408176maxresident)k
0inputs+24outputs (0major+2708085minor)pagefaults 0swaps
39.99user 3.42system 0:43.27elapsed 100%CPU (0avgtext+0avgdata 408192maxresident)k
0inputs+24outputs (0major+2179604minor)pagefaults 0swaps

Junio C Hamano (4):
  merge_bases_many(): split out the logic to paint history
  merge-base: "--is-ancestor A B"
  in_merge_bases(): use paint_down_to_common()
  get_merge_bases_many(): walk from many tips in parallel

 builtin/merge-base.c |  21 ++++++++
 commit.c             | 143 +++++++++++++++++++++++++++++++++------------------
 2 files changed, 114 insertions(+), 50 deletions(-)

-- 
1.7.12.293.g6aeebca