Message ID | 20230405194813.548329-1-i.maximets@ovn.org |
---|---|
Headers | show |
Series | expr: Optimize OR expressions. | expand |
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(-) >
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(-) > > >
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(-) >> > >>
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(-) > >> > > >> > >