From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from out3-smtp.messagingengine.com (out3-smtp.messagingengine.com [66.111.4.27]) by dpdk.org (Postfix) with ESMTP id 6E8D15B40 for ; Fri, 26 Oct 2018 00:35:24 +0200 (CEST) Received: from compute1.internal (compute1.nyi.internal [10.202.2.41]) by mailout.nyi.internal (Postfix) with ESMTP id E0CB421FDE; Thu, 25 Oct 2018 18:35:23 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute1.internal (MEProxy); Thu, 25 Oct 2018 18:35:23 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=monjalon.net; h= from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding:content-type; s=mesmtp; bh=Cm35mgJXHvt/I2SVdrNKuOtzMwn1yTQEi0NOUJck8vA=; b=W3G4P4vstlW0 RMuXCfHBEBYitc9DNU/FD0pnr2gg2kLO88iCi/pqLR3wkhL+xzzyJi3vtIBHl30u /BHkwIiA3Vp4CTlydftbDrKr5DmbsSbDxfzauqPI1kllkfu+3fDgAWNKvOOTUT2X 5LnVPmxiZQIREZUCkFOPtaTlONHUf3s= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm1; bh=Cm35mgJXHvt/I2SVdrNKuOtzMwn1yTQEi0NOUJck8 vA=; b=PkkDV6dQ+zSa6lsde3ATsp+9O1kuJHcfZ2bpqokK0YiHu+h+P1Rvt4OXl lnzVn75HBNk42yZ66w58FMDD4PnIt6shUOLpTHJkHgbx0fPWX25QJ5gSLLf1TFQP QLJ/Fd9/qVucMKSC2QdL+PYUzrGtaJq9RZ5JJesXaQyVRajmRuMZq5OSgfskmJVA XlijddoukJ2U0jZZTUirGLoanTLua+3hGAdnvhVIcJ/LjxqQCM2cl9Xly+nlb2fr pB8IFrCRmnd2/GbcOMh0PCdPaKTsE+6M2pGVmqCm5LAK/zMLuyvZX5OpqkM7Rc8I bMu9pTOMnaoga6cEH2JFUTNqWoBow== X-ME-Sender: X-ME-Proxy: Received: from xps.localnet (184.203.134.77.rev.sfr.net [77.134.203.184]) by mail.messagingengine.com (Postfix) with ESMTPA id 3589E102DE; Thu, 25 Oct 2018 18:35:22 -0400 (EDT) From: Thomas Monjalon To: Yipeng Wang Cc: dev@dpdk.org, bruce.richardson@intel.com, honnappa.nagarahalli@arm.com Date: Fri, 26 Oct 2018 00:35:24 +0200 Message-ID: <1717822.zS3DjFTGi4@xps> In-Reply-To: <1540233588-202969-1-git-send-email-yipeng1.wang@intel.com> References: <1540233588-202969-1-git-send-email-yipeng1.wang@intel.com> MIME-Version: 1.0 Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="us-ascii" Subject: Re: [dpdk-dev] [PATCH v8 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: Thu, 25 Oct 2018 22:35:24 -0000 22/10/2018 20:39, Yipeng Wang: > This patch has dependency on another bug fix patch set: > http://patchwork.dpdk.org/cover/45611/ > > This patch set makes two major optimizations over the current rte_hash > library. > > 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 will > 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 buckets 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 keys > that fail to get in the primary and the secondary bucket and the cuckoo path > could 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 match. > > Second, the patch set changes the current hashing algorithm to be "partial-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 signature > 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. > > v7->v8: > patchwork splits the V7 into two patch series and the first one got merged > into V6. > Try to post again to resolve this issue. > > v6->v7: > Fix a bug accidentally introduced in V5. In iterate function, the main table > copmleted condition should be > *next == total_entries_main instead of total_entries > > v5->v6: > 1. hash: fix a typo in comment, found by Honnappa. > 2. Fix typos in commit messages. > 3. Add review-by and acked-by. > > 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. > > v3->v4: > 1. hash: Revise commit message to be more clear for "utilization" (Honnappa) > 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 locks. > 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 function > into three. It may make future extension easier (Honnappa) > 7. hash: change the comment for typedef uint32_t hash_sig_t to be more clear > to users (Honnappa) > > 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 last > entry in the linked list will be placed in the vacant slot from the deleted > 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 benefit > lookup speed. > 5. Other minor coding style/comments improvements. > > 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 during > 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. > > Signed-off-by: Yipeng Wang > > > 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 Applied, thanks