Hi Yipeng, > -----Original Message----- > From: Wang, Yipeng1 > Sent: Tuesday, October 3, 2017 5:32 AM > To: dev@dpdk.org; De Lara Guarch, Pablo > <pablo.de.lara.gua...@intel.com> > Cc: tho...@monjalon.net; Tai, Charlie <charlie....@intel.com>; Gobriel, > Sameh <sameh.gobr...@intel.com>; Mcnamara, John > <john.mcnam...@intel.com>; Wang, Yipeng1 <yipeng1.w...@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.w...@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.gua...@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.
