Message ID | cover.1588967562.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 7C1D3A0352; Fri, 8 May 2020 21:59:01 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id EEBCE1DA1A; Fri, 8 May 2020 21:59:00 +0200 (CEST) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 9D7D91DA11 for <dev@dpdk.org>; Fri, 8 May 2020 21:58:58 +0200 (CEST) IronPort-SDR: DtZ26ZGOBu1eD4/PzAlpk3y7An6W/CyPUYd8rzd0lJJ2Oy+tDoFlflaIp6aWHiHeTrTOqdsPHr vStqZk17qh8g== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by orsmga102.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 08 May 2020 12:58:57 -0700 IronPort-SDR: tEhVT+tLFmFgEwsTXLQVRp+xAlF8Sr9uuOPfTCN1qWiJPvz4z7pLmpBuJGabjXecYQDrhRfITK jBtQi272qTgQ== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.73,368,1583222400"; d="scan'208";a="285584857" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga004.fm.intel.com with ESMTP; 08 May 2020 12:58:55 -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: Fri, 8 May 2020 20:58:49 +0100 Message-Id: <cover.1588967562.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <cover.1586974408.git.vladimir.medvedkin@intel.com> References: <cover.1586974408.git.vladimir.medvedkin@intel.com> Subject: [dpdk-dev] [PATCH v4 0/4] add new kv 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 kv hash table | |
Message
Medvedkin, Vladimir
May 8, 2020, 7:58 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 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
Comments
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.