Bug 84635 - TABLE: Slow layout of large tables (quadratic time)
Summary: TABLE: Slow layout of large tables (quadratic time)
Status: NEW
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Writer (show other bugs)
Version: 4.2.6.3 release
Hardware: All All
: medium normal
Assignee: Not Assigned
QA Contact:
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-10-03 15:18 UTC by Peter Grimtell
Modified: 2014-11-14 20:57 UTC (History)
3 users (show)

See Also:
i915 platform:
i915 features:


Attachments
Time to load and lay out document as function of number of rows (50.39 KB, text/plain)
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

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 Beluga 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?


Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.