On Mon, 16 Jul 2018 20:34:45 +0300 Alex Kiselev <a...@therouter.net> wrote:
> > On Wed, 11 Jul 2018 20:53:46 +0300 > > Alex Kiselev <a...@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.
