This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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

On Mon, Jul 18, 2016 at 7:36 PM, Alexander Monakov <> 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]


> Thanks.
> Alexander

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]