Hi Yipeng, > -----Original Message----- > From: Wang, Yipeng1 > Sent: Tuesday, October 3, 2017 5:32 AM > To: [email protected]; De Lara Guarch, Pablo > <[email protected]> > Cc: [email protected]; Tai, Charlie <[email protected]>; Gobriel, > Sameh <[email protected]>; Mcnamara, John > <[email protected]>; Wang, Yipeng1 <[email protected]> > 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 <[email protected]>
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 <[email protected]> ... > +++ 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.
