| Message ID | cover.1586974408.git.vladimir.medvedkin@intel.com (mailing list archive) |
|---|---|
| Headers |
Return-Path: <dev-bounces@dpdk.org> X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 9CC77A0563; Wed, 15 Apr 2020 20:17:33 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 7D9E51D9BB; Wed, 15 Apr 2020 20:17:33 +0200 (CEST) Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by dpdk.org (Postfix) with ESMTP id A9F811C1B1 for <dev@dpdk.org>; Wed, 15 Apr 2020 20:17:31 +0200 (CEST) IronPort-SDR: +iUK0lMY5ZYqjyyByTIN24tW5EL9cPochcvspmpolVSXC3vXRBrR2DjgJlHNMyAMKUPuUn2JZd 5nUJS7uOlHpg== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by fmsmga106.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 15 Apr 2020 11:17:30 -0700 IronPort-SDR: cZcF9m14HeWAQ8CLPjNlTjYUyqi6im0NzAiptyBZd76OPTKmYkuBCoCI6Ih/N4pZNONAtl6+0S Je3ePLxoQV0w== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.72,388,1580803200"; d="scan'208";a="277702347" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga004.fm.intel.com with ESMTP; 15 Apr 2020 11:17:29 -0700 From: Vladimir Medvedkin <vladimir.medvedkin@intel.com> To: dev@dpdk.org Cc: konstantin.ananyev@intel.com, yipeng1.wang@intel.com, sameh.gobriel@intel.com, bruce.richardson@intel.com Date: Wed, 15 Apr 2020 19:17:23 +0100 Message-Id: <cover.1586974408.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <cover.1586369591.git.vladimir.medvedkin@intel.com> References: <cover.1586369591.git.vladimir.medvedkin@intel.com> Subject: [dpdk-dev] [PATCH v3 0/4] add new k32v64 hash table X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions <dev.dpdk.org> List-Unsubscribe: <https://mails.dpdk.org/options/dev>, <mailto:dev-request@dpdk.org?subject=unsubscribe> List-Archive: <http://mails.dpdk.org/archives/dev/> List-Post: <mailto:dev@dpdk.org> List-Help: <mailto:dev-request@dpdk.org?subject=help> List-Subscribe: <https://mails.dpdk.org/listinfo/dev>, <mailto:dev-request@dpdk.org?subject=subscribe> Errors-To: dev-bounces@dpdk.org Sender: "dev" <dev-bounces@dpdk.org> |
| Series | add new k32v64 hash table | |
Message
Vladimir Medvedkin
April 15, 2020, 6:17 p.m. UTC
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? 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
Comments
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? > 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 >
15/04/2020 20:17, 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 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? > > 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) Please use --in-reply-to so we can follow version changes in the same email thread. Also I am changing the states in patchwork as superseded. Please remind updating status of old patches.
Hi Mattias, -----Original Message----- From: Mattias Rönnblom <mattias.ronnblom@ericsson.com> Sent: Wednesday, April 15, 2020 7:52 PM To: Medvedkin, Vladimir <vladimir.medvedkin@intel.com>; dev@dpdk.org Cc: Ananyev, Konstantin <konstantin.ananyev@intel.com>; Wang, Yipeng1 <yipeng1.wang@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>; Richardson, Bruce <bruce.richardson@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. > 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 >
On 2020-04-16 12:18, Medvedkin, Vladimir wrote: > Hi Mattias, > > -----Original Message----- > From: Mattias Rönnblom <mattias.ronnblom@ericsson.com> > Sent: Wednesday, April 15, 2020 7:52 PM > To: Medvedkin, Vladimir <vladimir.medvedkin@intel.com>; dev@dpdk.org > Cc: Ananyev, Konstantin <konstantin.ananyev@intel.com>; Wang, Yipeng1 <yipeng1.wang@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>; Richardson, Bruce <bruce.richardson@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 >>
Hi Thomas, On 16/04/2020 10:39, Thomas Monjalon wrote: > 15/04/2020 20:17, 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 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? >> >> 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) > Please use --in-reply-to so we can follow version changes > in the same email thread. > Also I am changing the states in patchwork as superseded. > Please remind updating status of old patches. > Hmm, strange, I used --in-reply-to. Also in patchwork I can see In-Reply-To: <cover.1586369591.git.vladimir.medvedkin@intel.com>
16/04/2020 16:02, Medvedkin, Vladimir: > Hi Thomas, > > On 16/04/2020 10:39, Thomas Monjalon wrote: > > 15/04/2020 20:17, 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 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? > >> > >> 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) > > Please use --in-reply-to so we can follow version changes > > in the same email thread. > > Also I am changing the states in patchwork as superseded. > > Please remind updating status of old patches. > > > > Hmm, strange, I used --in-reply-to. Also in patchwork I can see > > In-Reply-To: <cover.1586369591.git.vladimir.medvedkin@intel.com> Indeed, sorry my bad. I can see correct threading: http://inbox.dpdk.org/dev/26233198-907c-cf1c-f5ef-154d54c2ed7f@intel.com/
> -----Original Message----- > From: Mattias Rönnblom <mattias.ronnblom@ericsson.com> > Sent: Thursday, April 16, 2020 4:41 AM > To: Medvedkin, Vladimir <vladimir.medvedkin@intel.com>; dev@dpdk.org > Cc: Ananyev, Konstantin <konstantin.ananyev@intel.com>; Wang, Yipeng1 > <yipeng1.wang@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>; > Richardson, Bruce <bruce.richardson@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@ericsson.com> > > Sent: Wednesday, April 15, 2020 7:52 PM > > To: Medvedkin, Vladimir <vladimir.medvedkin@intel.com>; dev@dpdk.org > > Cc: Ananyev, Konstantin <konstantin.ananyev@intel.com>; Wang, Yipeng1 > > <yipeng1.wang@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>; > > Richardson, Bruce <bruce.richardson@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.
Hi everyone, > > > > On 2020-04-16 12:18, Medvedkin, Vladimir wrote: > > > Hi Mattias, > > > > > > -----Original Message----- > > > From: Mattias Rönnblom <mattias.ronnblom@ericsson.com> > > > Sent: Wednesday, April 15, 2020 7:52 PM > > > To: Medvedkin, Vladimir <vladimir.medvedkin@intel.com>; dev@dpdk.org > > > Cc: Ananyev, Konstantin <konstantin.ananyev@intel.com>; Wang, Yipeng1 > > > <yipeng1.wang@intel.com>; Gobriel, Sameh <sameh.gobriel@intel.com>; > > > Richardson, Bruce <bruce.richardson@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
Hi Yipeng, Sorry for late reply On 17/04/2020 01:21, Wang, Yipeng1 wrote: >> -----Original Message----- >> From: Mattias Rönnblom<mattias.ronnblom@ericsson.com> >> Sent: Thursday, April 16, 2020 4:41 AM >> To: Medvedkin, Vladimir<vladimir.medvedkin@intel.com>;dev@dpdk.org >> Cc: Ananyev, Konstantin<konstantin.ananyev@intel.com>; Wang, Yipeng1 >> <yipeng1.wang@intel.com>; Gobriel, Sameh<sameh.gobriel@intel.com>; >> Richardson, Bruce<bruce.richardson@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@ericsson.com> >>> Sent: Wednesday, April 15, 2020 7:52 PM >>> To: Medvedkin, Vladimir<vladimir.medvedkin@intel.com>;dev@dpdk.org >>> Cc: Ananyev, Konstantin<konstantin.ananyev@intel.com>; Wang, Yipeng1 >>> <yipeng1.wang@intel.com>; Gobriel, Sameh<sameh.gobriel@intel.com>; >>> Richardson, Bruce<bruce.richardson@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.