Thread (191 messages) flat view 191 messages, 12 authors, 2022-02-03
STALE1664d

[PATCH 20/25] midx: don't provide a total for QSORT() progress

From: Ævar Arnfjörð Bjarmason <hidden>
Date: 2021-06-23 17:49:08
Subsystem: the rest · Maintainer: Linus Torvalds

The quicksort algorithm can be anywhere between O(n) and O(n^2), so
providing a "num objects" as a total means that in some cases we're
going to go past 100%.

This fixes a logic error in 5ae18df9d8e (midx: during verify group
objects by packfile to speed verification, 2019-03-21), which in turn
seems to have been diligently copied from my own logic error in the
commit-graph.c code, see 890226ccb57 (commit-graph write: add
itermediate progress, 2019-01-19).

That commit-graph code of mine was removed in
1cbdbf3bef7 (commit-graph: drop count_distinct_commits() function,
2020-12-07), so we don't need to fix that too.

Signed-off-by: Ævar Arnfjörð Bjarmason <redacted>
---
 midx.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)
diff --git a/midx.c b/midx.c
index d80e68998b8..9f1b4018c1c 100644
--- a/midx.c
+++ b/midx.c
@@ -1265,8 +1265,7 @@ int verify_midx_file(struct repository *r, const char *object_dir, unsigned flag
 	}
 
 	if (flags & MIDX_PROGRESS)
-		progress = start_progress(_("Sorting objects by packfile"),
-					  m->num_objects);
+		progress = start_progress(_("Sorting objects by packfile"), 0);
 	display_progress(progress, 0); /* TODO: Measure QSORT() progress */
 	QSORT(pairs, m->num_objects, compare_pair_pos_vs_id);
 	stop_progress(&progress);
-- 
2.32.0.599.g3967b4fa4ac
Keyboard shortcuts
hback out one level
jnext message in thread
kprevious message in thread
ldrill in
Escclose help / fold thread tree
?toggle this help