From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <thomas.monjalon@6wind.com>
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)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20130820;
 h=x-gm-message-state:from:to:cc:subject:date:message-id:organization
 :user-agent:in-reply-to:references:mime-version
 :content-transfer-encoding:content-type;
 bh=2WOUmH0qz9j8ng5mhjbDj2Gw4jl4DYIvhmC+yJc9LeY=;
 b=eqqeBCoTEI5BlwCuyaK3IaKWFqkeU2gUffxCTYdkTEEMjKDSXD7XWg39S5Hk2fo4nZ
 xqv0NQG5wDa0pM2V8wiRQ+9GrOiYSYRW4+QBKQlaHwZLr60UfBdwu5rJl00+bdFKQuYj
 S6hkte5F8YZc2ZcvluHsHYTmDsN97PYK4aMZfqW67UHwArdeW20O3I4Wzm8dOov9aGay
 X4v3DKVWuVhPHKOrWE8HDo/s+nngTfZyARvI5Eyw9mY4m8jZ2hD6+i1XkJQngRUMDrOV
 VSOUL8CbgWQ5+f6Ig8bNTdgvzmo1BQmMjdG4t6FFqbwhp2y192fF6v4vPuGu0iAfyECB
 7oEA==
X-Gm-Message-State: ALoCoQl9e92wOAPArM9rHqn5Pz/zAmg0ZS3mq5bXyNbg9MpB3m+5CEqu5XpUh0YU14trrjCfREKI
X-Received: by 10.194.60.5 with SMTP id d5mr12880174wjr.97.1445720135179;
 Sat, 24 Oct 2015 13:55:35 -0700 (PDT)
Received: from xps13.localnet (APoitiers-657-1-137-120.w86-222.abo.wanadoo.fr.
 [86.222.2.120])
 by smtp.gmail.com with ESMTPSA id lb10sm29979858wjc.9.2015.10.24.13.55.34
 (version=TLSv1/SSLv3 cipher=OTHER);
 Sat, 24 Oct 2015 13:55:34 -0700 (PDT)
From: Thomas Monjalon <thomas.monjalon@6wind.com>
To: Mark Smith <marks439@gmail.com>
Date: Sat, 24 Oct 2015 22:54:09 +0200
Message-ID: <1765839.LM5i19bLmN@xps13>
Organization: 6WIND
User-Agent: KMail/4.14.10 (Linux/4.1.6-1-ARCH; KDE/4.14.11; x86_64; ; )
In-Reply-To: <2601191342CEEE43887BDE71AB97725836A81DD8@irsmsx105.ger.corp.intel.com>
References: <1440617118-1583-1-git-send-email-marsmith@akamai.com>
 <2601191342CEEE43887BDE71AB97725836A81DD8@irsmsx105.ger.corp.intel.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 7Bit
Content-Type: text/plain; charset="us-ascii"
Cc: dev@dpdk.org
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 <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>
X-List-Received-Date: Sat, 24 Oct 2015 20:55:35 -0000

> > 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