mbox series

[ovs-dev,v4,0/2] expr: Optimize OR expressions.

Message ID 20230405194813.548329-1-i.maximets@ovn.org
Headers show
Series expr: Optimize OR expressions. | expand

Message

Ilya Maximets April 5, 2023, 7:48 p.m. UTC
This patch set covers removal of expressions which are subsets of other
wider expressions.  This allows to avoid flow explosion in case of
negative matches.  More details are in commit messages.

Version 2:
  * Became a patch set.
  * Added tests and missing bitmap.h include.
  * Code switched to work with bitwise maskable fields only (ORDINAL).
  * Added a new patch to combine smaller expressions into wider ones.
  * Added a patch to fix a crash uncovered with expression aggregation.

Version 3:
  * Dropped patch 3 for performance reasons for now, because it doesn't
    allow to make use of I-P in many cases.
  * Patch 1 re-worked to not cause performance issues for normal
    address sets generated in OVN.
  * Performance of the patch 1 significantly improved by not perfroming
    a full n^2 search and not comparing huge empty parts of subvalues.
    The patch became a bit less straightforward, but I hope it's still
    fairly readable.

Version 4:
  * Added extra comments.
  * Added ACK from Han to patch 2.
  * Re-worked path shortening (next[]) to track the last non-NULL entry.
  * Restricted superset optmization to expressions that do not track
    address sets.  To preserve ability to use I-P. [Han]

Ilya Maximets (2):
  expr: Remove supersets from OR expressions.
  expr: Avoid crash if all sub-expressions crushed down to 'true'.

 include/ovn/expr.h |   1 +
 lib/expr.c         | 255 +++++++++++++++++++++++++++++++++++----------
 tests/ovn.at       |  12 +++
 3 files changed, 212 insertions(+), 56 deletions(-)

Comments

Ilya Maximets April 5, 2023, 7:50 p.m. UTC | #1
On 4/5/23 21:48, Ilya Maximets wrote:
> This patch set covers removal of expressions which are subsets of other
> wider expressions.  This allows to avoid flow explosion in case of
> negative matches.  More details are in commit messages.
> 
> Version 2:
>   * Became a patch set.
>   * Added tests and missing bitmap.h include.
>   * Code switched to work with bitwise maskable fields only (ORDINAL).
>   * Added a new patch to combine smaller expressions into wider ones.
>   * Added a patch to fix a crash uncovered with expression aggregation.
> 
> Version 3:
>   * Dropped patch 3 for performance reasons for now, because it doesn't
>     allow to make use of I-P in many cases.
>   * Patch 1 re-worked to not cause performance issues for normal
>     address sets generated in OVN.
>   * Performance of the patch 1 significantly improved by not perfroming
>     a full n^2 search and not comparing huge empty parts of subvalues.
>     The patch became a bit less straightforward, but I hope it's still
>     fairly readable.
> 
> Version 4:
>   * Added extra comments.
>   * Added ACK from Han to patch 2.
>   * Re-worked path shortening (next[]) to track the last non-NULL entry.
>   * Restricted superset optmization to expressions that do not track
>     address sets.  To preserve ability to use I-P. [Han]
Forgot to add:

    * Fixed the memset value: s/0xf/0xff/.  [Han]

> 
> Ilya Maximets (2):
>   expr: Remove supersets from OR expressions.
>   expr: Avoid crash if all sub-expressions crushed down to 'true'.
> 
>  include/ovn/expr.h |   1 +
>  lib/expr.c         | 255 +++++++++++++++++++++++++++++++++++----------
>  tests/ovn.at       |  12 +++
>  3 files changed, 212 insertions(+), 56 deletions(-)
>
Han Zhou April 10, 2023, 6:45 p.m. UTC | #2
On Wed, Apr 5, 2023 at 12:50 PM Ilya Maximets <i.maximets@ovn.org> wrote:
>
> On 4/5/23 21:48, Ilya Maximets wrote:
> > This patch set covers removal of expressions which are subsets of other
> > wider expressions.  This allows to avoid flow explosion in case of
> > negative matches.  More details are in commit messages.
> >
> > Version 2:
> >   * Became a patch set.
> >   * Added tests and missing bitmap.h include.
> >   * Code switched to work with bitwise maskable fields only (ORDINAL).
> >   * Added a new patch to combine smaller expressions into wider ones.
> >   * Added a patch to fix a crash uncovered with expression aggregation.
> >
> > Version 3:
> >   * Dropped patch 3 for performance reasons for now, because it doesn't
> >     allow to make use of I-P in many cases.
> >   * Patch 1 re-worked to not cause performance issues for normal
> >     address sets generated in OVN.
> >   * Performance of the patch 1 significantly improved by not perfroming
> >     a full n^2 search and not comparing huge empty parts of subvalues.
> >     The patch became a bit less straightforward, but I hope it's still
> >     fairly readable.
> >
> > Version 4:
> >   * Added extra comments.
> >   * Added ACK from Han to patch 2.
> >   * Re-worked path shortening (next[]) to track the last non-NULL entry.
> >   * Restricted superset optmization to expressions that do not track
> >     address sets.  To preserve ability to use I-P. [Han]

Thanks Ilya. Ideally the restriction can be more relaxed to allow merging
for expr resulted from negation on address sets, because address set I-P
doesn't support negation anyway and it would be expensive without merging
for supersets. But I think the current approach should be fine because from
what I can tell it is less common to apply negation on address sets. This
can be improved further if needed.

So, I went ahead and applied the series to main.

Regards,
Han

> Forgot to add:
>
>     * Fixed the memset value: s/0xf/0xff/.  [Han]
>
> >
> > Ilya Maximets (2):
> >   expr: Remove supersets from OR expressions.
> >   expr: Avoid crash if all sub-expressions crushed down to 'true'.
> >
> >  include/ovn/expr.h |   1 +
> >  lib/expr.c         | 255 +++++++++++++++++++++++++++++++++++----------
> >  tests/ovn.at       |  12 +++
> >  3 files changed, 212 insertions(+), 56 deletions(-)
> >
>
Ilya Maximets April 24, 2023, 12:49 p.m. UTC | #3
On 4/10/23 20:45, Han Zhou wrote:
> 
> 
> On Wed, Apr 5, 2023 at 12:50 PM Ilya Maximets <i.maximets@ovn.org <mailto:i.maximets@ovn.org>> wrote:
>>
>> On 4/5/23 21:48, Ilya Maximets wrote:
>> > This patch set covers removal of expressions which are subsets of other
>> > wider expressions.  This allows to avoid flow explosion in case of
>> > negative matches.  More details are in commit messages.
>> >
>> > Version 2:
>> >   * Became a patch set.
>> >   * Added tests and missing bitmap.h include.
>> >   * Code switched to work with bitwise maskable fields only (ORDINAL).
>> >   * Added a new patch to combine smaller expressions into wider ones.
>> >   * Added a patch to fix a crash uncovered with expression aggregation.
>> >
>> > Version 3:
>> >   * Dropped patch 3 for performance reasons for now, because it doesn't
>> >     allow to make use of I-P in many cases.
>> >   * Patch 1 re-worked to not cause performance issues for normal
>> >     address sets generated in OVN.
>> >   * Performance of the patch 1 significantly improved by not perfroming
>> >     a full n^2 search and not comparing huge empty parts of subvalues.
>> >     The patch became a bit less straightforward, but I hope it's still
>> >     fairly readable.
>> >
>> > Version 4:
>> >   * Added extra comments.
>> >   * Added ACK from Han to patch 2.
>> >   * Re-worked path shortening (next[]) to track the last non-NULL entry.
>> >   * Restricted superset optmization to expressions that do not track
>> >     address sets.  To preserve ability to use I-P. [Han]
> 
> Thanks Ilya. Ideally the restriction can be more relaxed to allow merging for expr resulted from negation on address sets, because address set I-P doesn't support negation anyway and it would be expensive without merging for supersets. But I think the current approach should be fine because from what I can tell it is less common to apply negation on address sets. This can be improved further if needed.

I think, this should already work, because expansion of "!="
expression will loose the address set reference anyway during
simplification in expr_simplify_ne().

> 
> So, I went ahead and applied the series to main.

Thanks!

Best regards, Ilya Maximets.

> 
> Regards,
> Han
> 
>> Forgot to add:
>>
>>     * Fixed the memset value: s/0xf/0xff/.  [Han]
>>
>> >
>> > Ilya Maximets (2):
>> >   expr: Remove supersets from OR expressions.
>> >   expr: Avoid crash if all sub-expressions crushed down to 'true'.
>> >
>> >  include/ovn/expr.h |   1 +
>> >  lib/expr.c         | 255 +++++++++++++++++++++++++++++++++++----------
>> >  tests/ovn.at <http://ovn.at>       |  12 +++
>> >  3 files changed, 212 insertions(+), 56 deletions(-)
>> >
>>
Han Zhou April 24, 2023, 4:37 p.m. UTC | #4
On Mon, Apr 24, 2023 at 5:49 AM Ilya Maximets <i.maximets@ovn.org> wrote:

> On 4/10/23 20:45, Han Zhou wrote:
> >
> >
> > On Wed, Apr 5, 2023 at 12:50 PM Ilya Maximets <i.maximets@ovn.org
> <mailto:i.maximets@ovn.org>> wrote:
> >>
> >> On 4/5/23 21:48, Ilya Maximets wrote:
> >> > This patch set covers removal of expressions which are subsets of
> other
> >> > wider expressions.  This allows to avoid flow explosion in case of
> >> > negative matches.  More details are in commit messages.
> >> >
> >> > Version 2:
> >> >   * Became a patch set.
> >> >   * Added tests and missing bitmap.h include.
> >> >   * Code switched to work with bitwise maskable fields only (ORDINAL).
> >> >   * Added a new patch to combine smaller expressions into wider ones.
> >> >   * Added a patch to fix a crash uncovered with expression
> aggregation.
> >> >
> >> > Version 3:
> >> >   * Dropped patch 3 for performance reasons for now, because it
> doesn't
> >> >     allow to make use of I-P in many cases.
> >> >   * Patch 1 re-worked to not cause performance issues for normal
> >> >     address sets generated in OVN.
> >> >   * Performance of the patch 1 significantly improved by not
> perfroming
> >> >     a full n^2 search and not comparing huge empty parts of subvalues.
> >> >     The patch became a bit less straightforward, but I hope it's still
> >> >     fairly readable.
> >> >
> >> > Version 4:
> >> >   * Added extra comments.
> >> >   * Added ACK from Han to patch 2.
> >> >   * Re-worked path shortening (next[]) to track the last non-NULL
> entry.
> >> >   * Restricted superset optmization to expressions that do not track
> >> >     address sets.  To preserve ability to use I-P. [Han]
> >
> > Thanks Ilya. Ideally the restriction can be more relaxed to allow
> merging for expr resulted from negation on address sets, because address
> set I-P doesn't support negation anyway and it would be expensive without
> merging for supersets. But I think the current approach should be fine
> because from what I can tell it is less common to apply negation on address
> sets. This can be improved further if needed.
>
> I think, this should already work, because expansion of "!="
> expression will loose the address set reference anyway during
> simplification in expr_simplify_ne().


Yes you are right! Sorry for missing this point.

Thanks,
Han

>
>
> >
> > So, I went ahead and applied the series to main.
>
> Thanks!
>
> Best regards, Ilya Maximets.
>
> >
> > Regards,
> > Han
> >
> >> Forgot to add:
> >>
> >>     * Fixed the memset value: s/0xf/0xff/.  [Han]
> >>
> >> >
> >> > Ilya Maximets (2):
> >> >   expr: Remove supersets from OR expressions.
> >> >   expr: Avoid crash if all sub-expressions crushed down to 'true'.
> >> >
> >> >  include/ovn/expr.h |   1 +
> >> >  lib/expr.c         | 255
> +++++++++++++++++++++++++++++++++++----------
> >> >  tests/ovn.at <http://ovn.at>       |  12 +++
> >> >  3 files changed, 212 insertions(+), 56 deletions(-)
> >> >
> >>
>
>