[dpdk-dev] [PATCH v5 3/7] member: implement vBF mode
De Lara Guarch, Pablo
pablo.de.lara.guarch at intel.com
Tue Oct 3 10:50:24 CEST 2017
> -----Original Message-----
> From: Wang, Yipeng1
> Sent: Tuesday, October 3, 2017 5:32 AM
> To: dev at dpdk.org; De Lara Guarch, Pablo
> <pablo.de.lara.guarch at intel.com>
> Cc: thomas at monjalon.net; Tai, Charlie <charlie.tai at intel.com>; Gobriel,
> Sameh <sameh.gobriel at intel.com>; Mcnamara, John
> <john.mcnamara at intel.com>; Wang, Yipeng1 <yipeng1.wang at intel.com>
> Subject: [PATCH v5 3/7] member: implement vBF mode
> Bloom Filter (BF)  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.
> 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 at intel.com>
Just a comment below. The rest looks fine to me (and thanks for the explanations
in the v4 patch, all clear), so keep my "Reviewed-by" in next version.
Reviewed-by: Pablo de Lara <pablo.de.lara.guarch at intel.com>
> +++ b/lib/librte_member/rte_member_vbf.c
> + /*
> + * 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);
Remove the whitespace added after the tab in the two lines above.
More information about the dev