diff options
author | Luboš Luňák <l.lunak@collabora.com> | 2019-05-16 17:50:09 +0200 |
---|---|---|
committer | Luboš Luňák <l.lunak@collabora.com> | 2019-05-20 10:04:13 +0200 |
commit | b81004e95638da19cbcaa7a61f9edd094a9eac31 (patch) | |
tree | 339cf686771522d70f60e0696ec16630da6e78f2 | |
parent | 5d5e308331e7166726264c43545798b5fb833c8a (diff) |
cache mdds positions during ScDocument::CopyBlockFromClip() (tdf#112000)
Make RefUpdateContext and ScColumn::UpdateReferenceOnCopy() use the same
sc::ColumnBlockPositionSet that CopyFromClipContext uses. Without it
pathological cases like in tdf#112000 trigger quadratic cost because
of repeated mdds searches from the start.
Includes also an mdds patch that allows it to search backwards
from a position hint. Without it, this would be very difficult to fix
otherwise, as CopyFromClip() in ScDocument::CopyBlockFromClip()
moves the position hint past the area that UpdateReferenceOnCopy()
would use. It also just plain makes sense to try to go backwards
in an std::vector.
Change-Id: I985e3a40e4abf1a824e55c76d82579882fa75cc2
Reviewed-on: https://gerrit.libreoffice.org/72424
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lunak@collabora.com>
-rw-r--r-- | external/mdds/UnpackedTarball_mdds.mk | 1 | ||||
-rw-r--r-- | external/mdds/use-position-hint-also-back.patch | 50 | ||||
-rw-r--r-- | sc/inc/clipcontext.hxx | 1 | ||||
-rw-r--r-- | sc/inc/column.hxx | 2 | ||||
-rw-r--r-- | sc/inc/refupdatecontext.hxx | 8 | ||||
-rw-r--r-- | sc/source/core/data/column.cxx | 8 | ||||
-rw-r--r-- | sc/source/core/data/document.cxx | 1 | ||||
-rw-r--r-- | sc/source/core/data/refupdatecontext.cxx | 13 |
8 files changed, 80 insertions, 4 deletions
diff --git a/external/mdds/UnpackedTarball_mdds.mk b/external/mdds/UnpackedTarball_mdds.mk index c015f4c13f5a..625204d29619 100644 --- a/external/mdds/UnpackedTarball_mdds.mk +++ b/external/mdds/UnpackedTarball_mdds.mk @@ -14,6 +14,7 @@ $(eval $(call gb_UnpackedTarball_set_tarball,mdds,$(MDDS_TARBALL))) $(eval $(call gb_UnpackedTarball_set_patchlevel,mdds,0)) $(eval $(call gb_UnpackedTarball_add_patches,mdds,\ + external/mdds/use-position-hint-also-back.patch \ )) # vim: set noet sw=4 ts=4: diff --git a/external/mdds/use-position-hint-also-back.patch b/external/mdds/use-position-hint-also-back.patch new file mode 100644 index 000000000000..0b38c38d5536 --- /dev/null +++ b/external/mdds/use-position-hint-also-back.patch @@ -0,0 +1,50 @@ +From 726e2f02d14833bde2f7eef9677f5564c485a992 Mon Sep 17 00:00:00 2001 +From: =?UTF-8?q?Lubo=C5=A1=20Lu=C5=88=C3=A1k?= <l.lunak@centrum.cz> +Date: Fri, 17 May 2019 13:55:20 +0200 +Subject: [PATCH] use position hint also when it is past the actual position + +The m_blocks data structure is a vector. It means that it can be +also walked back, instead of resetting and starting from the very +start. + +Allows a noticeable performance improvement in +https://gerrit.libreoffice.org/#/c/72424/ . +--- + include/mdds/multi_type_vector_def.inl | 21 ++++++++++++++++++++- + 1 file changed, 20 insertions(+), 1 deletion(-) + +diff --git a/include/mdds/multi_type_vector_def.inl b/include/mdds/multi_type_vector_def.inl +index 22a0ee2..09894e6 100644 +--- include/mdds/multi_type_vector_def.inl ++++ include/mdds/multi_type_vector_def.inl +@@ -861,7 +861,26 @@ void multi_type_vector<_CellBlockFunc, _EventFunc>::get_block_position( + + if (pos < start_row) + { +- // Position hint is past the insertion position. Reset. ++ // Position hint is past the insertion position. ++ // Walk back if that seems efficient. ++ if (pos > start_row / 2) ++ { ++ for (size_type i = block_index; i > 0;) ++ { ++ --i; ++ const block& blk = m_blocks[i]; ++ start_row -= blk.m_size; ++ if (pos >= start_row) ++ { ++ // Row is in this block. ++ block_index = i; ++ return; ++ } ++ // Specified row is not in this block. ++ } ++ assert(start_row == 0); ++ } ++ // Otherwise reset. + start_row = 0; + block_index = 0; + } +-- +2.16.4 + diff --git a/sc/inc/clipcontext.hxx b/sc/inc/clipcontext.hxx index f2a7af56818b..6752104fb34c 100644 --- a/sc/inc/clipcontext.hxx +++ b/sc/inc/clipcontext.hxx @@ -40,6 +40,7 @@ public: virtual ~ClipContextBase(); ColumnBlockPosition* getBlockPosition(SCTAB nTab, SCCOL nCol); + ColumnBlockPositionSet* getBlockPositionSet() { return mpSet.get(); } }; class CopyFromClipContext : public ClipContextBase diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx index 340b5628faf6..e7e40fd528bf 100644 --- a/sc/inc/column.hxx +++ b/sc/inc/column.hxx @@ -417,7 +417,7 @@ public: void ResetChanged( SCROW nStartRow, SCROW nEndRow ); - bool UpdateReferenceOnCopy( const sc::RefUpdateContext& rCxt, ScDocument* pUndoDoc = nullptr ); + bool UpdateReferenceOnCopy( sc::RefUpdateContext& rCxt, ScDocument* pUndoDoc = nullptr ); /** * Update reference addresses in formula cell in response to mass cell diff --git a/sc/inc/refupdatecontext.hxx b/sc/inc/refupdatecontext.hxx index 7b5afe926e1a..bc86cb9e1afe 100644 --- a/sc/inc/refupdatecontext.hxx +++ b/sc/inc/refupdatecontext.hxx @@ -21,6 +21,9 @@ class ScDocument; namespace sc { +struct ColumnBlockPosition; +class ColumnBlockPositionSet; + /** * Keep track of all named expressions that have been updated during * reference update. @@ -76,10 +79,15 @@ struct RefUpdateContext UpdatedRangeNames maUpdatedNames; ColumnSet maRegroupCols; + ColumnBlockPositionSet* mpBlockPos; // not owning + RefUpdateContext(ScDocument& rDoc); bool isInserted() const; bool isDeleted() const; + + void setBlockPositionReference( ColumnBlockPositionSet* blockPos ); + ColumnBlockPosition* getBlockPosition(SCTAB nTab, SCCOL nCol); }; struct RefUpdateResult diff --git a/sc/source/core/data/column.cxx b/sc/source/core/data/column.cxx index 548e6403cc8b..18132d2fc454 100644 --- a/sc/source/core/data/column.cxx +++ b/sc/source/core/data/column.cxx @@ -42,6 +42,7 @@ #include <listenercontext.hxx> #include <formulagroup.hxx> #include <drwlayer.hxx> +#include <mtvelements.hxx> #include <svl/poolcach.hxx> #include <svl/zforlist.hxx> @@ -2424,14 +2425,17 @@ public: } -bool ScColumn::UpdateReferenceOnCopy( const sc::RefUpdateContext& rCxt, ScDocument* pUndoDoc ) +bool ScColumn::UpdateReferenceOnCopy( sc::RefUpdateContext& rCxt, ScDocument* pUndoDoc ) { // When copying, the range equals the destination range where cells // are pasted, and the dx, dy, dz refer to the distance from the // source range. UpdateRefOnCopy aHandler(rCxt, pUndoDoc); - sc::CellStoreType::position_type aPos = maCells.position(rCxt.maRange.aStart.Row()); + sc::ColumnBlockPosition* blockPos = rCxt.getBlockPosition(nTab, nCol); + sc::CellStoreType::position_type aPos = blockPos + ? maCells.position(blockPos->miCellPos, rCxt.maRange.aStart.Row()) + : maCells.position(rCxt.maRange.aStart.Row()); sc::ProcessBlock(aPos.first, maCells, aHandler, rCxt.maRange.aStart.Row(), rCxt.maRange.aEnd.Row()); // The formula groups at the top and bottom boundaries are expected to diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx index 4e74fc8dbf56..106ca902534e 100644 --- a/sc/source/core/data/document.cxx +++ b/sc/source/core/data/document.cxx @@ -2675,6 +2675,7 @@ void ScDocument::CopyBlockFromClip( aRefCxt.mnColDelta = nDx; aRefCxt.mnRowDelta = nDy; aRefCxt.mnTabDelta = nDz; + aRefCxt.setBlockPositionReference(rCxt.getBlockPositionSet()); // share mdds position caching if (rCxt.getClipDoc()->GetClipParam().mbCutMode) { // Update references only if cut originates from the same diff --git a/sc/source/core/data/refupdatecontext.cxx b/sc/source/core/data/refupdatecontext.cxx index d4cce81dc680..c34ac6860ee1 100644 --- a/sc/source/core/data/refupdatecontext.cxx +++ b/sc/source/core/data/refupdatecontext.cxx @@ -9,6 +9,7 @@ #include <refupdatecontext.hxx> #include <algorithm> +#include <mtvelements.hxx> namespace sc { @@ -64,7 +65,7 @@ bool UpdatedRangeNames::isEmpty(SCTAB nTab) const RefUpdateContext::RefUpdateContext(ScDocument& rDoc) : - mrDoc(rDoc), meMode(URM_INSDEL), mnColDelta(0), mnRowDelta(0), mnTabDelta(0) {} + mrDoc(rDoc), meMode(URM_INSDEL), mnColDelta(0), mnRowDelta(0), mnTabDelta(0), mpBlockPos( nullptr ) {} bool RefUpdateContext::isInserted() const { @@ -76,6 +77,16 @@ bool RefUpdateContext::isDeleted() const return (meMode == URM_INSDEL) && (mnColDelta < 0 || mnRowDelta < 0 || mnTabDelta < 0); } +void RefUpdateContext::setBlockPositionReference( ColumnBlockPositionSet* blockPos ) +{ + mpBlockPos = blockPos; +} + +ColumnBlockPosition* RefUpdateContext::getBlockPosition(SCTAB nTab, SCCOL nCol) +{ + return mpBlockPos ? mpBlockPos->getBlockPosition(nTab, nCol) : nullptr; +} + RefUpdateResult::RefUpdateResult() : mbValueChanged(false), mbReferenceModified(false), mbNameModified(false) {} RefUpdateInsertTabContext::RefUpdateInsertTabContext(ScDocument& rDoc, SCTAB nInsertPos, SCTAB nSheets) : |