From nobody Wed Apr 19 17:24:20 2023 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4Q1nhm0VS4z46DjT; Wed, 19 Apr 2023 17:24:24 +0000 (UTC) (envelope-from hselasky@freebsd.org) Received: from mail.turbocat.net (turbocat.net [IPv6:2a01:4f8:c17:6c4b::2]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4Q1nhl42GRz4Wqv; Wed, 19 Apr 2023 17:24:23 +0000 (UTC) (envelope-from hselasky@freebsd.org) Authentication-Results: mx1.freebsd.org; none Received: from [10.36.2.154] (unknown [46.212.121.255]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mail.turbocat.net (Postfix) with ESMTPSA id CDD7E26096F; Wed, 19 Apr 2023 19:24:21 +0200 (CEST) Message-ID: Date: Wed, 19 Apr 2023 19:24:20 +0200 List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:102.0) Gecko/20100101 Thunderbird/102.10.0 Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm. To: Brooks Davis Cc: src-committers@freebsd.org, dev-commits-src-all@freebsd.org, dev-commits-src-main@freebsd.org References: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> Content-Language: en-US From: Hans Petter Selasky In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Rspamd-Queue-Id: 4Q1nhl42GRz4Wqv X-Spamd-Bar: ---- X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:24940, ipnet:2a01:4f8::/32, country:DE] X-Rspamd-Pre-Result: action=no action; module=replies; Message is reply to one we originated X-ThisMailContainsUnwantedMimeParts: N On 4/19/23 17:46, Brooks Davis wrote: > On Wed, Apr 19, 2023 at 12:06:26PM +0000, Hans Petter Selasky wrote: >> The branch main has been updated by hselasky: >> >> URL: https://cgit.FreeBSD.org/src/commit/?id=8dcf3a82c54cb216df3213a013047907636a01da >> >> commit 8dcf3a82c54cb216df3213a013047907636a01da >> Author: Hans Petter Selasky >> AuthorDate: 2022-09-08 10:16:43 +0000 >> Commit: Hans Petter Selasky >> CommitDate: 2023-04-19 12:04:22 +0000 >> >> libc: Implement bsort(3) a bitonic type of sorting algorithm. >> >> The bsort(3) algorithm works by swapping objects, similarly to qsort(3), >> and does not require any significant amount of additional memory. >> >> The bsort(3) algorithm doesn't suffer from the processing time issues >> known the plague the qsort(3) family of algorithms, and is bounded by >> a complexity of O(log2(N) * log2(N) * N), where N is the number of >> elements in the sorting array. The additional complexity compared to >> mergesort(3) is a fair tradeoff in situations where no memory may >> be allocated. >> >> The bsort(3) APIs are identical to those of qsort(3), allowing for >> easy drop-in and testing. >> >> The design of the bsort(3) algorithm allows for future parallell CPU >> execution when sorting arrays. The current version of the bsort(3) >> algorithm is single threaded. This is possible because fixed areas >> of the sorting data is compared at a time, and can easily be divided >> among different CPU's to sort large arrays faster. >> >> Reviewed by: gbe@, delphij@, pauamma_gundo.com (manpages) >> Sponsored by: NVIDIA Networking >> Differential Revision: https://reviews.freebsd.org/D36493 > > Why was this needed? I'm not really a fan to adding new, non-standard > sorts without a clear use case. I understand it has some specific > advantages vs qsort, but are we going to use it? Doing so will make our > code less portable so we almost certainly can't s/qsort/bsort/. Hi Brooks, My long term plan is to get bsort() to replace qsort(), but because the two algorithms have different characteristics, then some people may complain it is good for me, but not for you. I want there to be an option besides from qsort(), which does not use malloc() as an integral part of sorting. And is faster than O(N*N) sorting (still the worst case for qsort in FreeBSD). qsort() is frequently used to do all kinds of sorting, and some pointed out that qsort() can technically be any kind of sorting algorithm, but looking around it is not. When I build applications of my own, I always use mergesort(), which depend on malloc(). Having a dependency on a certain memory allocator to get performance is not good. I want to distinguish from qsort() by calling it bsort(). If people use bsort() they know what they get cross-platform. If people use qsort() the output is random basically. It helps very little my application works on FreeBSD, but not Linux, for example. In FreeBSD qsort() is typically used for sorting files up to 16K entries per directory. Even if qsort() can explode in time, probably it's not that important. But when using qsort() for sorting millions of mathematical expressions, for example, doing number analysis, this is unacceptable. I think "C.A.R. Hoare's quicksort" technique is designed for single CPU systemsf only. Even if the best-case average is "N*log2(N)", that amount of processing cannot be split by multiple CPUs. The algorithm is serial as such. The bsort() algorithm is much more NCPU friendly, because it can split the work into fixed size smaller and independent work loads. Otherwise the work load doubles every time you merge two sorted lists. And when the number of lists to merge is fewer than the number of CPUs available, your system runs out of guts basically. > > I also note that the swap code is pointlessly slow for size > 256 and > should almost certainly use aliasing with matching words like memcpy > implementations do. Doing so would make it easier to port this code to > CHERI where that is required. I totally agree about the swap code being pointless. And I tried to look where is memswap(), but it was not there. This kind of swapping is done many places, and we could benefit from having a compiler supported memswap() function. What do you think? --HPS