From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 29496 invoked by alias); 18 Jul 2016 17:36:43 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 29481 invoked by uid 89); 18 Jul 2016 17:36:41 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.6 required=5.0 tests=AWL,BAYES_00,KAM_LAZY_DOMAIN_SECURITY,RCVD_IN_DNSWL_NONE,RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy=H*F:U*amonakov, HX-Envelope-From:sk:amonako, timings, H*M:2179 X-HELO: smtp.ispras.ru Received: from smtp.ispras.ru (HELO smtp.ispras.ru) (83.149.199.79) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 18 Jul 2016 17:36:36 +0000 Received: from monopod.intra.ispras.ru (unknown [83.149.199.91]) by smtp.ispras.ru (Postfix) with ESMTP id 7A40D203F2; Mon, 18 Jul 2016 20:36:33 +0300 (MSK) Date: Mon, 18 Jul 2016 17:36:00 -0000 From: Alexander Monakov To: Richard Biener cc: GCC Patches Subject: Re: [PATCH] Add qsort comparator consistency checking (PR71702) In-Reply-To: Message-ID: References: User-Agent: Alpine 2.20.13 (LNX 116 2015-12-14) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-SW-Source: 2016-07/txt/msg01068.txt.bz2 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