From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from smtp118.iad3a.emailsrvr.com (smtp118.iad3a.emailsrvr.com [173.203.187.118]) (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 2CCFC346ADC for ; Wed, 14 Oct 2026 03:14:23 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=173.203.187.118 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1791947666; cv=none; b=M2bMRI582sG+jwmPpay+PqbRcY3keWXsg9IYcBEtmyuQlb/KXXKfW+xBWwMuYBVEBajghSOrVyom+yLEzHF3wlBb77pOqrGLFt9Mwpa1ZAj7xIiXJg/wZ+PlTT5gSFHoxJ2WUEErAidcu7uiVGkAm+dY5J6Nss7SWAgPVk4Ek28= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1791947666; c=relaxed/simple; bh=bhwXdTXqKiibPegCCe6J0ssUrSwH1tDhXLzg9XzxUEc=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=rM308BwSWfkxiFbxKy0oxHgKuJLuTdTbwOu3mZiPQ/jcV7dhy9yxxbIE2xecem8rwysLcMpEjqorGsMpWFstmQ0xfaIdJcydEOdxYms5tatoHewyEEuw61i2T3IddaIoBEumbTGKeOMGH7yoKPzKl/f8fgqfbpS2WkCcF2KnFr8= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=jonsimons.org; spf=pass smtp.mailfrom=jonsimons.org; dkim=pass (1024-bit key) header.d=jonsimons.org header.i=@jonsimons.org header.b=lRLDQVfB; arc=none smtp.client-ip=173.203.187.118 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=jonsimons.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=jonsimons.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=jonsimons.org header.i=@jonsimons.org header.b="lRLDQVfB" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=jonsimons.org; s=20200911-u7gnnm7o; t=1791947663; bh=bhwXdTXqKiibPegCCe6J0ssUrSwH1tDhXLzg9XzxUEc=; h=From:To:Subject:Date:From; b=lRLDQVfBhb71rSUa8Mnok/GXxt7wr6KCwU4RZjlrU7E4yqyfNa1iAnbz3oNHBX4KX si1s7VXGfuHM1MKDyNxqfDhfbJMnBGuNaYW2h5r21r495MqKjKG/k3lktNk/X2KNXj v0xQqn8waBFwrbwtlIq6cUgHGCXOakdwBufovYrA= X-Auth-ID: jon@jonsimons.org Received: by smtp23.relay.iad3a.emailsrvr.com (Authenticated sender: jon-AT-jonsimons.org) with ESMTPSA id DAEF82530F; Tue, 13 Oct 2026 23:14:22 -0400 (EDT) From: Jon Simons To: git@vger.kernel.org Cc: Jon Simons Subject: [PATCH v2 12/12] remote: use strmap for apply_push_cas() Date: Tue, 13 Oct 2026 23:13:47 -0400 Message-ID: <20261014031347.50433-13-jon@jonsimons.org> X-Mailer: git-send-email 2.55.0 In-Reply-To: <20261014031347.50433-1-jon@jonsimons.org> References: <20261009192953.81794-1-jon@jonsimons.org> <20261014031347.50433-1-jon@jonsimons.org> Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Classification-ID: 20ae8d58-78b7-4215-81c6-d8119c94fa7d-13-1 Optimize apply_push_cas() by replacing a linear traversal of all advertised remote refs with strmap lookups. Before this change, applying N explicit --force-with-lease entries to M remote advertised refs entails O(N * M) calls to refname_match() in apply_one_cas(). After this change, we build a strmap of remote refs O(M), and use it for O(N * rules) lookups of the lease entry refnames. The refnames are resolved by issuing one strmap lookup for each candidate rules pattern generated with expand_ref_prefix(), as with earlier strmap conversions. p5516 timings show the speedup: Test HEAD~1 HEAD -------------------------------------------------------------------- 5516.16: empty:lease:1 0.13(0.07+0.10) 0.14(0.08+0.11) +7.7% 5516.19: empty:lease:10 0.16(0.10+0.10) 0.14(0.08+0.11) -12.5% 5516.22: empty:lease:100 0.45(0.39+0.10) 0.16(0.09+0.11) -64.4% 5516.25: mirror:lease:1 0.16(0.09+0.11) 0.17(0.10+0.12) +6.3% 5516.28: mirror:lease:10 0.19(0.12+0.10) 0.17(0.10+0.11) -10.5% 5516.31: mirror:lease:100 0.49(0.42+0.12) 0.19(0.11+0.12) -61.2% Signed-off-by: Jon Simons --- remote.c | 23 +++++++++++++++-------- 1 file changed, 15 insertions(+), 8 deletions(-) diff --git a/remote.c b/remote.c index 8dd163038d..c16f1a2b82 100644 --- a/remote.c +++ b/remote.c @@ -2991,17 +2991,17 @@ static void apply_cas_tracking(struct push_cas_option *cas, ref->check_reachable = cas->use_force_if_includes; } -static void apply_one_cas(struct ref *remote_refs, +static void apply_one_cas(struct strmap *ref_map, struct remote *remote, struct push_cas_option *cas, struct push_cas *entry) { - struct ref *ref; + struct strvec names = STRVEC_INIT; - for (ref = remote_refs; ref; ref = ref->next) { - if (ref->expect_old_sha1) - continue; - if (!refname_match(entry->refname, ref->name)) + expand_ref_prefix(&names, entry->refname); + for (size_t i = 0; i < names.nr; i++) { + struct ref *ref = strmap_get(ref_map, names.v[i]); + if (!ref || ref->expect_old_sha1) continue; if (entry->use_tracking) { apply_cas_tracking(cas, remote, ref); @@ -3010,6 +3010,7 @@ static void apply_one_cas(struct ref *remote_refs, oidcpy(&ref->old_oid_expect, &entry->expect); } } + strvec_clear(&names); } void apply_push_cas(struct push_cas_option *cas, @@ -3019,8 +3020,14 @@ void apply_push_cas(struct push_cas_option *cas, struct ref *ref; /* Apply each explicit --