From: "Medvedkin, Vladimir" <vladimir.medvedkin@intel.com>
To: "Wang, Yipeng1" <yipeng1.wang@intel.com>,
"Mattias Rönnblom" <mattias.ronnblom@ericsson.com>,
"dev@dpdk.org" <dev@dpdk.org>,
"Dumitrescu, Cristian" <cristian.dumitrescu@intel.com>
Cc: "Ananyev, Konstantin" <konstantin.ananyev@intel.com>,
"Gobriel, Sameh" <sameh.gobriel@intel.com>,
"Richardson, Bruce" <bruce.richardson@intel.com>
Subject: Re: [dpdk-dev] [PATCH v3 0/4] add new k32v64 hash table
Date: Fri, 8 May 2020 21:08:45 +0100 [thread overview]
Message-ID: <32a83242-5b35-fc78-8383-817f1571ce2d@intel.com> (raw)
In-Reply-To: <BY5PR11MB41661333804E1BF1388468BEC3D90@BY5PR11MB4166.namprd11.prod.outlook.com>
Hi Yipeng,
Sorry for late reply
On 17/04/2020 01:21, Wang, Yipeng1 wrote:
>> -----Original Message-----
>> From: Mattias Rönnblom<mattias.ronnblom@ericsson.com>
>> Sent: Thursday, April 16, 2020 4:41 AM
>> To: Medvedkin, Vladimir<vladimir.medvedkin@intel.com>;dev@dpdk.org
>> Cc: Ananyev, Konstantin<konstantin.ananyev@intel.com>; Wang, Yipeng1
>> <yipeng1.wang@intel.com>; Gobriel, Sameh<sameh.gobriel@intel.com>;
>> Richardson, Bruce<bruce.richardson@intel.com>
>> 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<mattias.ronnblom@ericsson.com>
>>> Sent: Wednesday, April 15, 2020 7:52 PM
>>> To: Medvedkin, Vladimir<vladimir.medvedkin@intel.com>;dev@dpdk.org
>>> Cc: Ananyev, Konstantin<konstantin.ananyev@intel.com>; Wang, Yipeng1
>>> <yipeng1.wang@intel.com>; Gobriel, Sameh<sameh.gobriel@intel.com>;
>>> Richardson, Bruce<bruce.richardson@intel.com>
>>> 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
next prev parent reply other threads:[~2020-05-08 20:08 UTC|newest]
Thread overview: 56+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-03-16 13:38 [dpdk-dev] [PATCH 0/3] add new Double Word Key " Vladimir Medvedkin
2020-03-16 13:38 ` [dpdk-dev] [PATCH 1/3] hash: add dwk hash library Vladimir Medvedkin
2020-03-16 13:38 ` [dpdk-dev] [PATCH 2/3] test: add dwk hash autotests Vladimir Medvedkin
2020-03-16 13:38 ` [dpdk-dev] [PATCH 3/3] test: add dwk perf tests Vladimir Medvedkin
2020-03-16 14:39 ` [dpdk-dev] [PATCH 0/3] add new Double Word Key hash table Morten Brørup
2020-03-16 18:27 ` Medvedkin, Vladimir
2020-03-16 19:32 ` Stephen Hemminger
2020-03-17 19:52 ` Wang, Yipeng1
2020-03-26 17:28 ` Medvedkin, Vladimir
2020-03-31 19:55 ` Thomas Monjalon
2020-03-31 21:17 ` Honnappa Nagarahalli
2020-04-01 18:37 ` Medvedkin, Vladimir
2020-04-01 18:28 ` Medvedkin, Vladimir
2020-03-16 19:33 ` Morten Brørup
2020-04-08 18:19 ` [dpdk-dev] [PATCH v2 0/4] add new k32v64 " Vladimir Medvedkin
2020-04-15 18:17 ` [dpdk-dev] [PATCH v3 " Vladimir Medvedkin
2020-04-15 18:51 ` Mattias Rönnblom
2020-04-16 10:18 ` Medvedkin, Vladimir
2020-04-16 11:40 ` Mattias Rönnblom
2020-04-17 0:21 ` Wang, Yipeng1
2020-04-23 16:19 ` Ananyev, Konstantin
2020-05-08 20:08 ` Medvedkin, Vladimir [this message]
2020-04-16 9:39 ` Thomas Monjalon
2020-04-16 14:02 ` Medvedkin, Vladimir
2020-04-16 14:38 ` Thomas Monjalon
2020-05-08 19:58 ` [dpdk-dev] [PATCH v4 0/4] add new kv " Vladimir Medvedkin
2020-06-16 16:37 ` Thomas Monjalon
2021-03-24 21:28 ` Thomas Monjalon
2021-03-25 12:03 ` Medvedkin, Vladimir
2023-06-12 16:11 ` Stephen Hemminger
2020-05-08 19:58 ` [dpdk-dev] [PATCH v4 1/4] hash: add kv hash library Vladimir Medvedkin
2020-06-23 15:44 ` Ananyev, Konstantin
2020-06-23 23:06 ` Ananyev, Konstantin
2020-06-25 19:56 ` Medvedkin, Vladimir
2020-06-25 19:49 ` Medvedkin, Vladimir
2020-06-24 1:19 ` Wang, Yipeng1
2020-06-25 20:26 ` Medvedkin, Vladimir
2020-06-25 4:27 ` Honnappa Nagarahalli
2020-05-08 19:58 ` [dpdk-dev] [PATCH v4 2/4] hash: add documentation for " Vladimir Medvedkin
2020-05-08 19:58 ` [dpdk-dev] [PATCH v4 3/4] test: add kv hash autotests Vladimir Medvedkin
2020-05-08 19:58 ` [dpdk-dev] [PATCH v4 4/4] test: add kv perf tests Vladimir Medvedkin
2020-04-15 18:17 ` [dpdk-dev] [PATCH v3 1/4] hash: add k32v64 hash library Vladimir Medvedkin
2020-04-15 18:59 ` Mattias Rönnblom
2020-04-16 10:23 ` Medvedkin, Vladimir
2020-04-23 13:31 ` Ananyev, Konstantin
2020-05-08 20:14 ` Medvedkin, Vladimir
2020-04-29 21:29 ` Honnappa Nagarahalli
2020-05-08 20:38 ` Medvedkin, Vladimir
2020-04-15 18:17 ` [dpdk-dev] [PATCH v3 2/4] hash: add documentation for " Vladimir Medvedkin
2020-04-15 18:17 ` [dpdk-dev] [PATCH v3 3/4] test: add k32v64 hash autotests Vladimir Medvedkin
2020-04-15 18:17 ` [dpdk-dev] [PATCH v3 4/4] test: add k32v64 perf tests Vladimir Medvedkin
2020-04-08 18:19 ` [dpdk-dev] [PATCH v2 1/4] hash: add k32v64 hash library Vladimir Medvedkin
2020-04-08 23:23 ` Ananyev, Konstantin
2020-04-08 18:19 ` [dpdk-dev] [PATCH v2 2/4] hash: add documentation for " Vladimir Medvedkin
2020-04-08 18:19 ` [dpdk-dev] [PATCH v2 3/4] test: add k32v64 hash autotests Vladimir Medvedkin
2020-04-08 18:19 ` [dpdk-dev] [PATCH v2 4/4] test: add k32v64 perf tests Vladimir Medvedkin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=32a83242-5b35-fc78-8383-817f1571ce2d@intel.com \
--to=vladimir.medvedkin@intel.com \
--cc=bruce.richardson@intel.com \
--cc=cristian.dumitrescu@intel.com \
--cc=dev@dpdk.org \
--cc=konstantin.ananyev@intel.com \
--cc=mattias.ronnblom@ericsson.com \
--cc=sameh.gobriel@intel.com \
--cc=yipeng1.wang@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).