Hi Yipeng,
Sorry for late reply
On 17/04/2020 01:21, Wang, Yipeng1 wrote:
-----Original Message-----
From: Mattias Rönnblom<mattias.ronnb...@ericsson.com>
Sent: Thursday, April 16, 2020 4:41 AM
To: Medvedkin, Vladimir<vladimir.medved...@intel.com>;dev@dpdk.org
Cc: Ananyev, Konstantin<konstantin.anan...@intel.com>; Wang, Yipeng1
<yipeng1.w...@intel.com>; Gobriel, Sameh<sameh.gobr...@intel.com>;
Richardson, Bruce<bruce.richard...@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.ronnb...@ericsson.com>
Sent: Wednesday, April 15, 2020 7:52 PM
To: Medvedkin, Vladimir<vladimir.medved...@intel.com>;dev@dpdk.org
Cc: Ananyev, Konstantin<konstantin.anan...@intel.com>; Wang, Yipeng1
<yipeng1.w...@intel.com>; Gobriel, Sameh<sameh.gobr...@intel.com>;
Richardson, Bruce<bruce.richard...@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
