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