Date: Thu, 8 Sep 2022 13:37:16 +0200 From: Hans Petter Selasky <hps@selasky.org> To: FreeBSD Current <freebsd-current@freebsd.org>, "freebsd-arch@freebsd.org" <freebsd-arch@FreeBSD.org> Subject: Re: [RFC] Proposal adding new sorting algorithm, bsort() to libc Message-ID: <6883e9bf-fce2-4514-e8b4-0689b4ecf6e4@selasky.org> In-Reply-To: <c7df2462-e0b7-f98c-d45d-ed1c185a2e07@selasky.org> References: <c7df2462-e0b7-f98c-d45d-ed1c185a2e07@selasky.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On 9/8/22 12:50, Hans Petter Selasky wrote: > See: > https://reviews.freebsd.org/D36493 > > Looking through base I see qsort() being used in places it shouldn't be > used. For example in fts_open(). > > If for example you fill a directory with 64k simply numerical file names > in the wrong order and ask fts_open() to sort these ascending for > example, qsort() will end stuck for a long-long time. So either switch > to mergesort, or if malloc() is unacceptable, use something like bsort() > which I've implemented in the above review as a drop-in replacement for > qsort(). The advantage with bsort() is that in can be CPU accelerated, > due to fixed comparison patterns. > > Quick sort is not always a quick sorting algorithm. Quick means simple, > and not clever this time. > > For the qsort's bad pattern, sorting 4096 entries 1024 times in a row took: > > qsort: 15 seconds > bsort: 230 milliseconds (non-CPU accelerated) > mergesort: 30 milliseconds > > The problem with qsort() is that as the array size grows, the time > consumption just gets worse and worse for the bad-patterns. > > Sorry there is no nice and fancy paper yet about this. > > --HPS > Hi, Also see the "kill_ls.c" test program I attached to D36493, which shows the direct affect of qsort() on the regular "ls" command! --HPS
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?6883e9bf-fce2-4514-e8b4-0689b4ecf6e4>