From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jeff King Subject: Re: [PATCH] walker: avoid quadratic list insertion in mark_complete Date: Fri, 22 Aug 2014 00:01:31 -0400 Message-ID: <20140822040131.GA27992@peff.net> References: <53F63AC0.1090605@web.de> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: QUOTED-PRINTABLE Cc: Git Mailing List , Junio C Hamano To: =?utf-8?B?UmVuw6k=?= Scharfe X-From: git-owner@vger.kernel.org Fri Aug 22 06:01:56 2014 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 1XKg30-0002Pu-BE for gcvg-git-2@plane.gmane.org; Fri, 22 Aug 2014 06:01:54 +0200 Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1750812AbaHVEBe convert rfc822-to-quoted-printable (ORCPT ); Fri, 22 Aug 2014 00:01:34 -0400 Received: from cloud.peff.net ([50.56.180.127]:56559 "HELO peff.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with SMTP id S1750733AbaHVEBd (ORCPT ); Fri, 22 Aug 2014 00:01:33 -0400 Received: (qmail 334 invoked by uid 102); 22 Aug 2014 04:01:33 -0000 Received: from c-71-63-4-13.hsd1.va.comcast.net (HELO sigill.intra.peff.net) (71.63.4.13) (smtp-auth username relayok, mechanism cram-md5) by peff.net (qpsmtpd/0.84) with ESMTPA; Thu, 21 Aug 2014 23:01:33 -0500 Received: by sigill.intra.peff.net (sSMTP sendmail emulation); Fri, 22 Aug 2014 00:01:31 -0400 Content-Disposition: inline In-Reply-To: <53F63AC0.1090605@web.de> Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Archived-At: On Thu, Aug 21, 2014 at 08:30:24PM +0200, Ren=C3=A9 Scharfe wrote: > Similar to 16445242 (fetch-pack: avoid quadratic list insertion in > mark_complete), sort only after all refs are collected instead of whi= le > inserting. The result is the same, but it's more efficient that way. > The difference will only be measurable in repositories with a large > number of refs. Thanks, this looks obviously correct. I wonder if we should do this on top: diff --git a/walker.c b/walker.c index 0148264..70088b8 100644 --- a/walker.c +++ b/walker.c @@ -203,7 +203,7 @@ static int interpret_target(struct walker *walker, = char *target, unsigned char * static int mark_complete(const char *path, const unsigned char *sha1, = int flag, void *cb_data) { struct commit *commit =3D lookup_commit_reference_gently(sha1, 1); - if (commit) { + if (commit && !(commit->object.flags & COMPLETE)) { commit->object.flags |=3D COMPLETE; commit_list_insert_by_date(commit, &complete); } It's not as big a deal with your patch since you've made it O(n log n), but reducing n further does not hurt. -Peff