[dpdk-dev] [PATCH v3 0/4] add new k32v64 hash table

[Wang, Yipeng1]

> -----Original Message-----
> From: Mattias Rönnblom <mattias.ronnblom at ericsson.com>
> Sent: Thursday, April 16, 2020 4:41 AM
> To: Medvedkin, Vladimir <vladimir.medvedkin at intel.com>; dev at dpdk.org
> Cc: Ananyev, Konstantin <konstantin.ananyev at intel.com>; Wang, Yipeng1
> <yipeng1.wang at intel.com>; Gobriel, Sameh <sameh.gobriel at intel.com>;
> Richardson, Bruce <bruce.richardson at 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 at ericsson.com>
> > Sent: Wednesday, April 15, 2020 7:52 PM
> > To: Medvedkin, Vladimir <vladimir.medvedkin at intel.com>; dev at dpdk.org
> > Cc: Ananyev, Konstantin <konstantin.ananyev at intel.com>; Wang, Yipeng1
> > <yipeng1.wang at intel.com>; Gobriel, Sameh <sameh.gobriel at intel.com>;
> > Richardson, Bruce <bruce.richardson at 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.

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.