From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 1ED8CA0352; Fri, 8 May 2020 21:59:19 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id DF9CB1DA49; Fri, 8 May 2020 21:59:04 +0200 (CEST) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 057511DA1C for ; Fri, 8 May 2020 21:59:00 +0200 (CEST) IronPort-SDR: yuHXyVK5fVcs3KhJqvdt0vqPay633CS7yc3/GsDjk3jzdLRa+l0HPF1CzMoIUf2ylcmS44ixsx lolr3TQuMVmw== 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:59:00 -0700 IronPort-SDR: 8SxWuMT+fUEUstK+648IyUVe5pKHAEmd0EHEI5FBHNPOLXTDT7vEj5hdjRYHxQ1dtmq8FqPveT 8FOScgq4shzA== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.73,368,1583222400"; d="scan'208";a="285584888" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga004.fm.intel.com with ESMTP; 08 May 2020 12:58:59 -0700 From: Vladimir Medvedkin 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:51 +0100 Message-Id: X-Mailer: git-send-email 2.7.4 In-Reply-To: References: MIME-Version: 1.0 In-Reply-To: References: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Subject: [dpdk-dev] [PATCH v4 2/4] hash: add documentation for kv hash library X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Add programmers guide and doxygen API for kv hash library Signed-off-by: Vladimir Medvedkin --- doc/api/doxy-api-index.md | 1 + doc/guides/prog_guide/index.rst | 1 + doc/guides/prog_guide/kv_hash_lib.rst | 66 +++++++++++++++++++++++++++++++++++ 3 files changed, 68 insertions(+) create mode 100644 doc/guides/prog_guide/kv_hash_lib.rst diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md index 93f0d93..eade5f5 100644 --- a/doc/api/doxy-api-index.md +++ b/doc/api/doxy-api-index.md @@ -121,6 +121,7 @@ The public API headers are grouped by topics: [jhash] (@ref rte_jhash.h), [thash] (@ref rte_thash.h), [FBK hash] (@ref rte_fbk_hash.h), + [KV hash] (@ref rte_kv_hash.h), [CRC hash] (@ref rte_hash_crc.h) - **classification** diff --git a/doc/guides/prog_guide/index.rst b/doc/guides/prog_guide/index.rst index f0ae3c1..28ddb2b 100644 --- a/doc/guides/prog_guide/index.rst +++ b/doc/guides/prog_guide/index.rst @@ -31,6 +31,7 @@ Programmer's Guide link_bonding_poll_mode_drv_lib timer_lib hash_lib + kv_hash_lib efd_lib member_lib lpm_lib diff --git a/doc/guides/prog_guide/kv_hash_lib.rst b/doc/guides/prog_guide/kv_hash_lib.rst new file mode 100644 index 0000000..44ed99a --- /dev/null +++ b/doc/guides/prog_guide/kv_hash_lib.rst @@ -0,0 +1,66 @@ +.. SPDX-License-Identifier: BSD-3-Clause + Copyright(c) 2020 Intel Corporation. + +.. _kv_hash_Library: + +KV Hash Library +=================== + +This hash library implementation is intended to be better optimized for some fixed key-value sizes when compared to existing Cuckoo hash-based rte_hash implementation. At the moment it supports 32-bit keys and 64 bit values. Current rte_fbk implementation is pretty fast but it has a number of drawbacks such as 2 byte values and limited collision resolving capabilities. rte_hash (which is based on Cuckoo hash algorithm) doesn't have these drawbacks, but it comes at a cost of lower performance compared to rte_fbk. + +The following flow illustrates the source of performance penalties of Cuckoo hash: + +* Loading two buckets at once (extra memory consumption) +* Сomparing signatures first (extra step before key comparison) +* If signature comparison hits, get a key index, find memory location with a key itself, and get the key (memory pressure and indirection) +* Using indirect call to memcmp() to compare two uint32_t (function call overhead) + +KV hash table doesn't have the drawbacks associated with rte_fbk while offering the same performance as rte_fbk. The bucket contains 4 consecutive keys which can be compared very quickly, and subsequent keys are kept in a linked list. + +The main disadvantage compared to rte_hash is performance degradation with high average table utilization due to chain resolving for 5th and subsequent collisions. + +To estimate the probability of 5th collision we can use "birthday paradox" approach. We can figure out the number of insertions (can be treated as a load factor) that will likely yield a 50% probability of 5th collision for a given number of buckets. + +It could be calculated with an asymptotic formula from [1]: + +E(n, k) ~= (k!)^(1/k)*Γ(1 + 1/k)*n^(1-1/k), n -> inf + +,where + +k - level of collision + +n - number of buckets + +Г - gamma function + +So, for k = 5 (5th collision), and given the fact that number of buckets is a power of 2, we can simplify formula: + +E(n) = 2.392 * 2^(m * 4/5) , where number of buckets n = 2^m + +.. note:: + + You can calculate it by yourself using Wolfram Alpha [2]. For example for 8k buckets: + + solve ((k!)^(1/k)*Γ(1 + 1/k)*n^(1-1/k), n = 8192, k = 5) + + +API Overview +----------------- + +The main configuration parameters for the hash table are: + +* Total number of hash entries in the table +* Socket id + +KV hash is "hash function-less", so user must specify precalculated hash value for every key. The main methods exported by the Hash Library are: + +* Add entry with key and precomputed hash: The key, precomputed hash and value are provided as input. +* Delete entry with key and precomputed hash: The key and precomputed hash are provided as input. +* Lookup entry with key and precomputed hash: The key, precomputed hash and a pointer to expected value are provided as input. If an entry with the specified key is found in the hash table (i.e. lookup hit), then the value associated with the key will be written to the memory specified by the pointer, and the function will return 0; otherwise (i.e. a lookup miss) a negative value is returned, and memory described by the pointer is not modified. + +References +---------- + +[1] M.S. Klamkin and D.J. Newman, Extensions of the Birthday Surprise + +[2] https://www.wolframalpha.com/ -- 2.7.4