Date: Thu, 8 Sep 2022 12:50:28 +0200 From: Hans Petter Selasky <hps@selasky.org> To: FreeBSD Current <freebsd-current@freebsd.org>, "freebsd-arch@freebsd.org" <freebsd-arch@FreeBSD.org> Subject: [RFC] Proposal adding new sorting algorithm, bsort() to libc Message-ID: <c7df2462-e0b7-f98c-d45d-ed1c185a2e07@selasky.org>
next in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?c7df2462-e0b7-f98c-d45d-ed1c185a2e07>