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

[Mattias Rönnblom]

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
>>