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 26948 invoked from network); 20 Jan 2023 13:40:18 -0000 Received: from second.openwall.net (193.110.157.125) by inbox.vuxu.org with ESMTPUTF8; 20 Jan 2023 13:40:18 -0000 Received: (qmail 8119 invoked by uid 550); 20 Jan 2023 13:40: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 8087 invoked from network); 20 Jan 2023 13:40:13 -0000 X-Injected-Via-Gmane: http://gmane.org/ To: musl@lists.openwall.com From: uwe@stderr.spb.ru (Valery Ushakov) Date: Fri, 20 Jan 2023 13:32:05 -0000 (UTC) Message-ID: References: User-Agent: tin/2.6.1-20211226 ("Convalmore") (NetBSD/8.1_STABLE (macppc)) Subject: [musl] Re: qsort Guy wrote: > I have a program whose bottleneck is qsort. > I noticed that the performance with musl is much slower then with glibc. > Why is quick sort not used in musl? Sorry for a random drive by remark that is only very tangentially related to your question... quicksort is not guaranteed to be quick and can be quadratic on "bad" input. Everyone probably knows that in a kind of theoretical way, but you can run into these pathological cases in quite mundane circumstances. E.g. the NNTP overviews for the Lua mailing list archives (gmane.comp.lang.lua.general) at gmane.io used to trigger this worst case scenario for me (~120s to enter the ng and sort/thread articles with qsort(3) vs. ~15s for heapsort). -uwe