From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from ms.lwn.net (ms.lwn.net [45.79.88.28]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D31FC3890FB for ; Wed, 5 Aug 2026 14:29:37 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=45.79.88.28 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1785940183; cv=none; b=FUNnYfGqYKA6oULPIR49xFbBhPTqkRh/7G1JSspkopWW5An+QqsDM1DPUI66E1w9Boarl3lmQKLTjTRgmXQZzaXWJqPYAiwl2y+F8037B/lBmnemJutd4EEHHA3+gxi0/TPnFfpMkccbASr9dQh4TRVgvBt0FzhCZ1aWIPWIwgA= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1785940183; c=relaxed/simple; bh=oAg9W+GjNtwhEnb0Ni4VVAGVpXJtJGK/GlGSBCSOhCk=; h=From:To:Cc:Subject:In-Reply-To:References:Date:Message-ID: MIME-Version:Content-Type; b=qFsgaqhk7c47CQ6H2FA8yds1KM4FOcSWh7Ilq632pS9W0jH6y1543uM4LZdZsZlGduWQbQY/KVNUGFhzLVJ/f6kRgiODcK7TUA1CnSiXxlpCCF+3qKjFZD6PBaQ0F86S6CImMC80+jeRW/rEYfad503b6uK62cIBA11nzbz8xTk= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=lwn.net; spf=pass smtp.mailfrom=lwn.net; dkim=pass (2048-bit key) header.d=lwn.net header.i=@lwn.net header.b=FJmlVJE2; arc=none smtp.client-ip=45.79.88.28 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=lwn.net Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=lwn.net Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=lwn.net header.i=@lwn.net header.b="FJmlVJE2" DKIM-Filter: OpenDKIM Filter v2.11.0 ms.lwn.net E980F408D0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=lwn.net; s=20201203; t=1785940174; bh=JZfxI5shXPwdWO6Bymbqi7Y0sEoKGSbfIIcp9PCzDzA=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=FJmlVJE2Wibngf3t93sC/2IbAgrtf9ejIEnQT5keG/aCiPgwvB9unDZdqqo2gA+V0 CE6VC7N+KcDXUkj6H5M4rH2wOlUE3QZDcia9O+SEyA+VDrTGXCoT+Q7hxKIgb3Jr+H d8eAY70XmANvf+x+9DbqqLencA3UH4VhSFa6Y1faDUuC4xvyk+WyWGs7xpI1cIoqzF j8ZfICTxVETCQkcg947iOg2NcK6MorLXxrURdwutkuN0my+97Twi73CRipScTpi2pG DjsKQ3i6JXlmM7bQpn/BEE3KFqyj1qSP76Sbf4SIRQbt5oAP8mIxq/FCKR4fvDndkD C/Ek1yeguX2pg== Received: from localhost (unknown [IPv6:2601:280:4600:27b::1fe]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (prime256v1) server-signature ECDSA (prime256v1) server-digest SHA256) (No client certificate requested) by ms.lwn.net (Postfix) with ESMTPSA id E980F408D0; Wed, 5 Aug 2026 14:29:33 +0000 (UTC) From: Jonathan Corbet To: Peter Taraba , akpm@linux-foundation.org Cc: linux-kernel@vger.kernel.org, peter.schuster.taraba@gmail.com Subject: Re: [PATCH] lib: add statsort(), a distribution/bucket sort In-Reply-To: <20260805004745.81449-1-peter.schuster.taraba@gmail.com> References: <20260804173557.782c7ed2242a19ca831c62f1@linux-foundation.org> <20260805004745.81449-1-peter.schuster.taraba@gmail.com> Date: Wed, 05 Aug 2026 08:29:33 -0600 Message-ID: <875x1or67m.fsf@trenco.lwn.net> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain Peter Taraba writes: > here are again benchamrks for large arrays: > > == n = 100000000 distribution = uniform == > statsort_longs best of 1: 9.0722 s ( 90.72 ns/elem) > sort (kernel) best of 1: 171.2293 s (1712.29 ns/elem) > qsort (libc) best of 1: 18.4959 s ( 184.96 ns/elem) > > == n = 100000000 distribution = gaussian == > statsort_longs best of 1: 8.6535 s ( 86.54 ns/elem) > sort (kernel) best of 1: 170.0339 s (1700.34 ns/elem) > qsort (libc) best of 1: 17.1339 s ( 171.34 ns/elem) > > Faster than qsort (~twice faster) and way faster than qsort(~19 times > faster) for both uniform and gaussian distribution. > > I only tested with other c file, which I have not included in this > patch. Would you like me to add tests? I can easily do so. > > As far as usage, just open your mind... I can't tell all my secrets, > because I don't want Microsoft to steal them and pretend it was their > idea :) We don't add new code to the kernel for users that are "secrets". If you have an intended user for this code, include it with the series, please. There is a recursive function in there, which we tend to avoid for the kernel. At a minimum, you would need to provide a convincing explanation of how you prevent it from overrunning the kernel stack. Until you showed up with this patch, you have never been seen on the kernel lists; what inspired you to make this change now? Was this code created with assistance from large language models? Thanks, jon