Re: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement policy.
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: ovs-dev-boun...@openvswitch.org [mailto:ovs-dev- > boun...@openvswitch.org] On Behalf Of Darrell Ball > Sent: Friday, August 4, 2017 8:38 PM > To: Ilya Maximets ; Wang, Yipeng1 > ; ovs-dev@openvswitch.org > Cc: Heetae Ahn > Subject: Re: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement > policy. > > > > -Original Message- > From: Ilya Maximets > Date: Monday, July 31, 2017 at 7:25 AM > To: Darrell Ball , "Wang, Yipeng1" > , "ovs-dev@openvswitch.org" d...@openvswitch.org> > Cc: Heetae Ahn > Subject: Re: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement > policy. > > On 31.07.2017 04:41, Darrell Ball wrote: > > > > > > -Original Message- > > From: on behalf of "Wang, > Yipeng1" > > Date: Friday, July 28, 2017 at 11:04 AM > > To: Ilya Maximets , "ovs- > d...@openvswitch.org" > > Cc: Heetae Ahn > > 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, > >
Re: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement policy.
-Original Message-
From: Ilya Maximets
Date: Monday, July 31, 2017 at 7:25 AM
To: Darrell Ball , "Wang, Yipeng1" ,
"ovs-dev@openvswitch.org"
Cc: Heetae Ahn
Subject: Re: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement policy.
On 31.07.2017 04:41, Darrell Ball wrote:
>
>
> -Original Message-
> From: on behalf of "Wang, Yipeng1"
> Date: Friday, July 28, 2017 at 11:04 AM
> To: Ilya Maximets , "ovs-dev@openvswitch.org"
> Cc: Heetae Ahn
> 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.
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: ovs-dev-boun...@openvswitch.org [mailto:ovs-dev-
> > boun...@openvswitch.org] On B
Re: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement policy.
On 31.07.2017 04:41, Darrell Ball wrote:
>
>
> -Original Message-
> From: on behalf of "Wang, Yipeng1"
>
> Date: Friday, July 28, 2017 at 11:04 AM
> To: Ilya Maximets , "ovs-dev@openvswitch.org"
>
> Cc: Heetae Ahn
> 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.
> //
>
> 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: ovs-dev-boun...@openvswitch.org [mailto:ovs-dev-
> > boun...@openvswitch.org] On Behalf Of Ilya Maximets
> > Sent: Friday, July 28, 2017 5:41 AM
> > To: ovs-dev@openvswitch.org
> > Cc: Ilya Maximets ; Heetae Ahn
> >
> > 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
Re: [ovs-dev] [PATCH] dpif-netdev: Simplify emc replacement policy.
-Original Message-
From: on behalf of "Wang, Yipeng1"
Date: Friday, July 28, 2017 at 11:04 AM
To: Ilya Maximets , "ovs-dev@openvswitch.org"
Cc: Heetae Ahn
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 – 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 ?
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: ovs-dev-boun...@openvswitch.org [mailto:ovs-dev-
> boun...@openvswitch.org] On Behalf Of Ilya Maximets
> Sent: Friday, July 28, 2017 5:41 AM
> To: ovs-dev@openvswitch.org
> Cc: Ilya Maximets ; Heetae Ahn
>
> 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
> ---
> 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
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;
Thanks
Yipeng
> -Original Message-
> From: ovs-dev-boun...@openvswitch.org [mailto:ovs-dev-
> boun...@openvswitch.org] On Behalf Of Ilya Maximets
> Sent: Friday, July 28, 2017 5:41 AM
> To: ovs-dev@openvswitch.org
> Cc: Ilya Maximets ; Heetae Ahn
>
> 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
> ---
> 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
> d...@openvswitch.org
> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
[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
---
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
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
