From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id D975BA0562; Tue, 31 Mar 2020 23:17:18 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id A2F2D1C139; Tue, 31 Mar 2020 23:17:17 +0200 (CEST) Received: from EUR05-DB8-obe.outbound.protection.outlook.com (mail-db8eur05on2051.outbound.protection.outlook.com [40.107.20.51]) by dpdk.org (Postfix) with ESMTP id 4E1F51C131 for ; Tue, 31 Mar 2020 23:17:16 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=MSpTswdDyL2tC76PsHBuBXGLp9NpZUUYS6RDMfAnvGo=; b=IPb3e+OGG4ZJ9+b/fbW4+TS1JLazWLNsyHvz6o+XDHEWlfgLIu6BhbxYdBkRv8V5mFNIoFFwXx0nx0oNQiaJA6p1LdeGT9NGxbnxGEQzkfn64EfzBrswgg9RUoMADTZYwdfqzElJIvR/ard3c5A7RUq5ViZJteqNHNf8PlhbrD0= Received: from DB6PR0802CA0046.eurprd08.prod.outlook.com (2603:10a6:4:a3::32) by HE1PR0801MB1626.eurprd08.prod.outlook.com (2603:10a6:3:86::10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2856.20; Tue, 31 Mar 2020 21:17:12 +0000 Received: from DB5EUR03FT010.eop-EUR03.prod.protection.outlook.com (2603:10a6:4:a3:cafe::a7) by DB6PR0802CA0046.outlook.office365.com (2603:10a6:4:a3::32) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2878.15 via Frontend Transport; Tue, 31 Mar 2020 21:17:12 +0000 Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; dpdk.org; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;dpdk.org; dmarc=bestguesspass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 63.35.35.123 as permitted sender) receiver=protection.outlook.com; client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com; Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by DB5EUR03FT010.mail.protection.outlook.com (10.152.20.96) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2856.17 via Frontend Transport; Tue, 31 Mar 2020 21:17:12 +0000 Received: ("Tessian outbound e2c88df8bbbe:v50"); Tue, 31 Mar 2020 21:17:12 +0000 X-CR-MTA-TID: 64aa7808 Received: from 5faf4ac34fe9.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id 927D99F7-4BD6-4CA4-8761-D7371F9E8088.1; Tue, 31 Mar 2020 21:17:07 +0000 Received: from EUR04-DB3-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id 5faf4ac34fe9.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Tue, 31 Mar 2020 21:17:07 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=jFS3Fma9LqvAGIp9l7yUm+VMxPfKmNdWJs3H6dn0DLCJVjsglQNCHI5Lm1DfNo9FR/YT8DaXcAjBp/dmV3PGzP/wnsOWZrH++WNgYVQdCvpx9ZG6VP5CiEeHFhuKaxA7nyki2G1I18kHpoU4Qx3hHfaz3GMq/RA9XKsDIIhb5D6JRJU9j3vqPt5wH8wpYfqr2qwyui36ChGpzg5Ki0eBUVXS0nlbBTsrN5AVXR4ag5otGNS/B0tzeWDyo5s0Wz4FTJUpknxEBb3Fje/Gv0KxcuEoVS2w0u9ka6hDlHL1N60d9jwWutA3FUUdWs2HyFCWaw6wWh1RP6Cr15xwV/Zwnw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=MSpTswdDyL2tC76PsHBuBXGLp9NpZUUYS6RDMfAnvGo=; b=bMmEFCyxM/OrzcxEC3c+t+AqgQNQ7IAvuSEDnuTO5NzJfqwrn7Xm4bpfvPPntPzcYyBqfS6Cp9bBia1ZOajYRnhO9PZyyJFL2ML9ybSU9v7hErxJG3QJ6+6ugDafZ0zXC/CzowO5RjFUBAH2FjOSuJ03W36ai6zUjgbbpgpdC33hEX1Hw8peKUCJeQ24DyvK7Rfp298/UQttbkxwfQ6Ei0odzEmagyWbhWu5YBLW4uD7Vtjqu7a/UuO54PwcyHZ91xE1I4EsNJljDl3+AomPGOS1iRZtxC81T7r2EFgB5GYjdNitu2WwlFikoVAK3NQGF/eR1ljdRE6X2rN/CJTfRw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=arm.com; dmarc=pass action=none header.from=arm.com; dkim=pass header.d=arm.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=MSpTswdDyL2tC76PsHBuBXGLp9NpZUUYS6RDMfAnvGo=; b=IPb3e+OGG4ZJ9+b/fbW4+TS1JLazWLNsyHvz6o+XDHEWlfgLIu6BhbxYdBkRv8V5mFNIoFFwXx0nx0oNQiaJA6p1LdeGT9NGxbnxGEQzkfn64EfzBrswgg9RUoMADTZYwdfqzElJIvR/ard3c5A7RUq5ViZJteqNHNf8PlhbrD0= Received: from AM6PR08MB4644.eurprd08.prod.outlook.com (10.255.98.10) by AM6PR08MB5160.eurprd08.prod.outlook.com (10.255.123.138) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2856.20; Tue, 31 Mar 2020 21:17:05 +0000 Received: from AM6PR08MB4644.eurprd08.prod.outlook.com ([fe80::f943:cc7e:200b:f54e]) by AM6PR08MB4644.eurprd08.prod.outlook.com ([fe80::f943:cc7e:200b:f54e%5]) with mapi id 15.20.2856.019; Tue, 31 Mar 2020 21:17:05 +0000 From: Honnappa Nagarahalli To: "thomas@monjalon.net" , "Medvedkin, Vladimir" CC: "Wang, Yipeng1" , Stephen Hemminger , "dev@dpdk.org" , =?iso-8859-1?Q?Morten_Br=F8rup?= , "dev@dpdk.org" , "Ananyev, Konstantin" , "Gobriel, Sameh" , "Richardson, Bruce" , Suanming Mou , Olivier Matz , "Xueming(Steven) Li" , Andrew Rybchenko , Asaf Penso , Ori Kam , nd , Honnappa Nagarahalli , nd Thread-Topic: [dpdk-dev] [PATCH 0/3] add new Double Word Key hash table Thread-Index: AQHWB5ZoAZGVbvps/EevOOrVKI09ZqhjM7QA Date: Tue, 31 Mar 2020 21:17:05 +0000 Message-ID: References: <3aa4f601-aaab-223f-8882-79b51f2e9251@intel.com> <4749580.haC6HkEk0m@xps> In-Reply-To: <4749580.haC6HkEk0m@xps> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ts-tracking-id: 8188ecb8-f21b-41c2-9da0-cb67fbb604d8.0 x-checkrecipientchecked: true Authentication-Results-Original: spf=none (sender IP is ) smtp.mailfrom=Honnappa.Nagarahalli@arm.com; x-originating-ip: [70.113.25.165] x-ms-publictraffictype: Email X-MS-Office365-Filtering-HT: Tenant X-MS-Office365-Filtering-Correlation-Id: f6d10255-d4ef-4c9f-7c37-08d7d5b8e150 x-ms-traffictypediagnostic: AM6PR08MB5160:|AM6PR08MB5160:|HE1PR0801MB1626: x-ld-processed: f34e5979-57d9-4aaa-ad4d-b122a662184d,ExtAddr x-ms-exchange-transport-forked: True X-Microsoft-Antispam-PRVS: x-checkrecipientrouted: true nodisclaimer: true x-ms-oob-tlc-oobclassifiers: OLM:10000;OLM:10000; x-forefront-prvs: 0359162B6D X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:AM6PR08MB4644.eurprd08.prod.outlook.com; PTR:; CAT:NONE; SFTY:; SFS:(10009020)(4636009)(366004)(136003)(376002)(346002)(39860400002)(396003)(9686003)(76116006)(66476007)(66946007)(64756008)(66574012)(52536014)(5660300002)(81156014)(66556008)(54906003)(966005)(33656002)(6506007)(110136005)(316002)(186003)(478600001)(66446008)(8676002)(8936002)(81166006)(4326008)(7696005)(7416002)(55016002)(71200400001)(2906002)(53546011)(26005)(86362001); DIR:OUT; SFP:1101; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) X-MS-Exchange-SenderADCheck: 1 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: 8syT+LlOYH5rkJxjajwjHwO4XdclgelLarVXOFA0erLHHffdlccTEHjhJokqQjICdNX13GfrbMlDM1qe4vCiG0lZ5KQ3Bri5y7SFIjiH0bSKMMORknwZPbxPo9QTbv5dykDjjANz3t666m6xPuy2+mfPL8qFRoGhxH68jSqq0Cce8zEnnDxBzQUPC/vCgWohsg2tSoxkRiOJM780YbS7lYBVtKiKtQNmS7AkJjXOQy3pMAtBRhEPdN3Af5p6MJJq30vYhh1s9MU9+WtKrdHGFPMpr5EgGJl7XOygguJ5iZTYG/JJkBwUuAwIhOmPqoMknFI/VcLrBO92kX2Cww98VcEHZdNNIHwKhAXWZ2wpRHqEi8MFABILwzuPDF97Y7pzeJE16UuNKfFNW2CCaKhIGl5a10MNiH+vDWc02lvY6srgH0GS91JcPGyOmKH8XepAiZ9Sj0RgSvHxrJ+W3lYkjy84ykVQBzsj8LeACZHUIYKVYiq1jtsxR7pbCgSq0YPxzbJ6/WzRw4XFQXsGt/Oz1A== x-ms-exchange-antispam-messagedata: GzimKhHH6otXqtXeUFEiOmyda/br4dQCE/baVzuxuGi/53fEYH1BfMqkqasonTtAFm7JgIKNTa97mZBrnKiIY9L7jsVsPFZ9wf+Pj4d2cW5J+HiCDgi+1lBgF1TOTxIERq9psxkHDsNWiQeLtDa6wA== Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB5160 Original-Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=Honnappa.Nagarahalli@arm.com; X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: DB5EUR03FT010.eop-EUR03.prod.protection.outlook.com X-Forefront-Antispam-Report: CIP:63.35.35.123; CTRY:IE; LANG:en; SCL:1; SRV:; IPV:CAL; SFV:NSPM; H:64aa7808-outbound-1.mta.getcheckrecipient.com; PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com; CAT:NONE; SFTY:; SFS:(10009020)(4636009)(346002)(396003)(136003)(39860400002)(376002)(46966005)(86362001)(316002)(54906003)(5660300002)(52536014)(478600001)(47076004)(82740400003)(966005)(110136005)(26826003)(70206006)(186003)(336012)(70586007)(26005)(8676002)(2906002)(33656002)(8936002)(66574012)(6506007)(7696005)(53546011)(81156014)(9686003)(356004)(4326008)(81166006)(55016002); DIR:OUT; SFP:1101; X-MS-Office365-Filtering-Correlation-Id-Prvs: 03ada20e-a95a-4bbb-4856-08d7d5b8dd2e X-Forefront-PRVS: 0359162B6D X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: 17jf2yTmcXyDZmIpvZlQ0v1mgzS6L01XjdQjBIdaaN7yIo34QSim99V8NQ+F2YNNChJG1MW4fr37bm7deaqT1C22QfTX0iaqxqsHqohflXPrhwXkJ6A1jWr7kpTUwuA47gkQg9HqDZJqnh0BEiEyFxFRstRRkZD9ok2R+ZAdHMl0clK97O1O2Vm78K1ztzCQcQFX0HmOAa6JsLNTxtLccu5RcZc/3f1ncROav5VnwRKF6Ztds8/LUU489y9vQ686G+Me6mG5IiXdj51GlOhU0+ndvONQHqxjScsVKqOnVjoBZnAaUVl4uC+HUCrMrz/Nv0aNNuAq6uUl5p4AjSjFWz4aiCDA4xuUWlT3H5R2pZ52pUiWYZoAA/uV0SybFD5oHIUVh/y7GE3Vx9L54KY3/e9EXA47pwa5+JlTndin6XlmSzfchY8pErysz5ABNIuqpv7aznhTs8qyBF/NyjitWDVqXKdIjxImx+GHMn1c1H4mgbP5nWlbqq+yD6fFYcXCYaf/TJOrqWguJIq4606YPW8Y5lZClYgfnw5DvNxeZ737Q30Fmt2aIR2hgsPoXiKbDgpqR4+5gWgF2hA+ESYvuw== X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 31 Mar 2020 21:17:12.7001 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: f6d10255-d4ef-4c9f-7c37-08d7d5b8e150 X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d; Ip=[63.35.35.123]; Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com] X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: HE1PR0801MB1626 Subject: Re: [dpdk-dev] [PATCH 0/3] add new Double Word Key hash table X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" >=20 > 26/03/2020 18:28, Medvedkin, Vladimir: > > Hi Yipeng, Stephen, all, > > > > On 17/03/2020 19:52, Wang, Yipeng1 wrote: > > > From: Stephen Hemminger > > >> On Mon, 16 Mar 2020 18:27:40 +0000 > > >> "Medvedkin, Vladimir" wrote: > > >> > > >>> Hi Morten, > > >>> > > >>> > > >>> On 16/03/2020 14:39, Morten Br=F8rup wrote: > > >>>>> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Vladimir > > >>>>> Medvedkin > > >>>>> Sent: Monday, March 16, 2020 2:38 PM > > >>>>> > > >>>>> Currently DPDK has a special implementation of a hash table for > > >>>>> 4 byte keys which is called FBK hash. Unfortunately its main > > >>>>> drawback is that it only supports 2 byte values. > > >>>>> The new implementation called DWK (double word key) hash > > >>>>> supports 8 byte values, which is enough to store a pointer. > > >>>>> > > >>>>> It would also be nice to get feedback on whether to leave the > > >>>>> old FBK and new DWK implementations, or whether to deprecate the > > >>>>> old > > >> one? > > >>>> > > >>>> > > >>>> Who comes up with these names?!? > > >>>> > > >>>> FBK (Four Byte Key) and DWK (Double Word Key) is supposed to mean > > >> the same. Could you use 32 somewhere in the name instead, like in > > >> int32_t, instead of using a growing list of creative synonyms for th= e same > thing? > > >> Pretty please, with a cherry on top! > > >>> > > >>> That's true, at first I named it as fbk2, but then it was decided > > >>> to rename it "dwk", so that there was no confusion with the > > >>> existing FBK library. Naming suggestions are welcome! > > >>> > > >>>> And if the value size is fixed too, perhaps the name should also > > >>>> indicate > > >> the value size. > > >>>> > > >>>> > > >>>> It's a shame we don't have C++ class templates available in DPDK..= . > > >>>> > > >>>> In other news, Mellanox has sent an RFC for an "indexed memory > pool" > > >> library [1] to conserve memory by using uintXX_t instead of > > >> pointers, so perhaps a variant of a 32 bit key hash library with 32 > > >> bit values (in addition to > > >> 16 bit values in FBK and 64 bit in DWK) would be nice combination > > >> with that library. > > >>>> [1]: http://mails.dpdk.org/archives/dev/2019-October/147513.html >=20 > Yes some work is in progress to propose a new memory allocator for small > objects of fixed size with small memory overhead. >=20 >=20 > > >> Why is this different (or better) than existing rte_hash. > > >> Having more flavors is not necessarily a good thing (except in > > >> Gelato) > > > [Wang, Yipeng] > > > Hi, Vladimir, > > > As Stephen mentioned, I think it is good idea to explain the benefit > > > of this new type of hash table more explicitly such as Specific use c= ases, > differences with current rte_hash, and performance numbers, etc. > > > > The main reason for this new hash library is performance. As I > > mentioned earlier, the current rte_fbk implementation is pretty fast > > but it has a number of drawbacks such as 2 byte values and limited > > collision resolving capabilities. On the other hand, rte_hash (cuckoo > > hash) doesn't have this drawbacks but at the cost of lower performance > > comparing to rte_fbk. > > > > If I understand correctly, performance penalty are due to : > > > > 1. Load two buckets > > > > 2. First compare signatures > > > > 3. If signature comparison hits get a key index and find memory > > location with a key itself and get the key > > > > 4. Using indirect call to memcmp() to compare two uint32_t. > > > > The new proposed 4 byte key hash table doesn't have rte_fbk drawbacks > > while offers the same performance as rte_fbk. > > > > Regarding use cases, in rte_ipsec_sad we are using rte_hash with 4 > > byte key size. Replacing it with a new implementation gives about 30% > > in performance. > > > > The main disadvantage comparing to rte_hash is some performance > > degradation with high average table utilization due to chain resolving > > for 5th and subsequent collision. rte_hash is linearly scalable across multiple cores for lookup due to lock-= free algorithm. How is the scalability for the new algorithm? >=20 > Thanks for explaining. > Please, such information should added in the documentation: > doc/guides/prog_guide/hash_lib.rst >=20 >=20