Hi Darrell, > The effect here is highly data dependent and in fact dominated by the packet > distribution which will not be random or rather pseudo-random. I had done > my own testing with pseudo random flows, fwiw. > I did not see any thrashing with even at 4000 flows and saw one alive/alive > choice at 8000.
An agreed standard packet distribution would be useful (essential really) for EMC performance characterization. What is the packet distribution you are using? Thanks, Billy. > -----Original Message----- > From: [email protected] [mailto:ovs-dev- > [email protected]] On Behalf Of Darrell Ball > Sent: Friday, August 4, 2017 8:38 PM > To: Ilya Maximets <[email protected]>; Wang, Yipeng1 > <[email protected]>; [email protected] > Cc: Heetae Ahn <[email protected]> > Subject: Re: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement > policy. > > > > -----Original Message----- > From: Ilya Maximets <[email protected]> > Date: Monday, July 31, 2017 at 7:25 AM > To: Darrell Ball <[email protected]>, "Wang, Yipeng1" > <[email protected]>, "[email protected]" <ovs- > [email protected]> > Cc: Heetae Ahn <[email protected]> > Subject: Re: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement > policy. > > On 31.07.2017 04:41, Darrell Ball wrote: > > > > > > -----Original Message----- > > From: <[email protected]> on behalf of "Wang, > Yipeng1" <[email protected]> > > Date: Friday, July 28, 2017 at 11:04 AM > > To: Ilya Maximets <[email protected]>, "ovs- > [email protected]" <[email protected]> > > Cc: Heetae Ahn <[email protected]> > > Subject: Re: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement > policy. > > > > Good catch. But I think the hash comparison is to "randomly" choose > one of the two entries to replace when both entries are live. > > Your change would always replace the first one in such case. It might > cause some thrashing issue for certain traffic. Meanwhile, to my experience, > the original "hash comparison" is also not a good way to choose random > entry, I encountered some thrashing issue before. > > > > I think we want some condition like below, but a way to fast choose > a > random entry. > > > > if (!to_be_replaced || (emc_entry_alive(to_be_replaced) && > !emc_entry_alive(current_entry) ) > > to_be_replaced = current_entry; > > else if((emc_entry_alive(to_be_replaced) && > (emc_entry_alive(current_entry)) > > to_be_replaced = random_entry; > > I agree that we need to have something like random choosing of active > entry to replace. > I though about this a little and came up with idea to reuse the random > value generated > for insertion probability. This should give a good distribution for > replacement. > I'll send v2 soon with that approach. > > The effect here is highly data dependent and in fact dominated by the packet > distribution which will not be random or rather pseudo-random. I had done > my own testing with pseudo random flows, fwiw. > I did not see any thrashing with even at 4000 flows and saw one alive/alive > choice at 8000. [[BO'M]] What is the packet distribution you are using? > > We can also see the data dependency with this patch in this first version. > This patch removed all randomness when choosing an entry to replace when > both candidates are alive and instead always choose the first entry. > > However, you observed that this fixed your problem of thrashing with your > dataset – if so, the dataset used in your testing may not be very random. > This change would have been worse in the general case, but seemed perfect > for your dataset. > > > > ////////////////// > > > > I agree – we are trying to randomly select one of two live entries with > the > last condition. > > Something like this maybe makes it more clear what we are trying to do ? > > Your code solves the issue with replacement of alive entries while dead > ones exists, > but you're still uses hashes as random values which is not right. Hashes > are > not random > and there is no any difference in choosing the first entry or the entry > with a > bit > set in a particular place. There always will be some bad case where you > will > replace > same entries all the time and performance of EMC will be low. > > > diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c > > index 47a9fa0..75cc039 100644 > > --- a/lib/dpif-netdev.c > > +++ b/lib/dpif-netdev.c > > @@ -2051,12 +2051,15 @@ emc_insert(struct emc_cache *cache, const > struct netdev_flow_key *key, > > } > > > > /* Replacement policy: put the flow in an empty (not alive) > entry, or > > - * in the first entry where it can be */ > > - if (!to_be_replaced > > - || (emc_entry_alive(to_be_replaced) > > - && !emc_entry_alive(current_entry)) > > - || current_entry->key.hash < to_be_replaced->key.hash) { > > + * randomly choose one of the two alive entries to be > replaced. */ > > + if (!to_be_replaced) { > > to_be_replaced = current_entry; > > + } else if (emc_entry_alive(to_be_replaced) && > !emc_entry_alive(current_entry)) { > > + to_be_replaced = current_entry; > > + } else if (emc_entry_alive(to_be_replaced) && > emc_entry_alive(current_entry)) { > > + if (current_entry->key.hash & 0x1) { > > + to_be_replaced = current_entry; > > + } > > } > > } > > /* We didn't find the miniflow in the cache. > > > > ////////////////// > > > > Thanks > > Yipeng > > > > > -----Original Message----- > > > From: [email protected] [mailto:ovs-dev- > > > [email protected]] On Behalf Of Ilya Maximets > > > Sent: Friday, July 28, 2017 5:41 AM > > > To: [email protected] > > > Cc: Ilya Maximets <[email protected]>; Heetae Ahn > > > <[email protected]> > > > Subject: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement > policy. > > > > > > Current EMC replacement policy allows to replace active EMC entry > > > even if there are dead (empty) entries available. This leads to > > > EMC trashing even on few hundreds of flows. In some cases PMD > > > threads starts to execute classifier lookups even in tests with > > > 50 - 100 active flows. > > > > > > Fix this by removing of srtange hash comparison rule from the > > > replacement checking. New behavior also matches the comment that > > > describes replacement policy. This comment wasn't correct before. > > > > > > Testing shows stable work of exact match cache without misses > > > with up to 3072 active flows and only 0.05% of EMC misses with > > > 4096 flows. With higher number of flows there is no significant > > > difference with current implementation. > > > > > > For the reference, number of EMC misses in current master is > > > around 20% for the case with 2048 active flows. > > > > > > Testing performed with 100% EMC insert probability. > > > > > > Signed-off-by: Ilya Maximets <[email protected]> > > > --- > > > lib/dpif-netdev.c | 3 +-- > > > 1 file changed, 1 insertion(+), 2 deletions(-) > > > > > > diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c > > > index 47a9fa0..4a8dd80 100644 > > > --- a/lib/dpif-netdev.c > > > +++ b/lib/dpif-netdev.c > > > @@ -2054,8 +2054,7 @@ emc_insert(struct emc_cache *cache, const > struct > > > netdev_flow_key *key, > > > * in the first entry where it can be */ > > > if (!to_be_replaced > > > || (emc_entry_alive(to_be_replaced) > > > - && !emc_entry_alive(current_entry)) > > > - || current_entry->key.hash < > to_be_replaced->key.hash) { > > > + && !emc_entry_alive(current_entry))) { > > > to_be_replaced = current_entry; > > > } > > > } > > > -- > > > 2.7.4 > > > > > > _______________________________________________ > > > dev mailing list > > > [email protected] > > > https://urldefense.proofpoint.com/v2/url?u=https- > 3A__mail.openvswitch.org_mailman_listinfo_ovs- > 2Ddev&d=DwICAg&c=uilaK90D4TOVoH58JNXRgQ&r=BVhFA09CGX7JQ5Ih- > uZnsw&m=HFvjSxTsGMYHRXD3eRZLc3k_Bp2JfICYTyAbSu8BVWY&s=TNifYfm > VzvLBYl_mTbSPOlNnLousX2rUvGA8khGcOcw&e= > > _______________________________________________ > > dev mailing list > > [email protected] > > https://urldefense.proofpoint.com/v2/url?u=https- > 3A__mail.openvswitch.org_mailman_listinfo_ovs- > 2Ddev&d=DwICAg&c=uilaK90D4TOVoH58JNXRgQ&r=BVhFA09CGX7JQ5Ih- > uZnsw&m=HFvjSxTsGMYHRXD3eRZLc3k_Bp2JfICYTyAbSu8BVWY&s=TNifYfm > VzvLBYl_mTbSPOlNnLousX2rUvGA8khGcOcw&e= > > > > > > > > > > > > > > > > > _______________________________________________ > dev mailing list > [email protected] > https://mail.openvswitch.org/mailman/listinfo/ovs-dev _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
