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=-0.8 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED,
	MAILING_LIST_MULTI,RCVD_IN_MSPIKE_H2 autolearn=ham autolearn_force=no
	version=3.4.4
Received: (qmail 22029 invoked from network); 20 Jan 2023 12:55:57 -0000
Received: from second.openwall.net (193.110.157.125)
  by inbox.vuxu.org with ESMTPUTF8; 20 Jan 2023 12:55:57 -0000
Received: (qmail 11293 invoked by uid 550); 20 Jan 2023 12:55:52 -0000
Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm
Precedence: bulk
List-Post: <mailto:musl@lists.openwall.com>
List-Help: <mailto:musl-help@lists.openwall.com>
List-Unsubscribe: <mailto:musl-unsubscribe@lists.openwall.com>
List-Subscribe: <mailto:musl-subscribe@lists.openwall.com>
List-ID: <musl.lists.openwall.com>
Reply-To: musl@lists.openwall.com
Received: (qmail 10237 invoked from network); 20 Jan 2023 12:55:52 -0000
Mime-Version: 1.0
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ayaya.dev; s=key1;
	t=1674219340;
	h=from:from:reply-to:subject:subject:date:date:message-id:message-id:
	 to:to:cc:mime-version:mime-version:content-type:content-type:
	 content-transfer-encoding:content-transfer-encoding:
	 in-reply-to:in-reply-to:references:references;
	bh=V36FZI7sH3FiJFRpnaYL70t722sxP+Kw/V6I6gaK6A8=;
	b=r80qd0pIN+i6EtVc9XKpd7k7s4QlcL3ap3h95P4Yg0xy93IN6/sJJKn5YcrU4qCTBdCOQ5
	G5OUqsRjaKJTp/+wLlO6mF9RtcyeQGX+/1a9x+8LZNmwjUFN4Ef13QSlhP3Gv4799BoHgR
	Gy8b+P48Ez6dhVIn+VtFm2VuEhaTe6k=
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8
Date: Fri, 20 Jan 2023 13:55:39 +0100
Message-Id: <CPX182QJK5D6.2Y2DE5NACZ1I@sumire>
X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers.
From: "alice" <alice@ayaya.dev>
To: <musl@lists.openwall.com>
References: <CAAEi2GextYuWRK-JKtpCLxewyJ2u380m5+s=M_0P=ZBDxyX-xA@mail.gmail.com>
In-Reply-To: <CAAEi2GextYuWRK-JKtpCLxewyJ2u380m5+s=M_0P=ZBDxyX-xA@mail.gmail.com>
X-Migadu-Flow: FLOW_OUT
Subject: Re: [musl] qsort

On Fri Jan 20, 2023 at 2:49 AM CET, Guy wrote:
> Hi,
>
> I have a program whose bottleneck is qsort.
> I noticed that the performance with musl is much slower then with glibc.

diagnosing why this is the case is somewhat difficult without either seeing
the program, or (better), a specific corpus of things that are being sorted=
 in
both cases (to have a solid test case).

> Why is quick sort not used in musl?

presumably, because:

 /* Smoothsort, an adaptive variant of Heapsort.  Memory usage: O(1).
    Run time: Worst case O(n log n), close to O(n) in the mostly-sorted cas=
e. */

vanilla quicksort is O(log(n)) additional memory use, and so the optimisati=
on
is more likely to be on memory use. on top of that, the worst-case performa=
nce
of quicksort is O(n^2) (apparently), but i'm not an expert on sorting
algorithms :). so, your specific (problem) case needs a specific example to
diagnose.

commit 22263709eda9f7d692a0f484fd759f757418dbd7 is the one that replaced th=
e
old heapsort with this custom smoothsort implementation, with
52cf5c18f4ad3a7a59fb7113cf115c6fc05c7494 being the one that added the above
comment.

>
> Thanks,
> Guy