From: Junio C Hamano <gitster@pobox.com>
To: Jon Simons <jon@jonsimons.org>
Cc: git@vger.kernel.org
Subject: Re: [PATCH v2 12/12] remote: use strmap for apply_push_cas()
Date: Thu, 05 Nov 2026 14:49:38 -0800 [thread overview]
Message-ID: <xmqqik2aq4fx.fsf@gitster.g> (raw)
In-Reply-To: <20261014031347.50433-13-jon@jonsimons.org> (Jon Simons's message of "Tue, 13 Oct 2026 23:13:47 -0400")
Jon Simons <jon@jonsimons.org> writes:
> 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.
OK. We may be checking multiple target refs, and we may be checking
with multiple cas rules, but the order of check does not matter, so
we do not have to be linearly scanning the remote_refs list at all.
> The refnames are resolved by issuing one strmap lookup for each
> candidate rules pattern generated with expand_ref_prefix(), as
> with earlier strmap conversions.
That trick is clever and apparently very effective ...
> 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%
... which is very nice.
Thanks.
prev parent reply other threads:[~2026-11-05 22:49 UTC|newest]
Thread overview: 37+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-10-09 19:29 [PATCH 00/15] push: speed up client-side refspec matching Jon Simons
2026-10-09 19:29 ` [PATCH 01/15] remote: validate --force-with-lease <refname> argument Jon Simons
2026-10-09 19:29 ` [PATCH 02/15] t5516: demonstrate push with "./"-prefixed source Jon Simons
2026-10-09 19:29 ` [PATCH 03/15] t5510: document fetch with "./"-prefixed branch.<name>.merge Jon Simons
2026-10-09 19:29 ` [PATCH 04/15] t/perf: add explicit delete refspec matching test Jon Simons
2026-10-09 19:29 ` [PATCH 05/15] refs: stop using mkpath() in refname_match() Jon Simons
2026-10-09 19:29 ` [PATCH 06/15] remote: use strmap for check_push_refs() Jon Simons
2026-10-09 19:29 ` [PATCH 07/15] t5516: test pushing two refspecs creating the same new branch Jon Simons
2026-10-09 19:29 ` [PATCH 08/15] t5408, t5410: test duplicate updates without relying on the client Jon Simons
2026-10-09 19:29 ` [PATCH 09/15] t5408: check refspec order with distinct destinations Jon Simons
2026-10-09 19:29 ` [PATCH 10/15] t5408: expect client-side error for duplicate destinations Jon Simons
2026-10-09 19:29 ` [PATCH 11/15] remote: reject duplicate destinations on an empty remote Jon Simons
2026-10-09 19:29 ` [PATCH 12/15] remote: use strmap for match_explicit_refs() Jon Simons
2026-10-09 19:29 ` [PATCH 13/15] t/perf: measure --force-with-lease in p5516 Jon Simons
2026-10-09 19:29 ` [PATCH 14/15] remote: restructure apply_push_cas() loops Jon Simons
2026-10-09 19:29 ` [PATCH 15/15] remote: use strmap for apply_push_cas() Jon Simons
2026-10-09 20:18 ` [PATCH 00/15] push: speed up client-side refspec matching Kristoffer Haugsbakk
2026-10-11 2:35 ` Jon Simons
2026-10-14 3:13 ` [PATCH v2 00/12] " Jon Simons
2026-10-14 3:13 ` [PATCH v2 01/12] remote: validate --force-with-lease <refname> argument Jon Simons
2026-10-14 3:13 ` [PATCH v2 02/12] t/perf: add explicit delete refspec matching test Jon Simons
2026-10-14 3:13 ` [PATCH v2 03/12] refs: stop using mkpath() in refname_match() Jon Simons
2026-10-28 21:19 ` SZEDER Gábor
2026-11-05 22:26 ` Junio C Hamano
2026-10-14 3:13 ` [PATCH v2 04/12] remote: use strmap for check_push_refs() Jon Simons
2026-10-14 3:13 ` [PATCH v2 05/12] send-pack: plug leak upon match_push_refs failure Jon Simons
2026-11-05 22:28 ` Junio C Hamano
2026-10-14 3:13 ` [PATCH v2 06/12] t5408, t5410: test duplicate updates without relying on the client Jon Simons
2026-10-14 3:13 ` [PATCH v2 07/12] t5408: check refspec order with distinct destinations Jon Simons
2026-10-14 3:13 ` [PATCH v2 08/12] remote: reject duplicate destinations on an empty remote Jon Simons
2026-11-05 22:32 ` Junio C Hamano
2026-10-14 3:13 ` [PATCH v2 09/12] remote: use strmap for match_explicit_refs() Jon Simons
2026-11-05 22:41 ` Junio C Hamano
2026-10-14 3:13 ` [PATCH v2 10/12] t/perf: measure --force-with-lease in p5516 Jon Simons
2026-10-14 3:13 ` [PATCH v2 11/12] remote: restructure apply_push_cas() loops Jon Simons
2026-10-14 3:13 ` [PATCH v2 12/12] remote: use strmap for apply_push_cas() Jon Simons
2026-11-05 22:49 ` Junio C Hamano [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=xmqqik2aq4fx.fsf@gitster.g \
--to=gitster@pobox.com \
--cc=git@vger.kernel.org \
--cc=jon@jonsimons.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox