Date: Fri, 3 Jun 2016 08:35:07 +0000 (UTC) From: Hans Petter Selasky <hselasky@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r301249 - head/sys/netinet Message-ID: <201606030835.u538Z7wF017158@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: hselasky Date: Fri Jun 3 08:35:07 2016 New Revision: 301249 URL: https://svnweb.freebsd.org/changeset/base/301249 Log: Use insertion sort instead of bubble sort in TCP LRO. Replacing the bubble sort with insertion sort gives an 80% reduction in runtime on average, with randomized keys, for small partitions. If the keys are pre-sorted, insertion sort runs in linear time, and even if the keys are reversed, insertion sort is faster than bubble sort, although not by much. Update comment describing "tcp_lro_sort()" while at it. Differential Revision: https://reviews.freebsd.org/D6619 Sponsored by: Mellanox Technologies Tested by: Netflix Suggested by: Pieter de Goeje <pieter@degoeje.nl> Reviewed by: ed, gallatin, gnn, transport Modified: head/sys/netinet/tcp_lro.c Modified: head/sys/netinet/tcp_lro.c ============================================================================== --- head/sys/netinet/tcp_lro.c Fri Jun 3 08:19:47 2016 (r301248) +++ head/sys/netinet/tcp_lro.c Fri Jun 3 08:35:07 2016 (r301249) @@ -387,7 +387,8 @@ tcp_lro_msb_64(uint64_t x) * number of elements to sort and 64 is the number of sequence bits * available. The algorithm is bit-slicing the 64-bit sequence number, * sorting one bit at a time from the most significant bit until the - * least significant one, skipping the constant bits. + * least significant one, skipping the constant bits. This is + * typically called a radix sort. */ static void tcp_lro_sort(struct lro_mbuf_sort *parray, uint32_t size) @@ -399,17 +400,13 @@ tcp_lro_sort(struct lro_mbuf_sort *parra uint32_t y; repeat: - /* for small arrays bubble sort is faster */ + /* for small arrays insertion sort is faster */ if (size <= 12) { - for (x = 0; x != size; x++) { - for (y = x + 1; y != size; y++) { - if (parray[x].seq > parray[y].seq) { - /* swap entries */ - temp = parray[x]; - parray[x] = parray[y]; - parray[y] = temp; - } - } + for (x = 1; x < size; x++) { + temp = parray[x]; + for (y = x; y > 0 && temp.seq < parray[y - 1].seq; y--) + parray[y] = parray[y - 1]; + parray[y] = temp; } return; }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201606030835.u538Z7wF017158>