From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <alex@therouter.net>
Received: from relay-out2.mail.masterhost.ru (relay-out2.mail.masterhost.ru
 [83.222.12.12]) by dpdk.org (Postfix) with ESMTP id 2BDFC23C
 for <dev@dpdk.org>; Mon, 16 Jul 2018 17:41:34 +0200 (CEST)
Received: from [37.139.80.50] (helo=nw)
 by relay2.mail.masterhost.ru with esmtpa 
 envelope from <alex@therouter.net>
 authenticated with alex@therouter.net
 message id 1ff5ct-0003nx-HV; Mon, 16 Jul 2018 18:41:27 +0300
Date: Mon, 16 Jul 2018 18:41:21 +0300
From: Alex Kiselev <alex@therouter.net>
Message-ID: <154967581.20180716184121@therouter.net>
To: Stephen Hemminger <stephen@networkplumber.org>
CC: "dev@dpdk.org" <dev@dpdk.org>,
 Bruce Richardson <bruce.richardson@intel.com>
In-Reply-To: <192110016.20180716183625@therouter.net>
References: <5b4c51d3.1c69fb81.7a4de.519aSMTPIN_ADDED_MISSING@mx.google.com> 
 <20180716081732.05302ae4@xeon-e3>
 <192110016.20180716183625@therouter.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=windows-1251
Content-Transfer-Encoding: quoted-printable
X-KLMS-Rule-ID: 1
X-KLMS-Message-Action: clean
X-KLMS-AntiSpam-Lua-Profiles: 126949 [Jul 16 2018]
X-KLMS-AntiSpam-Version: 5.8.3.0
X-KLMS-AntiSpam-Envelope-From: alex@therouter.net
X-KLMS-AntiSpam-Rate: 0
X-KLMS-AntiSpam-Status: not_detected
X-KLMS-AntiSpam-Method: none
X-KLMS-AntiSpam-Info: LuaCore: 150 150
 2a697033e93a7ef849763582d9d751a194e74ff1, {rep_avail}, DmarcAF: none
X-MS-Exchange-Organization-SCL: -1
X-KLMS-AntiSpam-Interceptor-Info: scan successful
X-KLMS-AntiPhishing: not scanned, disabled by settings
X-KLMS-AntiVirus: Kaspersky Security for Linux Mail Server, version 8.0.2.16,
 not scanned, license restriction
Subject: Re: [dpdk-dev] [PATCH v5 1/2] librte_lpm: Improve performance of
	the delete and add functions
X-BeenThere: dev@dpdk.org
X-Mailman-Version: 2.1.15
Precedence: list
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>
X-List-Received-Date: Mon, 16 Jul 2018 15:41:34 -0000

=C7=E4=F0=E0=E2=F1=F2=E2=F3=E9=F2=E5, Alex.

=C2=FB =EF=E8=F1=E0=EB=E8 16 =E8=FE=EB=FF 2018 =E3., 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=20
> 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%.

--=20
Alex