[dpdk-dev] [PATCH 0/7] Add Membership Library

Wang, Yipeng1 yipeng1.wang at intel.com
Wed Aug 23 04:58:51 CEST 2017


Hi Stephen,

Thanks for the comments. We will remove the needless return initialization in next version.

For the unified API concern, we think the current implementation has two benefits: 1. It is easier to extend the library
with new types of filters without adding a lot of top level APIs every time. 2. When users switch between different
types in their application, they do not need to switch between function calls. They can reuse same code for
different types. 

However, we agree with you that a switch case in the library affects the performance. We
did a quick test and here is the results (cycles/operation):
                          lookup    lookup_bulk(16 batch)     lookup_multi    lookup_multi_bulk
switch_case         50             36                                          57                    45
direct call              47            35                                           54                    45

There will be 3 cycle difference for non-bulk version lookup. I guess if users usually use bulk version, it maybe not
a big concern, but single key lookup indeed slower. If you think the benefit we mentioned does not outweigh the
performance slowdown, we would like to make the change.

We also considered using function pointers to get rid of switch case, but it will be unfriendly to the multi-process usages. 

Please comments.

Thanks
Yipeng

> -----Original Message-----
> From: Stephen Hemminger [mailto:stephen at networkplumber.org]
> Sent: Monday, August 21, 2017 9:02 PM
> To: Wang, Yipeng1 <yipeng1.wang at intel.com>
> Cc: vincent.jardin at 6wind.com; Richardson, Bruce
> <bruce.richardson at intel.com>; Ananyev, Konstantin
> <konstantin.ananyev at intel.com>; thomas at monjalon.net; dev at dpdk.org; Tai,
> Charlie <charlie.tai at intel.com>; Gobriel, Sameh <sameh.gobriel at intel.com>;
> Wang, Ren <ren.wang at intel.com>
> Subject: Re: [PATCH 0/7] Add Membership Library
> 
> On Mon, 21 Aug 2017 17:19:46 -0700
> Yipeng Wang <yipeng1.wang at intel.com> wrote:
> 
> > This patch set implements two types of set-summaries, i.e., hash-table
> > based set-summary (HTSS) and Vector Bloom Filter (vBF). HTSS supports
> > both the non-cache and cache modes. The non-cache mode can incur a
> > small chance of false-positives which is the case when the set-summary
> > indicates a key belongs to a given set while actually it is not. The
> > cache mode can also have false-negatives in addition to
> > false-positives. False-negatives means the case when the set-summary
> > indicates a key does not belong to a given set while actually it does.
> > This happens because cache mode allows new key to evict existing keys. vBF
> only has false-positives similar to the non-cache HTSS.
> > However, one can set the false-positive rate arbitrarily. HTSS's
> > false-positive rate is determined by the hash-table size and the signature size.
> 
> I don't think it makes sense to merge two different types  of  tables in one API.
> Especially in DPDK where every cycle counts. You are taking an extra branch on
> each lookup. The user of this API is likely to know exactly what type of objects
> and look are desired.



More information about the dev mailing list