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
