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

[Alex Kiselev <alex@therouter.net>]

Здравствуйте, Alex.

Вы писали 16 июля 2018 г., 18:36:25:


>> On Mon, 16 Jul 2018 11:05:27 +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.

>>> Signed-off-by: Alex Kiselev <alex@therouter.net>

>> Internet routers can have 1M rule sets.
>> The cost of a hash table maybe too high then?
> If I am not mistaken cuckoo hash algorithm on which the rte_hash is 
> based is just a plain array logically divided into buckets.

> So, I am not introducing any memory overhead in comparison
> with current rule storage implementation that uses a plain array.

Strictly speaking I do, since I use a multiplier 1.2 when calculating
hash size based on the given number of rules. So, overhead is 20%.

-- 
Alex