From patchwork Tue Jun 25 21:15:17 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 167755 Delivered-To: patch@linaro.org Received: by 2002:a92:4782:0:0:0:0:0 with SMTP id e2csp40136ilk; Tue, 25 Jun 2019 14:15:44 -0700 (PDT) X-Google-Smtp-Source: APXvYqxqGncI8639WfIqND8/5JQB25eAO+vKFjnIo8H6qC3XBC820BCHKmWVdZrUroP1OwXrKUMV X-Received: by 2002:a5d:6742:: with SMTP id l2mr136369wrw.323.1561497344448; Tue, 25 Jun 2019 14:15:44 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1561497344; cv=none; d=google.com; s=arc-20160816; b=BAIaM1SK0EcWZPRh7QTrF1Z/SUTgrWEWOrFAToFiu8Wc/Aj2s7Rwq8EBX7m8p8DtdN l6mrT4pzyVuZuag1YB5kWaPCyTJ0vvxdjDfgmPxbpGEo5L512xLqazw/yp7ft3SReZGR Uy9h4SSrGfejdBcLi6GYKTOF6Td6d0v+UAkuFU60wv6VuvvZ6W+AivjVZEy44AYD7UZ1 YgOJFJp+BsEQZRAbIk4bSwBiPpRM5wdwJYysQihKlamd7PNg2yjnTXoxrGk/oUKw2Mlr EnHAf9weWDFq2kFhKMn+Yhu4jaHupCqBhcMDtuoxR3GNJBXkZf33STuvAWTG8qKTNgxv I3bQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject:message-id:date:cc:to :from; bh=6oZ9TKWknWo6KBkPwfIrCNZvHbRDvGH7cshtmdBOn78=; b=zg05RmfjeoLI/0RFxnHaQEvoXrS/ZBVtzXTS7RrVoAfjgHZKxFWYNTo3qLDSb9KX5Z IfghjC5oOXdDNEwwIuqIH828SMn4+NWpW2krOhLJPmp/8/jJ3tYwtbdCHIOqYwiKJynd vFKt24pgdz5w7FeodlDUj+xRv9JR5b+tzvWg44TyDeFekiJXvu0bkjpUaCxYoiSj1TlZ 2zGmZkk/vRIkHygVBT2OLkjnowK6Nv0KKElxdZk58409Mts5z1DFa8nCO+c6QuvtV1vG /5Vn4gTIVPtAKsnvjTIDmZTayldYAPmvK2oyaIXWl1DcMpiz/pue5R/Qlj5bVkZMEBcs uKfw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Return-Path: Received: from dpdk.org (dpdk.org. [92.243.14.124]) by mx.google.com with ESMTP id v129si158624wma.165.2019.06.25.14.15.42; Tue, 25 Jun 2019 14:15:44 -0700 (PDT) Received-SPF: pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) client-ip=92.243.14.124; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dev-bounces@dpdk.org designates 92.243.14.124 as permitted sender) smtp.mailfrom=dev-bounces@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id C12F41B99B; Tue, 25 Jun 2019 23:15:41 +0200 (CEST) Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by dpdk.org (Postfix) with ESMTP id BDC1E1B99B for ; Tue, 25 Jun 2019 23:15:40 +0200 (CEST) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id E6BF7360; Tue, 25 Jun 2019 14:15:39 -0700 (PDT) Received: from qc2400f-1.austin.arm.com (qc2400f-1.austin.arm.com [10.118.12.65]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id D2EE13F246; Tue, 25 Jun 2019 14:15:39 -0700 (PDT) From: Honnappa Nagarahalli To: yipeng1.wang@intel.com, sameh.gobriel@intel.com, bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com, honnappa.nagarahalli@arm.com Cc: gavin.hu@arm.com, ruifeng.wang@arm.com, dev@dpdk.org, nd@arm.com Date: Tue, 25 Jun 2019 16:15:17 -0500 Message-Id: <20190625211520.43181-1-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.17.1 Subject: [dpdk-dev] [PATCH 0/3] lib/hash: perf improvements for lock-free 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: , Errors-To: dev-bounces@dpdk.org Sender: "dev" While using the rte_hash library, there are 2 sets of stores that happen. 1) The application writes its data to memory (whose address is provided in rte_hash_add_key_with_hash_data API (or NULL)) 2) The rte_hash library writes to its own internal data structures; key store entry and the hash table. The data from both of these stores is available to the readers only after the index of the key store entry (key_index) is written in the hash buckets by the library. So, key_index can act as the guard variable for both of these writes. When rte_hash_add_key_with_hash_data is called to update an existing entry, the key_index is not written. But, the store to the application data must complete before the address of the application data (pData) is updated in the key store entry. So, pData alone acts as the guard variable for this case. However, it should be noted that there are no ordering requirements between 1) and 2), except for one requirement - the store to the application data must complete before the store to key_index. In other words, there are no ordering requirements between the stores to the key store entry/signature and store to application data. So, the synchronization point for application data can be any point between the 'store to application data' and 'store to the key_index'. The first patch in this series moves the signature comparison before the load-acquire of the key_index. This does not result in any issues because of the full key comparison which is done after the load-acquire of the key_index. Performance improvements: Lookup Hit: 6.16% Lookup Miss: 8.54% The second patch in this series, moves the store-release of pData before the store to any hash internal data structures. This is not necessary, but just helps to show the non-dependency between application data and hash table data. On the reader side, the pData is loaded only if the keys match, this provides performance benefits. Performance improvements (with patch 1): Lookup Hit: 6.25% Lookup Miss: 13.97% The third patch moves the table change counter to the beginning of the cache line as it is one of the first fields accessed in the lookup function. Further work is required to adjust rte_hash structure to gain more performance. Performance improvements (with patch 1 and patch 2): Lookup Hit: 2.13% Lookup Miss: 1.56% Honnappa Nagarahalli (3): lib/hash: use ordered loads only if signature matches lib/hash: load pData after full key compare lib/hash: adjust tbl_chng_cnt position lib/librte_hash/rte_cuckoo_hash.c | 96 ++++++++++++++++--------------- lib/librte_hash/rte_cuckoo_hash.h | 6 +- 2 files changed, 53 insertions(+), 49 deletions(-) -- 2.17.1