Cover Comment List
List cover comments
GET /api/covers/45148/comments/?format=api
[ { "id": 86150, "web_url": "http://patches.dpdk.org/comment/86150/", "msgid": "<20180926125706.GB14380@bricha3-MOBL.ger.corp.intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/20180926125706.GB14380@bricha3-MOBL.ger.corp.intel.com", "date": "2018-09-26T12:57:06", "subject": "Re: [dpdk-dev] [PATCH v2 0/7] hash: add extendable bucket and\n\tpartial key hashing", "submitter": { "id": 20, "url": "http://patches.dpdk.org/api/people/20/?format=api", "name": "Bruce Richardson", "email": "bruce.richardson@intel.com" }, "content": "On Fri, Sep 21, 2018 at 10:17:28AM -0700, Yipeng Wang wrote:\n> The first four commits of the patch set try to fix small issues of\n> previous code.\n> \n> The other commits make two major optimizations over the current rte_hash\n> library.\n> \nI'd suggest splitting this set into two. The first 4 patches are easy to\nreview and should be quickly merged (I hope :-)), allowing us to focus more on\nthe bigger patches adding the key new feature support.\n\n/Bruce", "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 91FEB1B445;\n\tWed, 26 Sep 2018 14:57:11 +0200 (CEST)", "from mga07.intel.com (mga07.intel.com [134.134.136.100])\n\tby dpdk.org (Postfix) with ESMTP id BEE5F1B439\n\tfor <dev@dpdk.org>; Wed, 26 Sep 2018 14:57:10 +0200 (CEST)", "from fmsmga006.fm.intel.com ([10.253.24.20])\n\tby orsmga105.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;\n\t26 Sep 2018 05:57:10 -0700", "from bricha3-mobl.ger.corp.intel.com ([10.237.221.107])\n\tby fmsmga006.fm.intel.com with SMTP; 26 Sep 2018 05:57:07 -0700", "by (sSMTP sendmail emulation); Wed, 26 Sep 2018 13:57:06 +0100" ], "X-Amp-Result": "UNSCANNABLE", "X-Amp-File-Uploaded": "False", "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.54,306,1534834800\"; d=\"scan'208\";a=\"266848605\"", "Date": "Wed, 26 Sep 2018 13:57:06 +0100", "From": "Bruce Richardson <bruce.richardson@intel.com>", "To": "Yipeng Wang <yipeng1.wang@intel.com>", "Cc": "dev@dpdk.org, michel@digirati.com.br, honnappa.nagarahalli@arm.com", "Message-ID": "<20180926125706.GB14380@bricha3-MOBL.ger.corp.intel.com>", "References": "<1536253745-133104-1-git-send-email-yipeng1.wang@intel.com>\n\t<1537550255-252066-1-git-send-email-yipeng1.wang@intel.com>", "MIME-Version": "1.0", "Content-Type": "text/plain; charset=us-ascii", "Content-Disposition": "inline", "In-Reply-To": "<1537550255-252066-1-git-send-email-yipeng1.wang@intel.com>", "Organization": "Intel Research and Development Ireland Ltd.", "User-Agent": "Mutt/1.10.1 (2018-07-13)", "Subject": "Re: [dpdk-dev] [PATCH v2 0/7] 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>" }, "addressed": null }, { "id": 86186, "web_url": "http://patches.dpdk.org/comment/86186/", "msgid": "<D2C4A16CA39F7F4E8E384D204491D7A6614BF006@FMSMSX151.amr.corp.intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/D2C4A16CA39F7F4E8E384D204491D7A6614BF006@FMSMSX151.amr.corp.intel.com", "date": "2018-09-27T03:41:36", "subject": "Re: [dpdk-dev] [PATCH v2 0/7] hash: add extendable bucket and\n\tpartial key hashing", "submitter": { "id": 754, "url": "http://patches.dpdk.org/api/people/754/?format=api", "name": "Wang, Yipeng1", "email": "yipeng1.wang@intel.com" }, "content": "Done! Now they are two separate patch sets.\n\nThanks\nYipeng\n\n>-----Original Message-----\n>From: Richardson, Bruce\n>I'd suggest splitting this set into two. The first 4 patches are easy to\n>review and should be quickly merged (I hope :-)), allowing us to focus more on\n>the bigger patches adding the key new feature support.\n>\n>/Bruce", "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 708B71B13F;\n\tThu, 27 Sep 2018 05:41:42 +0200 (CEST)", "from mga12.intel.com (mga12.intel.com [192.55.52.136])\n\tby dpdk.org (Postfix) with ESMTP id 202E51B136\n\tfor <dev@dpdk.org>; Thu, 27 Sep 2018 05:41:40 +0200 (CEST)", "from fmsmga002.fm.intel.com ([10.253.24.26])\n\tby fmsmga106.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;\n\t26 Sep 2018 20:41:40 -0700", "from fmsmsx105.amr.corp.intel.com ([10.18.124.203])\n\tby fmsmga002.fm.intel.com with ESMTP; 26 Sep 2018 20:41:37 -0700", "from fmsmsx151.amr.corp.intel.com ([169.254.7.87]) by\n\tFMSMSX105.amr.corp.intel.com ([169.254.4.63]) with mapi id\n\t14.03.0319.002; Wed, 26 Sep 2018 20:41:37 -0700" ], "X-Amp-Result": "SKIPPED(no attachment in message)", "X-Amp-File-Uploaded": "False", "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.54,308,1534834800\"; d=\"scan'208\";a=\"89727443\"", "From": "\"Wang, Yipeng1\" <yipeng1.wang@intel.com>", "To": "\"Richardson, Bruce\" <bruce.richardson@intel.com>", "CC": "\"dev@dpdk.org\" <dev@dpdk.org>, \"Gobriel, Sameh\" <sameh.gobriel@intel.com>", "Thread-Topic": "[PATCH v2 0/7] hash: add extendable bucket and partial key\n\thashing", "Thread-Index": "AQHUVZhz9goevBjst0qR7BsRvEtccaUDfI7Q", "Date": "Thu, 27 Sep 2018 03:41:36 +0000", "Message-ID": "<D2C4A16CA39F7F4E8E384D204491D7A6614BF006@FMSMSX151.amr.corp.intel.com>", "References": "<1536253745-133104-1-git-send-email-yipeng1.wang@intel.com>\n\t<1537550255-252066-1-git-send-email-yipeng1.wang@intel.com>\n\t<20180926125706.GB14380@bricha3-MOBL.ger.corp.intel.com>", "In-Reply-To": "<20180926125706.GB14380@bricha3-MOBL.ger.corp.intel.com>", "Accept-Language": "en-US", "Content-Language": "en-US", "X-MS-Has-Attach": "", "X-MS-TNEF-Correlator": "", "dlp-product": "dlpe-windows", "dlp-version": "11.0.400.15", "dlp-reaction": "no-action", "x-ctpclassification": "CTP_NT", "x-titus-metadata-40": "eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiNzRlOWJlNWYtYmViZC00NGVhLWE2N2UtOTZkZmFjYmIxNWZhIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiUFcyRDhWdkJCbVFjS1JZVTd5RTRtK0pBQ0huTE1tUTRsYzRQYjQrUmRjbmFMVTZxc2RndnJyZnB1SXZyd1lUcyJ9", "x-originating-ip": "[10.1.200.108]", "Content-Type": "text/plain; charset=\"us-ascii\"", "Content-Transfer-Encoding": "quoted-printable", "MIME-Version": "1.0", "Subject": "Re: [dpdk-dev] [PATCH v2 0/7] 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>" }, "addressed": null }, { "id": 86188, "web_url": "http://patches.dpdk.org/comment/86188/", "msgid": "<AM6PR08MB3672ED8AC62B0C573756E85F98140@AM6PR08MB3672.eurprd08.prod.outlook.com>", "list_archive_url": "https://inbox.dpdk.org/dev/AM6PR08MB3672ED8AC62B0C573756E85F98140@AM6PR08MB3672.eurprd08.prod.outlook.com", "date": "2018-09-27T04:23:10", "subject": "Re: [dpdk-dev] [PATCH v2 0/7] hash: add extendable bucket and\n\tpartial key hashing", "submitter": { "id": 1045, "url": "http://patches.dpdk.org/api/people/1045/?format=api", "name": "Honnappa Nagarahalli", "email": "honnappa.nagarahalli@arm.com" }, "content": "> -----Original Message-----\n> From: Yipeng Wang <yipeng1.wang@intel.com>\n> Sent: Friday, September 21, 2018 12:17 PM\n> To: bruce.richardson@intel.com\n> Cc: dev@dpdk.org; yipeng1.wang@intel.com; michel@digirati.com.br;\n> Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>\n> Subject: [PATCH v2 0/7] hash: add extendable bucket and partial key hashing\n> \n> The first four commits of the patch set try to fix small issues of previous code.\n> \n> The other commits make two major optimizations over the current rte_hash\n> library.\n> \n> First, it adds Extendable Bucket Table feature: a new structure that can\n> accommodate keys that failed to get inserted into the main hash table due to\n> the unlikely event of excessive hash collisions. The hash table buckets will get\n> extended using a linked list to host these keys. This new design will guarantee\n> insertion of 100% of the keys for a given hash table size with minimal\n> overhead. A new flag value is added for user to indicate if the extendable\n> bucket feature should be enabled or not. The linked list buckets is similar\n> concept to the extendable bucket hash table in packet framework.\n> In details, for insertion, the linked buckets will be used to store the keys that\n> fail to get in the primary and the secondary bucket and the cuckoo path could\n> not find an empty location for the maximum path length (small probability).\n> For lookup, the key is checked first in the primary, then the secondary, then if\n> the secondary is extended the linked list is traversed for a possible match.\n> \n> Second, the patch set changes the current hashing algorithm to be \"partial-\n> key hashing\". Partial-key hashing is the concept from Bin Fan, et al.'s paper\n> \"MemC3: Compact and Concurrent MemCache with Dumber Caching and\n> Smarter Hashing\".\nI read this paper (but not the papers in references). My understanding is that the existing algorithm already uses 'partial-key hashing'. This patch set is not adding the 'partial-key hashing' feature. Instead it is reducing the size of the signature ('tag' as referred in the paper) from 32 to 16b.\nPlease let me know if I have not understood this correct.\n\n> Instead of storing both 32-bit signature and alternative\n> signature in the bucket, we only store a small 16-bit signature and calculate\n> the alternative bucket index by XORing the signature with the current bucket\n> index.\nAccording to the referenced paper, the signature ('tag') reduces the number of accesses to the keys, thus improving the performance.\nBut, if we reduce the size of the signature from 32b to 16b, it will result in higher probability of false matches on the signature. This in turn will increase the number of accesses to keys. Have you run any performance benchmarks and compared the numbers with the existing code? Is it possible to share the numbers?\n\n> This doubles the hash table memory efficiency since now one bucket only\n> occupies one cache line instead of two in the original design.\nAgree, reduced memory footprint should help increase the performance.\n\n> \n> V1->V2:\n> 1. hash: Rewrite rte_hash_get_last_bkt to be more concise.\n> 2. hash: Reorder the rte_hash struct to align cache line better.\n> 3. test: Minor changes in auto test to add key insertion failure check during\n> iteration test.\n> 4. test: Add new commit to fix read-write test non-consecutive core issue.\n> 4. hash: Add a new commit to remove unnecessary code introduced by\n> previous patches.\n> 5. hash: Comments improvement and coding style improvements over\n> multiple places.\n> \n> Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>\n> \n> Yipeng Wang (7):\n> test/hash: fix bucket size in hash perf test\n> test/hash: more accurate hash perf test output\n> test/hash: fix rw test with non-consecutive cores\n> hash: fix unnecessary code\n> hash: add extendable bucket feature\n> test/hash: implement extendable bucket hash test\n> hash: use partial-key hashing\n> \n> lib/librte_hash/rte_cuckoo_hash.c | 516 +++++++++++++++++++++++++++------\n> -----\n> lib/librte_hash/rte_cuckoo_hash.h | 13 +-\n> lib/librte_hash/rte_hash.h | 8 +-\n> test/test/test_hash.c | 151 ++++++++++-\n> test/test/test_hash_perf.c | 126 +++++++---\n> test/test/test_hash_readwrite.c | 78 +++---\n> 6 files changed, 672 insertions(+), 220 deletions(-)\n> \n> --\n> 2.7.4", "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 4495058F6;\n\tThu, 27 Sep 2018 06:23:14 +0200 (CEST)", "from EUR02-AM5-obe.outbound.protection.outlook.com\n\t(mail-eopbgr00073.outbound.protection.outlook.com [40.107.0.73])\n\tby dpdk.org (Postfix) with ESMTP id 1333158EC\n\tfor <dev@dpdk.org>; Thu, 27 Sep 2018 06:23:11 +0200 (CEST)", "from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by\n\tAM6PR08MB3302.eurprd08.prod.outlook.com (52.135.164.159) with\n\tMicrosoft SMTP Server (version=TLS1_2,\n\tcipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id\n\t15.20.1185.20; Thu, 27 Sep 2018 04:23:10 +0000", "from AM6PR08MB3672.eurprd08.prod.outlook.com\n\t([fe80::589e:d3cf:9777:5ff9]) by\n\tAM6PR08MB3672.eurprd08.prod.outlook.com\n\t([fe80::589e:d3cf:9777:5ff9%2]) with mapi id 15.20.1164.024;\n\tThu, 27 Sep 2018 04:23:10 +0000" ], "DKIM-Signature": "v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com;\n\ts=selector1-arm-com;\n\th=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck;\n\tbh=KrqWg136Ujab/ATR3oG8+IZg4oioJjtE+ATYwTWuQXA=;\n\tb=R/CNxMXJT9VsKqpaEvek+9G4BBD0lBleALu7J0Rh0cptP3t8dK5k8yI3WVK06mDhxNmPlw7Y4+hXXyOphAD1boeRDOsoB/D4zxFp9Y56YH3n3Yv2fjkKLQNiBHZn1MEBRuu9EjZB1QlTDAvw7x/JuRbGUc7+Dc18/VCpfw9QVCg=", "From": "Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>", "To": "Yipeng Wang <yipeng1.wang@intel.com>, \"bruce.richardson@intel.com\"\n\t<bruce.richardson@intel.com>", "CC": "\"dev@dpdk.org\" <dev@dpdk.org>, \"michel@digirati.com.br\"\n\t<michel@digirati.com.br>, nd <nd@arm.com>", "Thread-Topic": "[PATCH v2 0/7] hash: add extendable bucket and partial key\n\thashing", "Thread-Index": "AQHUUgpQvkUCpgBJyE2x4Kf8Y9Fg+KT8zaJg", "Date": "Thu, 27 Sep 2018 04:23:10 +0000", "Message-ID": "<AM6PR08MB3672ED8AC62B0C573756E85F98140@AM6PR08MB3672.eurprd08.prod.outlook.com>", "References": "<1536253745-133104-1-git-send-email-yipeng1.wang@intel.com>\n\t<1537550255-252066-1-git-send-email-yipeng1.wang@intel.com>", "In-Reply-To": "<1537550255-252066-1-git-send-email-yipeng1.wang@intel.com>", "Accept-Language": "en-US", "Content-Language": "en-US", "X-MS-Has-Attach": "", "X-MS-TNEF-Correlator": "", "authentication-results": "spf=none (sender IP is )\n\tsmtp.mailfrom=Honnappa.Nagarahalli@arm.com; ", "x-originating-ip": "[217.140.111.135]", "x-ms-publictraffictype": "Email", "x-microsoft-exchange-diagnostics": "1; AM6PR08MB3302;\n\t6:NMDZA2IOIx6kw2pFc6v6SzKSBn3MuJUurF7EXyCjpYe3uRbyT4cx5wHw0kP6cfWWHdNSNzFOwxpiSveONC55Pye4YnBYAt+169grF4PedFeRdsAQo36xGw9lB6a89A4rrT4etjjlgjdnU7X0ZTB14NhK46dpfHbVyQg3ed+5lIwbkczSCk3Jbv0e/GgIJl9LHDbOgnj/QNC4bbqK2H8qdliSFD3Qwd6VLHAjFsvNUfw4Xg8alhSZh38CB5n1EcCOn1V3832EWffRPbnN7MTeX2hVqJFCw2jnX5JB61gq/UsVRMYDavzphBGYX88j/WdmXTiv+pmMnLCJb9iohaPVz8WeTSpIqmYQYvDrtyS6Sp6XW6g0yyUlEVnbyJbwGJ5Ww6e8C1myLL7xwBWIToMz3z3BbtIDwa37GvmQ35IM5BtxuG6kPoAgtC2urY3hsVsyRJDhcAGN62INbbTM1cr9WQ==;\n\t5:Je+Y3TdX/W86IOCwm+i6I3tHbZktceSwjaEIY53VIAqel3qUO160rTEu5ds9gGOJx2emWHnGdy6Gy2xr4Q+VJg7NbLh9ZgOvz7IhLbkI7LIeDsLeESvh+P/nqbrIiA0c+NPG8nXwNx6DuijBwR5BAdPy+NBTEaKRUXXm1R85hsg=;\n\t7:eZVQXXGm4m4JVta5wGFiX0WJtRRGgrY1W/2bG/kAhNUgdj8xeLKUQI/IwYXC0G4hhrKhMQ6/+gMel9zcS05I6TtV0344TFrcK8hfUNpTLwKrKSjwEDPhsdZNonLQNmrwtthmcQUW3WBHa5UgmGsoaIrmpc5VJj+vEJ82GSb2/cCOYwBmmMgwfUQ7YbJ8ELV1Hyy9zu9aSpvZW94uTqXUQaPkotOdaBJjdUgEuF1e4uBDfjjN2/64U9jaSN32Ez6N", "x-ms-exchange-antispam-srfa-diagnostics": "SOS;", "x-ms-office365-filtering-correlation-id": "27e2f35c-230c-425a-1b8f-08d62430eeec", "x-ms-office365-filtering-ht": "Tenant", "x-microsoft-antispam": "BCL:0; PCL:0;\n\tRULEID:(7020095)(4652040)(8989299)(4534165)(4627221)(201703031133081)(201702281549075)(8990200)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020);\n\tSRVR:AM6PR08MB3302; ", "x-ms-traffictypediagnostic": "AM6PR08MB3302:", "nodisclaimer": "True", "x-microsoft-antispam-prvs": "<AM6PR08MB33020A60D82FC5AFADD17B9798140@AM6PR08MB3302.eurprd08.prod.outlook.com>", "x-exchange-antispam-report-test": "UriScan:(228905959029699)(166494164430575)(180628864354917); ", "x-ms-exchange-senderadcheck": "1", "x-exchange-antispam-report-cfa-test": "BCL:0; PCL:0;\n\tRULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(3231355)(944501410)(52105095)(93006095)(93001095)(3002001)(10201501046)(6055026)(149066)(150057)(6041310)(20161123560045)(20161123562045)(20161123564045)(20161123558120)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(201708071742011)(7699051);\n\tSRVR:AM6PR08MB3302; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3302; ", "x-forefront-prvs": "0808323E97", "x-forefront-antispam-report": "SFV:NSPM;\n\tSFS:(10009020)(366004)(376002)(136003)(346002)(39860400002)(396003)(199004)(189003)(13464003)(53936002)(34290500001)(53546011)(9686003)(6436002)(6506007)(55016002)(76176011)(7696005)(7736002)(305945005)(74316002)(86362001)(2900100001)(256004)(2906002)(14444005)(229853002)(71190400001)(71200400001)(97736004)(5660300001)(99286004)(102836004)(6246003)(3846002)(6116002)(8936002)(476003)(14454004)(54906003)(5250100002)(26005)(66066001)(68736007)(186003)(2501003)(110136005)(4326008)(25786009)(33656002)(486006)(8676002)(81156014)(81166006)(106356001)(105586002)(316002)(478600001)(72206003)(446003)(11346002);\n\tDIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3302;\n\tH:AM6PR08MB3672.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en;\n\tPTR:InfoNoRecords; A:1; MX:1; ", "received-spf": "None (protection.outlook.com: arm.com does not designate\n\tpermitted sender hosts)", "x-microsoft-antispam-message-info": "/kcNSqoiE/VbfOSVPyiZjRqMYMEvzBmsnujTm1mID+FVrdYKMZLjAiXS4KVl+Qca8ByRvn5Iy8e2sVw+OMYEFwCToxtaXTsb11tPm44JHro3+iX1M4DGznUZ1wZ+7jHtJZ3bK67p6iZb6TZUpB8RSeis5j7nmnKxMGsOmIvn0JHCKjGWUevAn2iiebVQ6b0g5nsbitvsXNMY6jHUavFuofM/V7P9v7l4oxCePNT5kJ75CnZXGj3S9bGVANF60F7VXax03VFoSqexIAhKlSMOx1/IVnFtCM/i1VemmzhL6L8XAwJFjum8J6eTesa0WZubXDV3dvs9MZ1q1cftZjJxhl7eH0MEOWM2YeoV6ftRI54=", "spamdiagnosticoutput": "1:99", "spamdiagnosticmetadata": "NSPM", "Content-Type": "text/plain; charset=\"us-ascii\"", "Content-Transfer-Encoding": "quoted-printable", "MIME-Version": "1.0", "X-OriginatorOrg": "arm.com", "X-MS-Exchange-CrossTenant-Network-Message-Id": "27e2f35c-230c-425a-1b8f-08d62430eeec", "X-MS-Exchange-CrossTenant-originalarrivaltime": "27 Sep 2018 04:23:10.3403\n\t(UTC)", "X-MS-Exchange-CrossTenant-fromentityheader": "Hosted", "X-MS-Exchange-CrossTenant-id": "f34e5979-57d9-4aaa-ad4d-b122a662184d", "X-MS-Exchange-Transport-CrossTenantHeadersStamped": "AM6PR08MB3302", "Subject": "Re: [dpdk-dev] [PATCH v2 0/7] 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>" }, "addressed": null }, { "id": 86349, "web_url": "http://patches.dpdk.org/comment/86349/", "msgid": "<D2C4A16CA39F7F4E8E384D204491D7A6614E9719@FMSMSX151.amr.corp.intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/D2C4A16CA39F7F4E8E384D204491D7A6614E9719@FMSMSX151.amr.corp.intel.com", "date": "2018-09-29T00:46:15", "subject": "Re: [dpdk-dev] [PATCH v2 0/7] hash: add extendable bucket and\n\tpartial key hashing", "submitter": { "id": 754, "url": "http://patches.dpdk.org/api/people/754/?format=api", "name": "Wang, Yipeng1", "email": "yipeng1.wang@intel.com" }, "content": ">-----Original Message-----\n>From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]\n>> Second, the patch set changes the current hashing algorithm to be \"partial-\n>> key hashing\". Partial-key hashing is the concept from Bin Fan, et al.'s paper\n>> \"MemC3: Compact and Concurrent MemCache with Dumber Caching and\n>> Smarter Hashing\".\n>I read this paper (but not the papers in references). My understanding is that the existing algorithm already uses 'partial-key hashing'.\n>This patch set is not adding the 'partial-key hashing' feature. Instead it is reducing the size of the signature ('tag' as referred in the\n>paper) from 32 to 16b.\n>Please let me know if I have not understood this correct.\n[Wang, Yipeng] Currently two signature values are stored in hash table: sig_current and sig_alt.\nThey are used to derived the index of two alternative buckets.\nPartial key hashing avoids storing two values, but stores only one. The alternative bucket\nIndex is derived by XOR this single signature with the current bucket index.\nSo, this commit not only reduces the signature size from 32-bit to 16-bit, it also\nreduces the number of signatures stored from two to one.\nAs a result, we can use one 64-byte cache line for the bucket instead of two.\n\n>> Instead of storing both 32-bit signature and alternative\n>> signature in the bucket, we only store a small 16-bit signature and calculate\n>> the alternative bucket index by XORing the signature with the current bucket\n>> index.\n>According to the referenced paper, the signature ('tag') reduces the number of accesses to the keys, thus improving the performance.\n>But, if we reduce the size of the signature from 32b to 16b, it will result in higher probability of false matches on the signature. This in\n>turn will increase the number of accesses to keys. Have you run any performance benchmarks and compared the numbers with the\n>existing code? Is it possible to share the numbers?\n>\n[Wang, Yipeng] \nFrom our test it is very unlikely that two different keys would map to the same bucket and also have the same 16-bit signature.\nEven we reduce the signature size from 32-bit to 16-bit, it should be very very rare assuming a good hash function.\nFor performance numbers, it could vary depending on the test case. Since the speedup comes from the 2X memory efficiency,\nIf your hash table is large (e.g. over last level cache), it will give much higher speedup. For the existing unit test, I generally seen 10% speedup.", "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 763B31B1FC;\n\tSat, 29 Sep 2018 02:50:41 +0200 (CEST)", "from mga12.intel.com (mga12.intel.com [192.55.52.136])\n\tby dpdk.org (Postfix) with ESMTP id 2548F1B1F9\n\tfor <dev@dpdk.org>; Sat, 29 Sep 2018 02:50:39 +0200 (CEST)", "from orsmga001.jf.intel.com ([10.7.209.18])\n\tby fmsmga106.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;\n\t28 Sep 2018 17:50:38 -0700", "from fmsmsx104.amr.corp.intel.com ([10.18.124.202])\n\tby orsmga001.jf.intel.com with ESMTP; 28 Sep 2018 17:46:17 -0700", "from fmsmsx157.amr.corp.intel.com (10.18.116.73) by\n\tfmsmsx104.amr.corp.intel.com (10.18.124.202) with Microsoft SMTP\n\tServer (TLS) id 14.3.319.2; Fri, 28 Sep 2018 17:46:16 -0700", "from fmsmsx151.amr.corp.intel.com ([169.254.7.87]) by\n\tFMSMSX157.amr.corp.intel.com ([169.254.14.71]) with mapi id\n\t14.03.0319.002; Fri, 28 Sep 2018 17:46:16 -0700" ], "X-Amp-Result": "SKIPPED(no attachment in message)", "X-Amp-File-Uploaded": "False", "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.54,317,1534834800\"; d=\"scan'208\";a=\"94889566\"", "From": "\"Wang, Yipeng1\" <yipeng1.wang@intel.com>", "To": "Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>, \"Richardson, Bruce\"\n\t<bruce.richardson@intel.com>", "CC": "\"dev@dpdk.org\" <dev@dpdk.org>, \"michel@digirati.com.br\"\n\t<michel@digirati.com.br>, nd <nd@arm.com>", "Thread-Topic": "[PATCH v2 0/7] hash: add extendable bucket and partial key\n\thashing", "Thread-Index": "AQHUUgpQ9goevBjst0qR7BsRvEtccaT8zaJggAml8eA=", "Date": "Sat, 29 Sep 2018 00:46:15 +0000", "Message-ID": "<D2C4A16CA39F7F4E8E384D204491D7A6614E9719@FMSMSX151.amr.corp.intel.com>", "References": "<1536253745-133104-1-git-send-email-yipeng1.wang@intel.com>\n\t<1537550255-252066-1-git-send-email-yipeng1.wang@intel.com>\n\t<AM6PR08MB3672ED8AC62B0C573756E85F98140@AM6PR08MB3672.eurprd08.prod.outlook.com>", "In-Reply-To": "<AM6PR08MB3672ED8AC62B0C573756E85F98140@AM6PR08MB3672.eurprd08.prod.outlook.com>", "Accept-Language": "en-US", "Content-Language": "en-US", "X-MS-Has-Attach": "", "X-MS-TNEF-Correlator": "", "dlp-product": "dlpe-windows", "dlp-version": "11.0.400.15", "dlp-reaction": "no-action", "x-ctpclassification": "CTP_NT", "x-titus-metadata-40": "eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiZjUzYzRkMmMtZGZiNS00N2U5LTk0OTItMTA0OGU0ZGZiOTkwIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoic2ZiTmNjYkZDSjNtNmkzTFBkRVwveGlvNTN0TjArVjNjQkh0NDdSTkkzTWlzb0Q3bGE2d0R5WlNOSVhFUHlDRHQifQ==", "x-originating-ip": "[10.1.200.106]", "Content-Type": "text/plain; charset=\"us-ascii\"", "Content-Transfer-Encoding": "quoted-printable", "MIME-Version": "1.0", "Subject": "Re: [dpdk-dev] [PATCH v2 0/7] 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>" }, "addressed": null } ]