From patchwork Mon Mar 4 10:49:40 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Steinhardt X-Patchwork-Id: 13580406 Received: from wfhigh1-smtp.messagingengine.com (wfhigh1-smtp.messagingengine.com [64.147.123.152]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 101F639AC5 for ; Mon, 4 Mar 2024 10:49:43 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=64.147.123.152 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709549385; cv=none; b=WgorfiFiT1oSBI3JV2LnXDT9xygNlrk0HmFXQvlK0N1YzQFex8DknwuKjmNIXidMyWZv+vWV+Nh+5DcRy3CqeV/PMMbK5uvfiUliCgTZuzF6O/s3u1HeihJZJXCGCnzoDKhByXNHG9SKCvfSVdPNxz1YuzyIVWtnPYPgFhLCAjA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709549385; c=relaxed/simple; bh=VuTOlBoW6+nLMAMDcdh88HurEDIQ330ZYDvBquPnWVg=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=BHGWgYTcxpgVCKwkZhZB9mPO0GDxBx4bUywD0XvCHdaK68DA8AB8eL3Jza79J6RZBLmghV/K7vKmcWr24h8adN0WLEgmnuqAPjlwPkL8Kj2jlKFvuY2/oykbJ4XnnGAJU9tktERJJIAEhxbHD+0yuKYxJT7tYDVwd+68emNfYp0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im; spf=pass smtp.mailfrom=pks.im; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b=jbEy9NZ7; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=YTih2vJU; arc=none smtp.client-ip=64.147.123.152 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=pks.im Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pks.im Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pks.im header.i=@pks.im header.b="jbEy9NZ7"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="YTih2vJU" Received: from compute7.internal (compute7.nyi.internal [10.202.2.48]) by mailfhigh.west.internal (Postfix) with ESMTP id 312BA18000C9; Mon, 4 Mar 2024 05:49:43 -0500 (EST) Received: from mailfrontend2 ([10.202.2.163]) by compute7.internal (MEProxy); Mon, 04 Mar 2024 05:49:43 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:subject :subject:to:to; s=fm1; t=1709549382; x=1709635782; bh=Bt8cI77Z7I fp+qqujXP1KNS0o625AI8DASHi7iVaGgc=; b=jbEy9NZ71U3/l7K1iUQBoLN9+V rL8VJh5YZk0mswOKxD/W6lBRnoxFl/UyCqvKNALKvM59nd6Que4iysv4RMKhqTcI xgECaQz2w07Ho8WVMguNzX5G0UQCHSqChme7bCefhZmaGcm0nDy1oWhbQksJ0cx1 xMr6bwTet8smHQWhC5MHHPiqqLEZnQsjCe1XptDacc0QSXJQe4YN6l0EUSl6GCe+ 7zQo2SYLvUGTq50xu1akd+snggbFj+xU2vd1EWaOvg8TUujhkwxY8WQtE4mLrmJf ocMD5t40XH70xIFobx0Z6cnzoDrfMI5GFfq6U78s5EXaMMuFO6m9+CieOYfw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm1; t=1709549382; x=1709635782; bh=Bt8cI77Z7Ifp+qqujXP1KNS0o625 AI8DASHi7iVaGgc=; b=YTih2vJU5oEcQPRurL/AAdlGd773BcYlGKPf1TlPWE2p BEEF/1N7OU/+dFt0NJ7BbbswUMQwdZ4OBdrAyQ336a21MGFb6drutfr6cZTfimta zDWHtf52X6T4DNvkJ7fXYLHXnnJWdZZMDZgTT5BrAe4ZDyLqENlhvOknXrfncGoP 8FTwEQdn7MLqQzfb46yMgFNWPvikzWEo1aj4L5ZQYzzYCx9+7cTWG37bXiwS2KTO Ri4XuoEhpoMs2F0Y2l79BhVmzHqKKH3sG4BKmLdxyfG9G3bznFXv+JtWmXc9r+nK nDruW62JuWMT4UZfE4McHiVRVpY4xaAVG76rS49+EA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvledrheejgddvtdcutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpeffhffvvefukfhfgggtuggjsehgtderredttdejnecuhfhrohhmpefrrghtrhhi tghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtthgvrh hnpeetueevhffhudefvdegieeuieelgedthfegfedtueevjeejtdfgjeehudejuedtuden ucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpshesph hkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 4 Mar 2024 05:49:41 -0500 (EST) Received: by vm-mail (OpenSMTPD) with ESMTPSA id d0ac9118 (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Mon, 4 Mar 2024 10:45:16 +0000 (UTC) Date: Mon, 4 Mar 2024 11:49:40 +0100 From: Patrick Steinhardt To: git@vger.kernel.org Cc: Justin Tobler , James Liu Subject: [PATCH v3 13/13] refs/reftable: precompute prefix length Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: We're recomputing the prefix length on every iteration of the ref iterator. Precompute it for another speedup when iterating over 1 million refs: Benchmark 1: show-ref: single matching ref (revision = HEAD~) Time (mean ± σ): 100.3 ms ± 3.7 ms [User: 97.3 ms, System: 2.8 ms] Range (min … max): 97.5 ms … 139.7 ms 1000 runs Benchmark 2: show-ref: single matching ref (revision = HEAD) Time (mean ± σ): 95.8 ms ± 3.4 ms [User: 92.9 ms, System: 2.8 ms] Range (min … max): 93.0 ms … 121.9 ms 1000 runs Summary show-ref: single matching ref (revision = HEAD) ran 1.05 ± 0.05 times faster than show-ref: single matching ref (revision = HEAD~) Signed-off-by: Patrick Steinhardt --- refs/reftable-backend.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c index 6c11c4a5e3..249a618b5a 100644 --- a/refs/reftable-backend.c +++ b/refs/reftable-backend.c @@ -346,6 +346,7 @@ struct reftable_ref_iterator { struct object_id oid; const char *prefix; + size_t prefix_len; unsigned int flags; int err; }; @@ -371,8 +372,8 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator) if (!starts_with(iter->ref.refname, "refs/")) continue; - if (iter->prefix && - strncmp(iter->prefix, iter->ref.refname, strlen(iter->prefix))) { + if (iter->prefix_len && + strncmp(iter->prefix, iter->ref.refname, iter->prefix_len)) { iter->err = 1; break; } @@ -481,6 +482,7 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_ iter = xcalloc(1, sizeof(*iter)); base_ref_iterator_init(&iter->base, &reftable_ref_iterator_vtable); iter->prefix = prefix; + iter->prefix_len = prefix ? strlen(prefix) : 0; iter->base.oid = &iter->oid; iter->flags = flags; iter->refs = refs;