DPDK patches and discussions
 help / color / mirror / Atom feed
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>
Subject: Re: [dpdk-dev] [PATCH v4 0/4] hash: add extendable bucket and partial	key hashing
Date: Wed, 3 Oct 2018 19:05:21 +0000	[thread overview]
Message-ID: <911FC8EF-C552-4306-B42C-415C250B3054@arm.com> (raw)
In-Reply-To: <1538155426-145177-1-git-send-email-yipeng1.wang@intel.com>

Tested OK on Qualcomm Centriq 2400.

> On Sep 28, 2018, at 12:23 PM, Yipeng Wang <yipeng1.wang@intel.com> wrote:
> 
> This patch set made 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.
> 
> 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 <yipeng1.wang@intel.com>
> 
> 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
> 
> 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(-)
> 
> -- 
> 2.7.4
> 
Acked-by: Dharmik Thakkar <dharmik.thakkar@arm.com>

  parent reply	other threads:[~2018-10-03 19:05 UTC|newest]

Thread overview: 107+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-09-06 17:09 [dpdk-dev] [PATCH v1 0/5] hash: add extendable bucket and partial-key hashing Yipeng Wang
2018-09-06 17:09 ` [dpdk-dev] [PATCH v1 1/5] test: fix bucket size in hash table perf test Yipeng Wang
2018-09-06 17:09 ` [dpdk-dev] [PATCH v1 2/5] test: more accurate hash table perf test output Yipeng Wang
2018-09-06 17:09 ` [dpdk-dev] [PATCH v1 3/5] hash: add extendable bucket feature Yipeng Wang
2018-09-06 17:09 ` [dpdk-dev] [PATCH v1 4/5] test: implement extendable bucket hash test Yipeng Wang
2018-09-06 17:09 ` [dpdk-dev] [PATCH v1 5/5] hash: use partial-key hashing Yipeng Wang
2018-09-21 17:17 ` [dpdk-dev] [PATCH v2 0/7] hash: add extendable bucket and partial key hashing Yipeng Wang
2018-09-21 17:17   ` [dpdk-dev] [PATCH v2 1/7] test/hash: fix bucket size in hash perf test Yipeng Wang
2018-09-26 10:04     ` Bruce Richardson
2018-09-27  3:39       ` Wang, Yipeng1
2018-09-27  4:23     ` Honnappa Nagarahalli
2018-09-29  0:31       ` Wang, Yipeng1
2018-09-21 17:17   ` [dpdk-dev] [PATCH v2 2/7] test/hash: more accurate hash perf test output Yipeng Wang
2018-09-26 10:07     ` Bruce Richardson
2018-09-21 17:17   ` [dpdk-dev] [PATCH v2 3/7] test/hash: fix rw test with non-consecutive cores Yipeng Wang
2018-09-26 11:02     ` Bruce Richardson
2018-09-27  3:40       ` Wang, Yipeng1
2018-09-26 11:13     ` Bruce Richardson
2018-09-21 17:17   ` [dpdk-dev] [PATCH v2 4/7] hash: fix unnecessary code Yipeng Wang
2018-09-26 12:55     ` Bruce Richardson
2018-09-21 17:17   ` [dpdk-dev] [PATCH v2 5/7] hash: add extendable bucket feature Yipeng Wang
2018-09-27  4:23     ` Honnappa Nagarahalli
2018-09-27 11:15       ` Bruce Richardson
2018-09-27 11:27         ` Ananyev, Konstantin
2018-09-27 12:27           ` Bruce Richardson
2018-09-27 12:33             ` Ananyev, Konstantin
2018-09-27 19:21         ` Honnappa Nagarahalli
2018-09-28 17:35           ` Wang, Yipeng1
2018-09-29 21:09             ` Honnappa Nagarahalli
2018-09-29  1:10       ` Wang, Yipeng1
2018-10-01 20:56         ` Honnappa Nagarahalli
2018-10-02  1:56           ` Wang, Yipeng1
2018-09-21 17:17   ` [dpdk-dev] [PATCH v2 6/7] test/hash: implement extendable bucket hash test Yipeng Wang
2018-09-27  4:24     ` Honnappa Nagarahalli
2018-09-29  0:50       ` Wang, Yipeng1
2018-09-21 17:17   ` [dpdk-dev] [PATCH v2 7/7] hash: use partial-key hashing Yipeng Wang
2018-09-27  4:24     ` Honnappa Nagarahalli
2018-09-29  0:55       ` Wang, Yipeng1
2018-09-26 12:57   ` [dpdk-dev] [PATCH v2 0/7] hash: add extendable bucket and partial key hashing Bruce Richardson
2018-09-27  3:41     ` Wang, Yipeng1
2018-09-27  4:23   ` Honnappa Nagarahalli
2018-09-29  0:46     ` Wang, Yipeng1
2018-09-26 12:54 ` [dpdk-dev] [PATCH v3 0/5] hash: fix multiple issues Yipeng Wang
2018-09-26 12:54   ` [dpdk-dev] [PATCH v3 1/5] test/hash: fix bucket size in hash perf test Yipeng Wang
2018-09-27 11:17     ` Bruce Richardson
2018-09-26 12:54   ` [dpdk-dev] [PATCH v3 2/5] test/hash: more accurate hash perf test output Yipeng Wang
2018-09-26 12:54   ` [dpdk-dev] [PATCH v3 3/5] test/hash: fix rw test with non-consecutive cores Yipeng Wang
2018-09-27 11:18     ` Bruce Richardson
2018-09-26 12:54   ` [dpdk-dev] [PATCH v3 4/5] test/hash: fix missing file in meson build file Yipeng Wang
2018-09-27 11:22     ` Bruce Richardson
2018-09-26 12:54   ` [dpdk-dev] [PATCH v3 5/5] hash: fix unused define Yipeng Wang
2018-09-28 14:11   ` [dpdk-dev] [PATCH v4 0/5] hash: fix multiple issues Yipeng Wang
2018-09-28 14:11     ` [dpdk-dev] [PATCH v4 1/5] test/hash: fix bucket size in hash perf test Yipeng Wang
2018-10-01 20:28       ` Honnappa Nagarahalli
2018-09-28 14:11     ` [dpdk-dev] [PATCH v4 2/5] test/hash: more accurate hash perf test output Yipeng Wang
2018-09-28 14:11     ` [dpdk-dev] [PATCH v4 3/5] test/hash: fix rw test with non-consecutive cores Yipeng Wang
2018-09-28 14:11     ` [dpdk-dev] [PATCH v4 4/5] test/hash: fix missing file in meson build file Yipeng Wang
2018-09-28 14:11     ` [dpdk-dev] [PATCH v4 5/5] hash: fix unused define Yipeng Wang
2018-10-25 22:04     ` [dpdk-dev] [PATCH v4 0/5] hash: fix multiple issues Thomas Monjalon
2018-09-26 20:26 ` [dpdk-dev] [PATCH v3 0/3] hash: add extendable bucket and partial key hashing Yipeng Wang
2018-09-26 20:26   ` [dpdk-dev] [PATCH v3 1/3] hash: add extendable bucket feature Yipeng Wang
2018-09-26 20:26   ` [dpdk-dev] [PATCH v3 2/3] test/hash: implement extendable bucket hash test Yipeng Wang
2018-09-26 20:26   ` [dpdk-dev] [PATCH v3 3/3] hash: use partial-key hashing Yipeng Wang
2018-09-28 17:23   ` [dpdk-dev] [PATCH v4 0/4] hash: add extendable bucket and partial key hashing Yipeng Wang
2018-09-28 17:23     ` [dpdk-dev] [PATCH v4 1/4] hash: fix race condition in iterate Yipeng Wang
2018-10-01 20:23       ` Honnappa Nagarahalli
2018-10-02  0:17         ` Wang, Yipeng1
2018-10-02  4:26           ` Honnappa Nagarahalli
2018-10-02 23:53             ` Wang, Yipeng1
2018-09-28 17:23     ` [dpdk-dev] [PATCH v4 2/4] hash: add extendable bucket feature Yipeng Wang
2018-10-02  3:58       ` Honnappa Nagarahalli
2018-10-02 23:39         ` Wang, Yipeng1
2018-10-03  4:37           ` Honnappa Nagarahalli
2018-10-03 15:08           ` Stephen Hemminger
2018-10-03 15:08       ` Stephen Hemminger
2018-10-03 16:53         ` Wang, Yipeng1
2018-10-03 17:59           ` Honnappa Nagarahalli
2018-10-04  1:22             ` Wang, Yipeng1
2018-09-28 17:23     ` [dpdk-dev] [PATCH v4 3/4] test/hash: implement extendable bucket hash test Yipeng Wang
2018-10-01 19:53       ` Honnappa Nagarahalli
2018-09-28 17:23     ` [dpdk-dev] [PATCH v4 4/4] hash: use partial-key hashing Yipeng Wang
2018-10-01 20:09       ` Honnappa Nagarahalli
2018-10-03 19:05     ` Dharmik Thakkar [this message]
2018-10-01 18:34   ` [dpdk-dev] [PATCH v5 0/4] hash: add extendable bucket and partial key hashing Yipeng Wang
2018-10-01 18:34     ` [dpdk-dev] [PATCH v5 1/4] hash: fix race condition in iterate Yipeng Wang
2018-10-02 17:26       ` Honnappa Nagarahalli
2018-10-01 18:35     ` [dpdk-dev] [PATCH v5 2/4] hash: add extendable bucket feature Yipeng Wang
2018-10-01 18:35     ` [dpdk-dev] [PATCH v5 3/4] test/hash: implement extendable bucket hash test Yipeng Wang
2018-10-01 18:35     ` [dpdk-dev] [PATCH v5 4/4] hash: use partial-key hashing Yipeng Wang
2018-10-02 20:52       ` Dharmik Thakkar
2018-10-03  0:43         ` Wang, Yipeng1
2018-10-03 19:10     ` [dpdk-dev] [PATCH v5 0/4] hash: add extendable bucket and partial key hashing Dharmik Thakkar
2018-10-04  0:36       ` Wang, Yipeng1
2018-10-04 16:35   ` [dpdk-dev] [PATCH v6 " Yipeng Wang
2018-10-04 16:35     ` [dpdk-dev] [PATCH v6 1/4] hash: fix race condition in iterate Yipeng Wang
2018-10-04 16:35     ` [dpdk-dev] [PATCH v6 2/4] hash: add extendable bucket feature Yipeng Wang
2018-10-04 16:35     ` [dpdk-dev] [PATCH v6 3/4] test/hash: implement extendable bucket hash test Yipeng Wang
2018-10-04 16:35     ` [dpdk-dev] [PATCH v6 4/4] hash: use partial-key hashing Yipeng Wang
2018-10-10 21:27     ` [dpdk-dev] [PATCH v7 0/4] hash: add extendable bucket and partial key hashing Yipeng Wang
2018-10-10 21:27       ` [dpdk-dev] [PATCH v7 1/4] hash: fix race condition in iterate Yipeng Wang
2018-10-10 21:27       ` [dpdk-dev] [PATCH v7 2/4] hash: add extendable bucket feature Yipeng Wang
2018-10-10 21:27       ` [dpdk-dev] [PATCH v7 3/4] test/hash: implement extendable bucket hash test Yipeng Wang
2018-10-10 21:27       ` [dpdk-dev] [PATCH v7 4/4] hash: use partial-key hashing Yipeng Wang
2018-10-16 18:47       ` [dpdk-dev] [PATCH] doc: update release note for hash library Yipeng Wang
2018-10-17 20:09         ` Honnappa Nagarahalli
2018-10-25 18:45           ` Wang, Yipeng1
2018-10-25 23:07             ` Thomas Monjalon

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=911FC8EF-C552-4306-B42C-415C250B3054@arm.com \
    --to=dharmik.thakkar@arm.com \
    --cc=Honnappa.Nagarahalli@arm.com \
    --cc=bruce.richardson@intel.com \
    --cc=dev@dpdk.org \
    --cc=konstantin.ananyev@intel.com \
    --cc=nd@arm.com \
    --cc=sameh.gobriel@intel.com \
    --cc=yipeng1.wang@intel.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).