From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by dpdk.org (Postfix) with ESMTP id 697AD8D35 for ; Wed, 2 Sep 2015 11:05:17 +0200 (CEST) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga102.fm.intel.com with ESMTP; 02 Sep 2015 02:05:16 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.17,452,1437462000"; d="scan'208";a="553711850" Received: from irsmsx110.ger.corp.intel.com ([163.33.3.25]) by FMSMGA003.fm.intel.com with ESMTP; 02 Sep 2015 02:05:15 -0700 Received: from irsmsx105.ger.corp.intel.com ([169.254.7.51]) by irsmsx110.ger.corp.intel.com ([163.33.3.25]) with mapi id 14.03.0224.002; Wed, 2 Sep 2015 10:05:10 +0100 From: "Ananyev, Konstantin" To: Mark Smith , "dev@dpdk.org" Thread-Topic: [PATCH] acl: Improve acl_bld.c sort_rules() Thread-Index: AQHQ4DUZ/UmuNeFyoEWu4O59oHAP9Z4o/AYQ Date: Wed, 2 Sep 2015 09:05:09 +0000 Message-ID: <2601191342CEEE43887BDE71AB97725836A81DD8@irsmsx105.ger.corp.intel.com> References: <1440617118-1583-1-git-send-email-marsmith@akamai.com> In-Reply-To: <1440617118-1583-1-git-send-email-marsmith@akamai.com> Accept-Language: en-IE, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [163.33.239.182] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [dpdk-dev] [PATCH] acl: Improve acl_bld.c sort_rules() X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 02 Sep 2015 09:05:17 -0000 > -----Original Message----- > From: Mark Smith [mailto:marks439@gmail.com] > Sent: Wednesday, August 26, 2015 8:25 PM > To: Ananyev, Konstantin; dev@dpdk.org > Cc: rsanford@akamai.com; marsmith@akamai.com > Subject: [PATCH] acl: Improve acl_bld.c sort_rules() >=20 > Replace O(n^2) list sort with an O(n log n) merge sort. > The merge sort is based on the solution suggested in: > http://cslibrary.stanford.edu/105/LinkedListProblems.pdf > Tested sort_rules() improvement: > 100K rules: O(n^2): 31382 milliseconds; O(n log n): 10 milliseconds > 259K rules: O(n^2): 133753 milliseconds; O(n log n): 22 milliseconds >=20 > Signed-off-by: Mark Smith Acked-by: Konstantin Ananyev > ---