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

[PATCH v2 17/18] commit-reach: make can_all_from_reach... linear

From
Derrick Stolee <dstolee@microsoft.com>
Date
Jul 20, 2018, 16:33 UTC
Message-ID
<20180720163227.105950-18-dstolee@microsoft.com>
In-Reply-To
<20180720163227.105950-1-dstolee@microsoft.com>

The can_all_from_reach_with_flags() algorithm is currently quadratic in the worst case, because it calls the reachable() method for every 'from' without tracking which commits have already been walked or which can already reach a commit in 'to'.

Rewrite the algorithm to walk each commit a constant number of times.

We also add some optimizations that should work for the main consumer of this method: fetch negotitation (haves/wants).

The first step includes using a depth-first-search (DFS) from each 'from' commit, sorted by ascending generation number. We do not walk beyond the minimum generation number or the minimum commit date. This DFS is likely to be faster than the existing reachable() method because we expect previous ref values to be along the first-parent history.

If we find a target commit, then we mark everything in the DFS stack as a RESULT. This expands the set of targets for the other 'from' commits. We also mark the visited commits using 'assign_flag' to prevent re- walking the same commits.

We still need to clear our flags at the end, which is why we will have a total of three visits to each commit.

Performance was measured on the Linux repository using 'test-tool reach can_all_from_reach'. The input included rows seeded by tag values. The "small" case included X-rows as v4.[0-9]* and Y-rows as v3.[0-9]*. This mimics a (very large) fetch that says "I have all major v3 releases and want all major v4 releases." The "large" case included X-rows as "v4.*" and Y-rows as "v3.*". This adds all release-candidate tags to the set, which does not greatly increase the number of objects that are considered, but does increase the number of 'from' commits, demonstrating the quadratic nature of the previous code.

Small Case:
Before: 1.52 s
 After: 0.26 s
Large Case:
Before: 3.50 s
 After: 0.27 s

Note how the time increases between the two cases in the two versions. The new code increases relative to the number of commits that need to be walked, but not directly relative to the number of 'from' commits.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 122 ++++++++++++++++++++++++++++++-------------------
 commit-reach.h |   9 ++--
 upload-pack.c  |   5 +-
 3 files changed, 83 insertions(+), 53 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index f5858944fd..bc522d6840 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -514,66 +514,87 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,
 	return is_descendant_of(commit, list);
 }
 
-int reachable(struct commit *from, unsigned int with_flag,
-	      unsigned int assign_flag, time_t min_commit_date)
+static int compare_commits_by_gen(const void *_a, const void *_b)
 {
-	struct prio_queue work = { compare_commits_by_commit_date };
+	const struct commit *a = (const struct commit *)_a;
+	const struct commit *b = (const struct commit *)_b;
 
-	prio_queue_put(&work, from);
-	while (work.nr) {
-		struct commit_list *list;
-		struct commit *commit = prio_queue_get(&work);
-
-		if (commit->object.flags & with_flag) {
-			from->object.flags |= assign_flag;
-			break;
-		}
-		if (!commit->object.parsed)
-			parse_object(the_repository, &commit->object.oid);
-		if (commit->object.flags & REACHABLE)
-			continue;
-		commit->object.flags |= REACHABLE;
-		if (commit->date < min_commit_date)
-			continue;
-		for (list = commit->parents; list; list = list->next) {
-			struct commit *parent = list->item;
-			if (!(parent->object.flags & REACHABLE))
-				prio_queue_put(&work, parent);
-		}
-	}
-	from->object.flags |= REACHABLE;
-	clear_commit_marks(from, REACHABLE);
-	clear_prio_queue(&work);
-	return (from->object.flags & assign_flag);
+	if (a->generation < b->generation)
+		return -1;
+	if (a->generation > b->generation)
+		return 1;
+	return 0;
 }
 
 int can_all_from_reach_with_flag(struct object_array *from,
 				 unsigned int with_flag,
 				 unsigned int assign_flag,
-				 time_t min_commit_date)
+				 time_t min_commit_date,
+				 uint32_t min_generation)
 {
+	struct commit **list = NULL;
 	int i;
+	int result = 1;
 
+	ALLOC_ARRAY(list, from->nr);
 	for (i = 0; i < from->nr; i++) {
-		struct object *from_one = from->objects[i].item;
+		list[i] = (struct commit *)from->objects[i].item;
 
-		if (from_one->flags & assign_flag)
-			continue;
-		from_one = deref_tag(the_repository, from_one, "a from object", 0);
-		if (!from_one || from_one->type != OBJ_COMMIT) {
-			/* no way to tell if this is reachable by
-			 * looking at the ancestry chain alone, so
-			 * leave a note to ourselves not to worry about
-			 * this object anymore.
-			 */
-			from->objects[i].item->flags |= assign_flag;
-			continue;
-		}
-		if (!reachable((struct commit *)from_one, with_flag, assign_flag,
-			       min_commit_date))
+		if (parse_commit(list[i]) ||
+		    list[i]->generation < min_generation)
 			return 0;
 	}
-	return 1;
+
+	QSORT(list, from->nr, compare_commits_by_gen);
+
+	for (i = 0; i < from->nr; i++) {
+		/* DFS from list[i] */
+		struct commit_list *stack = NULL;
+
+		list[i]->object.flags |= assign_flag;
+		commit_list_insert(list[i], &stack);
+
+		while (stack) {
+			struct commit_list *parent;
+
+			if (stack->item->object.flags & with_flag) {
+				pop_commit(&stack);
+				continue;
+			}
+
+			for (parent = stack->item->parents; parent; parent = parent->next) {
+				if (parent->item->object.flags & (with_flag | RESULT))
+					stack->item->object.flags |= RESULT;
+
+				if (!(parent->item->object.flags & assign_flag)) {
+					parent->item->object.flags |= assign_flag;
+
+					if (parse_commit(parent->item) ||
+					    parent->item->date < min_commit_date ||
+					    parent->item->generation < min_generation)
+						continue;
+
+					commit_list_insert(parent->item, &stack);
+					break;
+				}
+			}
+
+			if (!parent)
+				pop_commit(&stack);
+		}
+
+		if (!(list[i]->object.flags & (with_flag | RESULT))) {
+			result = 0;
+			goto cleanup;
+		}
+	}
+
+cleanup:
+	for (i = 0; i < from->nr; i++) {
+		clear_commit_marks(list[i], RESULT);
+		clear_commit_marks(list[i], assign_flag);
+	}
+	return result;
 }
 
 int can_all_from_reach(struct commit_list *from, struct commit_list *to,
@@ -583,6 +604,7 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 	time_t min_commit_date = cutoff_by_min_date ? from->item->date : 0;
 	struct commit_list *from_iter = from, *to_iter = to;
 	int result;
+	uint32_t min_generation = GENERATION_NUMBER_INFINITY;
 
 	while (from_iter) {
 		add_object_array(&from_iter->item->object, NULL, &from_objs);
@@ -590,6 +612,9 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 		if (!parse_commit(from_iter->item)) {
 			if (from_iter->item->date < min_commit_date)
 				min_commit_date = from_iter->item->date;
+
+			if (from_iter->item->generation < min_generation)
+				min_generation = from_iter->item->generation;
 		}
 
 		from_iter = from_iter->next;
@@ -599,6 +624,9 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 		if (!parse_commit(to_iter->item)) {
 			if (to_iter->item->date < min_commit_date)
 				min_commit_date = to_iter->item->date;
+
+			if (to_iter->item->generation < min_generation)
+				min_generation = to_iter->item->generation;
 		}
 
 		to_iter->item->object.flags |= PARENT2;
@@ -607,7 +635,7 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 	}
 
 	result = can_all_from_reach_with_flag(&from_objs, PARENT2, PARENT1,
-					      min_commit_date);
+					      min_commit_date, min_generation);
 
 	while (from) {
 		clear_commit_marks(from->item, PARENT1);
diff --git a/commit-reach.h b/commit-reach.h
index aa202c9703..7d313e2975 100644
--- a/commit-reach.h
+++ b/commit-reach.h
@@ -59,19 +59,18 @@ define_commit_slab(contains_cache, enum contains_result);
 int commit_contains(struct ref_filter *filter, struct commit *commit,
 		    struct commit_list *list, struct contains_cache *cache);
 
-int reachable(struct commit *from, unsigned int with_flag,
-	      unsigned int assign_flag, time_t min_commit_date);
-
 /*
  * Determine if every commit in 'from' can reach at least one commit
  * that is marked with 'with_flag'. As we traverse, use 'assign_flag'
  * as a marker for commits that are already visited. Do not walk
- * commits with date below 'min_commit_date'.
+ * commits with date below 'min_commit_date' or generation below
+ * 'min_generation'.
  */
 int can_all_from_reach_with_flag(struct object_array *from,
 				 unsigned int with_flag,
 				 unsigned int assign_flag,
-				 time_t min_commit_date);
+				 time_t min_commit_date,
+				 uint32_t min_generation);
 int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 		       int commit_date_cutoff);
 
diff --git a/upload-pack.c b/upload-pack.c
index 11c426685d..1e498f1188 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -338,11 +338,14 @@ static int got_oid(const char *hex, struct object_id *oid)
 
 static int ok_to_give_up(void)
 {
+	uint32_t min_generation = GENERATION_NUMBER_ZERO;
+
 	if (!have_obj.nr)
 		return 0;
 
 	return can_all_from_reach_with_flag(&want_obj, THEY_HAVE,
-					    COMMON_KNOWN, oldest_have);
+					    COMMON_KNOWN, oldest_have,
+					    min_generation);
 }
 
 static int get_common_commits(void)

-- 
2.18.0.118.gd4f65b8d14
Previous: Derrick StoleeNext: Jonathan Tan
Message 102 of 118 in “Consolidate reachability logic”
  1. 00/16 Consolidate reachability logicDerrick Stolee via GitGitGadget, Jul 16, 2018
  2. 04/16 upload-pack: make reachable() more genericDerrick Stolee via GitGitGadget, Jun 19, 2018
  3. 05/16 upload-pack: refactor ok_to_give_up()Derrick Stolee via GitGitGadget, Jun 19, 2018
  4. 01/16 commit-reach: move walk methods from commit.cDerrick Stolee via GitGitGadget, Jun 25, 2018
  5. Stefan BellerJul 16, 2018
  6. Jonathan TanJul 16, 2018
  7. 02/16 commit-reach: move ref_newer from remote.cDerrick Stolee via GitGitGadget, Jun 25, 2018
  8. Stefan BellerJul 16, 2018
  9. 03/16 commit-reach: move commit_contains from ref-filterDerrick Stolee via GitGitGadget, Jun 25, 2018
  10. Stefan BellerJul 16, 2018
  11. 15/16 commit-reach: make can_all_from_reach... linearDerrick Stolee via GitGitGadget, Jun 28, 2018
  12. Stefan BellerJul 16, 2018
  13. Jonathan TanJul 17, 2018
  14. René ScharfeOct 1, 2018
  15. Derrick StoleeOct 1, 2018
  16. René ScharfeOct 1, 2018
  17. René ScharfeOct 4, 2018
  18. Derrick StoleeOct 5, 2018
  19. Jeff KingOct 5, 2018
  20. René ScharfeOct 5, 2018
  21. Jeff KingOct 5, 2018
  22. René ScharfeOct 5, 2018
  23. Jeff KingOct 5, 2018
  24. René ScharfeOct 14, 2018
  25. Derrick StoleeOct 15, 2018
  26. René ScharfeOct 15, 2018
  27. Junio C HamanoOct 16, 2018
  28. Jeff KingOct 17, 2018
  29. Jonathan NiederNov 18, 2020
  30. Jeff KingNov 18, 2020
  31. René ScharfeNov 18, 2020
  32. Ævar Arnfjörð BjarmasonOct 5, 2018
  33. Jeff KingOct 5, 2018
  34. Ævar Arnfjörð BjarmasonOct 5, 2018
  35. Jeff KingOct 5, 2018
  36. 06/16 upload-pack: generalize commit date cutoffDerrick Stolee via GitGitGadget, Jul 12, 2018
  37. Stefan BellerJul 16, 2018
  38. Derrick StoleeJul 18, 2018
  39. 07/16 commit-reach: move can_all_from_reach_with_flagsDerrick Stolee via GitGitGadget, Jul 12, 2018
  40. Jonathan TanJul 16, 2018
  41. 08/16 test-reach: create new test tool for ref_newerDerrick Stolee via GitGitGadget, Jul 13, 2018
  42. Jonathan TanJul 16, 2018
  43. Derrick StoleeJul 18, 2018
  44. 09/16 test-reach: test in_merge_basesDerrick Stolee via GitGitGadget, Jul 13, 2018
  45. 10/16 test-reach: test is_descendant_ofDerrick Stolee via GitGitGadget, Jul 13, 2018
  46. 11/16 test-reach: test get_merge_bases_manyDerrick Stolee via GitGitGadget, Jul 13, 2018
  47. Stefan BellerJul 16, 2018
  48. Jonathan TanJul 16, 2018
  49. 12/16 test-reach: test reduce_headsDerrick Stolee via GitGitGadget, Jul 13, 2018
  50. Stefan BellerJul 16, 2018
  51. Eric SunshineJul 16, 2018
  52. 13/16 test-reach: test can_all_from_reach_with_flagsDerrick Stolee via GitGitGadget, Jul 13, 2018
  53. Stefan BellerJul 16, 2018
  54. Derrick StoleeJul 18, 2018
  55. Jonathan TanJul 17, 2018
  56. 14/16 commit-reach: replace ref_newer logicDerrick Stolee via GitGitGadget, Jul 13, 2018
  57. Stefan BellerJul 16, 2018
  58. 16/16 commit-reach: use can_all_from_reachDerrick Stolee via GitGitGadget, Jul 13, 2018
  59. Stefan BellerJul 16, 2018
  60. Ramsay JonesJul 16, 2018
  61. Jeff KingJul 16, 2018
  62. Eric SunshineJul 16, 2018
  63. Jeff KingJul 16, 2018
  64. Eric SunshineJul 16, 2018
  65. Johannes SchindelinJul 18, 2018
  66. Johannes SchindelinJul 18, 2018
  67. Jeff KingJul 18, 2018
  68. Johannes SchindelinJul 19, 2018
  69. Stefan BellerJul 16, 2018
  70. Eric SunshineJul 16, 2018
  71. Derrick StoleeJul 16, 2018
  72. Johannes SchindelinJul 18, 2018
  73. Duy NguyenJul 18, 2018
  74. Junio C HamanoJul 18, 2018
  75. Derrick StoleeJul 18, 2018
  76. Johannes SchindelinJul 19, 2018
  77. Johannes SchindelinJul 19, 2018
  78. 00/18 Consolidate reachability logicDerrick Stolee, Jul 20, 2018
  79. 02/18 commit.h: remove method declarationsDerrick Stolee, Jul 20, 2018
  80. 03/18 commit-reach: move ref_newer from remote.cDerrick Stolee, Jul 20, 2018
  81. 04/18 commit-reach: move commit_contains from ref-filterDerrick Stolee, Jul 20, 2018
  82. Jonathan NiederAug 28, 2018
  83. Derrick StoleeAug 28, 2018
  84. commit-reach: correct accidental #include of C fileJonathan Nieder, Aug 28, 2018
  85. Derrick StoleeAug 28, 2018
  86. 05/18 upload-pack: make reachable() more genericDerrick Stolee, Jul 20, 2018
  87. 07/18 upload-pack: generalize commit date cutoffDerrick Stolee, Jul 20, 2018
  88. 06/18 upload-pack: refactor ok_to_give_up()Derrick Stolee, Jul 20, 2018
  89. 09/18 test-reach: create new test tool for ref_newerDerrick Stolee, Jul 20, 2018
  90. 08/18 commit-reach: move can_all_from_reach_with_flagsDerrick Stolee, Jul 20, 2018
  91. 11/18 test-reach: test is_descendant_ofDerrick Stolee, Jul 20, 2018
  92. 12/18 test-reach: test get_merge_bases_manyDerrick Stolee, Jul 20, 2018
  93. 10/18 test-reach: test in_merge_basesDerrick Stolee, Jul 20, 2018
  94. 14/18 test-reach: test can_all_from_reach_with_flagsDerrick Stolee, Jul 20, 2018
  95. 15/18 test-reach: test commit_containsDerrick Stolee, Jul 20, 2018
  96. Jonathan TanJul 23, 2018
  97. Junio C HamanoJul 25, 2018
  98. Derrick StoleeJul 25, 2018
  99. 16/18 commit-reach: replace ref_newer logicDerrick Stolee, Jul 20, 2018
  100. 01/18 commit-reach: move walk methods from commit.cDerrick Stolee, Jul 20, 2018
  101. 18/18 commit-reach: use can_all_from_reachDerrick Stolee, Jul 20, 2018
  102. 17/18 commit-reach: make can_all_from_reach... linearDerrick Stolee, Jul 20, 2018
  103. Jonathan TanJul 23, 2018
  104. Derrick StoleeAug 1, 2018
  105. Jeff KingSep 12, 2018
  106. Jeff KingSep 12, 2018
  107. Derrick StoleeSep 12, 2018
  108. 13/18 test-reach: test reduce_headsDerrick Stolee, Jul 20, 2018
  109. Stefan BellerJul 20, 2018
  110. Derrick StoleeJul 20, 2018
  111. Stefan BellerJul 20, 2018
  112. Derrick StoleeAug 1, 2018
  113. Derrick StoleeJul 20, 2018
  114. Eric SunshineJul 20, 2018
  115. Derrick StoleeJul 20, 2018
  116. Duy NguyenJul 20, 2018
  117. Derrick StoleeJul 20, 2018
  118. Junio C HamanoJul 20, 2018

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.