From patchwork Sun Jul 2 22:35:40 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Jeff King X-Patchwork-Id: 13299511 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id A0FE6EB64D9 for ; Sun, 2 Jul 2023 22:35:44 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230018AbjGBWfn (ORCPT ); Sun, 2 Jul 2023 18:35:43 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55914 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229709AbjGBWfm (ORCPT ); Sun, 2 Jul 2023 18:35:42 -0400 Received: from cloud.peff.net (cloud.peff.net [104.130.231.41]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E2AF2E49 for ; Sun, 2 Jul 2023 15:35:41 -0700 (PDT) Received: (qmail 17856 invoked by uid 109); 2 Jul 2023 22:35:41 -0000 Received: from Unknown (HELO peff.net) (10.0.1.2) by cloud.peff.net (qpsmtpd/0.94) with ESMTP; Sun, 02 Jul 2023 22:35:41 +0000 Authentication-Results: cloud.peff.net; auth=none Received: (qmail 16702 invoked by uid 111); 2 Jul 2023 22:35:43 -0000 Received: from coredump.intra.peff.net (HELO sigill.intra.peff.net) (10.0.0.2) by peff.net (qpsmtpd/0.94) with (TLS_AES_256_GCM_SHA384 encrypted) ESMTPS; Sun, 02 Jul 2023 18:35:43 -0400 Authentication-Results: peff.net; auth=none Date: Sun, 2 Jul 2023 18:35:40 -0400 From: Jeff King To: Jan =?utf-8?q?Kl=C3=B6tzke?= Cc: git@vger.kernel.org, Junio C Hamano , Steve Kemp , =?utf-8?b?UmVuw6k=?= Scharfe , Stefan Beller Subject: [PATCH 1/3] ref-filter: avoid parsing tagged objects in match_points_at() Message-ID: <20230702223540.GA3494279@coredump.intra.peff.net> References: <20230702223342.GA1598765@coredump.intra.peff.net> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20230702223342.GA1598765@coredump.intra.peff.net> Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org When we peel tags to check if they match a --points-at oid, we recursively parse the tagged object to see if it is also a tag. But since the tag itself tells us the type of the object it points to (and even gives us the appropriate object struct via its "tagged" member), we can use that directly. We do still have to make sure to call parse_tag() before looking at each tag. This is redundant for the outermost tag (since we did call parse_object() to find its type), but that's OK; parse_tag() is smart enough to make this a noop when the tag has already been parsed. In my clone of linux.git, with 782 tags (and only 3 non-tags), this yields a significant speedup (bringing us back where we were before the commit before this one started recursively dereferencing tags): Benchmark 1: ./git.old for-each-ref --points-at=HEAD --format="%(refname)" Time (mean ± σ): 20.3 ms ± 0.5 ms [User: 11.1 ms, System: 9.1 ms] Range (min … max): 19.6 ms … 21.5 ms 141 runs Benchmark 2: ./git.new for-each-ref --points-at=HEAD --format="%(refname)" Time (mean ± σ): 11.4 ms ± 0.2 ms [User: 6.3 ms, System: 5.0 ms] Range (min … max): 11.0 ms … 12.2 ms 250 runs Summary './git.new for-each-ref --points-at=HEAD --format="%(refname)"' ran 1.79 ± 0.05 times faster than './git.old for-each-ref --points-at=HEAD --format="%(refname)"' Signed-off-by: Jeff King --- This could optionally be squashed into the original. If we leave it as its own patch, it might be worth replacing "the commit before this one" with the actual oid (once Junio has picked it up and it's stable). ref-filter.c | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-) diff --git a/ref-filter.c b/ref-filter.c index ad7f244414..e091f056ab 100644 --- a/ref-filter.c +++ b/ref-filter.c @@ -2225,10 +2225,18 @@ static const struct object_id *match_points_at(struct oid_array *points_at, return oid; obj = parse_object(the_repository, oid); while (obj && obj->type == OBJ_TAG) { - oid = get_tagged_oid((struct tag *)obj); + struct tag *tag = (struct tag *)obj; + + if (parse_tag(tag) < 0) { + obj = NULL; + break; + } + + oid = get_tagged_oid(tag); if (oid_array_lookup(points_at, oid) >= 0) return oid; - obj = parse_object(the_repository, oid); + + obj = tag->tagged; } if (!obj) die(_("malformed object at '%s'"), refname); From patchwork Sun Jul 2 22:37:47 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Jeff King X-Patchwork-Id: 13299512 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 4D8C8EB64D9 for ; Sun, 2 Jul 2023 22:37:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230023AbjGBWhu (ORCPT ); Sun, 2 Jul 2023 18:37:50 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56166 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229709AbjGBWht (ORCPT ); Sun, 2 Jul 2023 18:37:49 -0400 Received: from cloud.peff.net (cloud.peff.net [104.130.231.41]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B125F1B7 for ; Sun, 2 Jul 2023 15:37:48 -0700 (PDT) Received: (qmail 18000 invoked by uid 109); 2 Jul 2023 22:37:48 -0000 Received: from Unknown (HELO peff.net) (10.0.1.2) by cloud.peff.net (qpsmtpd/0.94) with ESMTP; Sun, 02 Jul 2023 22:37:48 +0000 Authentication-Results: cloud.peff.net; auth=none Received: (qmail 16720 invoked by uid 111); 2 Jul 2023 22:37:50 -0000 Received: from coredump.intra.peff.net (HELO sigill.intra.peff.net) (10.0.0.2) by peff.net (qpsmtpd/0.94) with (TLS_AES_256_GCM_SHA384 encrypted) ESMTPS; Sun, 02 Jul 2023 18:37:50 -0400 Authentication-Results: peff.net; auth=none Date: Sun, 2 Jul 2023 18:37:47 -0400 From: Jeff King To: Jan =?utf-8?q?Kl=C3=B6tzke?= Cc: git@vger.kernel.org, Junio C Hamano , Steve Kemp , =?utf-8?b?UmVuw6k=?= Scharfe , Stefan Beller Subject: [PATCH 2/3] ref-filter: avoid parsing non-tags in match_points_at() Message-ID: <20230702223747.GB3494279@coredump.intra.peff.net> References: <20230702223342.GA1598765@coredump.intra.peff.net> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20230702223342.GA1598765@coredump.intra.peff.net> Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org When handling --points-at, we have to try to peel each ref to see if it's a tag that points at a requested oid. We start this process by calling parse_object() on the oid pointed to by each ref. The cost of parsing each object adds up, especially in an output that doesn't otherwise need to open the objects at all. Ideally we'd use peel_iterated_oid() here, which uses the cached information in the packed-refs file. But we can't, because our --points-at must match not only the fully peeled value, but any interim values (so if tag A points to tag B which points to commit C, we should match --points-at=B, but peel_iterated_oid() will only tell us about C). So the best we can do (absent changes to the packed-refs peel traits) is to avoid parsing non-tags. The obvious way to do that is to call oid_object_info() to check the type before parsing. But there are a few gotchas there, like checking if the object has already been parsed. Instead we can just tell parse_object() that we are OK skipping the hash check, which lets it turn on several optimizations. Commits can be loaded via the commit graph (so it's both fast and we have the benefit of the parsed data if we need it later at the output stage). Blobs are not loaded at all. Trees are still loaded, but it's rather rare to have a ref point directly to a tree (and since this is just an optimization, kicking in 99% of the time is OK). Even though we're paying for an extra lookup, the cost to avoid parsing the non-tags is a net benefit. In my git.git repository with 941 tags and 1440 other refs pointing to commits, this significantly cuts the runtime: Benchmark 1: ./git.old for-each-ref --points-at=HEAD Time (mean ± σ): 26.8 ms ± 0.5 ms [User: 24.5 ms, System: 2.2 ms] Range (min … max): 25.9 ms … 29.2 ms 107 runs Benchmark 2: ./git.new for-each-ref --points-at=HEAD Time (mean ± σ): 9.1 ms ± 0.3 ms [User: 6.8 ms, System: 2.2 ms] Range (min … max): 8.6 ms … 10.2 ms 308 runs Summary './git.new for-each-ref --points-at=HEAD' ran 2.96 ± 0.10 times faster than './git.old for-each-ref --points-at=HEAD' In a repository that is mostly annotated tags, we'd expect less improvement (we might still skip a few object loads, but that's balanced by the extra lookups). In my clone of linux.git, which has 782 tags and 3 branches, the run-time is about the same (it's actually ~1% faster on average after this patch, but that's within the run-to-run noise). Signed-off-by: Jeff King --- ref-filter.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/ref-filter.c b/ref-filter.c index e091f056ab..f5ac486430 100644 --- a/ref-filter.c +++ b/ref-filter.c @@ -2223,7 +2223,8 @@ static const struct object_id *match_points_at(struct oid_array *points_at, if (oid_array_lookup(points_at, oid) >= 0) return oid; - obj = parse_object(the_repository, oid); + obj = parse_object_with_flags(the_repository, oid, + PARSE_OBJECT_SKIP_HASH_CHECK); while (obj && obj->type == OBJ_TAG) { struct tag *tag = (struct tag *)obj; From patchwork Sun Jul 2 22:38:29 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff King X-Patchwork-Id: 13299513 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id B17D1EB64D9 for ; Sun, 2 Jul 2023 22:38:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230018AbjGBWic (ORCPT ); Sun, 2 Jul 2023 18:38:32 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56264 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229709AbjGBWib (ORCPT ); Sun, 2 Jul 2023 18:38:31 -0400 Received: from cloud.peff.net (cloud.peff.net [104.130.231.41]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8C4C61B7 for ; Sun, 2 Jul 2023 15:38:30 -0700 (PDT) Received: (qmail 18057 invoked by uid 109); 2 Jul 2023 22:38:30 -0000 Received: from Unknown (HELO peff.net) (10.0.1.2) by cloud.peff.net (qpsmtpd/0.94) with ESMTP; Sun, 02 Jul 2023 22:38:30 +0000 Authentication-Results: cloud.peff.net; auth=none Received: (qmail 16728 invoked by uid 111); 2 Jul 2023 22:38:32 -0000 Received: from coredump.intra.peff.net (HELO sigill.intra.peff.net) (10.0.0.2) by peff.net (qpsmtpd/0.94) with (TLS_AES_256_GCM_SHA384 encrypted) ESMTPS; Sun, 02 Jul 2023 18:38:32 -0400 Authentication-Results: peff.net; auth=none Date: Sun, 2 Jul 2023 18:38:29 -0400 From: Jeff King To: Jan =?utf-8?q?Kl=C3=B6tzke?= Cc: git@vger.kernel.org, Junio C Hamano , Steve Kemp , =?utf-8?b?UmVuw6k=?= Scharfe , Stefan Beller Subject: [PATCH 3/3] ref-filter: simplify return type of match_points_at Message-ID: <20230702223829.GC3494279@coredump.intra.peff.net> References: <20230702223342.GA1598765@coredump.intra.peff.net> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20230702223342.GA1598765@coredump.intra.peff.net> Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org We return the oid that matched, but the sole caller only cares whether we matched anything at all. This is mostly academic, since there's only one caller, but the lifetime of the returned pointer is not immediately clear. Sometimes it points to an oid in a tag struct, which should live forever. And sometimes to the oid passed in, which only lives as long as the each_ref_fn callback we're called from. Simplify this to a boolean return which is more direct and obvious. As a bonus, this lets us avoid the weird pattern of overwriting our "oid" parameter in the loop (since we now only refer to the tagged oid one time, and can just inline the call to get it). Signed-off-by: Jeff King --- ref-filter.c | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-) diff --git a/ref-filter.c b/ref-filter.c index f5ac486430..0629435f08 100644 --- a/ref-filter.c +++ b/ref-filter.c @@ -2209,20 +2209,22 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter, /* * Given a ref (oid, refname), check if the ref belongs to the array * of oids. If the given ref is a tag, check if the given tag points - * at one of the oids in the given oid array. + * at one of the oids in the given oid array. Returns non-zero if a + * match is found. + * * NEEDSWORK: * As the refs are cached we might know what refname peels to without * the need to parse the object via parse_object(). peel_ref() might be a * more efficient alternative to obtain the pointee. */ -static const struct object_id *match_points_at(struct oid_array *points_at, - const struct object_id *oid, - const char *refname) +static int match_points_at(struct oid_array *points_at, + const struct object_id *oid, + const char *refname) { struct object *obj; if (oid_array_lookup(points_at, oid) >= 0) - return oid; + return 1; obj = parse_object_with_flags(the_repository, oid, PARSE_OBJECT_SKIP_HASH_CHECK); while (obj && obj->type == OBJ_TAG) { @@ -2233,15 +2235,14 @@ static const struct object_id *match_points_at(struct oid_array *points_at, break; } - oid = get_tagged_oid(tag); - if (oid_array_lookup(points_at, oid) >= 0) - return oid; + if (oid_array_lookup(points_at, get_tagged_oid(tag)) >= 0) + return 1; obj = tag->tagged; } if (!obj) die(_("malformed object at '%s'"), refname); - return NULL; + return 0; } /*