Stephen, what was the main reason you use red-black tree instead of dir-24-8? Did you switch to using trees because of too big memory working set of dir-24-8 algorithm?
2016-04-19 18:46 GMT+03:00 Stephen Hemminger <stephen at networkplumber.org>: > On Tue, 19 Apr 2016 14:11:11 +0300 > ????????? ??????? <kiselev99 at gmail.com> wrote: > > > Hi. > > > > Doing some test with rte_lpm (adding/deleting bgp full table rules) I > > noticed that > > rule subsystem is very slow even considering that probably it was never > > designed for using > > in a data forwarding plane. So I want to propose some changes to the > "rule" > > subsystem. > > > > I reimplemented rule part ot the lib using rte_hash, and perfomance of > > adding/deleted routes have increased dramatically. > > If increasing speed of adding deleting routes makes sence for anybody > else > > I would like to discuss my patch. > > The patch also include changes that make next_hop 64 bit, so please just > > ignore them. The rule changes are in the following > > functions only: > > > > rte_lpm2_create > > > > rule_find > > rule_add > > rule_delete > > find_previous_rule > > delete_depth_small > > delete_depth_big > > > > rte_lpm2_add > > rte_lpm2_delete > > rte_lpm2_is_rule_present > > rte_lpm2_delete_all > > > > We forked LPM back several versions ago. > I sent the patches to use BSD red-black tree for rules but the patches were > ignored. mostly because it broke ABI. > -- -- Kiselev Alexander
