libc: Implement bsort(3) bitonic sorting algorithm.

[• hselasky]

Summary

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.

Test Plan

# 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

[bcr]

Man page looks good now. Thanks, looks very interesting.

[pauamma_gundo.com]

lib/libc/stdlib/bsort.3

25

Do we still use that? I foegot.

77–78

100–101

112–118

Unless they implement different sorting algorithms.

127–136

Check that this is what you meant.

Does this need a .Xr set_constraint_handler_s 3 like there is in memset(3)?

132

Spurious line, or mdoc subtlety I'm missing?

[pauamma_gundo.com]

lib/libc/stdlib/bsort.3

136

Based on #bsddocs discussion

[• hselasky]

I'm currently waiting for D17083 to settle. Then there will be some updates here!

[• hselasky]

Rebase patch.

[• hselasky]

Fix build.

[gbe]

LGTM form my side since D17083 has finally landed.

[• hselasky]

Will update this patch tomorrow so that the argument order matches the glibc qsort_r.

[delphij]

In D36493#828985, @hselasky wrote:

@delphij : Once your review is settled, I can do that.

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.

lib/libc/stdlib/bsort_r.c

16

Please note that in this revision, bsort_r is using the GNU qsort_r style signature, and bsort_b will not work as presented. The reason is that the qsort_b implementation was using the historical BSD compar interface, which passed the context pointer as the first parameter, and that matches how block ABI passes the block context. With the API change, the first parameter of compar is no longer the context pointer, which breaks the assumption.

If the intention was to replace the qsort(3) implementation with bitonic sort, it would be easier to implement bsort_b using the historical qsort_r style interface (which needs to be made available anyway, if that's the goal). If that's not a goal, you can use a combination of DECLARE_BLOCK and CALL_BLOCK to implement the block function instead (in which case bsort_b would no longer need to be implemented as a wrapper).

[delphij]

lib/libc/stdlib/bsort.c

178–185

I think this can be done with clz? Perhaps something like:

max = 1 << (8 * sizeof(size_t) - __builtin_clzll(n));
if (!powerof2(n))
    max <<= 1;

(assuming n >= 2, which was tested above in line 174).

[• hselasky]

Yes, my goal is to replace qsort(). I'll have a look at your comments.

[• hselasky]

Probably will work on this next week. Was a little short of time this week.

[• hselasky]

Still a bit busy, but will try to look at this patch soon. Thanks for all the reviews.

[• hselasky]

• Rebase and update patch.
• Try to respond to all comments so far.

[• hselasky]

lib/libc/stdlib/bsort_r.c

16

Issues should be fixed now!

I would like bsort() to stay apart from qsort() in the beginning. Then at some later point we can simply alias the two. This will allow proper testing, in the rare case bsort has any issue.

Please review the latest version of this patch.

[• hselasky]

Fix use of clzll (should subtract one there).

[• hselasky]

Think about systems where sizeof(size_t) != sizeof(unsigned long) .

[pauamma_gundo.com]

Manual page English LGTM. As always, I can't attest to consistency with source code.

[rb_gid.co.uk]

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

[zlei]

In D36493#853291, @rb_gid.co.uk wrote:

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

For applications that expect repeatability, stable sort algorithms are required. In that case neither qsort nor bsort should be applied.

[rb_gid.co.uk]

In D36493#853292, @zlei wrote:

For applications that expect repeatability, stable sort algorithms are required. In that case neither qsort nor bsort should be applied.

I disagree. It's a POLA violation.

[• hselasky]

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.

[gbe]

In D36493#853748, @hselasky wrote:

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.

@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.

[• hselasky]

@delphij : Are you good with the current version of this patch?

[delphij]

In D36493#854605, @hselasky wrote:

@delphij : Are you good with the current version of this patch?

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 😊

include/stdlib.h

110

This should probably live under #if __BSD_VISIBLE as it's not in POSIX.

321

Similarly -- this should be #if __BSD_VISIBLE.

367

Ditto; this is not part of the ISO C standard, so it should be covered by our namespace (I do think it's logically belonging here, nested under __EXT1_VISIBLE)

lib/libc/stdlib/bsort_r.c

18

Style: a blank line should be added between the variable definition and actual code.

[• hselasky]

@delphij : Thank you for all input. I will start working on it next week hopefully!

[• hselasky]

@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?

[zlei]

In D36493#854753, @hselasky wrote:

@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!

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)!

How important is this?

It depends.

1. For the case that natural sort, such as arrays of elements like {'a', 'c', 'b', 'b', 'd'} or {1, 3, 2, 2, 4}, both stable sort and unstable ones are competent.
2. For more complex cases, stable sort might be valuable, think of this case:

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.
When the array is dynamic, i.e. elements change after every sort, for unstable sort that may end up of different order of "Charlie" and "Smith" (for every sort).
Still it is possible we add a field original_order ( I think it is same as position in the array of bsort ) to the element and supply a comparator that sort by age and then original_order, but that might be overkilled and cumbersome.

I'd suggested that do benchmarking test before implementing bitonic sorting algorithm a stable one.

[• hselasky]

@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.

[• hselasky]

Rebase and add some checks for BSD visible.

[• hselasky]

Fix style issue by inserting blank line.

[• hselasky]

include/stdlib.h

321

It's already BSD_VISIBLE - which makes me wonder if qsort_r() should be out of BSD_VISIBLE actually.

See further up!

lib/libc/stdlib/bsort.3

25

I just copied from qsort.3 . Should I remove it?

[• hselasky]

Ping !

Can people have a look here? I'd like to get this into FreeBSD-14.

Regarding the stablesort property, this must be done by the compare function. Because this algorithm relies on SWAP() only in a binary fashion, it is not easy to compare this with stable sort.

[zlei]

In D36493#902429, @hselasky wrote:

Ping !

Can people have a look here? I'd like to get this into FreeBSD-14.

Regarding the stablesort property, this must be done by the compare function. Because this algorithm relies on SWAP() only in a binary fashion, it is not easy to compare this with stable sort.

After discussed with @delphij and some developers in Telegram group, and more thoughts on this, I have no strong options for stable sort property. This can be don by the comparator anyway.

[delphij]

LGTM (please remove the $FreeBSD$ before pushing)

lib/libc/stdlib/bsort.c

29–38

lib/libc/stdlib/bsort_s.c

4–5

This too.

[• hselasky]

I'll make those changes before commit.

[• hselasky]

I will also update the symbol maps file under the 1.7 section.

[• hselasky]

Final version (some minor changes and nits)

• limit on-stack buffer for copying objects to 256 bytes
• add check for zero object size to bsort_s().

[• hselasky]

Doing some test builds, and then I'll push this.

[• hselasky]

Add a "case 0:" for the object size.

[• hselasky]

Adding a nice SVG picture showing how the algorithm is sorting data. BSORT_TABLE_MAX=2 and n=16 elements to sort.

{F59845002}

bsort.svg23 KBDownload