Cover Detail
Show a cover letter.
GET /api/covers/44366/?format=api
{ "id": 44366, "url": "http://patches.dpdk.org/api/covers/44366/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/cover/1536253745-133104-1-git-send-email-yipeng1.wang@intel.com/", "project": { "id": 1, "url": "http://patches.dpdk.org/api/projects/1/?format=api", "name": "DPDK", "link_name": "dpdk", "list_id": "dev.dpdk.org", "list_email": "dev@dpdk.org", "web_url": "http://core.dpdk.org", "scm_url": "git://dpdk.org/dpdk", "webscm_url": "http://git.dpdk.org/dpdk", "list_archive_url": "https://inbox.dpdk.org/dev", "list_archive_url_format": "https://inbox.dpdk.org/dev/{}", "commit_url_format": "" }, "msgid": "<1536253745-133104-1-git-send-email-yipeng1.wang@intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/1536253745-133104-1-git-send-email-yipeng1.wang@intel.com", "date": "2018-09-06T17:09:00", "name": "[v1,0/5] hash: add extendable bucket and partial-key hashing", "submitter": { "id": 754, "url": "http://patches.dpdk.org/api/people/754/?format=api", "name": "Wang, Yipeng1", "email": "yipeng1.wang@intel.com" }, "mbox": "http://patches.dpdk.org/project/dpdk/cover/1536253745-133104-1-git-send-email-yipeng1.wang@intel.com/mbox/", "series": [ { "id": 1216, "url": "http://patches.dpdk.org/api/series/1216/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=1216", "date": "2018-09-06T17:09:00", "name": "hash: add extendable bucket and partial-key hashing", "version": 1, "mbox": "http://patches.dpdk.org/series/1216/mbox/" } ], "comments": "http://patches.dpdk.org/api/covers/44366/comments/", "headers": { "Return-Path": "<dev-bounces@dpdk.org>", "X-Original-To": "patchwork@dpdk.org", "Delivered-To": "patchwork@dpdk.org", "Received": [ "from [92.243.14.124] (localhost [127.0.0.1])\n\tby dpdk.org (Postfix) with ESMTP id BBB0A4C80;\n\tFri, 7 Sep 2018 02:13:50 +0200 (CEST)", "from mga04.intel.com (mga04.intel.com [192.55.52.120])\n\tby dpdk.org (Postfix) with ESMTP id 531EC37B0\n\tfor <dev@dpdk.org>; Fri, 7 Sep 2018 02:13:48 +0200 (CEST)", "from orsmga005.jf.intel.com ([10.7.209.41])\n\tby fmsmga104.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;\n\t06 Sep 2018 17:13:47 -0700", "from skx-yipeng.jf.intel.com ([10.54.81.175])\n\tby orsmga005.jf.intel.com with ESMTP; 06 Sep 2018 17:13:46 -0700" ], "X-Amp-Result": "SKIPPED(no attachment in message)", "X-Amp-File-Uploaded": "False", "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.53,340,1531810800\"; d=\"scan'208\";a=\"255176881\"", "From": "Yipeng Wang <yipeng1.wang@intel.com>", "To": "pablo.de.lara.guarch@intel.com,\n\tbruce.richardson@intel.com", "Cc": "dev@dpdk.org, yipeng1.wang@intel.com, michel@digirati.com.br,\n\thonnappa.nagarahalli@arm.com", "Date": "Thu, 6 Sep 2018 10:09:00 -0700", "Message-Id": "<1536253745-133104-1-git-send-email-yipeng1.wang@intel.com>", "X-Mailer": "git-send-email 2.7.4", "Subject": "[dpdk-dev] [PATCH v1 0/5] hash: add extendable bucket and\n\tpartial-key hashing", "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>,\n\t<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>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org", "Sender": "\"dev\" <dev-bounces@dpdk.org>" }, "content": "This patch set made two major improvements over the current rte_hash library.\n\nFirst, it adds Extendable Bucket Table feature: a new structure that can\naccommodate keys that failed to get inserted into the main hash table due to\nthe unlikely event of excessive hash collisions. The hash table buckets will\nget extended using a linked list to host these keys. This new design will\nguarantee insertion of 100% of the keys for a given hash table size with\nminimal overhead. A new flag value is added for user to indicate if the\nextendable bucket feature should be enabled or not. The linked list buckets is\nsimilar concept to the extendable bucket hash table in packet framework.\nIn details, for insertion, the linked buckets will be used to store the keys\nthat fail to get in the primary and the secondary bucket and the cuckoo path\ncould not find an empty location for the maximum path length (small\nprobability). For lookup, the key is checked first in the primary, then the\nsecondary, then if the secondary is extended the linked list is traversed\nfor a possible match.\n\nSecond, the patch set changes the current hashing algorithm to be \"partial-key\nhashing\". Partial-key hashing is the concept from Bin Fan, et al.'s paper\n\"MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter\nHashing\". Instead of storing both 32-bit signature and alternative signature\nin the bucket, we only store a small 16-bit signature and calculate the\nalternative bucket index by XORing the signature with the current bucket index.\nThis doubles the hash table memory efficiency since now one bucket\nonly occupies one cache line instead of two in the original design.\n\nSigned-off-by: Yipeng Wang <yipeng1.wang@intel.com>\n\nYipeng Wang (5):\n test: fix bucket size in hash table perf test\n test: more accurate hash table perf test output\n hash: add extendable bucket feature\n test: implement extendable bucket hash test\n hash: use partial-key hashing\n\n lib/librte_hash/rte_cuckoo_hash.c | 518 +++++++++++++++++++++++++++-----------\n lib/librte_hash/rte_cuckoo_hash.h | 11 +-\n lib/librte_hash/rte_hash.h | 3 +\n test/test/test_hash.c | 145 ++++++++++-\n test/test/test_hash_perf.c | 126 +++++++---\n 5 files changed, 618 insertions(+), 185 deletions(-)" }