Re: [PATCH 1/2] midx: show progress during QSORT operation

[Junio C Hamano <gitster@pobox.com>]

Ayush Chandekar <ayu.chandekar@gmail.com> writes:

> Add progress reporting during the QSORT operation in multi-pack-index
> verification. This helps users track the progress of large sorting
> operations.

Hmph.  If the implementation is correct (which I cannot tell), this
needs to explain why it is a bit better than saying nothing.

> +/*
> + * Limit calls to display_progress() for performance reasons.
> + * The interval here was arbitrarily chosen.
> + */
> +#define SPARSE_PROGRESS_INTERVAL (1 << 12)
> +#define midx_display_sparse_progress(progress, n) \
> +	do { \
> +		uint64_t _n = (n); \
> +		if ((_n & (SPARSE_PROGRESS_INTERVAL - 1)) == 0) \
> +			display_progress(progress, _n); \
> +	} while (0)
> +
>  struct pair_pos_vs_id
>  {
>  	uint32_t pos;
>  	uint32_t pack_int_id;
>  };
>  
> +static struct progress *sort_progress;
> +static uint64_t last_max_pos;
> +
>  static int compare_pair_pos_vs_id(const void *_a, const void *_b)
>  {
>  	struct pair_pos_vs_id *a = (struct pair_pos_vs_id *)_a;
>  	struct pair_pos_vs_id *b = (struct pair_pos_vs_id *)_b;

This is a compar callback function used by the sorting machinery,
which is called QSORT but system-provided qsort() implementations
are not necessarily quick-sort [*].

> +	
> +	if (sort_progress) {
> +		uint64_t max_pos = (a->pos > b->pos) ? a->pos : b->pos;
> +		if (max_pos > last_max_pos) {
> +			last_max_pos = max_pos;
> +			midx_display_sparse_progress(sort_progress, last_max_pos);
> +		}
> +	}

So I do not quite understand the assumption this implementation of
the progress meter makes.  

The assumption seems to be that the element in the array with the
highest index MUST not be summoned for comparison until the very end
of the sorting process, but what guarantees that?  Even if we assume
that the qsort() implementation supplied by the system implements
the divide and conquer plain vanilla quicksort, it may divide the
array into half, and then sort the top half first before it sorts
the bottom half, and doing so recursively will give you the
comparison between elements near the end of the array with the
highest index fairly early in the process, no?

And the standard does not even specify what algorithm should
internally be used to implement qsort(3), which our QSORT() macro
eventually calls, so making any assumption on the order the elements
of the array is fed to the compar callback function sounds doubly a
frigile deal.

Thanks.