[v4,0/4] add new kv hash table

  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 KV hash
supports 4 byte keys and 8 byte associated values,
which is enough to store a pointer.

v4:
- internal implementation is hided under universal API for any key and value sizes
- add and delete API now return old value
- add transaction counter modification to _add()
- transaction counter now modifies with c11 atomics

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 kv hash library
  hash: add documentation for kv hash library
  test: add kv hash autotests
  test: add kv perf tests

 app/test/Makefile                      |   1 +
 app/test/autotest_data.py              |  12 ++
 app/test/meson.build                   |   3 +
 app/test/test_hash_perf.c              | 111 +++++++++++++
 app/test/test_kv_hash.c                | 242 ++++++++++++++++++++++++++++
 doc/api/doxy-api-index.md              |   1 +
 doc/guides/prog_guide/index.rst        |   1 +
 doc/guides/prog_guide/kv_hash_lib.rst  |  66 ++++++++
 lib/Makefile                           |   2 +-
 lib/librte_hash/Makefile               |  14 +-
 lib/librte_hash/k32v64_hash.c          | 277 +++++++++++++++++++++++++++++++++
 lib/librte_hash/k32v64_hash.h          |  98 ++++++++++++
 lib/librte_hash/k32v64_hash_avx512vl.c |  59 +++++++
 lib/librte_hash/meson.build            |  17 +-
 lib/librte_hash/rte_hash_version.map   |   6 +-
 lib/librte_hash/rte_kv_hash.c          | 184 ++++++++++++++++++++++
 lib/librte_hash/rte_kv_hash.h          | 169 ++++++++++++++++++++
 17 files changed, 1258 insertions(+), 5 deletions(-)
 create mode 100644 app/test/test_kv_hash.c
 create mode 100644 doc/guides/prog_guide/kv_hash_lib.rst
 create mode 100644 lib/librte_hash/k32v64_hash.c
 create mode 100644 lib/librte_hash/k32v64_hash.h
 create mode 100644 lib/librte_hash/k32v64_hash_avx512vl.c
 create mode 100644 lib/librte_hash/rte_kv_hash.c
 create mode 100644 lib/librte_hash/rte_kv_hash.h
  

Waiting for reviews please.

08/05/2020 21:58, Vladimir Medvedkin:
> 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 KV hash
> supports 4 byte keys and 8 byte associated values,
> which is enough to store a pointer.
> 
> v4:
> - internal implementation is hided under universal API for any key and value sizes
> - add and delete API now return old value
> - add transaction counter modification to _add()
> - transaction counter now modifies with c11 atomics
> 
> 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 kv hash library
>   hash: add documentation for kv hash library
>   test: add kv hash autotests
>   test: add kv perf tests
  

08/05/2020 21:58, Vladimir Medvedkin:
> 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 KV hash
> supports 4 byte keys and 8 byte associated values,
> which is enough to store a pointer.

Waiting for a v5.
Is it abandoned?
  

Hi Thomas,

On 25/03/2021 00:28, Thomas Monjalon wrote:
> 08/05/2020 21:58, Vladimir Medvedkin:
>> 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 KV hash
>> supports 4 byte keys and 8 byte associated values,
>> which is enough to store a pointer.
> 
> Waiting for a v5.
> Is it abandoned?

It is suspended till further rework.

> 
>
  

On Thu, 25 Mar 2021 15:03:24 +0300
"Medvedkin, Vladimir" <vladimir.medvedkin@intel.com> wrote:

> Hi Thomas,
> 
> On 25/03/2021 00:28, Thomas Monjalon wrote:
> > 08/05/2020 21:58, Vladimir Medvedkin:  
> >> 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 KV hash
> >> supports 4 byte keys and 8 byte associated values,
> >> which is enough to store a pointer.  
> > 
> > Waiting for a v5.
> > Is it abandoned?  
> 
> It is suspended till further rework.
> 
> > 

Since nothing more has arrived in 2 years,
marking the original patchset as Changes requested.