[upstream] Poor performance with find & replace with empty value on large data set

[Bryan Quigley]

[SRU justification]

[Impact]

Hang or Very slow performance after replaceall or searchall massive data

Regression in Find and Replace with LO Calc 4.2 (last worked in 4.1). It now takes a long time to "Find and Replace" if the to be replaced is to nothing.

See comment #5/#6 of upstream for reproducer.
See commend #8 for bibisect.

[Test Case]

fill A column to 0
select A column

Replace All 0 to " " ( null space )

[Regression Potential]
restricted, relevant patches are currently:
- upstream master
- all upstream 4.4.0 alpha/beta builds
- upstream 4-4 branch
- backported (by me) to upstream 4-3 branch
  => thus also included in upstream 4.3.5~rc1 released on November, 27th
  => thus will also be released by upstream 4.3.5 on ~December, 18th
- backported to 4.3.4/utopic package (downstream, Ubuntu only)
- backported to 4.2.7/trusty package (downstream, Ubuntu only)
- included in all current 4.3.x and 4.2.x backports in the LibreOffice PPAs
- included in all the 4.4~beta1 builds on the LibreOffice prereleases PPA

[Other Info]
upstream patch

http://cgit.freedesktop.org/libreoffice/core/commit/?id=1cf19ea84794ca065749667b480dfed2d27d47b7
http://cgit.freedesktop.org/libreoffice/core/commit/?id=1e721077b43de84edab2a3ed2f316ddcbec6e3ec
http://cgit.freedesktop.org/libreoffice/core/commit/?id=91502a72c12c559442e8bf77c27a516b49c2a68d

[El Samuels (wesamuels)]

Problem description:

Steps to reproduce:
1. Open on .ods file in Calc with large amount of data, e.g., 584 columns & 755 rows
2. Run Search & Replace to replace contents of ~20% of cells
3. Program freezes, requires a kill process (TERM command) to unfreeze

Current behavior:
So, that's one way to describe the issue in operationalizable terms, but it's really that when a large file is opened, many operations in Calc can be _greatly_ lagging. E.g., scrolling right through columns can start to lag behind a continually-pressed key (viz., right arrow) such that Calc takes several seconds to catch up after the key is let up. I'm not in any way a programmer, but seems like maybe an issue of how objects are held and manipulated in memory?

In a sense, I'm asking for a lot (and, yeah, sorry but probably through a very poorly-submitted & -formatted bug report; this isn't my bailiwick), but, yeah, I _do_ ask a lot of the spreadsheet program of an office suite. I believe it's where most people make their decision about what office suite to use. Word processors, presentation software, etc. are simpler and usually contain less importantly rich information that needs quicker processing.

Expected behavior:
Faster responsiveness on larger files. Perfection right now! : )

Oh, and maybe knowing (& finding out how to) better submit bug reports and help improve LO qua end user.
Operating System: Ubuntu
Version: 4.2.3.3 rc

[Mariosv (mariosv)]

Hi Wes, thanks for reporting.

Please can you attach a sample file.

[El Samuels (wesamuels)]

Created attachment 97320
attachment-2559-0.html

Hi There,

Of course.

The original file contains highly sensitive information (personal,
identifiable data from a longitudinal study of at-risk adolescents), so
I've used the sed command to replace the the original contents with
nonsense. But, I've replicated it with that new, attached file (and found
it with other large files, too). I was trying to replace the cells
containing NA with empty cells (and vice-versa).

This is may be nothing more than the patient trying to tell the doctor how
to do his job, but it seems related to how RAM is used, and perhaps
includes elements from the document history: Larger files on which many,
complex operations are done (e.g., copying in formulae that operate on
several cells into _all_ cells in a column) will crash it, and this seems
both to get a bit worse as the file has been worked on for a while and to
get a bit better after LO is restarted.

Unrelatedly, I am interested in helping out with LO, but don't have many
skills that are useful. So, if you know of things an average Joe end user
can do (beta testing, language clean-up in online guides, etc.), please let
me know. I've looked around a bit on the site to find this, but probably
more through lack of sufficient effort haven't found things I personally
can do to help.

Sorry for the longiloquence, and thank you so much for the help!

El

On Sun, Apr 13, 2014 at 11:10 AM, <email address hidden> wrote:

> m.a.riosv <email address hidden> changed bug 77382<https://bugs.freedesktop.org/show_bug.cgi?id=77382>
> What Removed Added Status UNCONFIRMED NEEDINFO CC
> <email address hidden> Ever confirmed 1
>
> *Comment # 1 <https://bugs.freedesktop.org/show_bug.cgi?id=77382#c1> on
> bug 77382 <https://bugs.freedesktop.org/show_bug.cgi?id=77382> from
> m.a.riosv <email address hidden> *
>
> Hi Wes, thanks for reporting.
>
> Please can you attach a sample file.
>
> ------------------------------
> You are receiving this mail because:
>
> - You reported the bug.
>
>

[El Samuels (wesamuels)]

Created attachment 97321
attachment-2559-1.dat

[El Samuels (wesamuels)]

Created attachment 97322
bug.77382.sample.file.ods

[Mariosv (mariosv)]

Reproducible with:
Win7x64Ultimate
Version: 4.2.0.4 Build ID: 05dceb5d363845f2cf968344d7adab8dcfb2ba71
Version: 4.2.1.1 Build ID: d7dbbd7842e6a58b0f521599204e827654e1fb8b
Version: 4.2.2.1 Build ID: 3be8cda0bddd8e430d8cda1ebfd581265cca5a0f
Version: 4.2.3.3 Build ID: 6c3586f855673fa6a1576797f575b31ac6fa0ba3

With the attached sample file in the next comment.
About 11 seconds to replace AN for nothing on 16384 cells
About 36 seconds to replace AN for nothing on 32768 cells
About 168 seconds to replace AN for nothing on 65536 cells

The number of replacements increases the time to replace in a exponential way.

With Version: 4.1.6.1 Build ID: a59ce81388f477fc89db57f0c27f222f31884eb
about 15 seconds to replace 65536 cells

[Mariosv (mariosv)]

Created attachment 97324
Sample file with data for verification.

[Libreoffice-0 (libreoffice-0)]

So, it's the "replace with empty" operation that's slow. When you replace all with non-empty value, it's not slow.

[Gquigs+bugs (gquigs+bugs)]

Created attachment 102039
bibisectlog

Bibisected to source-hash-022c54742e7997bf46a608f1ab0b500f2537f7f5, commit 0461728e0d5cd5e24954864881357a5f370c4714, WaE: private field 'mrCells' is not used

[Gquigs+bugs (gquigs+bugs)]

My tests indicate the slowdown is in the bool ScTable::Search function (or in how it's called) in sc/source/core/data/table6.cxx. When comparing the speed of the function with FindAll vs ReplaceAll the performance for Replace All starts at about 141 times the Find all. By the end of the search they are about at the same level though.

[Gquigs+bugs (gquigs+bugs)]

This call in (table6.cxx)
aCol[nCol].SetString(nRow, nTab, aString, pDocument->GetAddressConvention()); is very slow, and appears to be further to the cause...

Also in a ReplaceAll, for an reason I don't understand SetString is also called somewhere here:
ScAddress aAdr( nCol, nRow, nTab );
aCell.commit(*pUndoDoc, aAdr);

[Gquigs+bugs (gquigs+bugs)]

Alright so I was wrong on the last count it's actually.
-> SearchCell -> The last else statement -> aCol[nCol].SetString(nRow, nTab, aString, pDocument->GetAddressConvention());
-> aNewCell.release(*this, nRow); (In SetString, column3.cxx)
-> ScCellValue::release (cellvalue.cxx), it falls to default in the switch
-> rColumn.Delete(nRow); -> ScColumn::Delete( SCROW nRow ) (column3.css)
Final in LibO - maCells.set_empty(nRow, nRow); Which is actually defined in mdds

[1] Link to before the commits that changes this around for reference: http://cgit.freedesktop.org/libreoffice/core/tree/sc/source/core/data/column3.cxx?id=b139f6fedfcf3cbed0eadeb007e2155b576413d2

[Gquigs+bugs (gquigs+bugs)]

I believe the issue was introduced specifically in this commit (by Kohei Yoshida):
http://cgit.freedesktop.org/libreoffice/core/commit/sc/source/core/data/column3.cxx?id=c008dc483f8c6840803983e7e351cec6fdd32070

Specifically in the need to change how "Delete" works.

[Libreoffice-0 (libreoffice-0)]

*** Bug 82013 has been marked as a duplicate of this bug. ***

[Libreoffice-0 (libreoffice-0)]

(In reply to comment #12)
> I believe the issue was introduced specifically in this commit (by Kohei
> Yoshida):

Of course I broke it! That's not news. How to fix it is the question.

[JBF (jbf-faure)]

I think it is useless to fill a window with all cells changed when they are thousands, the user will not read them. I think it is enough to say him how many cells have been replaced when the amount exceeds something like 100 or 1000.

Best regards. JBF

[Ubuntu Foundations Team Bug Bot (crichton)]

The attachment "optimize_performance_after_replaceall.debdiff" seems to be a debdiff. The ubuntu-sponsors team has been subscribed to the bug report so that they can review and hopefully sponsor the debdiff. If the attachment isn't a patch, please remove the "patch" flag from the attachment, remove the "patch" tag, and if you are member of the ~ubuntu-sponsors, unsubscribe the team.

[This is an automated message performed by a Launchpad user owned by ~brian-murray, for any issue please contact him.]

[Björn Michaelsen (bjoern-michaelsen)]

Applied to Ubuntu trusty packaging branch:

 http://anonscm.debian.org/cgit/pkg-openoffice/libreoffice.git/commit/?h=ubuntu-trusty-4.2&id=0473b22f2213ef31e9a0ad28b5969ec4962ee8f2

[Björn Michaelsen (bjoern-michaelsen)]

@xtrusia: Did you ever even test that debdiff vs. 4.2? I doesnt even seem to compile:
- For one there seems to be an obvious typo in using both rMark.getMarkedRanges() and rMark.GetMarkedRanges() in the same patch
- Curiously this typo isnt even there in the upstream commit 91502a72c12c559442e8bf77c27a516b49c2a68d from which it was derived
- then the patch uses sc::ColRowSpan which does not seem to be available on LibreOffice 4.2.x yet

Here is an example build log failure:
https://launchpadlibrarian.net/187606247/buildlog_ubuntu-trusty-amd64.libreoffice_1%3A4.2.7~rc2-0ubuntu1_FAILEDTOBUILD.txt.gz

Im not too happy to have wasted some time to rebase the patch from 4.2.6 on 4.2.7, now realizing this likely never build on 4.2.6 in the first place.

In the future, please in general consider using the upstream backport branches as per: https://wiki.documentfoundation.org/Development/Branches#libreoffice-X-Y on https://gerrit.libreoffice.org. For one, this gives you the support of upstream CI and buildbots, but more importantly also the support of upstream reviewers. Sadly, its now too late for this to succeed with that as 4.2.7.2 has been tagged and is at the end of the upstream support for this series.

For now, I will leave the patch in packaging (so that the rebase work isnt lost), but disable it. If you want this patch to still make the next trusty SRU, the patch needs to be in a good form against 4.2.7 and be thoroughly tested before the end of October 2014. That means you need to do a build and at least run the autopkgtests against it and at least do some basic manual testing in the patched functionality. Thanks.

[Seyeong Kim (seyeongkim)]

sorry, something wrong in my test env,

ill check this again

[Seyeong Kim (seyeongkim)]

Hello

How can i get 4.2.7 version?

rmadison libreoffice shows only 4.2.6.3-0ubuntu1 now

Thanks

[Björn Michaelsen (bjoern-michaelsen)]

Currently testbuilding at:

 https://launchpad.net/~bjoern-michaelsen/+archive/ubuntu/libreoffice-staging
 https://launchpad.net/~bjoern-michaelsen/+archive/ubuntu/libreoffice-staging/+sourcepub/4482489/+listing-archive-extra

Note that this one isnt tested in any reasonable way yet, so use at own risk. Im planing to move that build over to https://launchpad.net/~libreoffice/+archive/ubuntu/ppa early next week.

[Björn Michaelsen (bjoern-michaelsen)]

Has there been any testing of this? I see the commits have not been backported to 4.3 and have not yet been released in any upstream release. Are we sure these patches are not causing any regressions by having all that is needed and nothing more?

[Björn Michaelsen (bjoern-michaelsen)]

Pushed for cherry-pick and review for (still upstream alive) libreoffice-4-3 branch (for LibreOffice 4.3.5, ETA Week 51 , Dec 15, 2014 - Dec 21, 2014), so we will have this on Utopic and later:
 https://gerrit.libreoffice.org/#/c/13041/

[Björn Michaelsen (bjoern-michaelsen)]

This should be fixed on master with:
http://cgit.freedesktop.org/libreoffice/core/commit/?id=1cf19ea84794ca065749667b480dfed2d27d47b7
http://cgit.freedesktop.org/libreoffice/core/commit/?id=1e721077b43de84edab2a3ed2f316ddcbec6e3ec
http://cgit.freedesktop.org/libreoffice/core/commit/?id=91502a72c12c559442e8bf77c27a516b49c2a68d

[Björn Michaelsen (bjoern-michaelsen)]

Patched versions for this have been uploaded to the ppas.

For LibreOffice 4.2 as 1:4.2.7-0ubuntu2~trusty4 at the LibreOffice-4-2 ppa:
 https://launchpad.net/~libreoffice/+archive/ubuntu/libreoffice-4-2

For LibreOffice 4.3 as 1:4.3.4-0ubuntu1~utopic1 at the LibreOffice-4-3 and the generic LibreOffice ppa:
 https://launchpad.net/~libreoffice/+archive/ubuntu/libreoffice-4-3
 https://launchpad.net/~libreoffice/+archive/ubuntu/ppa

[Björn Michaelsen (bjoern-michaelsen)]

resolving as per comment 16.

[Brian Murray (brian-murray)]

Hello Bryan, or anyone else affected,

Accepted libreoffice into trusty-proposed. The package will build now and be available at https://launchpad.net/ubuntu/+source/libreoffice/1:4.2.7-0ubuntu2 in a few hours, and then in the -proposed repository.

Please help us by testing this new package. See https://wiki.ubuntu.com/Testing/EnableProposed for documentation how to enable and use -proposed. Your feedback will aid us getting this update out to other Ubuntu users.

If this package fixes the bug for you, please add a comment to this bug, mentioning the version of the package you tested, and change the tag from verification-needed to verification-done. If it does not fix the bug for you, please add a comment stating that, and change the tag to verification-failed. In either case, details of your testing will help us make a better decision.

Further information regarding the verification process can be found at https://wiki.ubuntu.com/QATeam/PerformingSRUVerification . Thank you in advance!

[Seyeong Kim (seyeongkim)]

It works for me

libreoffice-calc 1:4.2.7-0ubuntu2 amd64

[Launchpad Janitor (janitor)]

This bug was fixed in the package libreoffice - 1:4.2.7-0ubuntu2

---------------
libreoffice (1:4.2.7-0ubuntu2) trusty; urgency=medium

  * backport search & replace w/ empty performance fix (LP: #1342175)
  * add additional backported upstream fixes for fdo#82936, fdo#85282,
    fdo#85215, fdo#83765, fdo#79441, fdo#86708 (LP: #1389858)
 -- Bjoern Michaelsen <email address hidden> Wed, 26 Nov 2014 19:24:35 +0100

[Brian Murray (brian-murray)]

The verification of the Stable Release Update for libreoffice has completed successfully and the package has now been released to -updates. Subsequently, the Ubuntu Stable Release Updates Team is being unsubscribed and will not receive messages about this bug report. In the event that you encounter a regression using the package from -updates please report a new bug using ubuntu-bug and tag the bug report regression-update so we can easily find any regressions.

[KS NAIR (nair-ks)]

Hi

Sorry, the attachment was sent without this post about the problem that I encountered.

I found this bug page when trying to deal with a similar find and replace problem on a file containing ~2000 rows and 60 rows.

The file is enclosed in comment #36 above

If I try and replace "SA" with "A" (quotes not required) and look in values only, it takes anywhere between 4-7 minutes to complete. Even after the replace is complete, it takes a very long to close the Find and Replace box

Version Version: 5.1.5.2
Build ID: 1:5.1.5~rc2-0ubuntu1~trusty1

May I request help to confirm that the problem still persists in this version and provide a fix if confirmed?

Thanks

[Seyeong Kim (seyeongkim)]

@nair-ks

just checking.

your libreoffice build is in private ppa?

I recommand you to test default version for each supportable releases.

Trusty: 4.2.8-0ubuntu4
Xenial: 5.1.2-0ubuntu1
Yakkety: 5.2.2-0ubuntu1

Thanks a lot

[KS NAIR (nair-ks)]

My sources.lst.d contains this file and this entry:
File:libreoffice-libreoffice-5-1-trusty.list
Contents: deb http://ppa.launchpad.net/libreoffice/libreoffice-5-1/ubuntu trusty main

I oversee an environment of around 50 PCs that are all running the same version of Linux Mint (17.1) and Libre Office. In order to keep all the systems up to date, we have a local mirror of a part of the Linux Mint / Ubuntu repositories and this includes LibreOffice locally mirrored, using the same ppa mentioned above.

We would like to be on at least 5.1.x for all our client systems and would like to remain on this version or move to 5.2.x if that is stable.

Could you please tell me where and how to download / install the bug-fixed version (deb version, please) that you mentioned in your comment, so that I can test the same and also deploy it to all the client machines via our local repository? And also which ppa we can use to keep all systems in sync?

Thanks very much for your help.

[KS NAIR (nair-ks)]

Hi

Could someone help in pointing me in the right direction to upgrade our current version to the one that fixes the problem?

I have tried this on Linux Mint 18.1 Beta which installs Libreoffice Calc 5.1.4.2, and the problem still exists.

The real issue seems to be that the Find/Replace function is trying to populate thousands of records into a small window for display to the user and the system takes a very long time (> 15 min) to display this. In any case, the window is of not much use especially if more than 20-30 records are being replaced, as the user cannot do much with the information once the replacement has taken place.

Alternatively, is there a patch that can be applied for only Calc which resolves this issue?

Thanks for any help that I can get.

[KS NAIR (nair-ks)]

<bump>.. Please do respond. Thanks

[Seyeong Kim (seyeongkim)]

Hello nair-ks.

I've been busy and had PTO.

and I can't focus this issue deeply because I'm busy.

I think you need to help this issue.

Please test various version and upstream one.

and report to upstream bug https://bugs.freedesktop.org/ as well.

there could be someone who can help you.

I'll try to test upstream but.. I can't guarantee this.

Thanks.

[KS NAIR (nair-ks)]

Dear Seyeong Kim

Thanks for the quick reply and sorry to trouble your busy schedule.

I just need to know how to download the exact version that you mentioned as
I was unable to locate it. Testing I will do, no problem, but could you
please point me in the right direction for the version to test?

Thanks once again.

Regards
KS Nair

On 19 December 2016 at 13:28, Seyeong Kim <email address hidden> wrote:

> Hello nair-ks.
>
> I've been busy and had PTO.
>
> and I can't focus this issue deeply because I'm busy.
>
> I think you need to help this issue.
>
> Please test various version and upstream one.
>
> and report to upstream bug https://bugs.freedesktop.org/ as well.
>
> there could be someone who can help you.
>
> I'll try to test upstream but.. I can't guarantee this.
>
> Thanks.
>
> --
> You received this bug notification because you are subscribed to the bug
> report.
> https://bugs.launchpad.net/bugs/1342175
>
> Title:
> [upstream] Poor performance with find & replace with empty value on
> large data set
>
> Status in LibreOffice:
> Fix Released
> Status in libreoffice package in Ubuntu:
> Fix Released
> Status in libreoffice source package in Trusty:
> Fix Released
>
> Bug description:
> [SRU justification]
>
> [Impact]
>
> Hang or Very slow performance after replaceall or searchall massive
> data
>
> Regression in Find and Replace with LO Calc 4.2 (last worked in 4.1).
> It now takes a long time to "Find and Replace" if the to be replaced
> is to nothing.
>
> See comment #5/#6 of upstream for reproducer.
> See commend #8 for bibisect.
>
> [Test Case]
>
> fill A column to 0
> select A column
>
> Replace All 0 to " " ( null space )
>
> [Regression Potential]
> restricted, relevant patches are currently:
> - upstream master
> - all upstream 4.4.0 alpha/beta builds
> - upstream 4-4 branch
> - backported (by me) to upstream 4-3 branch
> => thus also included in upstream 4.3.5~rc1 released on November, 27th
> => thus will also be released by upstream 4.3.5 on ~December, 18th
> - backported to 4.3.4/utopic package (downstream, Ubuntu only)
> - backported to 4.2.7/trusty package (downstream, Ubuntu only)
> - included in all current 4.3.x and 4.2.x backports in the LibreOffice
> PPAs
> - included in all the 4.4~beta1 builds on the LibreOffice prereleases PPA
>
>
> [Other Info]
> upstream patch
>
> http://cgit.freedesktop.org/libreoffice/core/commit/?id=
> 1cf19ea84794ca065749667b480dfed2d27d47b7
> http://cgit.freedesktop.org/libreoffice/core/commit/?id=
> 1e721077b43de84edab2a3ed2f316ddcbec6e3ec
> http://cgit.freedesktop.org/libreoffice/core/commit/?id=
> 91502a72c12c559442e8bf77c27a516b49c2a68d
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/df-libreoffice/+bug/1342175/+subscriptions
>

[Seyeong Kim (seyeongkim)]

erm..

you said 5.1.5.2 is not working.

I would suggest to test upstream latest one first. ( need to be built )

you can choose 5.x higher version then you tested(5.1.5.2)
you can choose 4.x version if it's working. ( official libreoffice with normal ubuntu trust, xenial.. etc )

if all version is not working. it needs to be fixed in upstream first. then report to libreoffice.

if you can find some version among them. state here then it would be starting point for debugging

e.g
install ubuntu trusty, xenial on your vm and test
install sourcecode from libreoffice.org and build and test

if you don't have enough time or don't know exactly how to build it.

you can ask via irc channel.

please refer libreoffice.org

[Seyeong Kim (seyeongkim)]

Hey KS NAIR

I made some rough ppa pkg for this.

sudo add-apt-repository ppa:libreoffice/libreoffice-5-1
sudo add-apt-repository ppa:xtrusia/libreoffice-5.1.6-rc2-t
sudo apt update

sudo apt install libreoffice

test your file with calc

is there any performance changes?

I'm trying to contribute this but will take a while.

Thanks

[KS NAIR (nair-ks)]

Hi Seyeong Kim

Thanks for the message and updates.

I tested the above and there does NOT appear to be any change in performance:

a. It takes about 2 minutes for the "Search Results" window to appear (using the file provided in comment # 36 above)
b. After clicking on the "Close" button, it takes about 1 minute before the focus gets back to the Main Search and Replace window
c. It takes another 1 minute to "Close" the Search and Replace window.

As an end user, if appropriate, I would like to make a request / suggestion about the Search results window:

1. Can the "Search Results" window be made as optional with a check box where the default set to NOT display results, thus reducing overhead?
2. The cells are already replaced and the only functionality in the Results window is an ability to go to the replaced cell. Already the changed cells are highlighted and the user can see these, thus making some of the functionality redundant.

I am not sure if you can take this forward?

Thankful for any help that can be given for fixing the problem.

Regards
KS Nair

[Seyeong Kim (seyeongkim)]

hey nair-ks

sorry, changing design is not my job..

I also need to suggest this(if it fixes performance) to upstream code.

im just trying to fix performance issue.

and that's weird.. in my testing env, Search Result Dialog show up in 10 seconds

Could you please check your version first if it's upgraded one?

Thanks.

ps my cpu is xeon 3.4GHz, what is yours?