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

On Thu, Aug 05 2021, Phillip Wood wrote:

On 22/07/2021 13:20, Ævar Arnfjörð Bjarmason wrote:

quoted

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)...".)