git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: gitster@pobox.com, vdye@github.com,
	Derrick Stolee <stolee@gmail.com>,
	Derrick Stolee <stolee@gmail.com>
Subject: [PATCH v3 4/4] p1500: add is-base performance tests
Date: Wed, 14 Aug 2024 10:31:30 +0000	[thread overview]
Message-ID: <cce9921bbd8825c3a12d32b2c8b62a2c4b06333a.1723631490.git.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.1768.v3.git.1723631490.gitgitgadget@gmail.com>

From: Derrick Stolee <stolee@gmail.com>

The previous two changes introduced a commit walking heuristic for finding
the most likely base branch for a given source. This algorithm walks
first-parent histories until reaching a collision.

This walk _should_ be very fast. Exceptions include cases where a
commit-graph file does not exist, leading to a full walk of all reachable
commits to compute generation numbers, or a case where no collision in the
first-parent history exists, leading to a walk of all first-parent history
to the root commits.

The p1500 test script guarantees a complete commit-graph file during its
setup, so we will not test that scenario. Do create a new root commit in an
effort to test the scenario of parallel first-parent histories.

Even with the extra root commit, these tests take no longer than 0.02
seconds on my machine for the Git repository. However, the results are
slightly more interesting in a copy of the Linux kernel repository:

Test
---------------------------------------------------------------
1500.2: ahead-behind counts: git for-each-ref              0.12
1500.3: ahead-behind counts: git branch                    0.12
1500.4: ahead-behind counts: git tag                       0.12
1500.5: contains: git for-each-ref --merged                0.04
1500.6: contains: git branch --merged                      0.04
1500.7: contains: git tag --merged                         0.04
1500.8: is-base check: test-tool reach (refs)              0.03
1500.9: is-base check: test-tool reach (tags)              0.03
1500.10: is-base check: git for-each-ref                   0.03
1500.11: is-base check: git for-each-ref (disjoint-base)   0.07

Signed-off-by: Derrick Stolee <stolee@gmail.com>
---
 t/perf/p1500-graph-walks.sh | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)

diff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh
index e14e7620cce..5b23ce5db93 100755
--- a/t/perf/p1500-graph-walks.sh
+++ b/t/perf/p1500-graph-walks.sh
@@ -20,6 +20,21 @@ test_expect_success 'setup' '
 		echo tag-$ref ||
 		return 1
 	done >tags &&
+
+	echo "A:HEAD" >test-tool-refs &&
+	for line in $(cat refs)
+	do
+		echo "X:$line" >>test-tool-refs || return 1
+	done &&
+	echo "A:HEAD" >test-tool-tags &&
+	for line in $(cat tags)
+	do
+		echo "X:$line" >>test-tool-tags || return 1
+	done &&
+
+	commit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&
+	git update-ref refs/heads/disjoint-base $commit &&
+
 	git commit-graph write --reachable
 '
 
@@ -47,4 +62,20 @@ test_perf 'contains: git tag --merged' '
 	xargs git tag --merged=HEAD <tags
 '
 
+test_perf 'is-base check: test-tool reach (refs)' '
+	test-tool reach get_branch_base_for_tip <test-tool-refs
+'
+
+test_perf 'is-base check: test-tool reach (tags)' '
+	test-tool reach get_branch_base_for_tip <test-tool-tags
+'
+
+test_perf 'is-base check: git for-each-ref' '
+	git for-each-ref --format="%(is-base:HEAD)" --stdin <refs
+'
+
+test_perf 'is-base check: git for-each-ref (disjoint-base)' '
+	git for-each-ref --format="%(is-base:refs/heads/disjoint-base)" --stdin <refs
+'
+
 test_done
-- 
gitgitgadget

  parent reply	other threads:[~2024-08-14 10:31 UTC|newest]

Thread overview: 23+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2024-08-01 22:10 [PATCH 0/3] git for-each-ref: is-base atom and base branches Derrick Stolee via GitGitGadget
2024-08-01 22:10 ` [PATCH 1/3] commit-reach: add get_branch_base_for_tip Derrick Stolee via GitGitGadget
2024-08-01 22:10 ` [PATCH 2/3] for-each-ref: add 'is-base' token Derrick Stolee via GitGitGadget
2024-08-01 22:10 ` [PATCH 3/3] p1500: add is-base performance tests Derrick Stolee via GitGitGadget
2024-08-01 23:06 ` [PATCH 0/3] git for-each-ref: is-base atom and base branches Junio C Hamano
2024-08-02 14:32   ` Derrick Stolee
2024-08-02 16:55     ` Junio C Hamano
2024-08-02 17:30       ` Junio C Hamano
2024-08-11 17:34 ` [PATCH v2 " Derrick Stolee via GitGitGadget
2024-08-11 17:34   ` [PATCH v2 1/3] commit-reach: add get_branch_base_for_tip Derrick Stolee via GitGitGadget
2024-08-12 20:30     ` Junio C Hamano
2024-08-13 13:39       ` Derrick Stolee
2024-08-11 17:34   ` [PATCH v2 2/3] for-each-ref: add 'is-base' token Derrick Stolee via GitGitGadget
2024-08-12 21:05     ` Junio C Hamano
2024-08-13 13:44       ` Derrick Stolee
2024-08-11 17:34   ` [PATCH v2 3/3] p1500: add is-base performance tests Derrick Stolee via GitGitGadget
2024-08-14 10:31   ` [PATCH v3 0/4] git for-each-ref: is-base atom and base branches Derrick Stolee via GitGitGadget
2024-08-14 10:31     ` [PATCH v3 1/4] commit-reach: add get_branch_base_for_tip Derrick Stolee via GitGitGadget
2024-08-14 10:31     ` [PATCH v3 2/4] commit: add gentle reference lookup method Derrick Stolee via GitGitGadget
2024-08-14 10:31     ` [PATCH v3 3/4] for-each-ref: add 'is-base' token Derrick Stolee via GitGitGadget
2024-08-14 10:31     ` Derrick Stolee via GitGitGadget [this message]
2024-08-19 19:52     ` [PATCH v3 0/4] git for-each-ref: is-base atom and base branches Junio C Hamano
2024-08-20  1:33       ` Derrick Stolee

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=cce9921bbd8825c3a12d32b2c8b62a2c4b06333a.1723631490.git.gitgitgadget@gmail.com \
    --to=gitgitgadget@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=stolee@gmail.com \
    --cc=vdye@github.com \
    /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;
as well as URLs for NNTP newsgroup(s).