Implement bsort(3) as a drop in replacement for qsort(3).
bsort(3) does not suffer from the same processing time issues that qsort(3) does, and can be CPU accelerated in the future.
Differential D36493
libc: Implement bsort(3) bitonic sorting algorithm. hselasky on Sep 8 2022, 10:21 AM. Authored by Tags None Referenced Files
Details
Implement bsort(3) as a drop in replacement for qsort(3). bsort(3) does not suffer from the same processing time issues that qsort(3) does, and can be CPU accelerated in the future. # apply patch and make -C lib/libc cp -i include/stdlib.h /usr/include/ # mergesort(3) 4096 entries cc -Wall /usr/obj/usr/img/freebsd.git/amd64.amd64/lib/libc/libc.a -O2 testsort.c && time ./a.out 12 3 2 # bsort(3) 4096 entries cc -Wall /usr/obj/usr/img/freebsd.git/amd64.amd64/lib/libc/libc.a -O2 testsort.c && time ./a.out 12 2 2 # qsort(3) 4096 entries cc -Wall /usr/obj/usr/img/freebsd.git/amd64.amd64/lib/libc/libc.a -O2 testsort.c && time ./a.out 12 1 2
Diff Detail
Event TimelineThere are a very large number of changes, so older changes are hidden. Show Older Changes Comment Actions # This C-program shows how qsort() affects ls's performance. rm -rf /tmp/kill_ls cc -O2 kill_ls.c && ./a.out time ls -f /tmp/kill_ls/ time ls /tmp/kill_ls/ Comment Actions Patch for https://github.com/izabera/qsortbench.git leaderboard 1. illumos 10.782269 1.000000 2. mine 11.456753 1.062555 3. system 17.338236 1.608032 4. glibc 11.094431 1.028951 5. freebsd 14.988042 1.390064 6. plan9 16.398762 1.520901 7. bsd 16.851684 1.562907 8. wada 18.539832 1.719474 9. musl 45.581364 4.227437 10. linux 32.343515 2.999695 11. diet 24.761722 2.296522 12. mini 75.945953 7.043597 13. uclibc 54.332577 5.039067 14. bsort 50.088221 4.645425 Comment Actions Optimisations:
New numbers from: leaderboard 1. illumos 10.854616 1.000000 2. mine 11.947272 1.100663 3. system 18.172552 1.674177 4. glibc 11.479372 1.057557 5. freebsd 15.017861 1.383546 6. plan9 16.430186 1.513659 7. bsd 16.926317 1.559366 8. wada 18.590203 1.712654 9. bsort 41.552180 3.828065 10. musl 47.432818 4.369829 11. linux 33.225245 3.060932 12. diet 25.536346 2.352579 13. mini 76.650238 7.061534 14. uclibc 55.612454 5.123392 Comment Actions Pushed sorting algorithm here aswell, for easy testing: https://github.com/hselasky/qsortbench gmake CC=clang && ./qsort 100000 --HPS
Comment Actions Will update this patch tomorrow so that the argument order matches the glibc qsort_r. Comment Actions Hi, I think the bsort_b will not work as-is, please see my comment in bsort_r.c (should it be bsort_b.c or probably removed?) for additional details.
Comment Actions Still a bit busy, but will try to look at this patch soon. Thanks for all the reviews.
Comment Actions I have a concern about this change. Qsort and bsort are both deterministic but neither is stable, and I imagine they won't sort equal keys in the same order. This could be an issue for an application that expects repeatability and should be flagged up very visibly Comment Actions For applications that expect repeatability, stable sort algorithms are required. In that case neither qsort nor bsort should be applied. Comment Actions If you want deterministic behaviour, we have mergesort in base. The only problem with mergesort is that it needs allocate additional memory. qsort and bsort are currently the only sorting algorithms that only swap two and two elements. The point with bsort is to avoid the excess CPU usage which qsort can lead to. Comment Actions @hselasky first thanks for the update and the improvement on such an important part of FreeBSD. I wouldn't think its not a POLA violation and could be integrated in -CURRENT and possibly merge to stable/13. Comment Actions Sorry for the delay, I was sick in the past week. I think the change is fine overall (with some minor nits, see comments inline; and if you are adding new interface, you would want to add them to Symbol.map, see rG597b02675751e48dd04777f1e91fee382bf3a966 for a recent example. Note that once they are added there we would be committed to the new interfaces and are expected to keep them forever). I don't particularly like the new bsort_b implementation (mainly, a translator is used to translate the block function call to a regular bsort_r call, so callers of bsort_b are slightly penalized). For a initial implementation I think we can land it as-is, but we are so close and I do feel it's better to just do it right in one goal 😊
Comment Actions @zlei: Your point is valid, and it is not very difficult to add code to make the algorithm a stable sorter, simply by including the position in the array when comparing elements! How important is this? Comment Actions I've not read though the bitonic sorting algorithm but it is great that making it a stable one is simple (and not performance penalty)!
It depends.
The element struct person { char *name, int age, ... } , and the array { { "Charlie", 20 }, { "Smith", 20 }, { "Adam ", 19}, ... }, and we want to sort the array by age. I'd suggested that do benchmarking test before implementing bitonic sorting algorithm a stable one. Comment Actions @zlei : I'll try to look into the stable-sort property of this algorithm. Else I've simply done a rebase and added some checks for BSD visible, simply. |