From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jeff King Subject: Re: [PATCH 5/5] (BROKEN) get_merge_bases_many(): walk from many tips in parallel Date: Wed, 29 Aug 2012 07:08:12 -0400 Message-ID: <20120829110812.GA14069@sigill.intra.peff.net> References: <1346109123-12357-1-git-send-email-gitster@pobox.com> <1346109123-12357-6-git-send-email-gitster@pobox.com> <7vipc3q041.fsf@alter.siamese.dyndns.org> <7v8vcyzomw.fsf@alter.siamese.dyndns.org> <7vvcg2y4bk.fsf@alter.siamese.dyndns.org> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Cc: git@vger.kernel.org, Thomas Rast To: Junio C Hamano X-From: git-owner@vger.kernel.org Wed Aug 29 13:09:03 2012 Return-path: Envelope-to: gcvg-git-2@plane.gmane.org Received: from vger.kernel.org ([209.132.180.67]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1T6g8p-0006kS-Bw for gcvg-git-2@plane.gmane.org; Wed, 29 Aug 2012 13:08:59 +0200 Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752684Ab2H2LIS (ORCPT ); Wed, 29 Aug 2012 07:08:18 -0400 Received: from 75-15-5-89.uvs.iplsin.sbcglobal.net ([75.15.5.89]:46965 "EHLO peff.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752541Ab2H2LIR (ORCPT ); Wed, 29 Aug 2012 07:08:17 -0400 Received: (qmail 31635 invoked by uid 107); 29 Aug 2012 11:08:33 -0000 Received: from sigill.intra.peff.net (HELO sigill.intra.peff.net) (10.0.0.7) (smtp-auth username relayok, mechanism cram-md5) by peff.net (qpsmtpd/0.84) with ESMTPA; Wed, 29 Aug 2012 07:08:33 -0400 Received: by sigill.intra.peff.net (sSMTP sendmail emulation); Wed, 29 Aug 2012 07:08:12 -0400 Content-Disposition: inline In-Reply-To: <7vvcg2y4bk.fsf@alter.siamese.dyndns.org> Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Archived-At: 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 > ' > > 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