Re: [RFH] git cherry vs. git rev-list --cherry, or: Why does "..." suck?

From: Michael J Gruber <git@drmicha.warpmail.net>
Date: Mar 23, 2011, 16:46 UTC
Message-ID: <4D8A23CD.9030203@drmicha.warpmail.net>
In-Reply-To: <4D889119.3020009@drmicha.warpmail.net>

Adding some recent insight:

Michael J Gruber venit, vidit, dixit 22.03.2011 13:07:

Show 8 quoted lines

> Performance
> ===========
> 
> I don't get this:
> 
> git cherry A B: 0.4s
> git rev-list --cherry A...B: 1.7s
> (more details below)

I can get the latter down to 0.95s and this

> merge-base A B: 0.95s
> merge-base --all A B: 0.95s
> rev-parse A...B: 0.95s

to 0.16s each. The downside is that merge-base may give a few unneccessary candidates (commits which are ancestors of other commits it returns), but this does not change the results for rev-list, of course.

I get this dramatic speedup by removing the check for duplicates from get_merge_bases_many() in commit.c. After a first merge_bases_many() run, returning N commits, that check calls merge_bases_many() again for each pair (N choose 2) to check whether one is contained in the other. Quite a bottleneck. Removing it works great. But can we live with a few additional merge bases?

Michael