[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <tqe54l$aln$1@ciao.gmane.io>
Date: Fri, 20 Jan 2023 13:32:05 -0000 (UTC)
From: uwe@...err.spb.ru (Valery Ushakov)
To: musl@...ts.openwall.com
Subject: Re: qsort
Guy <galfandary@...il.com> 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
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
