Bug 85867 - LibreOffice slow at rendering charts involving a large number of data points
Summary: LibreOffice slow at rendering charts involving a large number of data points
Status: NEW
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Chart (show other bugs)
(earliest affected) release
Hardware: x86-64 (AMD64) Linux (All)
: medium major
Assignee: Not Assigned
Keywords: perf
: 85882 96340 105912 (view as bug list)
Depends on:
Blocks: Chart
  Show dependency treegraph
Reported: 2014-11-04 16:56 UTC by Diggory Hardy
Modified: 2021-11-06 15:37 UTC (History)
9 users (show)

See Also:
Crash report or crash signature:

1st version (823 bytes, patch)
2015-02-16 12:35 UTC, Pierre-Eric Pelloux-Prayer
Screenshot with draw_as_hair_line.patch applied (206.44 KB, image/jpeg)
2015-02-16 12:37 UTC, Pierre-Eric Pelloux-Prayer
2nd version (448 bytes, patch)
2015-02-16 12:39 UTC, Pierre-Eric Pelloux-Prayer
Screenshot with draw_as_hair_polygon.patch applied (153.58 KB, image/jpeg)
2015-02-16 12:40 UTC, Pierre-Eric Pelloux-Prayer
The test data (801.43 KB, text/plain)
2018-11-27 21:10 UTC, Robert Pollak
Example file with data (589.14 KB, application/vnd.oasis.opendocument.spreadsheet)
2021-11-06 15:37 UTC, Buovjaga

Note You need to log in before you can comment on or make changes to this bug.
Description Diggory Hardy 2014-11-04 16:56:46 UTC
This is related to https://bugs.freedesktop.org/show_bug.cgi?id=36779 . It is basically about rendering of charts involving large numbers of data points being slow, but with a testable condition.

Steps to reproduce slow chart rendering:

1. Download this file: https://openmalaria.googlecode.com/git-history/1e60bce9bd62a87c6e80fc81b96915089614eda1/test/expected/ctsoutSimpleMPDTest.txt
2. Load into LibreOffice: `LibreOffice --calc ctsoutSimpleMPDTest.txt`
3. Select start from line 2, and select tab (\t) as a field separator
4. Select columns A and C
5. Click the "insert chart" button
6. Select XY (Scatter)
7. Select "Lines only" (third image)
8. Wait until the UI is responsive again (for me this takes several seconds)

(Note: the lag occurs even before clicking "finish" on the plot wizard.)

Expected behaviour: no major lag. UI is never unresponsive for more than around half a second _and_ the chart is rendered in under a second (even if at reduced quality).
Comment 1 m.a.riosv 2014-11-05 10:50:43 UTC
*** Bug 85882 has been marked as a duplicate of this bug. ***
Comment 2 Robert Pollak 2014-11-07 09:03:42 UTC
This bug is certainly a duplicate of an existing one, but I could not find that yet. If it stays open, a reduced version of the test data should be directly attached.

This test chart only contains 7448 x/y samples. On my machine (Intel Core i7-2600K @ 3.4 GHz) I notice about 2 seconds of delay when switching from "Points only" to "Lines only" (in LibreOffice on Windows 7).

I often work with data sets containing ~32k samples, where the corresponding delays are really annoying.

PS: If you read this and just want to express that you are also affected, please don't post a comment!. Just CC yourselves instead, to keep the issue readable.
Comment 3 Pierre-Eric Pelloux-Prayer 2015-02-16 12:33:38 UTC
Here's my understanding of the problem.
Line graph are drawn using the PolygonStrokePrimitive2D primitive (see sdrdecompositiontools.cxx)
When the UI is frozen, the stacktrace is:
(gdb) bt 10
#0  solveHorizontalEdges (rTrDeSimpleEdges=std::vector of length 3567, capacity 4096 = {...}, this=0x7fffffffb3c0) at basegfx/source/polygon/b2dtrapez
#1  TrapezoidSubdivider (rSourcePolyPolygon=..., this=0x7fffffffb3c0) at basegfx/source/polygon/b2dtrapezoid.cxx:591
#2  basegfx::tools::trapezoidSubdivide (ro_Result=std::vector of length 0, capacity 0, rSourcePolyPolygon=...) at basegfx/source/polygon/b2dtrapezoid.
#3  0x00007fffe0a663ff in X11SalGraphicsImpl::drawPolyPolygon (this=0x1bd26d0, rOrigPolyPoly=..., fTransparency=0) at vcl/unx/generic/gdi/gdiimpl.cxx:
#4  0x00007ffff2493769 in SalGraphics::DrawPolyPolygon (this=0x1bd4c50, i_rPolyPolygon=..., i_fTransparency=i_fTransparency@entry=0, i_pOutDev=i_pOutDev@entry=0x1bd89a8) at /home/pierre
#5  0x00007ffff237de27 in OutputDevice::drawLine (this=this@entry=0x1bd89a8, aLinePolyPolygon=..., rInfo=...) at vcl/source/outdev/line.cxx:260
#6  0x00007ffff237f4a5 in OutputDevice::drawPolyLine (this=this@entry=0x1bd89a8, rPoly=..., rLineInfo=...) at vcl/source/outdev/polyline.cxx:247
#7  0x00007ffff237eee6 in OutputDevice::DrawPolyLine (this=0x1bd89a8, rB2DPolygon=..., fLineWidth=fLineWidth@entry=5.2791686397418474, eLineJoin=eLineJoin@entry=basegfx::B2DLINEJOIN_ROU
ND, eLineCap=eLineCap@entry=com::sun::star::drawing::LineCap_BUTT) at vcl/source/outdev/polyline.cxx:215
#8  0x00007fffee7f1fee in drawinglayer::processor2d::VclProcessor2D::RenderPolygonStrokePrimitive2D (this=this@entry=0x1c2f0b0, rPolygonStrokeCandidate=...) at breoffice/drawinglayer/source/processor2d/vclprocessor2d.cxx:1322
#9  0x00007fffee7ed695 in drawinglayer::processor2d::VclPixelProcessor2D::processBasePrimitive2D (this=0x1c2f0b0, rCandidate=...) at drawinglayer/sour

The polypolygon to trapezoid method is complex and doesn't scale well when 10.000+ edges are involved.

I tested various patches but I'm not sure which one is better
Comment 4 Pierre-Eric Pelloux-Prayer 2015-02-16 12:35:43 UTC
Created attachment 113430 [details]
1st version

First approach: do not use the generic 'draw lines as polypolygon' code path, but use the simpler 'draw lines as hair line'.

Pros: render times are acceptable
Cons: ignore line width, so graph looks different (line graphs have a default line width of 80)
Comment 5 Pierre-Eric Pelloux-Prayer 2015-02-16 12:37:12 UTC
Created attachment 113431 [details]
Screenshot with draw_as_hair_line.patch applied
Comment 6 Pierre-Eric Pelloux-Prayer 2015-02-16 12:39:33 UTC
Created attachment 113432 [details]
2nd version

This patch changes the way line drawing is done. Instead of using the drawPolyPolygon method, each polygon is drawn separatly.

Pro: render time is acceptable
Con: ?
Comment 7 Pierre-Eric Pelloux-Prayer 2015-02-16 12:40:34 UTC
Created attachment 113433 [details]
Screenshot with draw_as_hair_polygon.patch applied
Comment 8 Pierre-Eric Pelloux-Prayer 2015-02-16 12:42:52 UTC
Other potential approaches:
 * improve TrapezoidSubdivider performance on large set (b2dtrapezoid), maybe using spatial partitioning.
 * add a proper DrawLine primitive
Comment 9 Diggory Hardy 2015-02-16 14:44:15 UTC
The results look great Pierre!

Using thinner lines when there are many points is actually an advantage (at least in this example), though maybe ignoring the line width is a bit cheeky.
Comment 10 Armin Le Grand 2015-11-17 09:34:15 UTC
Hi Guys, ignoring the LineWidth is a no-go from my POV. It changes the intended visualization. Maybe change the default LineWidth to 0 in the model description and thus use hairline in the future, but that would then work for all newly created or adapted/changed charts. Just drawing hairlines instead of lines with the given width is a wrong visualization (discretization) of given geometry data, but helps to detect and show the weak point.
The better way which you already intend is to find a better way to render PolyPolygons with a LineWidth != zero. This is what is done on Win and Mac already. Problem on Linux is that X does not have a direct command to draw fat lines with evtl. pattern and the correct line start/end and cap styles. Due to that the line geometry is prepared as filled PolyPolygons (using primitives and basegfx, but may also be old stuff in vcl). If this is currently converted to trapezoids we should check if this is needed - at least, X can draw filled polygons (but not PolyPolygons).
With the recent moves to more advanced system renderers on Linux it will be solvable much better. Ideally a system-dependent, optimized primitive renderer chooses what to do for the given render platform (X or OpenGL or ...). Evtl it is possible to avoid trapezoidation, that would help, not sure if optimizing it will do much in the sense of runtime complexity...
Comment 11 m.a.riosv 2016-01-11 17:39:41 UTC
*** Bug 96340 has been marked as a duplicate of this bug. ***
Comment 12 m.a.riosv 2017-02-10 09:09:18 UTC
*** Bug 105912 has been marked as a duplicate of this bug. ***
Comment 13 Pedro Côrte-Real 2017-11-26 16:15:24 UTC
I'm getting the same issue on Ubuntu 16.04 using Calc version 5.1.6~rc2-0ubuntu1~xenial2. Calc is completely unresponsive and when it does eventually draw a chart it's a rendering mess. My data set has about 20 thousand points (temperature data from a logger).
Comment 14 QA Administrators 2018-11-27 03:43:16 UTC Comment hidden (obsolete)
Comment 15 Robert Pollak 2018-11-27 21:10:26 UTC
Created attachment 147076 [details]
The test data

I have now downloaded the originally used test data from https://raw.githubusercontent.com/SwissTPH/openmalaria/1e60bce9bd62a87c6e80fc81b96915089614eda1/test/expected/ctsoutSimpleMPDTest.txt and attached it here.
Comment 16 Robert Pollak 2018-11-28 11:27:36 UTC
Testing LO (x64), I can still confirm the ~2 sec delay from my comment 2 (on the same OS and HW).
Comment 17 QA Administrators 2019-11-29 03:45:13 UTC Comment hidden (obsolete)
Comment 18 Robert Pollak 2019-12-02 10:58:35 UTC
I still see the ~2 sec delay, now on Intel Core i7-4770 @ 3.40GHz.
Build ID: 1:6.3.3-0ubuntu0.18.04.1~lo1
CPU threads: 8; OS: Linux 4.15; UI render: default; VCL: gtk3; 
Locale: en-US (en_DK.utf8); UI-Language: en-US
Calc: threaded
Comment 19 Buovjaga 2021-11-06 15:37:51 UTC
Created attachment 176134 [details]
Example file with data

Here is the data copied into a document.

I guess I get the slight lag when selecting the chart type, but is it normal to not see any lines in the chart? I don't see them on Windows or Linux. Tested also with 7.2, 6.4 and 6.3

Version: (x64) / LibreOffice Community
Build ID: 5c5f36aa73b11356a3bff0a9cc8b5fe8d1a776b9
CPU threads: 2; OS: Windows 10.0 Build 19042; UI render: Skia/Raster; VCL: win
Locale: fi-FI (fi_FI); UI: en-US
Calc: threaded