[dpdk-dev] perfomance of rte_lpm rule subsystem

[dpdk-dev] perfomance of rte_lpm rule subsystem

[Александр Киселев]

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


P.S. the patch was made for 2.2.0 version.
P.P.S. Would it be more convinient to include full source file instead of
patch?

Re: [dpdk-dev] perfomance of rte_lpm rule subsystem

[Stephen Hemminger]

On Tue, 19 Apr 2016 14:11:11 +0300
Александр Киселев <kiselev99@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.

Re: [dpdk-dev] perfomance of rte_lpm rule subsystem

[Vladimir Medvedkin]

Hi Alexander,

Why next_hop is 64 bit long?


2016-04-19 18:46 GMT+03:00 Stephen Hemminger <stephen@networkplumber.org>:

> On Tue, 19 Apr 2016 14:11:11 +0300
> Александр Киселев <kiselev99@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.
>



-- 
Regards,
Vladimir

Re: [dpdk-dev] perfomance of rte_lpm rule subsystem

[Alexander Kiselev]

I just realizied that my patch could be confusing. I want to emphasize that it contains two completly different and independent set of changes. One is new rule subsystem and the other is 64 bit next hop. Maybe I should've prepared a patch with only rule changes, but I wanted to discuss fist and if there would be interest spend some time and make the final patch containing only rule changes. 

Please ignore the next hop changes. They have nothing to do with rule subsystem changes. The rule changes don't need new next hop and I don't want 64 bit next hop to be part of dpdk.

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

Re: [dpdk-dev] perfomance of rte_lpm rule subsystem

[Wiles, Keith]

>I just realizied that my patch could be confusing. I want to emphasize that it contains two completly different and independent set of changes. One is new rule subsystem and the other is 64 bit next hop. Maybe I should've prepared a patch with only rule changes, but I wanted to discuss fist and if there would be interest spend some time and make the final patch containing only rule changes.

Normally if you have two or more distinct changes then you need split them up into different patch sets. Each change needs to be a complete patch and independent unless you have a order issue with the patches.

> 
>
>Please ignore the next hop changes. They have nothing to do with rule subsystem changes. The rule changes don't need new next hop and I don't want 64 bit next hop to be part of dpdk.
>
>>> 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
>


Regards,
Keith

Re: [dpdk-dev] perfomance of rte_lpm rule subsystem

[Александр Киселев]

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@networkplumber.org>:

> On Tue, 19 Apr 2016 14:11:11 +0300
> Александр Киселев <kiselev99@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