On 22/07/2021 13:20, Ævar Arnfjörð Bjarmason wrote:
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%.
Being pedantic QSORT() is not necessarily a quicksort, for example
compact/qsort_s.c implements a merge sort.
I'm confused as to how we go past 100% when we only call
display_progress(progress, 0) and then stop_progress(). If my reading of
progress.c is correct then this change means we'll stop displaying a
percentage as progress->total will be zero in
static void display(struct progress *progress, uint64_t n, const char *done)
{
/* ... */
if (progress->total) {
unsigned percent = n * 100 / progress->total;
if (percent != progress->last_percent || progress_update) {
progress->last_percent = percent;
strbuf_reset(counters_sb);
strbuf_addf(counters_sb,
"%3u%% (%"PRIuMAX"/%"PRIuMAX")%s", percent,
(uintmax_t)n, (uintmax_t)progress->total,
tp);
show_update = 1;
}
} else if (progress_update) {
strbuf_reset(counters_sb);
strbuf_addf(counters_sb, "%"PRIuMAX"%s", (uintmax_t)n, tp);
show_update = 1;
}
/* ... */
}
Best Wishes
Phillip
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 <avarab@xxxxxxxxx>
---
midx.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/midx.c b/midx.c
index 9a35b0255d..eaae75ab19 100644
--- a/midx.c
+++ b/midx.c
@@ -1291,7 +1291,7 @@ int verify_midx_file(struct repository *r, const char *object_dir, unsigned flag
if (flags & MIDX_PROGRESS)
progress = start_sparse_progress(_("Sorting objects by packfile"),
- m->num_objects);
+ 0);
display_progress(progress, 0); /* TODO: Measure QSORT() progress */
QSORT(pairs, m->num_objects, compare_pair_pos_vs_id);
stop_progress(&progress);
