Re: [RFC] Proposal adding new sorting algorithm, bsort() to libc

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