From mboxrd@z Thu Jan  1 00:00:00 1970
From: Alex Kiselev <alex@therouter.net>
Subject: Re: [PATCH v5 1/2] librte_lpm: Improve performance of
	the delete and add functions
Date: Mon, 16 Jul 2018 18:36:25 +0300
Message-ID: <192110016.20180716183625@therouter.net>
References: <5b4c51d3.1c69fb81.7a4de.519aSMTPIN_ADDED_MISSING@mx.google.com>
 <20180716081732.05302ae4@xeon-e3>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Cc: "dev@dpdk.org" <dev@dpdk.org>,
 Bruce Richardson <bruce.richardson@intel.com>
To: Stephen Hemminger <stephen@networkplumber.org>
Return-path: <dev-bounces@dpdk.org>
Received: from relay-out4.mail.masterhost.ru (relay-out4.mail.masterhost.ru
 [83.222.12.14]) by dpdk.org (Postfix) with ESMTP id 11D5123C
 for <dev@dpdk.org>; Mon, 16 Jul 2018 17:36:41 +0200 (CEST)
In-Reply-To: <20180716081732.05302ae4@xeon-e3>
List-Id: DPDK patches and discussions <dev.dpdk.org>
List-Unsubscribe: <https://mails.dpdk.org/options/dev>,
 <mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://mails.dpdk.org/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <https://mails.dpdk.org/listinfo/dev>,
 <mailto:dev-request@dpdk.org?subject=subscribe>
Errors-To: dev-bounces@dpdk.org
Sender: "dev" <dev-bounces@dpdk.org>


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


-- 
Alex