From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: <Dharmik.Thakkar@arm.com> Received: from EUR02-VE1-obe.outbound.protection.outlook.com (mail-eopbgr20074.outbound.protection.outlook.com [40.107.2.74]) by dpdk.org (Postfix) with ESMTP id 9FC511B115 for <dev@dpdk.org>; Wed, 3 Oct 2018 21:10:47 +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=IJviStX37algklgZAzqp8ovIdykk3jVmwtLwWkm/mIY=; b=IniEjyKp36/ZBCNylYE8yJGBA73CgYLJr1Ntiy3Vmx7J1b9xZJ9GSOp/Bsv5zui/HgWbjh0fzQlWOLFp+Wul8D0ZMIypyQpkra1B1JjcJCpSmQAs4pTpwXUUbz5pJA9D/zRR47bAOpEd47SlNJboBBEMkgPuJC5XVPwGy/nz1x0= Received: from AM0PR08MB3379.eurprd08.prod.outlook.com (20.177.109.79) by AM0PR08MB3474.eurprd08.prod.outlook.com (20.177.109.216) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1207.18; Wed, 3 Oct 2018 19:10:45 +0000 Received: from AM0PR08MB3379.eurprd08.prod.outlook.com ([fe80::c1f3:44ba:fafe:8650]) by AM0PR08MB3379.eurprd08.prod.outlook.com ([fe80::c1f3:44ba:fafe:8650%2]) with mapi id 15.20.1207.021; Wed, 3 Oct 2018 19:10:45 +0000 From: Dharmik Thakkar <Dharmik.Thakkar@arm.com> To: Yipeng Wang <yipeng1.wang@intel.com> CC: "bruce.richardson@intel.com" <bruce.richardson@intel.com>, "konstantin.ananyev@intel.com" <konstantin.ananyev@intel.com>, "dev@dpdk.org" <dev@dpdk.org>, Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>, "sameh.gobriel@intel.com" <sameh.gobriel@intel.com>, nd <nd@arm.com> Thread-Topic: [dpdk-dev] [PATCH v5 0/4] hash: add extendable bucket and partial key hashing Thread-Index: AQHUWfDia3OhhgjaeEqKMxWmx5oUSKUN5bCA Date: Wed, 3 Oct 2018 19:10:45 +0000 Message-ID: <619837D7-C4DB-4864-B94E-F0A0B18E3017@arm.com> References: <1537993618-92630-1-git-send-email-yipeng1.wang@intel.com> <1538418902-154892-1-git-send-email-yipeng1.wang@intel.com> In-Reply-To: <1538418902-154892-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=Dharmik.Thakkar@arm.com; x-originating-ip: [217.140.111.135] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; AM0PR08MB3474; 6:eCsPrtAN6xFI3Yrw4+PqCe8BR0R11T1DT9A8nrM/LBRCgfq5zjqnj9eKURqOxumrPsp8d3EE/n9xD2HaiZ3dYl5MU4EP+DEPQ4gSm0CMWPNa3El9NrEzEkjmsDU1okIjCMKX/C3yh3/ABNASRdjzqVsNiHcXzwQGYWxDATARxRRaTuLdIN5PV7Om59ga1azTOXTF1ZKf8+VySDUx31mLDkQDK9Fbw5X1lz+EiAv7phf58Vnwz7Dp/kELZQtdQbh6c4ukZU1KRoDw2oYKUbJDrFKeuH8U+c28wN6ux4Rgj1nH5UIECf5FyvznbIQ1/KYhjrwEm9YHo+HdMBAB/hO8slEbSjQkzFj5TPDzNpdL8ydctliuYJFZxmxDGaMWcPBA+Uvf61wsHxlRyeBgZuJTqgMuv0cims/nbHhVL/MGIJCNSG4J6/DHDRuCLiybq8CXktjF9wcJVFxrW5mq2M/Trw==; 5:KdgBcCHPoGTPK7jlyZ3S1FhPohJQADPDRKF8rFZCD+/9xVDoQfkZkI8hB6526Bhin6lLPrKhKdHpmVbusXdM+XYxhMc3ouhZNrw7Owg2JijaQALRmA68rPCaUh/KHXsLPtxh7YzhEqrm31DGFNxsn4UXhPhgljcGgdmcYo6uSxA=; 7:nZHBwJh9eWDFXJgPv03ukEjk4ie2rIcRYhDiqZ2fs2lLsDtRt5hTsGsjq6RbIrt7bDo3MVQ8tzQZEJuXkjVEvkBRIVehhkuoN+lWdC4JHIuJz7tKw9UQOScHgBtDKmWXOL5PeodjHUSjDt62i2qHdVcp+oee5KsETsLgyuCg8fbl7qFMIyUfZK4fDd6oNep8FTmqISwR75KwCZn9vIM8UcuXXp1MiMILW/UE2zxgP/MkPsgRHgraLobwL7wgh4Gd x-ms-exchange-antispam-srfa-diagnostics: SOS;SOR; x-ms-office365-filtering-correlation-id: 3b91302c-1c93-4da4-4da1-08d62963ec15 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:AM0PR08MB3474; x-ms-traffictypediagnostic: AM0PR08MB3474: nodisclaimer: True x-microsoft-antispam-prvs: <AM0PR08MB3474C68C0423744D6E753EE2FBE90@AM0PR08MB3474.eurprd08.prod.outlook.com> x-exchange-antispam-report-test: UriScan:(17755550239193)(228905959029699)(180628864354917); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(93006095)(93001095)(10201501046)(3231355)(944501410)(52105095)(3002001)(6055026)(149066)(150057)(6041310)(20161123562045)(20161123560045)(20161123558120)(20161123564045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(201708071742011)(7699051); SRVR:AM0PR08MB3474; BCL:0; PCL:0; RULEID:; SRVR:AM0PR08MB3474; x-forefront-prvs: 0814A2C7A3 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(376002)(136003)(39860400002)(366004)(396003)(346002)(199004)(189003)(966005)(14444005)(4326008)(99286004)(53936002)(105586002)(106356001)(76176011)(14454004)(256004)(6116002)(3846002)(229853002)(316002)(68736007)(97736004)(6512007)(6486002)(25786009)(6306002)(54906003)(6436002)(71190400001)(186003)(71200400001)(83716004)(7736002)(102836004)(26005)(86362001)(33656002)(81156014)(81166006)(5250100002)(2616005)(446003)(476003)(486006)(5660300001)(6246003)(2906002)(8936002)(53546011)(11346002)(305945005)(82746002)(72206003)(6506007)(478600001)(2900100001)(6916009)(66066001)(36756003); DIR:OUT; SFP:1101; SCL:1; SRVR:AM0PR08MB3474; H:AM0PR08MB3379.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: wSzGmLzSbTsEDkUFEvQ+bH2uNyA/Lv78iYJhzs4eMxY+quKqJPUVmn5XPV6mUT8Tl8FhoEWbiXpSU1y4mKJ6cj9YXsn5BR7lVaD8acWeQVN7ZAxxEVMGDbMnDlKho8vEifoynl00u93iDB59tj6LjoWdtVHteqJwutQjlIxUmvX1DoH9sP3s4lu9BRYErhK8o4+yNGadAZCiE7dbo8JP2EffVokXwQWNpo8Bno/XxDrUDkxvf9gqetkgxFzWHXtM0Vpit1yh8q6Psf5xZwvgUv8d05XV7jUGoNPSP1F72C5xnqMn65BN28MpPWrfgwF5gCVbaa5UlV5vZDeDy3LSm/9botIKYCbT59/k19r1T9c= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="us-ascii" Content-ID: <6E506AE8116D0C4ABC67378382B11452@eurprd08.prod.outlook.com> Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: 3b91302c-1c93-4da4-4da1-08d62963ec15 X-MS-Exchange-CrossTenant-originalarrivaltime: 03 Oct 2018 19:10:45.6792 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM0PR08MB3474 Subject: Re: [dpdk-dev] [PATCH v5 0/4] 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 <dev.dpdk.org> List-Unsubscribe: <https://mails.dpdk.org/options/dev>, <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>, <mailto:dev-request@dpdk.org?subject=subscribe> X-List-Received-Date: Wed, 03 Oct 2018 19:10:47 -0000 Tested OK on Qualcomm Centriq 2400. > On Oct 1, 2018, at 1:34 PM, Yipeng Wang <yipeng1.wang@intel.com> wrote: >=20 > This patch set made 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 > guarantee 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 > extendable bucket feature should be enabled or not. The linked list bucke= ts is > similar 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 p= ath > could not find an empty location for the maximum path length (small > probability). For lookup, the key is checked first in the primary, then t= he > secondary, then if the secondary is extended the linked list is traversed > for a possible match. >=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 paper > "MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter > Hashing". Instead of storing both 32-bit signature and alternative signat= ure > in the bucket, we only store a small 16-bit signature and calculate the > alternative bucket index by XORing the signature with the current bucket = index. > This doubles the hash table memory efficiency since now one bucket > only occupies one cache line instead of two in the original design. >=20 > v4->v5: > 1. hash: for the first commit, move back the lock and read "position" in = the > while condition as Honnappa suggested. > 2. hash: minor coding style change (Honnappa) and commit message typo fix= . > 3. Add Review-by from Honnappa. >=20 > v3->v4: > 1. hash: Revise commit message to be more clear for "utilization" (Honnap= pa) > 2. hash: in delete key function, return bucket change to use rte_ring_sp_= enqueue > instead of rte_ring_mp_enqueue, since it is already protected inside lock= s. > 3. hash: update rte_hash_iterate comments (Honnappa) > 4. hash: Add a new commit to fix race condition in the rte_hash_iterate (= Honnappa) > 5. hash/test: during utilization test, double check rte_hash_cnt returns = correct > value (Honnappa) > 6. hash: for partial-key-hashing commit, break the get_buckets_index func= tion > into three. It may make future extension easier (Honnappa) > 7. hash: change the comment for typedef uint32_t hash_sig_t to be more cl= ear > to users (Honnappa) >=20 > v2->v3: > The first four commits were separated from this patch set as another > independent patch set: > https://mails.dpdk.org/archives/dev/2018-September/113118.html > 1. hash: move snprintf for ext_ring name under the ext_table condition. > 2. hash: fix memory leak by freeing ext_buckets in rte_hash_free. > 3. hash: after failing cuckoo path, search not only ext buckets, but also= the > secondary bucket first to see if there may be an empty location now. > 4. hash: totally rewrote the key deleting function logic. If the deleted = key was > not in the last bucket of the linked list when ext table enabled, the las= t > entry in the linked list will be placed in the vacant slot from the delet= ed > key. The purpose is to compact the entries in the linked list to be more = close > to the main table. This is to make sure that not many extendable buckets = are > wasted with only one or two entries after some time of running, also bene= fit > lookup speed. > 5. Other minor coding style/comments improvements. >=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 previo= us > patches. > 5. hash: Comments improvement and coding style improvements over multiple > places. >=20 > Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com> >=20 > Yipeng Wang (4): > hash: fix race condition in iterate > 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 | 580 ++++++++++++++++++++++++++++-----= ----- > lib/librte_hash/rte_cuckoo_hash.h | 11 +- > lib/librte_hash/rte_hash.h | 8 +- > test/test/test_hash.c | 159 ++++++++++- > test/test/test_hash_perf.c | 114 ++++++-- > 5 files changed, 677 insertions(+), 195 deletions(-) >=20 > --=20 > 2.7.4 >=20 Acked-by: Dharmik Thakkar <dharmik.thakkar@arm.com>