From mboxrd@z Thu Jan  1 00:00:00 1970
From: Stephen Hemminger <stephen@networkplumber.org>
Subject: Re: [PATCH v3 1/2] librte_lpm: Improve performance of
 the delete and add functions
Date: Mon, 16 Jul 2018 10:50:46 -0700
Message-ID: <20180716105046.6cd95b7d@xeon-e3>
References: <20180711175356.035761B462@dpdk.org>
 <20180711133025.256a8ae1@xeon-e3>
 <873586679.20180716203445@therouter.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Cc: "dev@dpdk.org" <dev@dpdk.org>, Bruce Richardson
 <bruce.richardson@intel.com>
To: Alex Kiselev <alex@therouter.net>
Return-path: <dev-bounces@dpdk.org>
Received: from mail-pg1-f194.google.com (mail-pg1-f194.google.com
 [209.85.215.194]) by dpdk.org (Postfix) with ESMTP id 40DA298
 for <dev@dpdk.org>; Mon, 16 Jul 2018 19:50:49 +0200 (CEST)
Received: by mail-pg1-f194.google.com with SMTP id m19-v6so7797256pgv.3
 for <dev@dpdk.org>; Mon, 16 Jul 2018 10:50:49 -0700 (PDT)
In-Reply-To: <873586679.20180716203445@therouter.net>
List-Id: DPDK patches and discussions <dev.dpdk.org>
List-Unsubscribe: <https://mails.dpdk.org/options/dev>,
 <mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://mails.dpdk.org/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <https://mails.dpdk.org/listinfo/dev>,
 <mailto:dev-request@dpdk.org?subject=subscribe>
Errors-To: dev-bounces@dpdk.org
Sender: "dev" <dev-bounces@dpdk.org>

On Mon, 16 Jul 2018 20:34:45 +0300
Alex Kiselev <alex@therouter.net> wrote:

> > On Wed, 11 Jul 2018 20:53:46 +0300
> > Alex Kiselev <alex@therouter.net> wrote:  
> 
> >> librte_lpm: Improve lpm6 performance  
> 
> >> Rework the lpm6 rule subsystem and replace
> >> current rules algorithm complexity O(n)
> >> with hashtables which allow dealing with
> >> large (50k) rule sets.  
> 
> 
> > Wouldn't it make more sense to use something like tree, and use left/right
> > in the rules entry. That way the memory is spread and scales with the number
> > of rules.  
> I guess you are trying to propose using a radix tree. I agree, it uses memory
> more efficient than hashtable. But, it would require to add a new dpdk library implementing a
> radix tree, then we can talk about using it as a lpm rule storage.
> 

I solved this problem several years ago by using the standard BSD red-black tree.
This was used by Vyatta/Brocade/ATT and submitted to DPDK but never merged.

The BSD red-black tree is in the libbsd-dev package in Linux. The issue which
seemed to block merging was the dependency on additional packages. Since DPDK
already depends on libnuma not sure why that was an issue.