Subject: Re: [PATCH 2/3] midx: don't provide a total for QSORT() progress

From: Ævar Arnfjörð Bjarmason <[email-masked]>
Date: Thu, 05 Aug 2021 21:07:36 +0200

On Thu, Aug 05 2021, Phillip Wood wrote:

> 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;
> 	}
> 	/* ... */
> }

Hrm, now I'm also confused. Yes you're right. This whole patch doesn't
make sense.

I.e. it's perfectly fine to provide a target of <num> for QSORT and then
use display_progress() just to bump the progress bar's display like
this, and we have other code in commit-graph.c that does the same.

I think I might have (badly) extracted this patch from some WIP work
where I was giving qsort() calls progress of some sort, or maybe I was
just being stupid...

(I have a few local experiments in progress bar output, one of those is
that you can give the API a <num> target, and not be sure if it'll be
O(n), O(log(n)), O(n^2) etc, and we'll show progress output
appropriately, i.e. "still working, at X items of work for N, so north
of O(N)...".)