Bug 84635 - TABLE: Slow layout of large tables (quadratic time)
Summary: TABLE: Slow layout of large tables (quadratic time)
Status: VERIFIED FIXED
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Writer (show other bugs)
Version:
(earliest affected)
4.2.6.3 release
Hardware: All All
: medium major
Assignee: Not Assigned
URL:
Whiteboard: target:5.3.0 target:6.3.0
Keywords: haveBacktrace, perf
Depends on:
Blocks: Writer-Tables CPU-AT-100%
  Show dependency treegraph
 
Reported: 2014-10-03 15:18 UTC by Peter Grimtell
Modified: 2019-08-20 06:06 UTC (History)
8 users (show)

See Also:
Crash report or crash signature:


Attachments
Time to load and lay out document as function of number of rows (50.39 KB, application/vnd.oasis.opendocument.spreadsheet)
2014-10-03 15:18 UTC, Peter Grimtell
Details
6 rows (1 page), 1 second to load (8.04 KB, application/vnd.oasis.opendocument.text)
2014-10-03 15:21 UTC, Peter Grimtell
Details
1034 rows (13 pages), 24 seconds to load (29.81 KB, application/vnd.oasis.opendocument.text)
2014-10-03 15:23 UTC, Peter Grimtell
Details
2178 rows (26 pages), 62 seconds to load (90.08 KB, application/vnd.oasis.opendocument.text)
2014-10-03 15:23 UTC, Peter Grimtell
Details
5871 rows (69 pages), 362 seconds to load (203.42 KB, application/vnd.oasis.opendocument.text)
2014-10-03 15:24 UTC, Peter Grimtell
Details
7183 rows (84 pages), 663 seconds to load (237.30 KB, application/vnd.oasis.opendocument.text)
2014-10-03 15:24 UTC, Peter Grimtell
Details
9897 rows (116 pages), 1251 seconds to load (333.67 KB, application/vnd.oasis.opendocument.text)
2014-10-03 15:25 UTC, Peter Grimtell
Details
10944 rows (128 pages), 1464 seconds to load (356.79 KB, application/vnd.oasis.opendocument.text)
2014-10-03 15:25 UTC, Peter Grimtell
Details
Perf flame graph for ~10000 rows (289.72 KB, application/x-7z-compressed)
2014-10-03 15:32 UTC, Peter Grimtell
Details
valgrind output for 69 page document, LO 5.1.1.2 in Ubuntu (29.19 KB, text/plain)
2016-03-15 14:38 UTC, Peter Grimtell
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Peter Grimtell 2014-10-03 15:18:56 UTC
Created attachment 107263 [details]
Time to load and lay out document as function of number of rows

When loading a writer document with a large table (spanning tens or hundreds of pages) it takes a long time to do the layout. The time seems to increase quadratically with the number of table rows.

The tested documents (created by my own code, and passing validation on http://odf-validator.rhcloud.com/) use a small font (4 pt), so the amount of text that fits in each page is large, but the seeming O(n^2) trend is worrying.
Comment 1 Peter Grimtell 2014-10-03 15:21:51 UTC
Created attachment 107264 [details]
6 rows (1 page), 1 second to load
Comment 2 Peter Grimtell 2014-10-03 15:23:08 UTC
Created attachment 107265 [details]
1034 rows (13 pages), 24 seconds to load
Comment 3 Peter Grimtell 2014-10-03 15:23:45 UTC
Created attachment 107266 [details]
2178 rows (26 pages), 62 seconds to load
Comment 4 Peter Grimtell 2014-10-03 15:24:14 UTC
Created attachment 107267 [details]
5871 rows (69 pages), 362 seconds to load
Comment 5 Peter Grimtell 2014-10-03 15:24:45 UTC
Created attachment 107268 [details]
7183 rows (84 pages), 663 seconds to load
Comment 6 Peter Grimtell 2014-10-03 15:25:27 UTC
Created attachment 107269 [details]
9897 rows (116 pages), 1251 seconds to load
Comment 7 Peter Grimtell 2014-10-03 15:25:53 UTC
Created attachment 107270 [details]
10944 rows (128 pages), 1464 seconds to load
Comment 8 Peter Grimtell 2014-10-03 15:32:43 UTC
Created attachment 107271 [details]
Perf flame graph for ~10000 rows
Comment 9 Peter Grimtell 2014-10-03 15:38:53 UTC
One thing I've noted is that LO first overestimates the number of pages (e.g. showing page count as 190 instead of 116) for a long time until the layout has been completed.

My computer specs: i7-3820@3.6GHz, 16 GB RAM, SSD.
Comment 10 Buovjaga 2014-11-14 18:44:18 UTC
I tested three of them. 4.4 alpha seems to be a lot better.

1034 rows (13 pages): 10 secs
5871 rows (69 pages): 83 secs
10944 rows (128 pages): 125 secs

Win 7 64-bit Version: 4.4.0.0.alpha2+
Build ID: b021b5983c62e266b82d9f0c5c6d8d8900553827
TinderBox: Win-x86@39, Branch:master, Time: 2014-11-12_01:10:08

i7-2640M@2.80Ghz, 8 GB RAM (with an Ubuntu VM running with 4 GB allocated to it of the 8 GB), no SSD.
Comment 11 A (Andy) 2014-11-14 20:57:38 UTC
Reproducible with LO 4.3.3.2, Win 8.1 (i3, 1.8GHz, 4GB RAM)

When trying to load the document with 1,034 rows it took for me more than 20 seconds to load it and the status bar was all the time flickering.

@Beluga: Thanks for also testing it on LO 4.4 and it is great to hear that there it is already faster.  I don't know if there can maybe also be made further improvements already for LO 4.3?
Comment 12 Peter Grimtell 2016-03-14 13:25:12 UTC
This problem remains in LO 5.1.1.3 as well as in 4.4.3.2, but it takes even longer in 5.1.1.3. It now takes ~14 minutes for the 69 page document and ~47 minutes for the 128 page document, around twice as long as my earlier numbers on the same hardware (i7-3820 @ 3.6GHz, 16 GB RAM, SSD.)

N.B. It does not suffice to wait for the status bar progress indication to appear ready. The pagination must be completed and show the same number of pages as indicated in the file names. Otherwise the next operation (e.g. print preview or PDF export) will be delayed until pagination is done. If the file is opened with a synchronous UNO call then that call will not return before then.
Comment 13 Buovjaga 2016-03-14 13:34:27 UTC
Peter: is it possible for you to do a valgrind run under Linux https://wiki.documentfoundation.org/QA/BugReport/Debug_Information
Comment 14 Peter Grimtell 2016-03-15 14:38:33 UTC
Created attachment 123603 [details]
valgrind output for 69 page document, LO 5.1.1.2 in Ubuntu

valgrind output for 69 page document, LO 5.1.1.2 in Ubuntu
Comment 15 Aron Budea 2016-05-04 14:53:19 UTC
I looked at the 13-page document with current master build, and in:
void PaMCorrAbs( const SwPaM& rRange, const SwPosition& rNewPos )

there's this loop:
for(const auto& pWeakUnoCursor : pDoc->mvUnoCursorTable)
http://opengrok.libreoffice.org/xref/core/sw/source/core/doc/doccorr.cxx#124

pDoc->mvUnoCursorTable is an evergrowing table with mostly expired weak references. If I put a breakpoint at the start of the loop, after a few irregular increases, each time the debugger stops the size of mvUnoCursorTable is shown to be increased by 5: ..., 22, 27, 32, 37, ..., 14012, ..., 53357, ..., 102312, ...

Each time only 4-5 references are valid in that vector. Function cleanupUnoCursorTable(), which is supposed to remove expired references from the vector is not called (though in this case it would be better to leave some reserved space for further ones, the aforementioned function also shrinks the vector).

Doing this before the for loop solves this particular issue, but it's likely not the best place:
pDoc->mvUnoCursorTable.erase(
        std::remove_if(pDoc->mvUnoCursorTable.begin(), pDoc->mvUnoCursorTable.end(), [](const std::weak_ptr<SwUnoCursor>& pWeakPtr) { return pWeakPtr.expired(); }),
        pDoc->mvUnoCursorTable.end());
		
I assume this is only one of the multiple causes of the performance issue.
I also wonder why the status indicator is so... lively, and keeps filling up again and again.
Comment 16 Commit Notification 2016-07-13 13:09:50 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

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

tdf#84635 - Slow layout of large tables

It will be available in 5.3.0.

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 17 Peter Grimtell 2016-07-20 07:33:11 UTC
I still get about the same times, e.g. ~ 6m13s for the 69 page document in the latest daily build. Did I download the wrong build?

Version: 5.3.0.0.alpha0+
Build ID: 86639b757b470ac7b1326afe13e19a1245499c51
CPU Threads: 8; OS Version: Windows 6.1; UI Render: GL; 
TinderBox: Win-x86@39, Branch:master, Time: 2016-07-20_06:46:14
Locale: sv-SE (sv_SE); Calc: CL

Thank you for looking into this issue!
Comment 18 Buovjaga 2016-07-20 09:51:50 UTC
Yep, confirmed the perf is still bad on Win and Linux. Win build was from yesterday.

Arch Linux 64-bit, KDE Plasma 5
Version: 5.3.0.0.alpha0+
Build ID: ab1b351840160655a9f0caedbb35e9fdf203c5a0
CPU Threads: 8; OS Version: Linux 4.6; UI Render: default; 
Locale: fi-FI (fi_FI.UTF-8); Calc: group
Built on July 16th 2016
Comment 19 Buovjaga 2016-07-20 09:56:38 UTC
(In reply to Buovjaga from comment #18)
> Yep, confirmed the perf is still bad on Win and Linux. Win build was from
> yesterday.

Ehh.. I forgot that maybe this is relative: I could open the 128 page document on my very fast Linux machine in about 2min30sec and on Windows it took over 6 mins, I had to close it as I was leaving work.
Comment 20 Telesto 2019-02-17 11:01:08 UTC
*** Bug 113539 has been marked as a duplicate of this bug. ***
Comment 21 Buovjaga 2019-03-28 07:44:50 UTC
(In reply to Telesto from comment #20)
> *** Bug 113539 has been marked as a duplicate of this bug. ***

Noel noticed some unknown soldier did work on this and now the slowness is gone for this report as well.

attachment 107270 [details] now takes

real    1m16,478s
user    1m15,524s
sys     0m1,652s

with latest master.

I think we can close.

Arch Linux 64-bit
Version: 6.3.0.0.alpha0+
Build ID: 9c5d33e3c9e4a680af61a9e7af8fa73d08b33834
CPU threads: 8; OS: Linux 5.0; UI render: default; VCL: gtk3; 
Locale: fi-FI (fi_FI.UTF-8); UI-Language: en-US
Calc: threaded
Built on 28 March 2019
Comment 22 Commit Notification 2019-03-29 06:30:33 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/+/912742333b67c08f7d65c200efabd5fab00b907f%5E%21

tdf#84635 quadratic slowdown on loading large tables

It will be available in 6.3.0.

The patch should be included in the daily builds available at
https://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
https://wiki.documentfoundation.org/Testing_Daily_Builds

Affected users are encouraged to test the fix and report feedback.
Comment 23 Buovjaga 2019-03-29 10:00:36 UTC
Tweaking status to fixed per previous commit.
Comment 24 Xisco Faulí 2019-04-24 13:17:55 UTC
attachment 107267 [details] opens in

real	1m9,412s
user	1m8,484s
sys	0m0,805s

in

Version: 6.2.4.0.0+
Build ID: 1149d20ce9f8682b58f98d3fa3bf289fc5974087
CPU threads: 4; OS: Linux 4.15; UI render: default; VCL: gtk3; 
Locale: ca-ES (ca_ES.UTF-8); UI-Language: en-US
Calc: threaded

while it takes

real	0m45,461s
user	0m45,160s
sys	0m0,965s

in

Version: 6.3.0.0.alpha0+
Build ID: 90e3b47b52f26420425a7417d2f51b6a386282d9
CPU threads: 4; OS: Linux 4.15; UI render: default; VCL: gtk3; 
Locale: ca-ES (ca_ES.UTF-8); UI-Language: en-US
Calc: threaded
Comment 25 Alexandre Letellier 2019-08-20 06:06:37 UTC Comment hidden (spam)