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 B9852A0563; Wed, 15 Apr 2020 20:17:49 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id C1D701D9CF; Wed, 15 Apr 2020 20:17:37 +0200 (CEST) Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by dpdk.org (Postfix) with ESMTP id 986A01D9C3 for ; Wed, 15 Apr 2020 20:17:34 +0200 (CEST) IronPort-SDR: SYUXpVdaKXKDfRJBdsV5eb6Tv6UpXsq7iZZ5cuHLfl1YKOQzZSk6hKdg4/GPB0XMfrJ1ViCQH8 8/azUJ5+6Qnw== 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:34 -0700 IronPort-SDR: /CtFvZoqXjORdcBvuCh3i9ZyWRRbc4smov2J7b6AyHr11SjMh7wEXI07hGlEw2SZE4jCtK3C1E WkJuk0RRotgQ== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.72,388,1580803200"; d="scan'208";a="277702364" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by fmsmga004.fm.intel.com with ESMTP; 15 Apr 2020 11:17:32 -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, john.mcnamara@intel.com Date: Wed, 15 Apr 2020 19:17:25 +0100 Message-Id: <34e8fe21cbfd9cbf7d5c208564180274ee63d518.1586974411.git.vladimir.medvedkin@intel.com> 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 v3 2/4] hash: add documentation for k32v64 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 k32v64 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/k32v64_hash_lib.rst | 66 +++++++++++++++++++++++++++++++ 3 files changed, 68 insertions(+) create mode 100644 doc/guides/prog_guide/k32v64_hash_lib.rst diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md index dff496b..ed3e8d7 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), + [K32V64 hash] (@ref rte_k32v64_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 fb250ab..ac56da5 100644 --- a/doc/guides/prog_guide/index.rst +++ b/doc/guides/prog_guide/index.rst @@ -30,6 +30,7 @@ Programmer's Guide link_bonding_poll_mode_drv_lib timer_lib hash_lib + k32v64_hash_lib efd_lib member_lib lpm_lib diff --git a/doc/guides/prog_guide/k32v64_hash_lib.rst b/doc/guides/prog_guide/k32v64_hash_lib.rst new file mode 100644 index 0000000..238033a --- /dev/null +++ b/doc/guides/prog_guide/k32v64_hash_lib.rst @@ -0,0 +1,66 @@ +.. SPDX-License-Identifier: BSD-3-Clause + Copyright(c) 2020 Intel Corporation. + +.. _k32v64_hash_Library: + +K32V64 Hash Library +=================== + +This hash library implementation is intended to be better optimized for 32-bit keys when compared to existing Cuckoo hash-based rte_hash implementation. 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) + +K32V64 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 + +K32V64 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