Bug 162047 - Table layout is quadratic in complexity
Summary: Table layout is quadratic in complexity
Status: NEW
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Writer (show other bugs)
Version:
(earliest affected)
24.2.0.0 alpha0+
Hardware: All All
: medium major
Assignee: Not Assigned
URL:
Whiteboard:
Keywords: bibisected, haveBacktrace, perf, regression
Depends on:
Blocks: Writer-Tables
  Show dependency tree / graph
 
Reported: 2024-07-15 19:29 UTC by Mike Kaganski
Modified: 2024-08-16 07:07 UTC (History)
6 users (show)

See Also:
Crash report or crash signature:

Attachments
An empty table with 24700 rows (32.27 KB, application/vnd.oasis.opendocument.text)
2024-07-15 19:29 UTC, Mike Kaganski 		Details
Two tables with 12350 rows (32.47 KB, application/vnd.oasis.opendocument.text)
2024-07-15 19:30 UTC, Mike Kaganski 		Details
Perf flamegraph of opening attachment 195319 (824.98 KB, image/svg+xml)
2024-08-16 07:06 UTC, Buovjaga 		Details
View All Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Mike Kaganski 2024-07-15 19:29:13 UTC 
Created attachment 195319 [details]
An empty table with 24700 rows

The attachment is a document without any text, only with a single-column 24700-row table.

Opening it, it shows 246 pages initially, and freezes for several minutes for repagination (7 minutes on my system), after which, it shows 747 pages, and becomes normally responsive.

If this table is split to two in the middle (which itself takes very long), then such a file is repaginated in about 1.5 minutes, i.e., around 4 times faster (even though the page count, and cell count, is the same).

The performance of table layout is decreasing quadratically.

https://ask.libreoffice.org/t/it-takes-7-minutes-to-load-an-odt-file-800-kb-with-one-large-table-solved/108214/
Comment 1 Mike Kaganski 2024-07-15 19:30:41 UTC 
Created attachment 195320 [details]
Two tables with 12350 rows
Comment 2 m_a_riosv 2024-07-16 01:11:00 UTC 
Reproducible
Version: 24.2.5.2 (X86_64) / LibreOffice Community
Build ID: bffef4ea93e59bebbeaf7f431bb02b1a39ee8a59
CPU threads: 16; OS: Windows 10.0 Build 22631; UI render: Skia/Raster; VCL: win
Locale: es-ES (es_ES); UI: en-US Calc: CL threaded
Version: 25.2.0.0.alpha0+ (X86_64) / LibreOffice Community
Build ID: bbd5079c58e352ece8f10328f8dcda9819c4cfbe
CPU threads: 16; OS: Windows 11 X86_64 (10.0 build 22631); UI render: Skia/Raster; VCL: win Locale: es-ES (es_ES); UI: en-US Calc: CL threaded


With
Version: 24.2.3.2 (X86_64) / LibreOffice Community
Build ID: 433d9c2ded56988e8a90e6b2e771ee4e6a5ab2ba

is a bit slower to open than with
Version: 7.6.7.2 (X86_64) / LibreOffice Community
Build ID: dd47e4b30cb7dab30588d6c79c651f218165e3c5

opens quick but has slow scrolling.
Comment 3 Buovjaga 2024-08-15 10:13:22 UTC 
Bibisected with linux-64-24.2 to 3999f5d12b2964d440a0a193cef76d889a9a0da7
Resolves: tdf#161430 reindex the correct style if there are duplicate names
Comment 4 Caolán McNamara 2024-08-15 20:42:58 UTC 
I'm not convinced the bisect here is helpful in the sense of identifying a perf regression. Presumably everything between d6bdcff5f739179efdd060083dc7feef14e5ba4d and 3999f5d12b2964d440a0a193cef76d889a9a0da7 is unsafe.
Comment 5 Buovjaga 2024-08-16 07:06:58 UTC 
Created attachment 195844 [details]
Perf flamegraph of opening attachment 195319 [details]

Version: 25.2.0.0.alpha0+ (X86_64) / LibreOffice Community
Build ID: da249b2c386f0e16a0e63e38ec363c4a5ffd8fdb
CPU threads: 8; OS: Linux 6.10; UI render: default; VCL: kf6 (cairo+wayland)
Locale: fi-FI (fi_FI.UTF-8); UI: en-US
Calc: CL threaded