Bug 119083 - Recalculation is slow with 90000 VLOOKUP
Summary: Recalculation is slow with 90000 VLOOKUP
Status: RESOLVED FIXED
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Calc (show other bugs)
Version:
(earliest affected)
Inherited From OOo
Hardware: All All
: medium minor
Assignee: Not Assigned
URL:
Whiteboard: target:7.3.0 target:7.4.0 target:7.3....
Keywords: perf, wantBacktrace
Depends on:
Blocks: Function-Vlookup
  Show dependency treegraph
 
Reported: 2018-08-03 14:32 UTC by Jean-Sebastien Bevilacqua
Modified: 2022-03-31 20:10 UTC (History)
10 users (show)

See Also:
Crash report or crash signature:


Attachments
Slow file (586.67 KB, application/vnd.oasis.opendocument.spreadsheet)
2018-08-03 14:32 UTC, Jean-Sebastien Bevilacqua
Details
FlameGraph (394.15 KB, image/svg+xml)
2019-10-06 10:55 UTC, Roman Kuznetsov
Details
perf flamegraph (22.55 KB, application/x-bzip)
2019-10-06 12:54 UTC, Julien Nabet
Details
perf flamegraph (674.85 KB, image/svg+xml)
2021-11-14 09:48 UTC, Julien Nabet
Details
Flamegraph (655.20 KB, image/svg+xml)
2021-11-14 10:17 UTC, Julien Nabet
Details
Flamegraph (470.32 KB, image/svg+xml)
2021-12-07 19:15 UTC, Julien Nabet
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Jean-Sebastien Bevilacqua 2018-08-03 14:32:58 UTC
Created attachment 143958 [details]
Slow file

Hello,

I have a LibreOffice file with lot of data and lot of formulas.
It can be very slow.

For example, try the following procedure:

1 - Open the joined file
2 - In the "Devis Strasbourg" sheet, try to insert a new column next to the "P" one
3 - Libreoffice freezes for a while.

Thanks,
Jean-Sébastien
Comment 1 m_a_riosv 2018-08-03 21:28:02 UTC
There are 90000 VLOOKUP in the file looking in a range of 10000 rows and 20000 COUNTIF. So when you insert a column all need to be evaluated.

Repro with
Version: 6.0.6.2 (x64)
Build ID: 0c292870b25a325b5ed35f6b45599d2ea4458e77
CPU threads: 4; OS: Windows 10.0; UI render: GL; 
Locale: es-ES (es_ES); Calc: CL
Version: 6.2.0.0.alpha0+ (x64)
Build ID: 715fcaff01ed048c52c69264a7a0fb773dd57b32
CPU threads: 4; OS: Windows 10.0; UI render: default; 
TinderBox: Win-x86_64@42, Branch:master, Time: 2018-07-21_02:21:27
Locale: es-ES (es_ES); Calc: CL
Comment 2 Xisco Faulí 2018-08-07 18:17:43 UTC
Also reproduced in

LibreOffice 3.3.0 
OOO330m19 (Build:6)
tag libreoffice-3.3.0.4

IMHO, this bug is too general, but let's keep it open as the document is attached and it can be useful...
Comment 3 Julien Nabet 2019-04-22 10:15:54 UTC
On pc Debian x86-64 with master sources updated today or with LO 6.1.5.2, I don't reproduce this (But I've got a Ryzen 5 2600 + RAM 32GB and SSD Nvme)
Comment 4 Roman Kuznetsov 2019-10-06 10:55:46 UTC Comment hidden (obsolete)
Comment 5 Roman Kuznetsov 2019-10-06 11:00:31 UTC
Julien, I can repro it in current master 

Версия: 6.4.0.0.alpha0+
ID сборки: 66e45a1ae861d50edf65fed9e39c9c9d5b15e0ac
Потоков ЦП: 4; ОС:Linux 5.0; Отрисовка ИП: по умолчанию; VCL: kf5; 
TinderBox: Linux-rpm_deb-x86_64@86-TDF, Branch:master, Time: 2019-09-28_15:31:38
Локаль: ru-RU (ru_RU.UTF-8); UI-Language: ru-RU
Calc: threaded

here is Core i3 2330m, 7 year old CPU with only 2 core and 4Gb of memory

And I tried to make FlameGraph (look at it in attach). It my first expirience, so may be it is not correct =(

Noel, could you look at it?
Comment 6 Julien Nabet 2019-10-06 12:54:54 UTC
Created attachment 154779 [details]
perf flamegraph

On pc Debian x86-64 with master sources updated today, I could reproduce this.
I was on the wrong sheet.
It's even worse for me since it's a complete freeze. I had to kill LO.
Comment 7 Roman Kuznetsov 2019-10-06 13:44:23 UTC Comment hidden (obsolete)
Comment 8 QA Administrators 2021-10-06 03:48:20 UTC Comment hidden (obsolete)
Comment 9 Roman Kuznetsov 2021-10-06 10:49:27 UTC
Column inserting takes around 2 minutes in

Version: 7.3.0.0.alpha0+ (x64) / LibreOffice Community
Build ID: fbfd91f2c5f4d66570c2d5a6f048b21f5d1671a4
CPU threads: 8; OS: Windows 10.0 Build 19043; UI render: Skia/Vulkan; VCL: win
Locale: ru-RU (ru_RU); UI: ru-RU
Calc: threaded

I think it's still a problem
Comment 10 Noel Grandin 2021-10-14 10:30:08 UTC
how long does Excel take to perform this operation?
Comment 11 Commit Notification 2021-10-14 11:37:56 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/c998691e22ceda15c89d55cf7005201f0392dadb

tdf#119083 small improvement to large vlookup sheet insert

It will be available in 7.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 12 m_a_riosv 2021-10-14 14:55:29 UTC
About 4 seconds with excel, about 15 with calc.

Microsoft® Excel® for Microsoft 365 MSO (Version 2109 Build 16.0.14430.20154) 32-bit 

Version: 7.2.2.2 (x64) / LibreOffice Community
Build ID: 02b2acce88a210515b4a5bb2e46cbfb63fe97d56
CPU threads: 4; OS: Windows 10.0 Build 21390; UI render: Skia/Raster; VCL: win
Locale: es-ES (es_ES); UI: en-US
Calc: CL
Comment 13 Roman Kuznetsov 2021-11-12 22:49:29 UTC
(In reply to Roman Kuznetsov from comment #9)
> Column inserting takes around 2 minutes in
> 
> Version: 7.3.0.0.alpha0+ (x64) / LibreOffice Community
> Build ID: fbfd91f2c5f4d66570c2d5a6f048b21f5d1671a4
> CPU threads: 8; OS: Windows 10.0 Build 19043; UI render: Skia/Vulkan; VCL:
> win
> Locale: ru-RU (ru_RU); UI: ru-RU
> Calc: threaded


So strange, it takes 3 min 45 sec now in

Version: 7.3.0.0.alpha1+ (x64) / LibreOffice Community
Build ID: c36fa9f86e54afa4e1876a9d296ebcbfcbd3a0ad
CPU threads: 4; OS: Windows 6.1 Service Pack 1 Build 7601; UI render: Skia/Raster; VCL: win
Locale: ru-RU (ru_RU); UI: ru-RU
Calc: CL
Comment 14 Julien Nabet 2021-11-14 09:48:55 UTC
Created attachment 176245 [details]
perf flamegraph

Here's a new Flamegraph retrieved on pc Debian x86-64 with  master sources updated today + gen rendering.

Remark: for a 600kB file, it's quite long to open too (about 30 seconds on a Ryzen 5 2600 + 32GB).
Comment 15 Julien Nabet 2021-11-14 09:51:11 UTC
Luboš: noticing https://cgit.freedesktop.org/libreoffice/core/commit/?id=ec0edb0969c23b25576f4d1b3b2ee5d3f21990ad (optimize VLOOKUP by returning SharedString if possible), thought you might be interested in this one. (see attached Flamegraph in my previous comment).
Of course, don't hesitate to uncc yourself if not interested, have no time, other.
Comment 16 Luboš Luňák 2021-11-14 10:06:31 UTC
I cannot reproduce the problem. If I right-click on column P and select to add a column after, it's almost instant.

Julien: Your flamegraph is from a debug build.
Comment 17 Luboš Luňák 2021-11-14 10:09:32 UTC
(In reply to Luboš Luňák from comment #16)
> I cannot reproduce the problem. If I right-click on column P and select to
> add a column after, it's almost instant.

Nevermind, wrong sheet, I can reproduce it.
Comment 18 Julien Nabet 2021-11-14 10:17:35 UTC
Created attachment 176246 [details]
Flamegraph
Comment 19 Julien Nabet 2021-11-14 10:19:37 UTC
(In reply to Luboš Luňák from comment #17)
> (In reply to Luboš Luňák from comment #16)
> > I cannot reproduce the problem. If I right-click on column P and select to
> > add a column after, it's almost instant.
> 
> Nevermind, wrong sheet, I can reproduce it.

Yes, I was writing this in a comment but you were quicker than me.

Sorry for the Flamegraph retrieved on a debug build, I retrieved another one on a non-debug build.
Comment 20 Commit Notification 2021-12-06 14:46:17 UTC
Luboš Luňák committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/e55723c0ba4172bf6ee80fda49b069fd441a0c90

try to broadcast in bulk (tdf#119083)

It will be available in 7.4.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 21 Commit Notification 2021-12-06 14:46:29 UTC
Luboš Luňák committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/8406139062d9ffe1daed32aefe4e261c6c55d63e

process broadcasts for adjacent cells together (tdf#119083)

It will be available in 7.4.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 22 Commit Notification 2021-12-06 21:19:49 UTC
Luboš Luňák committed a patch related to this issue.
It has been pushed to "libreoffice-7-3":

https://git.libreoffice.org/core/commit/47198583da8e67e0178466205d82835c391c8d73

try to broadcast in bulk (tdf#119083)

It will be available in 7.3.0.0.beta2.

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 Commit Notification 2021-12-06 21:21:02 UTC
Luboš Luňák committed a patch related to this issue.
It has been pushed to "libreoffice-7-3":

https://git.libreoffice.org/core/commit/8579b6e39ea30048ae7763f27d77e093b26e76dc

process broadcasts for adjacent cells together (tdf#119083)

It will be available in 7.3.0.0.beta2.

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 24 Roman Kuznetsov 2021-12-07 12:25:47 UTC
1 min 40 sec without Luboš's latest patches

38 sec with Luboš's latest patches

CPU - Intel  i7-10510U , Windows 10

It's a pity if you can't do something else here.
Comment 25 Julien Nabet 2021-12-07 19:15:45 UTC
Created attachment 176777 [details]
Flamegraph

@Roman: weird, I gave a new try with master sources updated today (7e5af164b7d293dd410710bed411e1ca64bbecf7) + gen rendering, it was about 2 secs (I double checked I was on the right sheet, "Devis Strasbourg")

I attached a new Flamegraph just in case.
Comment 26 Roman Kuznetsov 2021-12-07 19:58:40 UTC
(In reply to Julien Nabet from comment #25)
> Created attachment 176777 [details]
> Flamegraph
> 
> @Roman: weird, I gave a new try with master sources updated today
> (7e5af164b7d293dd410710bed411e1ca64bbecf7) + gen rendering, it was about 2
> secs (I double checked I was on the right sheet, "Devis Strasbourg")
> 
> I attached a new Flamegraph just in case.

I agree, it's really strange, because I tried it on my home PC with very old Intel Core 2 Quad 9450 right now and I really got only 2-3 sec result.

I'll retest tomorrow on my work notebook
Comment 27 Roman Kuznetsov 2021-12-08 07:27:57 UTC
(In reply to Roman Kuznetsov from comment #26)
 
> I'll retest tomorrow on my work notebook

18 sec >_<

CPU - Intel  i7-10510U , Windows 10

Version: 7.4.0.0.alpha0+ (x64) / LibreOffice Community
Build ID: 3a61cce54277fd12570103a191c50d9b37ef3dd3
CPU threads: 8; OS: Windows 10.0 Build 19043; UI render: Skia/Raster; VCL: win
Locale: ru-RU (ru_RU); UI: ru-RU
Calc: threaded

may be the problem here is the CPU is mobile and has only 1,8GHz by default and Windows can be in power save mode always...
Comment 28 Kevin Suo 2021-12-08 09:52:25 UTC
(In reply to Roman Kuznetsov from comment #27)
Are you testing using a debug build, or a non-debug build? Performance issues may appear much slower in debug builds.
Comment 29 BogdanB 2021-12-08 14:33:41 UTC
45 seconds in
Version: 7.3.0.0.beta1+ (x64) / LibreOffice Community
Build ID: d7a6869a531d0f2f26c47714466d5d47d78ddbfd
CPU threads: 4; OS: Windows 10.0 Build 19044; UI render: Skia/Raster; VCL: win
Locale: ro-RO (ro_RO); UI: en-US
Calc: threaded
Comment 30 Luboš Luňák 2021-12-08 14:45:01 UTC
I can actually reproduce on my Windows build that this doesn't help there. The cells to process together are in random order, possibly as a result of Windows threading acting slightly differently. Reopening, maybe this can be improved (although it's a question if and when given that I did this in my spare time).
Comment 31 m_a_riosv 2021-12-08 17:26:32 UTC
In any way, patches gets a great time reduction.

About 00:03:52 with
Version: 7.2.4.1 (x64) / LibreOffice Community
Build ID: 27d75539669ac387bb498e35313b970b7fe9c4f9
CPU threads: 4; OS: Windows 10.0 Build 21390; UI render: Skia/Raster; VCL: win
Locale: es-ES (es_ES); UI: en-US Calc: CL

About 59 seconds with master 2021-12-08.
Version: 7.4.0.0.alpha0+ (x64) / LibreOffice Community
Build ID: 7e5af164b7d293dd410710bed411e1ca64bbecf7
CPU threads: 4; OS: Windows 10.0 Build 21390; UI render: Skia/Raster; VCL: win
Locale: es-ES (es_ES); UI: en-US Calc: CL

About 3~4 seconds.
Microsoft® Excel® Microsoft 365 MSO (Version 2110 Build 16.0.14527.20234) 32-bit
Comment 32 Roman Kuznetsov 2021-12-08 18:45:21 UTC
(In reply to BogdanB from comment #29)
> 45 seconds in
> Version: 7.3.0.0.beta1+ (x64) / LibreOffice Community
> Build ID: d7a6869a531d0f2f26c47714466d5d47d78ddbfd
> CPU threads: 4; OS: Windows 10.0 Build 19044; UI render: Skia/Raster; VCL:
> win
> Locale: ro-RO (ro_RO); UI: en-US
> Calc: threaded

Bogdan, LO 7.3 beta 1 doesn't have latest Luboš's patches
Comment 33 Roman Kuznetsov 2021-12-08 18:46:13 UTC
(In reply to Kevin Suo from comment #28)
> (In reply to Roman Kuznetsov from comment #27)
> Are you testing using a debug build, or a non-debug build? Performance
> issues may appear much slower in debug builds.

I tested it in windows daily build by link https://dev-builds.libreoffice.org/daily/master/current.html
Comment 34 BogdanB 2021-12-08 20:09:03 UTC
I found the bug number in About dialog, so maybe appear there because were more changes in code from this bug. So you have right.
Comment 35 Commit Notification 2022-02-16 17:46:05 UTC
Eike Rathke committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/a1f21d7094deb6f1ae5388718f2bc28eecd5737a

Resolves: tdf#147398 Test Intersects() instead of Contains(), tdf#119083

It will be available in 7.4.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 36 Commit Notification 2022-02-17 10:36:21 UTC
Eike Rathke committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/f6b9c471cace1963e8b625ecfe2c20f5248984eb

Handle the possible case of broadcasted row block, tdf#119083 follow-up

It will be available in 7.4.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 37 Commit Notification 2022-02-17 10:48:45 UTC
Eike Rathke committed a patch related to this issue.
It has been pushed to "libreoffice-7-3":

https://git.libreoffice.org/core/commit/963330b5605e2350a34405c4752989c43c223b78

Resolves: tdf#147398 Test Intersects() instead of Contains(), tdf#119083

It will be available in 7.3.2.

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 38 Roman Kuznetsov 2022-02-18 22:46:02 UTC
Now on my old Intel Core 2 Quad 9450 the column inserting took only 3 sec in

Version: 7.4.0.0.alpha0+ (x64) / LibreOffice Community
Build ID: c856f9bec12d98ed49f01578ded79f16ae7be051
CPU threads: 4; OS: Windows 6.1 Service Pack 1 Build 7601; UI render: Skia/Raster; VCL: win
Locale: ru-RU (ru_RU); UI: en-US
Calc: CL Jumbo

Finally fixed?
Comment 39 Commit Notification 2022-02-20 07:02:41 UTC
Luboš Luňák committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/fdcea8ccc8236b0975ac9c85dcabf9c663e4b627

make CollectCellAction sort cells by cell address (tdf#119083)

It will be available in 7.4.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 40 Commit Notification 2022-02-21 13:48:53 UTC
Eike Rathke committed a patch related to this issue.
It has been pushed to "libreoffice-7-3":

https://git.libreoffice.org/core/commit/89c4b004a748457408781972c5b6c6d44360fb3e

Handle the possible case of broadcasted row block, tdf#119083 follow-up

It will be available in 7.3.2.

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 41 Commit Notification 2022-02-21 14:15:28 UTC
Eike Rathke committed a patch related to this issue.
It has been pushed to "libreoffice-7-3-1":

https://git.libreoffice.org/core/commit/eb07d94074cbc06cea4d938068161bbb25442d0a

Resolves: tdf#147398 Test Intersects() instead of Contains(), tdf#119083

It will be available in 7.3.1.

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 42 Ulf 2022-03-31 20:10:03 UTC
I tried the following:

Inserting new column as describes works fine for me. It takes just a moment. But
it takes 51.37 sek if i insert a new row.


1)insert new row e.g. over/under row 13
2)It takes 51.37 sek 

Version: 7.3.2.2 (x64) / LibreOffice Community
Build ID: 49f2b1bff42cfccbd8f788c8dc32c1c309559be0
CPU threads: 8; OS: Windows 10.0 Build 19044; UI render: Skia/Raster; VCL: win
Locale: de-DE (de_DE); UI: de-DE
Calc: CL