From: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>
To: Bruce Richardson <bruce.richardson@intel.com>
Cc: Yipeng Wang <yipeng1.wang@intel.com>,
"dev@dpdk.org" <dev@dpdk.org>,
"michel@digirati.com.br" <michel@digirati.com.br>
Subject: Re: [dpdk-dev] [PATCH v2 5/7] hash: add extendable bucket feature
Date: Thu, 27 Sep 2018 19:21:38 +0000 [thread overview]
Message-ID: <AM6PR08MB367208568C82C8873FBF08CF98140@AM6PR08MB3672.eurprd08.prod.outlook.com> (raw)
In-Reply-To: <20180927111501.GC19604@bricha3-MOBL.ger.corp.intel.com>
> > >
> > > Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
> > > ---
> > > lib/librte_hash/rte_cuckoo_hash.c | 326
> > > +++++++++++++++++++++++++++++++++-----
> > > lib/librte_hash/rte_cuckoo_hash.h | 5 +
> > > lib/librte_hash/rte_hash.h | 3 +
> > > 3 files changed, 292 insertions(+), 42 deletions(-)
> > >
> > > diff --git a/lib/librte_hash/rte_cuckoo_hash.c
> > > b/lib/librte_hash/rte_cuckoo_hash.c
> > > index f7b86c8..616900b 100644
> > > --- a/lib/librte_hash/rte_cuckoo_hash.c
> > > +++ b/lib/librte_hash/rte_cuckoo_hash.c
> > > @@ -31,6 +31,10 @@
> > > #include "rte_hash.h"
> > > #include "rte_cuckoo_hash.h"
> > >
> > > +#define FOR_EACH_BUCKET(CURRENT_BKT, START_BUCKET)
> > > \
> > > +for (CURRENT_BKT = START_BUCKET; \
> > > +CURRENT_BKT != NULL; \
> > > +CURRENT_BKT = CURRENT_BKT->next)
> > >
> > > TAILQ_HEAD(rte_hash_list, rte_tailq_entry);
> > >
> > > @@ -63,6 +67,14 @@ rte_hash_find_existing(const char *name) return
> > > h; }
> > >
> > > +static inline struct rte_hash_bucket * rte_hash_get_last_bkt(struct
> > > +rte_hash_bucket *lst_bkt) { while (lst_bkt->next != NULL) lst_bkt =
> > > +lst_bkt->next; return lst_bkt; }
> > > +
> > > void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t
> > > func) { h->cmp_jump_table_idx = KEY_CUSTOM; @@ -85,13 +97,17 @@
> > > rte_hash_create(const struct rte_hash_parameters
> > > *params)
> > > struct rte_tailq_entry *te = NULL;
> > > struct rte_hash_list *hash_list;
> > > struct rte_ring *r = NULL;
> > > +struct rte_ring *r_ext = NULL;
> > > char hash_name[RTE_HASH_NAMESIZE];
> > > void *k = NULL;
> > > void *buckets = NULL;
> > > +void *buckets_ext = NULL;
> > > char ring_name[RTE_RING_NAMESIZE];
> > > +char ext_ring_name[RTE_RING_NAMESIZE];
> > > unsigned num_key_slots;
> > > unsigned i;
> > > unsigned int hw_trans_mem_support = 0, multi_writer_support = 0;
> > > +unsigned int ext_table_support = 0;
> > > unsigned int readwrite_concur_support = 0;
> > >
> > > rte_hash_function default_hash_func = (rte_hash_function)rte_jhash;
> > > @@ -124,6 +140,9 @@ rte_hash_create(const struct
> rte_hash_parameters
> > > *params)
> > > multi_writer_support = 1;
> > > }
> > >
> > > +if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE)
> > > +ext_table_support = 1;
> > > +
> > > /* Store all keys and leave the first entry as a dummy entry for
> > > lookup_bulk */ if (multi_writer_support)
> > > /*
> > > @@ -145,6 +164,24 @@ rte_hash_create(const struct
> > > rte_hash_parameters
> > > *params)
> > > goto err;
> > > }
> > >
> > > +const uint32_t num_buckets = rte_align32pow2(params->entries) /
> > > +RTE_HASH_BUCKET_ENTRIES;
> > > +
> > > +snprintf(ext_ring_name, sizeof(ext_ring_name), "HT_EXT_%s",
> > > +params-
> > > >name);
> > Can be inside the if statement below.
> >
> > > +/* Create ring for extendable buckets. */ if (ext_table_support) {
> > > +r_ext = rte_ring_create(ext_ring_name, rte_align32pow2(num_buckets
> > > ++ 1),
> > > +params->socket_id, 0);
> > > +
> > > +if (r_ext == NULL) {
> > > +RTE_LOG(ERR, HASH, "ext buckets memory allocation
> > > "
> > > +"failed\n");
> > > +goto err;
> > > +}
> > > +}
> > > +
> > > snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name);
> > >
> > > rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
> > > @@ -177,18 +214,34 @@ rte_hash_create(const struct
> > > rte_hash_parameters
> > > *params)
> > > goto err_unlock;
> > > }
> > >
> > > -const uint32_t num_buckets = rte_align32pow2(params->entries) -/
> > > RTE_HASH_BUCKET_ENTRIES;
> > > -
> > > buckets = rte_zmalloc_socket(NULL,
> > > num_buckets * sizeof(struct rte_hash_bucket), RTE_CACHE_LINE_SIZE,
> > > params->socket_id);
> > >
> > > if (buckets == NULL) {
> > > -RTE_LOG(ERR, HASH, "memory allocation failed\n");
> > > +RTE_LOG(ERR, HASH, "buckets memory allocation failed\n");
> > > goto err_unlock;
> > > }
> > >
> > > +/* Allocate same number of extendable buckets */
> > IMO, we are allocating too much memory to support this feature. Especially,
> when we claim that keys ending up in the extendable table is a rare
> occurrence. By doubling the memory we are effectively saying that the main
> table might have 50% utilization. It will also significantly increase the cycles
> required to iterate the complete hash table (in rte_hash_iterate API) even
> when we expect that the extendable table contains very few entries.
> >
> > I am wondering if we can provide options to control the amount of extra
> memory that gets allocated and make the memory allocation dynamic (or on
> demand basis). I think this also goes well with the general direction DPDK is
> taking - allocate resources as needed rather than allocating all the resources
> during initialization.
> >
>
> Given that adding new entries should not normally be a fast-path function,
> how about allowing memory allocation in add itself. Why not initialize with a
> fairly small number of extra bucket entries, and then each time they are all
> used, double the number of entries. That will give efficient resource scaling, I
> think.
>
+1
'small number of extra bucket entries' == 5% of total capacity requested (assuming cuckoo hash will provide 95% efficiency)
> /Bruce
IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.
next prev parent reply other threads:[~2018-09-27 19:21 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 [this message]
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 ` [dpdk-dev] [PATCH v4 0/4] hash: add extendable bucket and partial key hashing Dharmik Thakkar
2018-10-01 18:34 ` [dpdk-dev] [PATCH v5 " 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=AM6PR08MB367208568C82C8873FBF08CF98140@AM6PR08MB3672.eurprd08.prod.outlook.com \
--to=honnappa.nagarahalli@arm.com \
--cc=bruce.richardson@intel.com \
--cc=dev@dpdk.org \
--cc=michel@digirati.com.br \
--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).