Bug Hunting Session
Bug 72413 - EDITING: Find&Replace too much slow for large changes in comparison with previous versions (more than fourty times)
Summary: EDITING: Find&Replace too much slow for large changes in comparison with prev...
Status: RESOLVED FIXED
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Calc (show other bugs)
Version:
(earliest affected)
4.2.0.0.beta2
Hardware: All All
: medium major
Assignee: Matúš Kukan
URL:
Whiteboard: target:4.3.0 target:4.2.0.1
Keywords: perf
: 76422 (view as bug list)
Depends on:
Blocks:
 
Reported: 2013-12-06 20:00 UTC by m.a.riosv
Modified: 2019-02-14 14:00 UTC (History)
5 users (show)

See Also:
Crash report or crash signature:


Attachments
Sample file to verify the issue. (27.11 KB, application/vnd.oasis.opendocument.spreadsheet)
2013-12-06 20:00 UTC, m.a.riosv
Details
Problems with find and replace of large data sets in calc (42.12 KB, application/vnd.oasis.opendocument.spreadsheet)
2014-01-12 11:21 UTC, andis.lazdins
Details
crashlog (542.73 KB, text/plain)
2014-01-12 14:57 UTC, retired
Details
Sample file with 32768 rows with data in column A (47.26 KB, application/vnd.oasis.opendocument.spreadsheet)
2014-02-01 16:29 UTC, m.a.riosv
Details

Note You need to log in before you can comment on or make changes to this bug.
Description m.a.riosv 2013-12-06 20:00:54 UTC
Created attachment 90375 [details]
Sample file to verify the issue.

Win7x64Ultimate
Version: 4.2.0.0.beta2+ Build ID: 69f401c5781f846162c803df92a50b09324ce02f
         TinderBox: Win-x86@42, Branch:libreoffice-4-2, Time: 2013-12-06_02:24:10

compared with:
Version: 4.1.4.1 Build ID: 414ce1317b94ce49e6044b84baf237918e9a659

Steps:
Menu/Edit/Find & Replace
Replace all letter 'c' with e.g. 'z'
4 seconds with 4.1.4.1
3 minutes 4 seconds with 4.2.0.0

Seems as if LibreOffice is frozen.

I don't know but maybe is in relation with the new window showing the list of cells with replacements. 
In this case I think to maintain it, really useful with a few changes, we need:
- An option for disable it.
- A limit of replacements to show.
Comment 1 Jorendc 2013-12-06 21:12:10 UTC
I can confirm this behavior, tested using Mac OSX 10.9 with LibreOffice 4.1.4.1 rc and 4.1.0b1.

Not sure this is only due the new dialog. Maybe also related to the new cell-handling?

Kind regards,
Joren
Comment 2 Jorendc 2013-12-06 21:17:26 UTC
(In reply to comment #1)
> Not sure this is only due the new dialog. Maybe also related to the new
> cell-handling?

I mean: delete all cells, except for about 10 "abcde" cells. Now try to do the steps again -> also long freeze. I don't think the freeze is due the population of that new dialog after the find and replace.
Comment 3 Cor Nouws 2013-12-06 21:24:17 UTC
(In reply to comment #1)
> Not sure this is only due the new dialog. Maybe also related to the new
> cell-handling?

Yes, there is something not yet solved in ceel-handling. It is sluggish so to say
Comment 4 Robinson Tryon (qubit) 2013-12-06 22:00:50 UTC
Remember to tag performance-related issues w/'perf' in the whiteboard :-)

Whiteboard: perf
Comment 5 Matúš Kukan 2013-12-07 00:41:37 UTC
I think it shouldn't show the new dialog when replacing. only when using 'find all'. I am confused why it's this way, probably it was since beginning and I just don't remember.

And yes, I think it would be best to not populate the dialog with more than 1000 items let's say.
Comment 6 m.a.riosv 2013-12-07 01:13:37 UTC
Hi Matus, thanks for take it.
I think is an improvement also when replacing. If it were possible an option with the number to show, 0 for nothing. Sometimes could be helpful with large find/replace, it is easy navigate the list.
And even better it were possible to use the list as navigator, double clicking a item for go to the cell.
Comment 7 Commit Notification 2013-12-09 08:16:59 UTC
Matuš Kukan committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=dc22a2aa1b2858394ad70806f34d1327936af7a0

fdo#72413: Fix O(n^2) in inserting SearchResults' items.



The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 8 Matúš Kukan 2013-12-09 08:23:05 UTC
It's now fast and also works the same way.
As I was pointed to, I had to disable slow algorithm to use faster ;-)

> And even better it were possible to use the list as navigator, double
> clicking a item for go to the cell.

It is possible, with just selecting the item.
But if the selected cell is outside of visible area, you don't notice:
http://cgit.freedesktop.org/libreoffice/core/commit/?id=d45bc3429c859392aa9fd7932908e50b0716a39c
should fix that.
Comment 9 Commit Notification 2013-12-09 08:25:33 UTC
Matuš Kukan committed a patch related to this issue.
It has been pushed to "libreoffice-4-2":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=1a8afa24ffc1ba1e606617f263e1f8833ad4d0a9&h=libreoffice-4-2

fdo#72413: Fix O(n^2) in inserting SearchResults' items.


It will be available in LibreOffice 4.2.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 10 m.a.riosv 2013-12-09 09:24:05 UTC
Thanks Matus, I'll try in a couple of days.
Comment 11 m.a.riosv 2013-12-12 00:48:27 UTC
Works fine in:
Win7x64Ultimate
Version: 4.2.0.0.beta2+ Build ID: 61a91e69eb627a86a7358e3d65a0892ac8dc4d9d
TinderBox: Win-x86@42, Branch:libreoffice-4-2, Time: 2013-12-11_00:41:52

a bit slower navigation window in:
Version: 4.3.0.0.alpha0+ Build ID: e8fff12af2c0bc3172c3db830b5f6a59869e5be0
TinderBox: Win-x86@39, Branch:master, Time: 2013-12-11_01:56:02
but seems in general master is a bit slower.

Hi Matus, I think can be changed to RESOLVED FIXED.
Comment 12 Kohei Yoshida 2013-12-13 22:48:49 UTC
I'll mark this fixed per Comment 11.
Comment 13 andis.lazdins 2014-01-12 11:21:43 UTC
Created attachment 91894 [details]
Problems with find and replace of large data sets in calc
Comment 14 andis.lazdins 2014-01-12 11:26:40 UTC
The problem is still in 4.2.0.2. I attached sample file to the bug report. Try to replace "0" with something else, like empty space. It takes forever with 100 % of CPU utilization. In Openoffice 4.0 it takes about 20 seconds.

The problem is present also in Libreoffice 4.1.4.2. Actually the only version not having this problem or at least not to such extend is 4.0.6.

We are using replace function quite heavily and this regression actually makes a lot of trouble. Luckily it is possible to replace values in Openoffice without loosing structure of calculations.
Comment 15 Cor Nouws 2014-01-12 11:42:36 UTC
(In reply to comment #14)
> The problem is still in 4.2.0.2. I attached sample file to the bug report.
> Try to replace "0" with something else, like empty space. It takes forever
> with 100 % of CPU utilization. 

for me it takes about 2 minutes in 4.2.0.2 on Ubuntu. still quite long.
Matúš, Kohei ?
Comment 16 andis.lazdins 2014-01-12 13:54:29 UTC
(In reply to comment #15)
> (In reply to comment #14)
> > The problem is still in 4.2.0.2. I attached sample file to the bug report.
> > Try to replace "0" with something else, like empty space. It takes forever
> > with 100 % of CPU utilization. 
> 
> for me it takes about 2 minutes in 4.2.0.2 on Ubuntu. still quite long.
> Matúš, Kohei ?

To be more accurate, I stopped program after about 20 minutes.
Ubuntu linux 32 bit, 3 GB RAM, 2 x Pentium Dual-Core CPU T4500 2.3 GHz
Comment 17 retired 2014-01-12 14:57:34 UTC
Created attachment 91901 [details]
crashlog
Comment 18 retired 2014-01-12 14:57:44 UTC
Confirmed:4.3.0.0a0+:OSX Confirmed:4.2.0.1:OSX
Version: 4.3.0.0.alpha0+
Build ID: cbe7ab3d6188e725414cbb15ca534f96fe51d8c7
TinderBox: MacOSX-x86@49-TDF, Branch:master, Time: 2014-01-12_00:08:19

Do repro steps from Bug Description > LO stalls force quitting after 2mins.

Re-Open since it is not fixed.

Andis, thanks a lot for the test file.

Crashlog attached.
Comment 19 andis.lazdins 2014-01-24 06:11:41 UTC
Hello!

I wanted to write that the problem is partially solved in 4.2.0.3, because I was lucky once to complete find/replace from the second attachment, however further attempts ended with crash of the program. So it seems to be still a problem.
Comment 20 m.a.riosv 2014-02-01 16:29:30 UTC
Created attachment 93175 [details]
Sample file with 32768 rows with data in column A

With the attached file with 32768 rows with data in column A, replacing one letter, deleting half of data doesn't crash with the first replace, but sometimes with the second.

I can reproduce the crash in about 3m 20~40s and slowness is there again with:
Winx64Ultimate-I3-2,13
Version: 4.2.0.4 Build ID: 05dceb5d363845f2cf968344d7adab8dcfb2ba71
Version: 4.2.1.0.0+ Build ID: 92346fb7714ca7c6a467771d8a8b01305c1b17d1
     TinderBox: Win-x86@42, Branch:libreoffice-4-2, Time: 2014-01-31_00:15:33

Works fine with, no crash and quick:
Win7x64Ultimate
Version: 4.3.0.0.alpha0+ Build ID: bab7eebba127d603a9f8011fed290627e2a64423
TinderBox: Win-x86@39, Branch:master, Time: 2014-01-31_00:56:43

I think this must be in MAB
Comment 21 andis.lazdins 2014-02-02 11:56:20 UTC
Hello!

I'm not sure, if anything is done for this particular issue, but on 4.1.5.2 find replace in second sample file takes now less than 2 minutes. Repeated twice, no crashes any more. I would say it is solved.
However, work with spreadsheets being larger than 1 MB and containing lot of array formulas is till very painful. I'm sure there is still lot of work to do in Calc.

Thank you very much and good luck!
Comment 22 m.a.riosv 2014-03-18 21:45:47 UTC
Seems now works fine in:
Win7x64
Version: 4.2.1.1 Build ID: d7dbbd7842e6a58b0f521599204e827654e1fb8b
Version: 4.2.2.1 Build ID: 3be8cda0bddd8e430d8cda1ebfd581265cca5a0f
Version: 4.2.3.1 Build ID: 3d4fc3d9dbf8f4c0aeb61498a81f91c5b7922f13
Version: 4.2.4.0.0+ Build ID: e1823627f35e4419880769fdd05acddbd0a9c25c
   TinderBox: Win-x86@42, Branch:libreoffice-4-2, Time: 2014-03-18_14:25:19

but bit slower in:
Version: 4.3.0.0.alpha0+ Build ID: 12ae7672f285da1d4c730315e8db23b3396b71cc
   TinderBox: Win-x86@39, Branch:master, Time: 2014-03-14_00:18:00

I think it can set up as Fixed.
Comment 23 m.a.riosv 2014-03-21 22:56:41 UTC
*** Bug 76422 has been marked as a duplicate of this bug. ***
Comment 24 Robinson Tryon (qubit) 2015-12-15 11:39:08 UTC Comment hidden (obsolete)