From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR02-AM5-obe.outbound.protection.outlook.com (mail-eopbgr00073.outbound.protection.outlook.com [40.107.0.73]) by dpdk.org (Postfix) with ESMTP id 1333158EC for ; Thu, 27 Sep 2018 06:23:11 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=KrqWg136Ujab/ATR3oG8+IZg4oioJjtE+ATYwTWuQXA=; b=R/CNxMXJT9VsKqpaEvek+9G4BBD0lBleALu7J0Rh0cptP3t8dK5k8yI3WVK06mDhxNmPlw7Y4+hXXyOphAD1boeRDOsoB/D4zxFp9Y56YH3n3Yv2fjkKLQNiBHZn1MEBRuu9EjZB1QlTDAvw7x/JuRbGUc7+Dc18/VCpfw9QVCg= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by AM6PR08MB3302.eurprd08.prod.outlook.com (52.135.164.159) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1185.20; Thu, 27 Sep 2018 04:23:10 +0000 Received: from AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::589e:d3cf:9777:5ff9]) by AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::589e:d3cf:9777:5ff9%2]) with mapi id 15.20.1164.024; Thu, 27 Sep 2018 04:23:10 +0000 From: Honnappa Nagarahalli To: Yipeng Wang , "bruce.richardson@intel.com" CC: "dev@dpdk.org" , "michel@digirati.com.br" , nd Thread-Topic: [PATCH v2 0/7] hash: add extendable bucket and partial key hashing Thread-Index: AQHUUgpQvkUCpgBJyE2x4Kf8Y9Fg+KT8zaJg Date: Thu, 27 Sep 2018 04:23:10 +0000 Message-ID: References: <1536253745-133104-1-git-send-email-yipeng1.wang@intel.com> <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 ) smtp.mailfrom=Honnappa.Nagarahalli@arm.com; x-originating-ip: [217.140.111.135] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; AM6PR08MB3302; 6:NMDZA2IOIx6kw2pFc6v6SzKSBn3MuJUurF7EXyCjpYe3uRbyT4cx5wHw0kP6cfWWHdNSNzFOwxpiSveONC55Pye4YnBYAt+169grF4PedFeRdsAQo36xGw9lB6a89A4rrT4etjjlgjdnU7X0ZTB14NhK46dpfHbVyQg3ed+5lIwbkczSCk3Jbv0e/GgIJl9LHDbOgnj/QNC4bbqK2H8qdliSFD3Qwd6VLHAjFsvNUfw4Xg8alhSZh38CB5n1EcCOn1V3832EWffRPbnN7MTeX2hVqJFCw2jnX5JB61gq/UsVRMYDavzphBGYX88j/WdmXTiv+pmMnLCJb9iohaPVz8WeTSpIqmYQYvDrtyS6Sp6XW6g0yyUlEVnbyJbwGJ5Ww6e8C1myLL7xwBWIToMz3z3BbtIDwa37GvmQ35IM5BtxuG6kPoAgtC2urY3hsVsyRJDhcAGN62INbbTM1cr9WQ==; 5:Je+Y3TdX/W86IOCwm+i6I3tHbZktceSwjaEIY53VIAqel3qUO160rTEu5ds9gGOJx2emWHnGdy6Gy2xr4Q+VJg7NbLh9ZgOvz7IhLbkI7LIeDsLeESvh+P/nqbrIiA0c+NPG8nXwNx6DuijBwR5BAdPy+NBTEaKRUXXm1R85hsg=; 7: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; RULEID:(7020095)(4652040)(8989299)(4534165)(4627221)(201703031133081)(201702281549075)(8990200)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:AM6PR08MB3302; x-ms-traffictypediagnostic: AM6PR08MB3302: nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(228905959029699)(166494164430575)(180628864354917); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(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); SRVR:AM6PR08MB3302; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3302; x-forefront-prvs: 0808323E97 x-forefront-antispam-report: SFV:NSPM; SFS:(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); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3302; H:AM6PR08MB3672.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted 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 (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 partial key hashing 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: , X-List-Received-Date: Thu, 27 Sep 2018 04:23:12 -0000 > -----Original Message----- > From: Yipeng Wang > Sent: Friday, September 21, 2018 12:17 PM > To: bruce.richardson@intel.com > Cc: dev@dpdk.org; yipeng1.wang@intel.com; michel@digirati.com.br; > Honnappa Nagarahalli > Subject: [PATCH v2 0/7] hash: add extendable bucket and partial key hashi= ng >=20 > The first four commits of the patch set try to fix small issues of previo= us code. >=20 > The other commits make two major optimizations over the current rte_hash > library. >=20 > First, it adds Extendable Bucket Table feature: a new structure that can > accommodate keys that failed to get inserted into the main hash table due= to > the unlikely event of excessive hash collisions. The hash table buckets w= ill get > extended using a linked list to host these keys. This new design will gua= rantee > insertion of 100% of the keys for a given hash table size with minimal > overhead. A new flag value is added for user to indicate if the extendabl= e > bucket feature should be enabled or not. The linked list buckets is simil= ar > concept to the extendable bucket hash table in packet framework. > In details, for insertion, the linked buckets will be used to store the k= eys that > fail to get in the primary and the secondary bucket and the cuckoo path c= ould > not find an empty location for the maximum path length (small probability= ). > For lookup, the key is checked first in the primary, then the secondary, = then if > the secondary is extended the linked list is traversed for a possible mat= ch. >=20 > Second, the patch set changes the current hashing algorithm to be "partia= l- > key hashing". Partial-key hashing is the concept from Bin Fan, et al.'s p= aper > "MemC3: Compact and Concurrent MemCache with Dumber Caching and > Smarter Hashing". I read this paper (but not the papers in references). My understanding is t= hat the existing algorithm already uses 'partial-key hashing'. This patch s= et 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. Please let me know if I have not understood this correct. > Instead of storing both 32-bit signature and alternative > signature in the bucket, we only store a small 16-bit signature and calcu= late > the alternative bucket index by XORing the signature with the current buc= ket > index. According to the referenced paper, the signature ('tag') reduces the number= of accesses to the keys, thus improving the performance. 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 turn will= increase the number of accesses to keys. Have you run any performance benc= hmarks and compared the numbers with the existing code? Is it possible to s= hare the numbers? > This doubles the hash table memory efficiency since now one bucket only > occupies one cache line instead of two in the original design. Agree, reduced memory footprint should help increase the performance. >=20 > V1->V2: > 1. hash: Rewrite rte_hash_get_last_bkt to be more concise. > 2. hash: Reorder the rte_hash struct to align cache line better. > 3. test: Minor changes in auto test to add key insertion failure check du= ring > iteration test. > 4. test: Add new commit to fix read-write test non-consecutive core issue= . > 4. hash: Add a new commit to remove unnecessary code introduced by > previous patches. > 5. hash: Comments improvement and coding style improvements over > multiple places. >=20 > Signed-off-by: Yipeng Wang >=20 > Yipeng Wang (7): > test/hash: fix bucket size in hash perf test > test/hash: more accurate hash perf test output > test/hash: fix rw test with non-consecutive cores > hash: fix unnecessary code > hash: add extendable bucket feature > test/hash: implement extendable bucket hash test > hash: use partial-key hashing >=20 > lib/librte_hash/rte_cuckoo_hash.c | 516 +++++++++++++++++++++++++++-----= - > ----- > lib/librte_hash/rte_cuckoo_hash.h | 13 +- > lib/librte_hash/rte_hash.h | 8 +- > test/test/test_hash.c | 151 ++++++++++- > test/test/test_hash_perf.c | 126 +++++++--- > test/test/test_hash_readwrite.c | 78 +++--- > 6 files changed, 672 insertions(+), 220 deletions(-) >=20 > -- > 2.7.4