From owner-svn-src-all@freebsd.org Fri Jun 3 08:35:08 2016 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 854CFB68F61; Fri, 3 Jun 2016 08:35:08 +0000 (UTC) (envelope-from hselasky@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 3A2171EE9; Fri, 3 Jun 2016 08:35:08 +0000 (UTC) (envelope-from hselasky@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id u538Z7Bv017159; Fri, 3 Jun 2016 08:35:07 GMT (envelope-from hselasky@FreeBSD.org) Received: (from hselasky@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id u538Z7wF017158; Fri, 3 Jun 2016 08:35:07 GMT (envelope-from hselasky@FreeBSD.org) Message-Id: <201606030835.u538Z7wF017158@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: hselasky set sender to hselasky@FreeBSD.org using -f From: Hans Petter Selasky Date: Fri, 3 Jun 2016 08:35:07 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r301249 - head/sys/netinet X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 03 Jun 2016 08:35:08 -0000 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 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; }