Differential D6472
Use optimised complexity safe sort routine instead of the kernel's qsort Authored by • hselasky on May 20 2016, 1:27 PM. Tags None Referenced Files
Details
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
Event TimelineComment Actions Implement suggestion from Drew:
Comment Actions 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. | ||||||||||||||||||||||||||||||||||||||||||||