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 9904 invoked from network); 17 Feb 2023 15:07:18 -0000 Received: from second.openwall.net (193.110.157.125) by inbox.vuxu.org with ESMTPUTF8; 17 Feb 2023 15:07:18 -0000 Received: (qmail 5411 invoked by uid 550); 17 Feb 2023 15:07:14 -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 5371 invoked from network); 17 Feb 2023 15:07:13 -0000 Date: Fri, 17 Feb 2023 10:07:00 -0500 From: Rich Felker To: Alexander Monakov Cc: musl@lists.openwall.com, David Wang <00107082@163.com> Message-ID: <20230217150700.GX4163@brightrain.aerifal.cx> References: <4d290220.36d6.1860222ca46.Coremail.00107082@163.com> <20230201180115.GB2626@voyager> <45a265c9.2f3.1865acb64f0.Coremail.00107082@163.com> <20230216160734.GV4163@brightrain.aerifal.cx> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [musl] qsort On Fri, Feb 17, 2023 at 04:17:05PM +0300, Alexander Monakov wrote: > On Thu, 16 Feb 2023, Rich Felker wrote: > > > Mergesort is simply not a candidate unless there's a way to make > > in-place merge practical, but as I understand it that's prohibitively > > costly, and I've never really seen a comprehensible implementation > > that was convincingly correct. If I'm wrong on this and it is doable, > > we could consider that. > > *** gestures at https://www.openwall.com/lists/musl/2014/09/01/2 Thank you for reminding me of this. I had completely forgotten it. I think I had some confusion over the performance figures that, glancing at it now, might have been the exact same sort of "memcpy vs inline swap" issue we've been discussing in this thread. I'm also not sure if the bugs mentioned later in the thread were ever resolved. I really do like the size and "simplicity" of the code, and I'm optimistic that this might be the path to try taking for getting qsort performance more comparable to other implementations. Rich