From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm0-f66.google.com (mail-wm0-f66.google.com [74.125.82.66]) by dpdk.org (Postfix) with ESMTP id DA06B592F for ; Mon, 2 May 2016 21:38:38 +0200 (CEST) Received: by mail-wm0-f66.google.com with SMTP id w143so241152wmw.3 for ; Mon, 02 May 2016 12:38:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc; bh=swWp0c2tJfDp+reu1QlX8o6DHfajiuFZtm6ZGz8K2jQ=; b=OqtM/NCpB7AyCd6LjlkvvB779pLoPBLffghMoj6dAdsJJSfKbT1xPoeLNxLGctyHt3 v4U9S9R0ha/BkGEBxYn658qLWO8Z1kzL94ZfNVCI2l/2Y3xNWUhBfyKBy8bY7+4rkLhB egStM9SS5AfD7p+PlXGXzWBt6sP6dTtVALPMrc31QSOJbNaFZpnoqxMiGpVTTjud+FHV qYAmewo860PcinVni3XfHrnXB716S5qPoK5vJdEbFwCQEC/DcuN5udiCOFFUtN+hG9w5 hUcUq/cWGjhY2brzjiz7NPpkPyurled7IkHXCa7I65LIFnAFUbuYaoi5Fxmyilk8Mpwt FVrg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc; bh=swWp0c2tJfDp+reu1QlX8o6DHfajiuFZtm6ZGz8K2jQ=; b=lRC1YaXlUqJufQEhL/44HMJy67PGyHl1ZCVjG7T0w6QRK5J13od7/reU2/gaLrNqo4 XXT/PIk8mxVNxaP0zPwrrlUcmHs/8N0oslLFM5rznmsgdfZ24b9vsXkdJT3CyGqRciDx TaGNiwQOLf9ETCLI15w5N5KFg6Izp1JibZ33E+GxR45HhSk2wVdRtVYQQI9wwFWb9maT ZSqJF8H+Pb30G9X1Hm1FeIoEozkpKSqroyAbY0nBoCX9zV/5uhqtVwwTJAqaXUR6+ax0 wzzlbvYiLMo+8UWi15Iv+uSI3n1rLOqZ5H7FTDjD31HK76o7HPUh2ee4/Nvm0x35pq6f NmjQ== X-Gm-Message-State: AOPr4FU6EpKYzQLe2PXLl2W1TaXVopobVVFp41C5faz1TDqLM+icc1k+13fylRemeJ8OcXu9BORtOYdGx4PnUg== MIME-Version: 1.0 X-Received: by 10.28.139.137 with SMTP id n131mr484451wmd.13.1462217918734; Mon, 02 May 2016 12:38:38 -0700 (PDT) Received: by 10.28.39.132 with HTTP; Mon, 2 May 2016 12:38:38 -0700 (PDT) In-Reply-To: <20160419084640.52235b05@xeon-e3> References: <20160419084640.52235b05@xeon-e3> Date: Mon, 2 May 2016 22:38:38 +0300 Message-ID: From: =?UTF-8?B?0JDQu9C10LrRgdCw0L3QtNGAINCa0LjRgdC10LvQtdCy?= To: Stephen Hemminger Cc: dev@dpdk.org Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Content-Filtered-By: Mailman/MimeDel 2.1.15 Subject: Re: [dpdk-dev] perfomance of rte_lpm rule subsystem X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 02 May 2016 19:38:39 -0000 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 : > On Tue, 19 Apr 2016 14:11:11 +0300 > =D0=90=D0=BB=D0=B5=D0=BA=D1=81=D0=B0=D0=BD=D0=B4=D1=80 =D0=9A=D0=B8=D1=81= =D0=B5=D0=BB=D0=B5=D0=B2 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 jus= t > > 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 we= re > ignored. mostly because it broke ABI. > --=20 -- Kiselev Alexander