sw/source/core/bastyp/swregion.cxx | 103 +++++++++++++++++++++++--------------
1 file changed, 65 insertions(+), 38 deletions(-)
New commits:
commit cc832cbbe2e6d9af16919f7d3801ec52b94a792a
Author: Luboš Luňák <l.lu...@collabora.com>
AuthorDate: Fri Sep 17 00:14:08 2021 +0200
Commit: Luboš Luňák <l.lu...@collabora.com>
CommitDate: Sun Sep 19 09:33:23 2021 +0200
optimize SwRegionRects::Compress() more
Implement Noel's idea of sorting the rectangles by Y axis and then
considering only pairs of rectangles that are close enough to
possibly get merged.
Change-Id: Iac4a94fc411237f8c0fb5812906dc832be398cfa
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/122216
Tested-by: Jenkins CollaboraOffice <jenkinscollaboraoff...@gmail.com>
Reviewed-by: Luboš Luňák <l.lu...@collabora.com>
diff --git a/sw/source/core/bastyp/swregion.cxx
b/sw/source/core/bastyp/swregion.cxx
index defc4c07e95c..55b857ffdefa 100644
--- a/sw/source/core/bastyp/swregion.cxx
+++ b/sw/source/core/bastyp/swregion.cxx
@@ -147,23 +147,32 @@ void SwRegionRects::Compress()
bool bAgain;
do
{
+ sort( begin(), end(), []( const SwRect& l, const SwRect& r ) { return
l.Top() < r.Top(); } );
bAgain = false;
for (size_type i = 0; i < size(); ++i )
{
- for ( size_type j = i+1; j < size(); ++j )
+ // Rectangles are sorted by Y axis, so check only pairs of
rectangles
+ // that are possibly overlapping or adjacent or close enough to be
grouped by the fuzzy
+ // code below.
+ const tools::Long nFuzzy = 1361513;
+ const tools::Long yMax = (*this)[i].Bottom() + nFuzzy /
(*this)[i].Width();
+ size_type j = i+1;
+ while( j < size() && (*this)[j].Top() <= yMax )
+ ++j;
+ --j;
+ // Walk backwards for simpler and faster erase().
+ for ( ; j >= i+1; --j )
{
// If one rectangle contains a second completely than the
latter
// does not need to be stored and can be deleted
if ( (*this)[i].IsInside( (*this)[j] ) )
{
erase( begin() + j );
- --j;
}
else if ( (*this)[j].IsInside( (*this)[i] ) )
{
(*this)[i] = (*this)[j];
erase( begin() + j );
- --j;
bAgain = true;
}
else
@@ -187,7 +196,6 @@ void SwRegionRects::Compress()
// paints), the area of the union can be a little bit
larger:
// ( 9622 * 141.5 = 1361513 ~= a quarter (1/4) centimeter
wider
// than the width of an A4 page
- const tools::Long nFuzzy = 1361513;
SwRect aUnion( (*this)[i] );
aUnion.Union( (*this)[j] );
SwRect aInter( (*this)[i] );
@@ -198,12 +206,15 @@ void SwRegionRects::Compress()
{
(*this)[i] = aUnion;
erase( begin() + j );
- --j;
bAgain = true;
}
}
}
}
+ // Code paths setting bAgain alter elements of the vector, possibly
breaking
+ // the Y-axis optimization, so run another pass just to make sure. The
adjacent-rects
+ // merging code may possibly benefit from a repeated pass also if two
pairs of merged
+ // rects might get merged again and this pass skipped that.
} while(bAgain);
}
commit f90fac8e0c7cf4b4ffcca8ad9cdc076460360cdb
Author: Luboš Luňák <l.lu...@collabora.com>
AuthorDate: Wed Sep 15 13:49:11 2021 +0200
Commit: Luboš Luňák <l.lu...@collabora.com>
CommitDate: Sun Sep 19 09:33:11 2021 +0200
optimize SwRegionRects::Compress()
This function gets called on modifying documents, and it shows up
noticeably e.g. when profiling editing in Online.
The code repeatedly restarts the whole process on most changes,
but in practice this seems to only lead to repeated checks with
the same outcome. So finish the whole compression and try again
only at the end, if deemed needed. And even there I'm not sure
if it's actually ever needed, since I couldn't trigger such a case
in practice.
Change-Id: I15b0a83c6865bad21fe60a7e9ca0b87ceea5b489
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/122156
Tested-by: Luboš Luňák <l.lu...@collabora.com>
Reviewed-by: Luboš Luňák <l.lu...@collabora.com>
(cherry picked from commit d13b63a9859d653d1aba688a56590aa0ef24b89c)
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/122121
Tested-by: Jenkins CollaboraOffice <jenkinscollaboraoff...@gmail.com>
diff --git a/sw/source/core/bastyp/swregion.cxx
b/sw/source/core/bastyp/swregion.cxx
index 09e07757b236..defc4c07e95c 100644
--- a/sw/source/core/bastyp/swregion.cxx
+++ b/sw/source/core/bastyp/swregion.cxx
@@ -136,7 +136,7 @@ void SwRegionRects::Invert()
swap( aInvRegion );
}
-static SwTwips CalcArea( const SwRect &rRect )
+static inline SwTwips CalcArea( const SwRect &rRect )
{
return rRect.Width() * rRect.Height();
}
@@ -144,51 +144,67 @@ static SwTwips CalcArea( const SwRect &rRect )
// combine all adjacent rectangles
void SwRegionRects::Compress()
{
- for (size_type i = 0; i < size(); )
+ bool bAgain;
+ do
{
- bool bRestart(false);
- for ( size_type j = i+1; j < size(); ++j )
+ bAgain = false;
+ for (size_type i = 0; i < size(); ++i )
{
- // If one rectangle contains a second completely than the latter
- // does not need to be stored and can be deleted
- if ( (*this)[i].IsInside( (*this)[j] ) )
+ for ( size_type j = i+1; j < size(); ++j )
{
- erase( begin() + j );
- --j;
- }
- else if ( (*this)[j].IsInside( (*this)[i] ) )
- {
- (*this)[i] = (*this)[j];
- erase( begin() + j );
- bRestart = true;
- break;
- }
- else
- {
- // If two rectangles have the same area of their union minus
the
- // intersection then one of them can be deleted.
- // For combining as much as possible (and for having less
single
- // paints), the area of the union can be a little bit larger:
- // ( 9622 * 141.5 = 1361513 ~= a quarter (1/4) centimeter wider
- // than the width of an A4 page
- const tools::Long nFuzzy = 1361513;
- SwRect aUnion( (*this)[i] );
- aUnion.Union( (*this)[j] );
- SwRect aInter( (*this)[i] );
- aInter.Intersection( (*this)[j] );
- if ( (::CalcArea( (*this)[i] ) +
- ::CalcArea( (*this)[j] ) + nFuzzy) >=
- (::CalcArea( aUnion ) - CalcArea( aInter )) )
+ // If one rectangle contains a second completely than the
latter
+ // does not need to be stored and can be deleted
+ if ( (*this)[i].IsInside( (*this)[j] ) )
+ {
+ erase( begin() + j );
+ --j;
+ }
+ else if ( (*this)[j].IsInside( (*this)[i] ) )
{
- (*this)[i] = aUnion;
+ (*this)[i] = (*this)[j];
erase( begin() + j );
- bRestart = true;
- break;
+ --j;
+ bAgain = true;
+ }
+ else
+ {
+ // TODO: I think the comment below and the code are
partially incorrect.
+ // An obvious mistake is the comment saying that one
rectangle can be deleted,
+ // while it's the union that gets used instead of the two
rectangles.
+ // I think this code is supposed to merge adjacent
rectangles (possibly
+ // overlapping), and such rectangles can be detected by
their merged areas
+ // being equal to the area of the union (which is
obviously the case if they
+ // share one side, and using the nFuzzy extra allow
merging also rectangles
+ // that do not quite cover the entire union but it's close
enough).
+ // So another mistake seems to be using '- CalcArea(
aInter )',
+ // it should be on the other side of the comparison to
subtract shared area
+ // counted twice. In practice it seems rectangles here do
not share areas,
+ // so the error is irrelevant.
+
+ // If two rectangles have the same area of their union
minus the
+ // intersection then one of them can be deleted.
+ // For combining as much as possible (and for having less
single
+ // paints), the area of the union can be a little bit
larger:
+ // ( 9622 * 141.5 = 1361513 ~= a quarter (1/4) centimeter
wider
+ // than the width of an A4 page
+ const tools::Long nFuzzy = 1361513;
+ SwRect aUnion( (*this)[i] );
+ aUnion.Union( (*this)[j] );
+ SwRect aInter( (*this)[i] );
+ aInter.Intersection( (*this)[j] );
+ if ( (::CalcArea( (*this)[i] ) +
+ ::CalcArea( (*this)[j] ) + nFuzzy) >=
+ (::CalcArea( aUnion ) - CalcArea( aInter )) )
+ {
+ (*this)[i] = aUnion;
+ erase( begin() + j );
+ --j;
+ bAgain = true;
+ }
}
}
}
- i = bRestart ? 0 : i+1;
- }
+ } while(bAgain);
}
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
