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 /external | |
| 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>
Diffstat (limited to 'external')
| -rw-r--r-- | external/mdds/UnpackedTarball_mdds.mk | 1 | ||||
| -rw-r--r-- | external/mdds/use-position-hint-also-back.patch | 50 |
2 files changed, 51 insertions, 0 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 + |