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)
Sat, Mar 29, 10:40 AM
Unknown Object (File)
Mar 9 2025, 11:51 AM
Unknown Object (File)
Mar 4 2025, 3:09 PM
Unknown Object (File)
Feb 25 2025, 9:31 AM
Unknown Object (File)
Feb 25 2025, 6:38 AM
Unknown Object (File)
Feb 24 2025, 5:51 PM
Unknown Object (File)
Feb 24 2025, 11:41 AM
Unknown Object (File)
Feb 24 2025, 9:22 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

PropertyOld ValueNew Value
svn:eol-stylenullnative
\ No newline at end of property
svn:keywordsnullFreeBSD=%H
\ No newline at end of property
svn:mime-typenulltext/plain
\ No newline at end of property
# $FreeBSD$
PORTNAME= pyfda
PORTVERSION= 0.1
DISTVERSIONSUFFIX= rc6
CATEGORIES= cad python devel
MASTER_SITES= CHEESESHOP
PKGNAMEPREFIX= ${PYTHON_PKGNAMEPREFIX}
MAINTAINER= yuri@FreeBSD.org
COMMENT= GUI tool for designing and analysing discrete time filters
LICENSE= MIT
LICENSE_FILE= ${WRKSRC}/LICENSE
RUN_DEPENDS= ${PYTHON_PKGNAMEPREFIX}docutils>0:textproc/py-docutils@${FLAVOR} \
${PYTHON_PKGNAMEPREFIX}matplotlib>0:math/py-matplotlib@${FLAVOR} \
${PYNUMPY} \
${PYTHON_PKGNAMEPREFIX}scipy>0:science/py-scipy@${FLAVOR}
USES= python:3.4+ pyqt:5
USE_PYTHON= distutils autoplist noflavors
matUnsubmitted
Not Done
Inline Actions

Also, setting noflavors (which is weird, no reason to do it) means that the FLAVOR variable is empty, thus, it makes this port broken because the dependencies line end with @ with no flavor.

mat: Also, setting noflavors (which is weird, no reason to do it) means that the FLAVOR variable is…
yuriAuthorUnsubmitted
Not Done
Inline Actions

But this is an app, not a library. Shouldn't python apps all be noflavors?

yuri: But this is an app, not a library. Shouldn't python apps all be `noflavors`?
matUnsubmitted
Not Done
Inline Actions

this has a PKGNAMEPREFIX, nothing against it having noflavors.

mat: this has a PKGNAMEPREFIX, nothing against it having noflavors.
USE_PYQT= core_run gui_run widgets_run
NO_ARCH= yes
post-extract:
@${MV} ${WRKSRC}/pyfda/pyfda_log.conf ${WRKSRC}/pyfda/pyfda_log.conf.sample
@${MV} ${WRKSRC}/pyfda/pyfda_log_debug.conf ${WRKSRC}/pyfda/pyfda_log_debug.conf.sample
post-patch:
@${REINPLACE_CMD} -e " \
s|package_data={'pyfda': \['pyfda_log.conf', 'pyfda_log_debug.conf',|package_data={'pyfda': [|; \
s|data_files = \[|data_files = [('${PREFIX}/etc', ['pyfda/pyfda_log.conf.sample', 'pyfda/pyfda_log_debug.conf.sample'])|" \
${WRKSRC}/setup.py
@${REINPLACE_CMD} -e " \
s|logging.config.fileConfig(os.path.join(base_dir, rc.log_config_file))|logging.config.fileConfig(os.path.join('${PREFIX}/etc', rc.log_config_file))|" \
${WRKSRC}/pyfda/pyfdax.py
@${REINPLACE_CMD} -e " \
s|'pyfda.log'|'/tmp/pyfda.log'|" \
${WRKSRC}/pyfda/*.conf.sample
post-stage:
@${REINPLACE_CMD} -E " \
s|(.*\.sample)$$|@sample \1|" \
${WRKDIR}/.PLIST.pymodtmp
.include <bsd.port.mk>
View Options

sys/netinet/tcp_lro.c

PropertyOld ValueNew Value
svn:eol-stylenullnative
\ No newline at end of property
svn:keywordsnullFreeBSD=%H
\ No newline at end of property
svn:mime-typenulltext/plain
\ No newline at end of property
# $FreeBSD$
PORTNAME= pyfda
PORTVERSION= 0.1
DISTVERSIONSUFFIX= rc6
CATEGORIES= cad python devel
MASTER_SITES= CHEESESHOP
PKGNAMEPREFIX= ${PYTHON_PKGNAMEPREFIX}
MAINTAINER= yuri@FreeBSD.org
COMMENT= GUI tool for designing and analysing discrete time filters
LICENSE= MIT
LICENSE_FILE= ${WRKSRC}/LICENSE
RUN_DEPENDS= ${PYTHON_PKGNAMEPREFIX}docutils>0:textproc/py-docutils@${FLAVOR} \
${PYTHON_PKGNAMEPREFIX}matplotlib>0:math/py-matplotlib@${FLAVOR} \
${PYNUMPY} \
${PYTHON_PKGNAMEPREFIX}scipy>0:science/py-scipy@${FLAVOR}
USES= python:3.4+ pyqt:5
USE_PYTHON= distutils autoplist noflavors
matUnsubmitted
Not Done
Inline Actions

Also, setting noflavors (which is weird, no reason to do it) means that the FLAVOR variable is empty, thus, it makes this port broken because the dependencies line end with @ with no flavor.

mat: Also, setting noflavors (which is weird, no reason to do it) means that the FLAVOR variable is…
yuriAuthorUnsubmitted
Not Done
Inline Actions

But this is an app, not a library. Shouldn't python apps all be noflavors?

yuri: But this is an app, not a library. Shouldn't python apps all be `noflavors`?
matUnsubmitted
Not Done
Inline Actions

this has a PKGNAMEPREFIX, nothing against it having noflavors.

mat: this has a PKGNAMEPREFIX, nothing against it having noflavors.
USE_PYQT= core_run gui_run widgets_run
NO_ARCH= yes
post-extract:
@${MV} ${WRKSRC}/pyfda/pyfda_log.conf ${WRKSRC}/pyfda/pyfda_log.conf.sample
@${MV} ${WRKSRC}/pyfda/pyfda_log_debug.conf ${WRKSRC}/pyfda/pyfda_log_debug.conf.sample
post-patch:
@${REINPLACE_CMD} -e " \
s|package_data={'pyfda': \['pyfda_log.conf', 'pyfda_log_debug.conf',|package_data={'pyfda': [|; \
s|data_files = \[|data_files = [('${PREFIX}/etc', ['pyfda/pyfda_log.conf.sample', 'pyfda/pyfda_log_debug.conf.sample'])|" \
${WRKSRC}/setup.py
@${REINPLACE_CMD} -e " \
s|logging.config.fileConfig(os.path.join(base_dir, rc.log_config_file))|logging.config.fileConfig(os.path.join('${PREFIX}/etc', rc.log_config_file))|" \
${WRKSRC}/pyfda/pyfdax.py
@${REINPLACE_CMD} -e " \
s|'pyfda.log'|'/tmp/pyfda.log'|" \
${WRKSRC}/pyfda/*.conf.sample
post-stage:
@${REINPLACE_CMD} -E " \
s|(.*\.sample)$$|@sample \1|" \
${WRKDIR}/.PLIST.pymodtmp
.include <bsd.port.mk>