From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 7FEFB38618B1 for ; Tue, 5 Dec 2023 10:41:00 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 7FEFB38618B1 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 7FEFB38618B1 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701772861; cv=none; b=eoGXouXU0PClVmvt+AoJdLtGdg+POAtUJufim9v+/7W+6UeZ1cRbhhJeZsGPf5LXPL8b/CMX3V3E8ltMB913zA0Bs4XdyoRSpjvSlPN2UC/T2d2SuTO+bd5p8Q54WrbQ2+WTx+Kk9om4WBoO+8Dh/Jer1eM8Q+ioTkNcJ2D8ORk= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701772861; c=relaxed/simple; bh=CgrXc5kjx/4iFO6kZ4Db1eyuULrzBtlADKjSb3FZr5g=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=tUr0kkOune9L2bB1O9kXUGkvdya0Hmzu9OiEwGzlYAjo0hlH9C+midntHyz8xwZcwo+jTCNtw/D0Eqo4SmUyKC1iOC8IlmhyQWaRFRw/hcXeFfRThBYjtit78Ln7SRVzxpnEddGIqE8WKmExfKZR6Lq954DQIxYJHTwRLgOnuvY= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1701772860; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=ohg1g0aki0G1a/kTW6RQ8NyB7kZh6SLY+G0TIcWgEWw=; b=FeGUhil2kjUXi9i81m3o8vfO6NTU7pyX7CwUQ1/Kba2PVg/PVOPRDkZ+h2fVuHmuedDv7y NlNG6mfLn6YYwiEl1f2kEb1UGeT2Trhx/T2jplMWNm00Qdsg8+n2A1O1HTTCnnAZOKskUH Dk35L1m0qj9lKig9Raz4CCysnyo9R3E= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-350-eQU5P-8RPHGkoQPf2qee0Q-1; Tue, 05 Dec 2023 05:40:57 -0500 X-MC-Unique: eQU5P-8RPHGkoQPf2qee0Q-1 Received: from smtp.corp.redhat.com (int-mx09.intmail.prod.int.rdu2.redhat.com [10.11.54.9]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id B7A9283B86F; Tue, 5 Dec 2023 10:40:56 +0000 (UTC) Received: from oldenburg.str.redhat.com (unknown [10.39.192.84]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 00DC2492BC6; Tue, 5 Dec 2023 10:40:55 +0000 (UTC) From: Florian Weimer To: Adhemerval Zanella Netto Cc: libc-alpha@sourceware.org Subject: Re: Review of the qsort situation References: <87fs0ixghf.fsf@oldenburg.str.redhat.com> Date: Tue, 05 Dec 2023 11:40:54 +0100 In-Reply-To: (Adhemerval Zanella Netto's message of "Mon, 4 Dec 2023 11:32:26 -0300") Message-ID: <87msupvsnd.fsf@oldenburg.str.redhat.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.3 (gnu/linux) MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.9 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-4.6 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: * Adhemerval Zanella Netto: > On 04/12/23 10:08, Florian Weimer wrote: >> Last week, I promised to look at the qsort situation. I see two major >> issues. >>=20 >> (a) Compatibility impact of the new implementation >>=20 >> We saw two different kinds of breakage in LLVM, a hang in 389-ds-base >> (the LDAP server), and a test suite failure in notmuch. I'm pretty sure >> this is just the surface, and there is much breakage we don't know about >> yet. Particularly in proprietary software. >>=20 >> So we'd probably have to retain the old implementation and add a symbol >> version. Not great, but manageable. > > Are still compatibility issues besides the sort callback being called > with same pointer (which should be fixed yet)? Lack of stability is the major issue, and that's also not going to be fixable. But if qsort were actually faster, that might be a compelling reason to deal with the compatibility fallout. > In any case, this still a latent issues that was not triggered before > because the quicksort was not taken in most cases. On a memory pressure > situation, the quicksort will be used and we caller will face the same > compatibility issues. Memory pressure is not relevant to short arrays. The issues we saw obviously were with short arrays. >> I can try to gather more performance numbers, but I don't think this >> looks good. It's slower, and there are far-ranging compatibility >> issues. So I don't think this is the right direction. If quicksort was >> actually faster than mergesort, it might be a different discussion. > > Yes, the quicksort performance is usually worse than mergesort and I did > advertise it on cover letter. But that's really counter-intuitive. Shouldn't quicksort be faster? What if we specialize the implementation for pointer-sized values, so that swapping does not require indirect calls or conditional branches? > So we can add back a compatibility symbol or even just revert this change= , > but it does not fully solve the corner case issue on what to do if malloc > fails. Should we abort, like gcc_sort does on gcc? Should we fallback to > heapsort (it might the best option in this case)? That doesn't seem unreasonable=E2=80=94it has a fairly compact implementati= on. Thanks, Florian