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 1557F3858D38 for ; Fri, 17 Nov 2023 10:35:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 1557F3858D38 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 1557F3858D38 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=1700217327; cv=none; b=p7PxBhhgK6OEv0hGEo6t7xnJSY+DFEUUbhjCCYsUYgDfZiA4Ymv1V/A8fdVmfNdfnbIudPE4N8tO8gs7UFkzrrPHkd+IEbegxyMmrcpAYSfznAnHCuIGshA61ViQGmdwqeB0pRbQHYHqTv1UF5o/4GKp5uweXo+p75v+du5KBsQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700217327; c=relaxed/simple; bh=mzqaag36dG3ghRWkcLlTX0sB8oJSpTl6zX6WeNH0RAU=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=tkBUHmPmCYCvxRayXdI1smrUc+tf3q2nuKnirWqjHOSSv2XjqOkQhy+Otb+PEDki8VYeZnuEEWq1c1ne6MayK86FRYGr1kW6ZBT+ogMjVfJ6dHGQGA7a2QKeoyyZ5q8EbObDzO2XcOE9Gd6rPQmWZiTy7312N9e3vwh7NxLzOwg= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1700217325; 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: in-reply-to:in-reply-to:references:references; bh=WPdH+RkaALAwpQkF5UkkLcMRSqMfQGbh7SABA9Tjkvc=; b=Bv8P+I8rsVNV8Cqve5uZdM7lTenYNrwNibf3FDmaDr0TDgi5j21q2B2ieVj11UrKArw+aR z/Gv+H0nZixQ8Bg4yK55LGymQi6l5Lw67ROqiN0VHUbIWNxT4HtwPPtO6MHzOTstulZtcQ 2Vu9pgDgOp+jeubP1k6gw59qderOJDA= Received: from mimecast-mx02.redhat.com (mx-ext.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-346-XQb46tubNC6x4fl5B85Ppw-1; Fri, 17 Nov 2023 05:35:24 -0500 X-MC-Unique: XQb46tubNC6x4fl5B85Ppw-1 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.rdu2.redhat.com [10.11.54.6]) (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 9AEFA3826D35; Fri, 17 Nov 2023 10:35:23 +0000 (UTC) Received: from oldenburg.str.redhat.com (unknown [10.2.16.3]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 1387E2166B27; Fri, 17 Nov 2023 10:35:21 +0000 (UTC) From: Florian Weimer To: Stepan Golosunov Cc: Adhemerval Zanella Netto , Andrew Pinski , Cristian =?utf-8?Q?Rodr=C3=ADguez?= , Adhemerval Zanella via Libc-alpha Subject: Re: rustc SIGILL since qsort_r patches References: <874jhxizve.fsf@oldenburg.str.redhat.com> <87fs1hd8ae.fsf@oldenburg.str.redhat.com> <87pm0lblbd.fsf@oldenburg.str.redhat.com> Date: Fri, 17 Nov 2023 11:35:20 +0100 In-Reply-To: <87pm0lblbd.fsf@oldenburg.str.redhat.com> (Florian Weimer's message of "Tue, 07 Nov 2023 17:05:42 +0100") Message-ID: <87bkbsr7kn.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.6 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain X-Spam-Status: No, score=-4.9 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: * Florian Weimer: > * Stepan Golosunov: > >> On Tue, Nov 07, 2023 at 02:04:09PM +0100, Florian Weimer wrote: >>> * Adhemerval Zanella Netto: >>> >>> > On 07/11/23 08:09, Florian Weimer wrote: >>> >> * Adhemerval Zanella Netto: >>> >> >>> >>> Just a side note that the quicksort implementation was also used for >>> >>> size (number of elements times size per element) larger than the >>> >>> installed system RAM (_SC_PHYS_PAGES / size > _SC_PAGESIZE) or >>> >>> whether malloc fails. So it is a latent issue, that did not trigger >>> >>> before by chance. >>> >> >>> >> Is it ever beneficial to call the comparison function with identical >>> >> pointers, though? >>> > >>> > Afaik this how introsort works, and I am not aware of any comparison >>> > sort with O(1) worst-case space complexity that does not require >>> > a comparison callback that work as <=>. >>> >>> I think the LLVM code will only assert if it is called with equal >>> pointers, as the array elements are expected to be distinct (hence the >>> assert). >>> >>> My question is more along these lines: If the pointers are equal, does >>> it make sense to perform the indirection function call? I guess that >>> depends on the nature of the comparison function. >>> >>> I'm not sure where equal-pointers call happens, but why wouldn't >>> something like this be an overall win? >>> >>> while (k <= n / 2) >>> { >>> size_t j = 2 * k; >> >> Shouldn't this be >> >> size_t j = 2 * k + 1; >> >> instead? Looks like the existing formula is designed for base-1 >> arrays. > > Not sure, Adhemerval? > > Obtaining the parent index would need adjusting then as well, right? I have isolated a test from stdlib/qsort.c and can confirm that heapsort_r does not actually reliably sort. Application-side, this does not sort in a mis-sort because of the insertion at the end, but the qsort is substantially slower against adversial inputs than the old implementation because it performs many more comparisons. It clearly shows quadratic behavior. I'm going to try to fix the heapsort implementation. Thanks, Florian