Page MenuHomeFreeBSD

Use optimised complexity safe sort routine instead of the kernel's qsort

Authored by hselasky on May 20 2016, 1:27 PM.
Referenced Files
Unknown Object (File)
Sun, Jan 1, 10:03 AM
Unknown Object (File)
Mar 21 2017, 9:18 PM
Unknown Object (File)
Mar 7 2017, 4:03 AM
Unknown Object (File)
Feb 5 2017, 10:52 PM
Unknown Object (File)
Jan 19 2017, 7:30 PM
Unknown Object (File)
Dec 13 2016, 8:23 AM
Unknown Object (File)
Dec 11 2016, 7:09 AM
Unknown Object (File)
Nov 19 2016, 11:39 AM


Group Reviewers

The kernels qsort() routine can in worst case spend O(N*N) amount of comparisons before the result is sorted.

Because the sorting key is very small, 64-bits, we can use a bit-slice sorter algorithmn instead, which is faster than mergesort() and comparable() to qsort().

Diff Detail

rS FreeBSD src repository - subversion
Lint Skipped
Tests Skipped

Event Timeline

hselasky retitled this revision from to Use optimised complexity safe sort routine instead of the kernel's qsort.
hselasky updated this object.
hselasky edited the test plan for this revision. (Show Details)
hselasky set the repository for this revision to rS FreeBSD src repository - subversion.
hselasky edited edge metadata.

Implement suggestion from Drew:

  • Keep all data in same array to optimize cache line usage
  • Further optimize sorting function.
kbowling added inline comments.

Simple typo alorithm >> algorithm

hselasky edited edge metadata.

Fix spelling. Found by Kevin.

hselasky edited edge metadata.

Use ffsll() when it is provided by the CPU.

Suggested by Drew.

hselasky edited edge metadata.

Use flsll() instead of ffsll(). Else sorting result will be bit-reversed.


hselasky edited edge metadata.

Optimize sorting algorithm.

gallatin edited edge metadata.

Great work -- faster AND safer

BTW, I tested a version of this patch in our Netflix code base. When serving roughly 80Gb/s with 80K TCP connections, the old method (qsort + tcp_lro_mbuf_compare_header) used 1.4% CPU, while the new (tcp_lro_sort) used 1.1% for LRO related sorting as measured by Intel Vtune. This test was done with a sysctl toggle to switch between qsort and the new sort.

That is why I mentioned that in addition to being safer (by limiting recursion), this is also faster.

rrs edited edge metadata.

If Drew says it works I am happy with it as well :-)

This revision is now accepted and ready to land.May 25 2016, 8:11 PM

Committed to head, r300731.