On Mon, Feb 01, 2021 at 12:47:27PM +0000, Derrick Stolee via GitGitGadget wrote:
From: Derrick Stolee <redacted>
Note that these are only modest improvements for the case where the two
independent commits are not in the commit-graph (not until v5.10). All
algorithms get faster as more commits are indexed, which is not a
surprise. However, the cost of walking extra commits is more and more
prevalent in relative terms as more commits are indexed. Finally, the
last case allows us to jump to the minimum generation between the last
two commits (that are actually independent) so we greatly reduce the
cost in that case.
Very nice. The explanation and implementation makes sense to me.
quoted hunk ↗ jump to hunk
Signed-off-by: Derrick Stolee <redacted>
---
commit-reach.c | 28 +++++++++++++++++++++-------
1 file changed, 21 insertions(+), 7 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index d3a6e2bdd04..c2e0747fea4 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -237,15 +237,27 @@ static int remove_redundant_with_gen(struct repository *r,
{
int i, count_non_stale = 0, count_still_independent = cnt;
timestamp_t min_generation = GENERATION_NUMBER_INFINITY;
- struct commit **walk_start;
+ struct commit **walk_start, **sorted;
size_t walk_start_nr = 0, walk_start_alloc = cnt;
+ int min_gen_pos = 0;
+
+ /*
+ * Sort the input by generation number, ascending. This allows
+ * us to increase the "min_generation" limit when we discover
+ * the commit with lowest generation is STALE. The index
+ * min_gen_pos points to the current position within 'array'
+ * that is not yet known to be STALE.
+ */
+ ALLOC_ARRAY(sorted, cnt);
+ COPY_ARRAY(sorted, array, cnt);
+ QSORT(sorted, cnt, compare_commits_by_gen);
+ min_generation = commit_graph_generation(sorted[0]);
This line caught my eye, but we return early in
commit-reach.c:reduce_heads() before even calling remove_redundant()
(which itself calls remove_redundant_with_gen()), so it's always OK to
assume that we have at least one element in 'array'.
This patch and the others in v2 all look good to me.
Thanks,
Taylor