This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Add qsort comparator consistency checking (PR71702)
On Mon, Jul 18, 2016 at 7:36 PM, Alexander Monakov <amonakov@ispras.ru> wrote:
> 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?
Yes. The other option is to enable this checking not with ENABLE_CHECKING
but some new checking option, say ENABLE_CHECKING_ALGORITHMS, and
do full checking in that case.
[The -fchecking option was supposed to be eventually extended to cover more
checking subsets, thus allow -fchecking=yes,algorithms for example]
Richard.
> Thanks.
> Alexander