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

[Ananyev, Konstantin]

Hi everyone,
 
> >
> > 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.

From my perspective Vladimir work is not an attempt to introduce new API -
but to fix (extend) existing FBK one.
Right now there is a contradictory situation:
from one side with 4B keys hash tables are quite common, from other side
because of its limitations (2B value, no mechanism to resolve collisions) fbk_hash
is hardly usable in majority of real-world scenarios.

About making it more generic - we already have one generic rte_hash API,
why should we introduce an new one?
My take we should fix FBK hash and make it usable.
If it is not an option by some reason, then I think we
should deprecate and remove FBK hash at all,
and concentrate on making generic one work faster for particular scenarios.
Let say we can try to move what Vladimir did, under rte_hash API umbrella
for special config (4B key).

Konstantin