[dpdk-dev] [PATCH v5 3/7] member: implement vBF mode

[De Lara Guarch, Pablo]

Hi Yipeng,

> -----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) [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 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.