| 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(-) > >> > > >> > >
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(-)