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

From: Phillip Wood <phillip.wood123@gmail.com>
Date: Aug 5, 2021, 15:07 UTC
Message-ID: <5cf55741-d06a-f8f3-5027-02c5e1dfa672@gmail.com>
In-Reply-To: <patch-2.3-3411fe0515-20210722T121801Z-avarab@gmail.com>

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

Show 29 quoted lines

> 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@gmail.com>
> ---
>   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);
>