Re: [PATCH] Add qsort comparator consistency checking (PR71702)

[Alexander Monakov <amonakov at ispras dot ru>]

On Mon, 18 Jul 2016, Richard Biener wrote:
> Ugh.  What impact does this have on stage2 compile-time?

It doesn't seem to be high enough to be measured reliably.  I've made a trial
run with -time=time.log in BOOT_CFLAGS, but there's a lot of variability in
timings and the sum total of times ended up 1% lower on the patched compiler.

However, this patch only runs checking for vec::qsort, while I'd like to have
such checking on all qsort calls.  That would make it a bit more concerning.

It is possible to consider other schemes of limiting the impact of this checking
by restricting the subset of pairs being tested. For instance, it's possible to
run all-pairs check on a really small prefix of the sorted array (e.g. 10,
instead of 100 in the proposed patch), and for the rest of the elements, check
only a logarithmic number of pairs. This would make this checking have time
complexity O(n log n), matching qsort (but likely with a lower constant factor).
Would this scheme be appropriate?

Thanks.
Alexander