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 0D99DA0352; Fri, 8 May 2020 22:08:52 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 80F401DA36; Fri, 8 May 2020 22:08:51 +0200 (CEST) Received: from mga05.intel.com (mga05.intel.com [192.55.52.43]) by dpdk.org (Postfix) with ESMTP id A0A171DA33 for ; Fri, 8 May 2020 22:08:49 +0200 (CEST) IronPort-SDR: +fXC+hEjF5X1939Zh1w/oDB2uJ+Nz8oluivY8QZHwb7AZ/YRjVg37B7VT8+64UVPniwA//sUDQ yrrn+jzQIE8A== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga006.fm.intel.com ([10.253.24.20]) by fmsmga105.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 08 May 2020 13:08:48 -0700 IronPort-SDR: ARieFih90BNLGa3LA05wQYiCoAgEiDtvm0ZbNcSyCI0upM5aJTieuljJeP9qEo7TmetqR4Vedc Bsc7Kk6IZldQ== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.73,369,1583222400"; d="scan'208";a="462702728" Received: from vmedvedk-mobl.ger.corp.intel.com (HELO [10.254.57.36]) ([10.254.57.36]) by fmsmga006.fm.intel.com with ESMTP; 08 May 2020 13:08:46 -0700 From: "Medvedkin, Vladimir" To: "Wang, Yipeng1" , =?UTF-8?Q?Mattias_R=c3=b6nnblom?= , "dev@dpdk.org" , "Dumitrescu, Cristian" Cc: "Ananyev, Konstantin" , "Gobriel, Sameh" , "Richardson, Bruce" References: Message-ID: <32a83242-5b35-fc78-8383-817f1571ce2d@intel.com> Date: Fri, 8 May 2020 21:08:45 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.7.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: en-US Subject: Re: [dpdk-dev] [PATCH v3 0/4] add new k32v64 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" Hi Yipeng, Sorry for late reply On 17/04/2020 01:21, Wang, Yipeng1 wrote: >> -----Original Message----- >> From: Mattias Rönnblom >> Sent: Thursday, April 16, 2020 4:41 AM >> To: Medvedkin, Vladimir;dev@dpdk.org >> Cc: Ananyev, Konstantin; Wang, Yipeng1 >> ; Gobriel, Sameh; >> Richardson, Bruce >> Subject: Re: [dpdk-dev] [PATCH v3 0/4] add new k32v64 hash table >> >> On 2020-04-16 12:18, Medvedkin, Vladimir wrote: >>> Hi Mattias, >>> >>> -----Original Message----- >>> From: Mattias Rönnblom >>> Sent: Wednesday, April 15, 2020 7:52 PM >>> To: Medvedkin, Vladimir;dev@dpdk.org >>> Cc: Ananyev, Konstantin; Wang, Yipeng1 >>> ; Gobriel, Sameh; >>> Richardson, Bruce >>> Subject: Re: [dpdk-dev] [PATCH v3 0/4] add new k32v64 hash table >>> >>> On 2020-04-15 20:17, Vladimir Medvedkin wrote: >>>> 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 K32V64 hash supports 4 byte keys and 8 >>>> byte associated 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 k32v64 implementations or deprecate the old one? >>> Do you think it would be feasible to support custom-sized values and remain >> efficient, in a similar manner to how rte_ring_elem.h does things? >>> I'm afraid it is not feasible. For the performance reason keys and >> corresponding values resides in single cache line so there are no extra memory >> for bigger values, such as 16B. >> >> >> Well, if you have a smaller value type (or key type) you would fit into >> something less-than-a-cache line, and thus reduce your memory working set >> further. >> >> >>>> v3: >>>> - added bulk lookup >>>> - avx512 key comparizon is removed from .h >>>> >>>> v2: >>>> - renamed from rte_dwk to rte_k32v64 as was suggested >>>> - reworked lookup function, added inlined subroutines >>>> - added avx512 key comparizon routine >>>> - added documentation >>>> - added statistic counters for total entries and extended >>>> entries(linked list) >>>> >>>> Vladimir Medvedkin (4): >>>> hash: add k32v64 hash library >>>> hash: add documentation for k32v64 hash library >>>> test: add k32v64 hash autotests >>>> test: add k32v64 perf tests >>>> >>>> app/test/Makefile | 1 + >>>> app/test/autotest_data.py | 12 ++ >>>> app/test/meson.build | 3 + >>>> app/test/test_hash_perf.c | 130 ++++++++++++ >>>> app/test/test_k32v64_hash.c | 229 ++++++++++++++++++++++ >>>> doc/api/doxy-api-index.md | 1 + >>>> doc/guides/prog_guide/index.rst | 1 + >>>> doc/guides/prog_guide/k32v64_hash_lib.rst | 66 +++++++ >>>> lib/Makefile | 2 +- >>>> lib/librte_hash/Makefile | 13 +- >>>> lib/librte_hash/k32v64_hash_avx512vl.c | 56 ++++++ >>>> lib/librte_hash/meson.build | 17 +- >>>> lib/librte_hash/rte_hash_version.map | 6 +- >>>> lib/librte_hash/rte_k32v64_hash.c | 315 >> ++++++++++++++++++++++++++++++ >>>> lib/librte_hash/rte_k32v64_hash.h | 211 ++++++++++++++++++++ >>>> 15 files changed, 1058 insertions(+), 5 deletions(-) >>>> create mode 100644 app/test/test_k32v64_hash.c >>>> create mode 100644 doc/guides/prog_guide/k32v64_hash_lib.rst >>>> create mode 100644 lib/librte_hash/k32v64_hash_avx512vl.c >>>> create mode 100644 lib/librte_hash/rte_k32v64_hash.c >>>> create mode 100644 lib/librte_hash/rte_k32v64_hash.h >>>> > [Wang, Yipeng] > Hi, Vladimir, > Thanks for responding with the use cases earlier. > I discussed with Sameh offline, here are some comments. > > 1. Since the proposed hash table also has some similarities to rte_table library used by packet framework, > have you tried it yet? Although it is mainly for packet framework, I believe you can use it independently as well. > It has implementations for special key value sizes. > I added Cristian for his comment. I looked at rte_table_hash. I'm afraid it doesn't fit our requirements due to it's design. First, it's API uses mbufs as a key container. Second, as I can see from the source code it is not safe in multi threaded environment regarding read-write concurrency by design. Also there are some information about it https://doc.dpdk.org/guides/prog_guide/packet_framework.html#shared-data-structures and Cristian's comment http://mails.dpdk.org/archives/dev/2015-September/024121.html > 2. We tend to agree with Mattias that it would be better if we have a more generic API name and with the same > API we can do multiple key/value size implementations. > This is to avoid adding new APIs in future to again handle different key/value > use cases. For example, we call it rte_kv_hash, and through the parameter struct we pass in a key-value size pair > we want to use. > Implementation-wise, we may only provide implementations for certain popular use cases (like the one you provided). > For other general use cases, people should go with the more flexible and generic cuckoo hash. > Then we should also merge the FBK under the new API. > Agree. As was discussed offline, I've made API to be more generic regarding to key and value sizes. -- Regards, Vladimir