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

From: Ayush Chandekar <ayu.chandekar@gmail.com>
Date: Feb 11, 2025, 12:23 UTC
Message-ID: <CAE7as+YPKuBd+ztBerim6e1kZXZwUHdb_qjcMfZSBa4LkiyJow@mail.gmail.com>
In-Reply-To: <xmqqzfitbuy1.fsf@gitster.g>

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

While going through the code, I noticed the TODO comment: "Measure QSORT() progress", and I thought it might be interesting to explore. For big codebases, being stuck at zero would make it feel like there's no progress happening and that is why putting a progress might be better.

Show 8 quoted lines

> >  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 [*].

Oh.

Initially, I was unsure how to approach it, but I believed that tracking the highest pos value seen in comparisons could give a rough estimate of progress. However, as you pointed out, this assumes that qsort() processes elements in a structured way where the highest-indexed element isn't compared until later in the sort. I now see that this isn't a safe assumption Since there's no guarantee that progress would be reflected meaningfully, this approach isn't good.

Let me know if you have any suggestions/comments:)

Thanks, Ayush