From mboxrd@z Thu Jan  1 00:00:00 1970
From: Thomas Monjalon <thomas.monjalon@6wind.com>
Subject: Re: [PATCH] acl: Improve acl_bld.c sort_rules()
Date: Sat, 24 Oct 2015 22:54:09 +0200
Message-ID: <1765839.LM5i19bLmN@xps13>
References: <1440617118-1583-1-git-send-email-marsmith@akamai.com>
 <2601191342CEEE43887BDE71AB97725836A81DD8@irsmsx105.ger.corp.intel.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7Bit
Cc: dev@dpdk.org
To: Mark Smith <marks439@gmail.com>
Return-path: <dev-bounces@dpdk.org>
Received: from mail-wi0-f173.google.com (mail-wi0-f173.google.com
 [209.85.212.173]) by dpdk.org (Postfix) with ESMTP id 5EA768DA1
 for <dev@dpdk.org>; Sat, 24 Oct 2015 22:55:35 +0200 (CEST)
Received: by wikq8 with SMTP id q8so117499999wik.1
 for <dev@dpdk.org>; Sat, 24 Oct 2015 13:55:35 -0700 (PDT)
In-Reply-To: <2601191342CEEE43887BDE71AB97725836A81DD8@irsmsx105.ger.corp.intel.com>
List-Id: patches and discussions about DPDK <dev.dpdk.org>
List-Unsubscribe: <http://dpdk.org/ml/options/dev>,
 <mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://dpdk.org/ml/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <http://dpdk.org/ml/listinfo/dev>,
 <mailto:dev-request@dpdk.org?subject=subscribe>
Errors-To: dev-bounces@dpdk.org
Sender: "dev" <dev-bounces@dpdk.org>

> > 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
> > 
> > Signed-off-by: Mark Smith <marsmith@akamai.com>
> 
> Acked-by: Konstantin Ananyev <konstantin.ananyev@intel.com>

Applied, thanks