git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v5 2/5] connected: do not sort input revisions

From
Patrick Steinhardt <ps@pks.im>
Date
Aug 9, 2021, 08:11 UTC
Message-ID
<d3f498a5633d88403381aefca58c8b11e1194831.1628496539.git.ps@pks.im>
In-Reply-To
<cover.1628496538.git.ps@pks.im>

In order to compute whether objects reachable from a set of tips are all connected, we do a revision walk with these tips as positive references and `--not --all`. `--not --all` will cause the revision walk to load all preexisting references as uninteresting, which can be very expensive in repositories with many references.

Benchmarking the git-rev-list(1) command highlights that by far the most expensive single phase is initial sorting of the input revisions: after all references have been loaded, we first sort commits by author date. In a real-world repository with about 2.2 million references, it makes up about 40% of the total runtime of git-rev-list(1).

Ultimately, the connectivity check shouldn't really bother about the order of input revisions at all. We only care whether we can actually walk all objects until we hit the cut-off point. So sorting the input is a complete waste of time.

Introduce a new "--unsorted-input" flag to git-rev-list(1) which will cause it to not sort the commits and adjust the connectivity check to always pass the flag. This results in the following speedups, executed in a clone of gitlab-org/gitlab [1]:

    Benchmark #1: git rev-list  --objects --quiet --not --all --not $(cat newrev)
      Time (mean ± σ):      7.639 s ±  0.065 s    [User: 7.304 s, System: 0.335 s]
      Range (min … max):    7.543 s …  7.742 s    10 runs
    Benchmark #2: git rev-list --unsorted-input --objects --quiet --not --all --not $newrev
      Time (mean ± σ):      4.995 s ±  0.044 s    [User: 4.657 s, System: 0.337 s]
      Range (min … max):    4.909 s …  5.048 s    10 runs
    Summary
      'git rev-list --unsorted-input --objects --quiet --not --all --not $(cat newrev)' ran
        1.53 ± 0.02 times faster than 'git rev-list  --objects --quiet --not --all --not $newrev'
[1]: https://gitlab.com/gitlab-org/gitlab.git. Note that not all refs
     are visible to clients.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 Documentation/rev-list-options.txt |  8 +++++++-
 connected.c                        |  1 +
 revision.c                         |  9 +++++++++
 t/t6000-rev-list-misc.sh           | 31 ++++++++++++++++++++++++++++++
 4 files changed, 48 insertions(+), 1 deletion(-)
diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 24569b06d1..b7bd27e171 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -968,6 +968,11 @@ list of the missing objects.  Object IDs are prefixed with a ``?'' character.
 	objects.
 endif::git-rev-list[]
 
+--unsorted-input::
+	Show commits in the order they were given on the command line instead
+	of sorting them in reverse chronological order by commit time. Cannot
+	be combined with `--no-walk` or `--no-walk=sorted`.
+
 --no-walk[=(sorted|unsorted)]::
 	Only show the given commits, but do not traverse their ancestors.
 	This has no effect if a range is specified. If the argument
@@ -975,7 +980,8 @@ endif::git-rev-list[]
 	given on the command line. Otherwise (if `sorted` or no argument
 	was given), the commits are shown in reverse chronological order
 	by commit time.
-	Cannot be combined with `--graph`.
+	Cannot be combined with `--graph`. Cannot be combined with
+	`--unsorted-input` if `sorted` or no argument was given.
 
 --do-walk::
 	Overrides a previous `--no-walk`.
diff --git a/connected.c b/connected.c
index b18299fdf0..b5f9523a5f 100644
--- a/connected.c
+++ b/connected.c
@@ -106,6 +106,7 @@ int check_connected(oid_iterate_fn fn, void *cb_data,
 	if (opt->progress)
 		strvec_pushf(&rev_list.args, "--progress=%s",
 			     _("Checking connectivity"));
+	strvec_push(&rev_list.args, "--unsorted-input");
 
 	rev_list.git_cmd = 1;
 	rev_list.env = opt->env;
diff --git a/revision.c b/revision.c
index 86bbcd10d2..47541407d2 100644
--- a/revision.c
+++ b/revision.c
@@ -2256,6 +2256,10 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 	} else if (!strcmp(arg, "--author-date-order")) {
 		revs->sort_order = REV_SORT_BY_AUTHOR_DATE;
 		revs->topo_order = 1;
+	} else if (!strcmp(arg, "--unsorted-input")) {
+		if (revs->no_walk)
+			die(_("--unsorted-input is incompatible with --no-walk"));
+		revs->unsorted_input = 1;
 	} else if (!strcmp(arg, "--early-output")) {
 		revs->early_output = 100;
 		revs->topo_order = 1;
@@ -2651,8 +2655,13 @@ static int handle_revision_pseudo_opt(const char *submodule,
 	} else if (!strcmp(arg, "--not")) {
 		*flags ^= UNINTERESTING | BOTTOM;
 	} else if (!strcmp(arg, "--no-walk")) {
+		if (!revs->no_walk && revs->unsorted_input)
+			die(_("--no-walk is incompatible with --unsorted-input"));
 		revs->no_walk = 1;
 	} else if (skip_prefix(arg, "--no-walk=", &optarg)) {
+		if (!revs->no_walk && revs->unsorted_input)
+			die(_("--no-walk is incompatible with --unsorted-input"));
+
 		/*
 		 * Detached form ("--no-walk X" as opposed to "--no-walk=X")
 		 * not allowed, since the argument is optional.
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index 12def7bcbf..ef849e5bc8 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -169,4 +169,35 @@ test_expect_success 'rev-list --count --objects' '
 	test_line_count = $count actual
 '
 
+test_expect_success 'rev-list --unsorted-input results in different sorting' '
+	git rev-list --unsorted-input HEAD HEAD~ >first &&
+	git rev-list --unsorted-input HEAD~ HEAD >second &&
+	! test_cmp first second &&
+	sort first >first.sorted &&
+	sort second >second.sorted &&
+	test_cmp first.sorted second.sorted
+'
+
+test_expect_success 'rev-list --unsorted-input incompatible with --no-walk' '
+	cat >expect <<-EOF &&
+		fatal: --no-walk is incompatible with --unsorted-input
+	EOF
+	test_must_fail git rev-list --unsorted-input --no-walk HEAD 2>error &&
+	test_cmp expect error &&
+	test_must_fail git rev-list --unsorted-input --no-walk=sorted HEAD 2>error &&
+	test_cmp expect error &&
+	test_must_fail git rev-list --unsorted-input --no-walk=unsorted HEAD 2>error &&
+	test_cmp expect error &&
+
+	cat >expect <<-EOF &&
+		fatal: --unsorted-input is incompatible with --no-walk
+	EOF
+	test_must_fail git rev-list --no-walk --unsorted-input HEAD 2>error &&
+	test_cmp expect error &&
+	test_must_fail git rev-list --no-walk=sorted --unsorted-input HEAD 2>error &&
+	test_cmp expect error &&
+	test_must_fail git rev-list --no-walk=unsorted --unsorted-input HEAD 2>error &&
+	test_cmp expect error
+'
+
 test_done

-- 
2.32.0
Previous: Patrick SteinhardtNext: Patrick Steinhardt
Message 61 of 64 in “Speed up connectivity checks via bitmaps”
  1. 0/3 Speed up connectivity checks via bitmapsPatrick Steinhardt, Jun 28, 2021
  2. 1/3 p5400: add perf tests for git-receive-pack(1)Patrick Steinhardt, Jun 28, 2021
  3. Ævar Arnfjörð BjarmasonJun 28, 2021
  4. Patrick SteinhardtJun 29, 2021
  5. Ævar Arnfjörð BjarmasonJun 29, 2021
  6. 2/3 receive-pack: skip connectivity checks on delete-only commandsPatrick Steinhardt, Jun 28, 2021
  7. Ævar Arnfjörð BjarmasonJun 28, 2021
  8. Ævar Arnfjörð BjarmasonJun 28, 2021
  9. Patrick SteinhardtJun 29, 2021
  10. Jeff KingJun 30, 2021
  11. Jeff KingJun 30, 2021
  12. Patrick SteinhardtJun 30, 2021
  13. 3/3 connected: implement connectivity check using bitmapsPatrick Steinhardt, Jun 28, 2021
  14. Taylor BlauJun 28, 2021
  15. Taylor BlauJun 29, 2021
  16. Jeff KingJun 30, 2021
  17. Taylor BlauJun 30, 2021
  18. Jeff KingJun 30, 2021
  19. Taylor BlauJul 2, 2021
  20. Jeff KingJul 2, 2021
  21. Jeff KingJun 30, 2021
  22. Patrick SteinhardtJul 20, 2021
  23. 0/4 Speed up connectivity checksPatrick Steinhardt, Aug 2, 2021
  24. 1/4 connected: do not sort input revisionsPatrick Steinhardt, Aug 2, 2021
  25. Ævar Arnfjörð BjarmasonAug 2, 2021
  26. Patrick SteinhardtAug 3, 2021
  27. Ævar Arnfjörð BjarmasonAug 4, 2021
  28. Junio C HamanoAug 2, 2021
  29. Patrick SteinhardtAug 3, 2021
  30. Junio C HamanoAug 3, 2021
  31. 2/4 revision: stop retrieving reference twicePatrick Steinhardt, Aug 2, 2021
  32. Ævar Arnfjörð BjarmasonAug 2, 2021
  33. 3/4 revision: avoid loading object headers multiple timesPatrick Steinhardt, Aug 2, 2021
  34. Ævar Arnfjörð BjarmasonAug 2, 2021
  35. Patrick SteinhardtAug 5, 2021
  36. Junio C HamanoAug 2, 2021
  37. Patrick SteinhardtAug 3, 2021
  38. Patrick SteinhardtAug 6, 2021
  39. 4/4 revision: avoid hitting packfiles when commits are in commit-graphPatrick Steinhardt, Aug 2, 2021
  40. Junio C HamanoAug 2, 2021
  41. Patrick SteinhardtAug 3, 2021
  42. Junio C HamanoAug 3, 2021
  43. Patrick SteinhardtAug 5, 2021
  44. Junio C HamanoAug 5, 2021
  45. Ævar Arnfjörð BjarmasonAug 4, 2021
  46. 0/6 Speed up connectivity checksPatrick Steinhardt, Aug 5, 2021
  47. 1/6 revision: separate walk and unsorted flagsPatrick Steinhardt, Aug 5, 2021
  48. Junio C HamanoAug 5, 2021
  49. 2/6 connected: do not sort input revisionsPatrick Steinhardt, Aug 5, 2021
  50. Junio C HamanoAug 5, 2021
  51. Patrick SteinhardtAug 6, 2021
  52. Junio C HamanoAug 6, 2021
  53. 3/6 revision: stop retrieving reference twicePatrick Steinhardt, Aug 5, 2021
  54. 4/6 revision: avoid loading object headers multiple timesPatrick Steinhardt, Aug 5, 2021
  55. 5/6 commit-graph: split out function to search commit positionPatrick Steinhardt, Aug 5, 2021
  56. 6/6 revision: avoid hitting packfiles when commits are in commit-graphPatrick Steinhardt, Aug 5, 2021
  57. 0/5 Speed up connectivity checksPatrick Steinhardt, Aug 9, 2021
  58. Patrick SteinhardtAug 9, 2021
  59. 0/5 Speed up connectivity checksPatrick Steinhardt, Aug 9, 2021
  60. 1/5 revision: separate walk and unsorted flagsPatrick Steinhardt, Aug 9, 2021
  61. 2/5 connected: do not sort input revisionsPatrick Steinhardt, Aug 9, 2021
  62. 3/5 revision: stop retrieving reference twicePatrick Steinhardt, Aug 9, 2021
  63. 4/5 commit-graph: split out function to search commit positionPatrick Steinhardt, Aug 9, 2021
  64. 5/5 revision: avoid hitting packfiles when commits are in commit-graphPatrick Steinhardt, Aug 9, 2021

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.