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 32257 invoked from network); 17 Feb 2023 22:53:42 -0000 Received: from second.openwall.net (193.110.157.125) by inbox.vuxu.org with ESMTPUTF8; 17 Feb 2023 22:53:42 -0000 Received: (qmail 1330 invoked by uid 550); 17 Feb 2023 22:53:38 -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 1289 invoked from network); 17 Feb 2023 22:53:37 -0000 Date: Fri, 17 Feb 2023 17:53:25 -0500 From: Rich Felker To: Bobby Bingham Cc: musl@lists.openwall.com Message-ID: <20230217225324.GZ4163@brightrain.aerifal.cx> References: <20140901071243.GA6828@duality.lan> <20230217155113.GY4163@brightrain.aerifal.cx> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20230217155113.GY4163@brightrain.aerifal.cx> User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [musl] [RFC] new qsort implementation On Fri, Feb 17, 2023 at 10:51:14AM -0500, Rich Felker wrote: > 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< multiply by 1.4 if shifted-out bit was 1" would suffice. Indeed, an approach like this (which is just taking the first-order approximation of sqrt centered at the next-lower power of two) seems to have a max error of around 6.7%, and the cost is essentially just one clz and one divide. If you're happy with up to 25% error, using the next-lower *even* power of two has a cost that's essentially just one clz. I think either could be made significantly better by using the nearest (resp. nearest-even) power of two rather than always going down, without any significant addition of costly operations. Rich