Re: [dpdk-dev] [PATCH v3 1/2] librte_lpm: Improve performance of the delete and add functions

[Stephen Hemminger <stephen@networkplumber.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.