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

[Medvedkin, Vladimir]

Hi Yipeng,

Sorry for late reply

On 17/04/2020 01:21, Wang, Yipeng1 wrote:
>> -----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.


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