mbox series

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

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

Message

Ilya Maximets March 29, 2023, 4:05 p.m. UTC 
This patch set covers removal of expressions which are subsets of other
wider expressions and aggregation of a few granular expressions into
wider expressions that cover all of them at once.  This allows to avoid
flow explosion in case of negative matches and reduce the total number
of flows required for address sets.  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.

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         | 240 ++++++++++++++++++++++++++++++++++-----------
 tests/ovn.at       |  12 +++
 3 files changed, 197 insertions(+), 56 deletions(-)