From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-1.0 required=5.0 tests=MAILING_LIST_MULTI, RCVD_IN_MSPIKE_H2 autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 15260 invoked from network); 17 Feb 2023 15:51:30 -0000 Received: from second.openwall.net (193.110.157.125) by inbox.vuxu.org with ESMTPUTF8; 17 Feb 2023 15:51:30 -0000 Received: (qmail 12267 invoked by uid 550); 17 Feb 2023 15:51:27 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com Received: (qmail 12225 invoked from network); 17 Feb 2023 15:51:26 -0000 Date: Fri, 17 Feb 2023 10:51:14 -0500 From: Rich Felker To: Bobby Bingham Cc: musl@lists.openwall.com Message-ID: <20230217155113.GY4163@brightrain.aerifal.cx> References: <20140901071243.GA6828@duality.lan> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20140901071243.GA6828@duality.lan> User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [musl] [RFC] new qsort implementation On Mon, Sep 01, 2014 at 02:12:43AM -0500, Bobby Bingham wrote: > Hi all, > > As I mentioned a while back on IRC, I've been looking into wikisort[1] > and grailsort[2] to see if either of them would be a good candidate for > use as musl's qsort. I'd forgotten about this until Alexander Monakov mentioned it in the context of the present qsort performance thread (introduced with Message-ID: ) and think it's probably worth pursuing. Apparently there was a bug with constant blocks that would need to be addressed. Since then, we've also added qsort_r. Between this changing the interface needs of the bsearch_pos function and the general avoidance in musl of special cross-component internal interfaces, I suspect it would make sense to just duplicate the bsearch code with the suitable interface as a static function in qsort.c. On performance, it looks like this already has something of an inlined element swap, which may be a big part of the difference. So to evaluate the degree to which it might be better, we really need to do the same with the existing smoothsort code and compare them apples to apples. Regarding the sqrt, nowadays musl's sqrt is basically all integer code except on targets with a native sqrt instruction, so it's probably not catastrophic to performance on softfloat archs. However, it is a little bit sketchy with respect to determinism since it's affected by (and in turn alters) the floating point environment (rounding mode, exception flags). I assume only an approximation within some reasonable bounds (to ensure the desired big-O) is needed, so it probably makes sense to do a fast integer approximation. Maybe even something that's essentially just "wordsize minus clz, >>1, 1<