Page MenuHomeFreeBSD
Differential D6472

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

Authored by • hselasky on May 20 2016, 1:27 PM.
Tags
None
Referenced Files
Unknown Object (File)
Fri, Sep 18, 1:03 AM
Unknown Object (File)
Sun, Sep 13, 12:57 PM
Unknown Object (File)
Thu, Sep 10, 8:56 PM
Unknown Object (File)
Mon, Sep 7, 11:19 PM
Unknown Object (File)
Sat, Sep 5, 10:59 AM
Unknown Object (File)
Sat, Sep 5, 9:36 AM
Unknown Object (File)
Sat, Sep 5, 7:28 AM
Unknown Object (File)
Sat, Sep 5, 5:56 AM
View All Files
Subscribers
imp
kbowling

Details

Reviewers
gallatin
rrs
sepherosa_gmail.com
gnn
Group Reviewers
transport
Summary

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

Repository
rS FreeBSD src repository - subversion
Lint
Lint Skipped
Unit
Tests Skipped

Event Timeline

• hselasky updated this revision to Diff 16619.May 20 2016, 1:27 PM
• 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 added reviewers: gallatin, sepherosa_gmail.com, gnn, rrs.
• hselasky set the repository for this revision to rS FreeBSD src repository - subversion.
Herald added a reviewer: transport. · View Herald TranscriptMay 20 2016, 1:27 PM
Herald added a subscriber: imp. · View Herald Transcript
• hselasky updated this revision to Diff 16634.May 20 2016, 5:35 PM
• hselasky edited edge metadata.

Implement suggestion from Drew:

  • Keep all data in same array to optimize cache line usage
  • Further optimize sorting function.
Herald edited edge metadata. · View Herald TranscriptMay 20 2016, 5:35 PM
kbowling added a subscriber: kbowling.May 20 2016, 6:01 PM
kbowling added inline comments.
sys/netinet/tcp_lro.c
384

Simple typo alorithm >> algorithm

• hselasky updated this revision to Diff 16636.May 20 2016, 6:17 PM
• hselasky edited edge metadata.

Fix spelling. Found by Kevin.

Herald edited edge metadata. · View Herald TranscriptMay 20 2016, 6:17 PM
• hselasky marked an inline comment as done.May 20 2016, 6:17 PM

Fixed.

sepherosa_gmail.com accepted this revision.May 23 2016, 2:11 AM
sepherosa_gmail.com edited edge metadata.

Looks good to me.

• hselasky updated this revision to Diff 16736.May 23 2016, 3:29 PM
• hselasky edited edge metadata.

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

Suggested by Drew.

Herald edited edge metadata. · View Herald TranscriptMay 23 2016, 3:29 PM
• hselasky updated this revision to Diff 16749.May 23 2016, 9:14 PM
• hselasky edited edge metadata.

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

--HPS

Herald edited edge metadata. · View Herald TranscriptMay 23 2016, 9:14 PM
• hselasky updated this revision to Diff 16802.May 24 2016, 1:57 PM
• hselasky edited edge metadata.

Optimize sorting algorithm.

Herald edited edge metadata. · View Herald TranscriptMay 24 2016, 1:57 PM
gallatin accepted this revision.May 25 2016, 4:00 PM
gallatin edited edge metadata.

Great work -- faster AND safer

gallatin added a comment.EditedMay 25 2016, 4:05 PM

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 accepted this revision.May 25 2016, 8:11 PM
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
• hselasky closed this revision.May 29 2016, 10:54 AM

Committed to head, r300731.

Revision Contents
Changeset List

PathSize
sys/
netinet/
10 lines
133 lines

Diff 16749

View Options

sys/netinet/tcp_lro.h

Loading...
View Options

sys/netinet/tcp_lro.c

Loading...