From: "De Lara Guarch, Pablo" <pablo.de.lara.guarch@intel.com>
To: "Wang, Yipeng1" <yipeng1.wang@intel.com>, "dev@dpdk.org" <dev@dpdk.org>
Cc: "thomas@monjalon.net" <thomas@monjalon.net>,
"Tai, Charlie" <charlie.tai@intel.com>,
"Gobriel, Sameh" <sameh.gobriel@intel.com>,
"Mcnamara, John" <john.mcnamara@intel.com>
Subject: Re: [dpdk-dev] [PATCH v4 3/7] member: implement vBF mode
Date: Mon, 2 Oct 2017 15:44:21 +0000 [thread overview]
Message-ID: <E115CCD9D858EF4F90C690B0DCB4D8976CC28D4C@IRSMSX108.ger.corp.intel.com> (raw)
In-Reply-To: <1506534034-39433-4-git-send-email-yipeng1.wang@intel.com>
> -----Original Message-----
> From: Wang, Yipeng1
> Sent: Wednesday, September 27, 2017 6:41 PM
> To: dev@dpdk.org
> Cc: thomas@monjalon.net; Tai, Charlie <charlie.tai@intel.com>; Gobriel,
> Sameh <sameh.gobriel@intel.com>; De Lara Guarch, Pablo
> <pablo.de.lara.guarch@intel.com>; Mcnamara, John
> <john.mcnamara@intel.com>; Wang, Yipeng1 <yipeng1.wang@intel.com>
> Subject: [PATCH v4 3/7] member: implement vBF mode
>
> Bloom Filter (BF) [1] is a well-known space-efficient probabilistic data
> structure that answers set membership queries.
> Vector of Bloom Filters (vBF) is an extension to traditional BF that supports
> multi-set membership testing. Traditional BF will return found or not-found
> for each key. vBF will also return which set the key belongs to if it is found.
>
> Since each set requires a BF, vBF should be used when set count is small.
> vBF's false positive rate could be set appropriately so that its memory
> requirement and lookup speed is better in certain cases comparing to HT
> based set-summary.
>
> This patch adds the vBF implementation.
>
> [1]B H Bloom, “Space/Time Trade-offs in Hash Coding with Allowable
> Errors,” Communications of the ACM, 1970.
>
> Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
...
> diff --git a/lib/librte_member/rte_member_vbf.c
> b/lib/librte_member/rte_member_vbf.c
...
> +int
> +rte_member_create_vbf(struct rte_member_setsum *ss,
> + const struct rte_member_parameters *params) {
> +
> + if (params->num_set > 32 || !rte_is_power_of_2(params-
> >num_set) ||
Magic number. Define a macro instead.
> + params->num_keys == 0 ||
> + params->false_positive_rate == 0 ||
> + params->false_positive_rate > 1) {
> + rte_errno = EINVAL;
> + RTE_MEMBER_LOG(ERR, "vBF create with invalid
> parameters\n");
> + return -EINVAL;
...
> +
> + /*
> + * reduce hash function count, until we approach the user specified
> + * false-positive rate. otherwise it is too conservative
Watch out for capital letters at the start of the comment and after a full stop.
> + */
> + int tmp_num_hash = ss->num_hashes;
> +
> + while (tmp_num_hash > 1) {
> + float tmp_fp = new_fp;
> +
> + tmp_num_hash--;
> + new_fp = pow((1 - pow((1 - 1.0 / ss->bits),
> num_keys_per_bf *
> + tmp_num_hash)), tmp_num_hash);
> + new_fp = 1 - pow((1 - new_fp), ss->num_set);
> +
> + if (new_fp > params->false_positive_rate) {
> + new_fp = tmp_fp;
> + tmp_num_hash++;
> + break;
> + }
> + }
> +
> + ss->num_hashes = tmp_num_hash;
> +
> + RTE_MEMBER_LOG(DEBUG, "vector bloom filter created, "
> + "each bloom filter expects %u keys, needs %u bits, %u
> hashes, "
> + "with false positive rate set as %.5f, "
> + "The new calculated vBF false positive rate is %.5f\n",
> + num_keys_per_bf, ss->bits, ss->num_hashes, x, new_fp);
Use a more descriptive variable name for "x".
> +
> + ss->table = rte_zmalloc_socket(NULL, ss->num_set * (ss->bits >> 3),
> + RTE_CACHE_LINE_SIZE, ss-
> >socket_id);
> +
> + /*
> + * To avoid multiplication and division:
> + * mul_shift is used for multiplication shift during bit test
> + * div_shift is used for division shift, to be divided by number of bits
> + * represented by a uint32_t variable
> + */
> + ss->mul_shift = __builtin_ctzl(ss->num_set);
> + ss->div_shift = __builtin_ctzl(32 >> ss->mul_shift);
> +
> + if (ss->table == NULL)
> + return -ENOMEM;
I would move this check just after the malloc call.
> +
> + return 0;
> +}
> +
> +static inline uint32_t
> +test_bit(uint32_t bit_loc, const struct rte_member_setsum *ss) {
> + uint32_t *vbf = ss->table;
> + uint32_t n = ss->num_set;
> + uint32_t div_shift = ss->div_shift;
> + uint32_t mul_shift = ss->mul_shift;
> + /*
> + * a is how many bits in one BF are represented by one 32bit
> + * variable.
> + */
> + uint32_t a = 32 >> mul_shift;
> + /*
> + * x>>b is the divide, x & (a-1) is the mod, & (1<<n-1) to mask out
> bits
> + * we do not need
> + */
> + return (vbf[bit_loc>>div_shift] >> ((bit_loc & (a - 1)) << mul_shift))
Add spaces around ">>".
> &
> + ((1ULL << n) - 1);
> +}
> +
> +static inline void
> +set_bit(uint32_t bit_loc, const struct rte_member_setsum *ss, int32_t
> +set) {
> + uint32_t *vbf = ss->table;
> + uint32_t div_shift = ss->div_shift;
> + uint32_t mul_shift = ss->mul_shift;
> + uint32_t a = 32 >> mul_shift;
> +
> + vbf[bit_loc>>div_shift] |= 1U << (((bit_loc & (a - 1)) << mul_shift) +
> + set - 1);
Same as above.
> +}
> +
> +int
> +rte_member_lookup_vbf(const struct rte_member_setsum *ss, const
> void *key,
> + member_set_t *set_id)
> +{
> + uint32_t j;
> + uint32_t h1 = MEMBER_HASH_FUNC(key, ss->key_len, ss-
> >prim_hash_seed);
> + uint32_t h2 = MEMBER_HASH_FUNC(&h1, sizeof(uint32_t),
> + ss->sec_hash_seed);
> + uint32_t mask = ~0;
> + uint32_t bit_loc;
> +
> + for (j = 0; j < ss->num_hashes; j++) {
> + bit_loc = (h1 + j * h2) & ss->bit_mask;
> + mask &= test_bit(bit_loc, ss);
> + }
> +
> + if (mask) {
> + *set_id = __builtin_ctzl(mask) + 1;
> + return 1;
Wouldn't it be better to return 0 when there is a hit and -ENOENT when there is not?
> + }
> +
> + *set_id = RTE_MEMBER_NO_MATCH;
> + return 0;
> +}
> +
> +uint32_t
> +rte_member_lookup_bulk_vbf(const struct rte_member_setsum *ss,
> + const void **keys, uint32_t num_keys, member_set_t
> *set_ids) {
> + uint32_t i, k;
> + uint32_t ret = 0;
Change variable name to "nr_matches/hits" or similar.
Same in the next functions.
next prev parent reply other threads:[~2017-10-02 15:44 UTC|newest]
Thread overview: 81+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-08-22 0:19 [dpdk-dev] [PATCH 0/7] Add Membership Library Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 1/7] member: implement main API Yipeng Wang
2017-08-22 3:59 ` Stephen Hemminger
2017-08-22 10:02 ` Luca Boccassi
2017-08-24 9:35 ` Ferruh Yigit
2017-08-24 9:55 ` Luca Boccassi
2017-08-24 10:32 ` Ferruh Yigit
2017-09-02 12:55 ` Luca Boccassi
2017-09-02 23:49 ` Luca Boccassi
2017-08-24 18:38 ` Wang, Yipeng1
2017-09-02 12:54 ` Luca Boccassi
2017-08-22 0:19 ` [dpdk-dev] [PATCH 2/7] member: implement HT mode Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 3/7] member: implement vBF mode Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 4/7] member: add AVX for HT mode Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 5/7] member: enable the library Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 6/7] test/member: add functional and perf tests Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 7/7] doc: add membership documentation Yipeng Wang
2017-08-22 4:01 ` [dpdk-dev] [PATCH 0/7] Add Membership Library Stephen Hemminger
2017-08-23 2:58 ` Wang, Yipeng1
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 " Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 1/7] member: implement main API Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 2/7] member: implement HT mode Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 3/7] member: implement vBF mode Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 4/7] member: add AVX for HT mode Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 5/7] member: enable the library Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 6/7] test/member: add functional and perf tests Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 7/7] doc: add membership documentation Yipeng Wang
2017-09-04 13:19 ` Mcnamara, John
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 0/7] Add Membership Library Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 1/7] member: implement main API Yipeng Wang
2017-09-22 10:47 ` Thomas Monjalon
2017-09-25 14:15 ` De Lara Guarch, Pablo
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 2/7] member: implement HT mode Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 3/7] member: implement vBF mode Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 4/7] member: add AVX for HT mode Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 5/7] member: enable the library Yipeng Wang
2017-09-22 10:48 ` Thomas Monjalon
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 6/7] test/member: add functional and perf tests Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 7/7] doc: add membership documentation Yipeng Wang
2017-09-18 18:42 ` Mcnamara, John
2017-09-25 12:30 ` De Lara Guarch, Pablo
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 0/7] Add Membership Library Yipeng Wang
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 1/7] member: implement main API Yipeng Wang
2017-10-02 10:04 ` De Lara Guarch, Pablo
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 2/7] member: implement HT mode Yipeng Wang
2017-10-02 13:30 ` De Lara Guarch, Pablo
2017-10-03 1:18 ` Wang, Yipeng1
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 3/7] member: implement vBF mode Yipeng Wang
2017-10-02 15:44 ` De Lara Guarch, Pablo [this message]
2017-10-03 1:24 ` Wang, Yipeng1
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 4/7] member: add AVX for HT mode Yipeng Wang
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 5/7] member: enable the library Yipeng Wang
2017-10-02 15:47 ` De Lara Guarch, Pablo
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 6/7] test/member: add functional and perf tests Yipeng Wang
2017-10-02 16:20 ` De Lara Guarch, Pablo
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 7/7] doc: add membership documentation Yipeng Wang
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 0/7] Add Membership Library Yipeng Wang
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 1/7] member: implement main API Yipeng Wang
2017-10-03 8:42 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 2/7] member: implement HT mode Yipeng Wang
2017-10-03 8:47 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 3/7] member: implement vBF mode Yipeng Wang
2017-10-03 8:50 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 4/7] member: add AVX for HT mode Yipeng Wang
2017-10-03 9:01 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 5/7] member: enable the library Yipeng Wang
2017-10-03 9:04 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 6/7] test/member: add functional and perf tests Yipeng Wang
2017-10-03 9:07 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 7/7] doc: add membership documentation Yipeng Wang
2017-10-03 9:08 ` De Lara Guarch, Pablo
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 0/7] Add Membership Library Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 1/7] member: implement main API Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 2/7] member: implement HT mode Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 3/7] member: implement vBF mode Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 4/7] member: add AVX for HT mode Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 5/7] member: enable the library Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 6/7] test/member: add functional and perf tests Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 7/7] doc: add membership documentation Yipeng Wang
2017-10-04 13:44 ` Mcnamara, John
2017-10-08 22:14 ` [dpdk-dev] [PATCH v6 0/7] Add Membership Library 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=E115CCD9D858EF4F90C690B0DCB4D8976CC28D4C@IRSMSX108.ger.corp.intel.com \
--to=pablo.de.lara.guarch@intel.com \
--cc=charlie.tai@intel.com \
--cc=dev@dpdk.org \
--cc=john.mcnamara@intel.com \
--cc=sameh.gobriel@intel.com \
--cc=thomas@monjalon.net \
--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).