From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-eopbgr60089.outbound.protection.outlook.com [40.107.6.89]) by dpdk.org (Postfix) with ESMTP id B05151B115 for ; Wed, 3 Oct 2018 21:05:23 +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=kGi0om/eI4eSCETrRii13YVvjZ5XyEVI2ChIq2KpDiA=; b=rxHDMnyJi114I/gIRzcPiEVKkL6bz3Z2/u5wGAbT1YVo0jX+GGoG28yMn/AQvcaHEqNfVpXewAq+xUXsdqIFddLL7nEeE/tVK7ZT7Vrnh2CiNnwcCfLawqA/0MVgqCNu8IFXROehPOkqZ+7X4MbDmBqnUsiPOz/l8IiX9HGxrCg= Received: from AM0PR08MB3379.eurprd08.prod.outlook.com (20.177.109.79) by AM0PR08MB3137.eurprd08.prod.outlook.com (52.134.93.142) 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:05:22 +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:05:22 +0000 From: Dharmik Thakkar To: Yipeng Wang CC: "bruce.richardson@intel.com" , "konstantin.ananyev@intel.com" , "dev@dpdk.org" , Honnappa Nagarahalli , "sameh.gobriel@intel.com" , nd Thread-Topic: [dpdk-dev] [PATCH v4 0/4] hash: add extendable bucket and partial key hashing Thread-Index: AQHUV4toh1Qudu1+SEGYD/x3iXtg36UN6PmA Date: Wed, 3 Oct 2018 19:05:21 +0000 Message-ID: <911FC8EF-C552-4306-B42C-415C250B3054@arm.com> References: <1537993618-92630-1-git-send-email-yipeng1.wang@intel.com> <1538155426-145177-1-git-send-email-yipeng1.wang@intel.com> In-Reply-To: <1538155426-145177-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; AM0PR08MB3137; 6:YvGUFcpJQFAdV1b/TpIwOnwZz6ilKn6qcwxL5aZ8VRj8kylzkMuTtkplbN/JPc0mEnwOhOs9fvqKbR49OIcDLTpVqE61z4Qecn5qiimpvzuhfH1icNDnN0dLfC17/XLIHFp+7PpFnKss6Zar+X5WQn+wU6Npss8/dooQ/6xYWRXN3SjNHMNmElVio7kcFbn6Z0SsuAQlvacEBUozYQ9Q3ODG4L5IYbANRqLrEfXp1WKI9FFVFEjZ1pIKVYis2sxVJyaQnnJQc7JKrivIZwdlNcp3VIzgb8OSoK4egjNK0iFpAaR3XEDqNJYNzkGEk3MwrGsB+J3bgsfOcJ2X3UIGWvvsLn1erkNMNbjeU3juHn9tUCmmQ0GgIPQlUF76rYgpmilL+Ox3VjAH4KGnip4+wCZMAfQ8NcAXIBU1/Fo0ZXakNEgln9JpTfWwWYVOUjv90lNM3tJY3nh4YaFyBkg6Qg==; 5:EzBbFpmut+ECHVohoFp3AanOxrS9TkxJ3qTKczRoXP85ZOYJVV9JlEAfV0xvSrtExVYMeTJS3OpufROMS246vDS+z1UX2QptjI3c5p+5sB5AViyjEI/No70GBBWHknokgpq4lMHIC2OIza3PXBiJFAoqf+IfWLjbiwEE+HRQZno=; 7:uWLuIuKqjMCrizANxAFZtuxDQtsznvQVm6jvdA1zHz887d2jfQzN0KT9lMmigzumw3gKwwhiFuKCHNjQKK/+zUMf/6rD00CkuOPy07RthpnQeaQySSO1e6eDhlJWn7scCJM2AJCSi5bgoSq0ZY1Cm9eMOzIF4Ds+AOePi5Az4yT4oeCCrxAzk/JfJ6Uf/NkwdMaEWc3BB1Fz9gs66lJePNaqHiILkm/o4KaoHHjeY/LHxCMcknn3EMh8aBA4cw9k x-ms-exchange-antispam-srfa-diagnostics: SOS;SOR; x-ms-office365-filtering-correlation-id: 1a3679ee-a1b2-47f0-5b7f-08d629632b0a 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:AM0PR08MB3137; x-ms-traffictypediagnostic: AM0PR08MB3137: nodisclaimer: True x-microsoft-antispam-prvs: 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)(5005006)(8121501046)(93006095)(93001095)(10201501046)(3002001)(3231355)(944501410)(52105095)(6055026)(149066)(150057)(6041310)(20161123558120)(20161123564045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123562045)(20161123560045)(201708071742011)(7699051); SRVR:AM0PR08MB3137; BCL:0; PCL:0; RULEID:; SRVR:AM0PR08MB3137; x-forefront-prvs: 0814A2C7A3 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(136003)(366004)(396003)(376002)(39860400002)(346002)(189003)(199004)(68736007)(72206003)(2900100001)(83716004)(71190400001)(71200400001)(478600001)(66066001)(966005)(14454004)(2906002)(6916009)(4326008)(5660300001)(305945005)(81166006)(6246003)(81156014)(106356001)(316002)(105586002)(256004)(14444005)(54906003)(6486002)(76176011)(82746002)(6506007)(53546011)(7736002)(8936002)(5250100002)(53936002)(6436002)(97736004)(99286004)(6512007)(6306002)(36756003)(186003)(486006)(26005)(6116002)(102836004)(2616005)(33656002)(25786009)(86362001)(3846002)(11346002)(476003)(229853002)(446003); DIR:OUT; SFP:1101; SCL:1; SRVR:AM0PR08MB3137; H:AM0PR08MB3379.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-microsoft-antispam-message-info: 9vd7LfLjDek3VhIZjXb2mBQ4xAJzrxfSft415Hkoj6GMBsgdarDX7Em27V9q/ks+GDyNSuyvglnP6gZEecRzQNudK09FuneyJwHI3P8RMntOyhXDa0ADT7LZoYEjeFLeKz7/4RUBOTJrSXpNym0tB6Ep/7N2ZtCF7+cFsUaJ/FojwwZpO4WUgfWY0xJE/0Os6c5ugUX9WRkO13MBo9Ttpb9ei+C6WVNdSaIIhjQGFih8G5uiMXvAcskhFjBrY2NK/c7i0Q8AvqL1a33QUApGMxTmeuY5160Pokjd9eZOr3xdyINW8QNomKV+lB4m/CA6OJnmnx+6IdPGccWa1joW8KxikKA1HLSL+3zNe2uILEE= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="us-ascii" Content-ID: <32D391968B181548B22BBFBDD7AF1637@eurprd08.prod.outlook.com> Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: 1a3679ee-a1b2-47f0-5b7f-08d629632b0a X-MS-Exchange-CrossTenant-originalarrivaltime: 03 Oct 2018 19:05:21.9322 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM0PR08MB3137 Subject: Re: [dpdk-dev] [PATCH v4 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 03 Oct 2018 19:05:23 -0000 Tested OK on Qualcomm Centriq 2400. > On Sep 28, 2018, at 12:23 PM, Yipeng Wang 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 > 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 >=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 | 585 ++++++++++++++++++++++++++++-----= ----- > 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, 683 insertions(+), 194 deletions(-) >=20 > --=20 > 2.7.4 >=20 Acked-by: Dharmik Thakkar