Bug 133699 - Slow sorting of a column
Summary: Slow sorting of a column
Status: VERIFIED FIXED
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Calc (show other bugs)
Version:
(earliest affected)
6.2.0.3 release
Hardware: All All
: medium normal
Assignee: Not Assigned
URL:
Whiteboard: target:7.1.0 target:7.0.0.1 target:6.4.6
Keywords: bibisected, bisected, perf, regression
Depends on:
Blocks:
 
Reported: 2020-06-05 11:08 UTC by Telesto
Modified: 2020-06-25 13:57 UTC (History)
3 users (show)

See Also:
Crash report or crash signature:


Attachments
Bibisect log (3.22 KB, text/plain)
2020-06-05 11:09 UTC, Telesto
Details
Example file (8.27 MB, application/vnd.openxmlformats-officedocument.spreadsheetml.sheet)
2020-06-05 11:14 UTC, Telesto
Details
flamegraph (400.81 KB, image/svg+xml)
2020-06-22 18:54 UTC, Xisco Faulí
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Telesto 2020-06-05 11:08:32 UTC
Description:
Slow sorting of a column

Steps to Reproduce:
1. Open the attached file
2. Select column A
3. Click sort descending + Current selection


Actual Results:
More than a minute

Expected Results:
8 seconds


Reproducible: Always


User Profile Reset: No



Additional Info:
Version: 7.1.0.0.alpha0+ (x64)
Build ID: 191288d6a7fb52b31038a21c4e71ee57ffa3bacd
CPU threads: 4; OS: Windows 6.3 Build 9600; UI render: Skia/Raster; VCL: win
Locale: nl-NL (nl_NL); UI: en-US
Calc: CL
Comment 1 Telesto 2020-06-05 11:09:09 UTC
Created attachment 161646 [details]
Bibisect log

Bisected to
author	Noel Grandin <noel.grandin@collabora.co.uk>	2018-10-03 15:23:13 +0200
committer	Noel Grandin <noel.grandin@collabora.co.uk>	2018-10-04 08:15:48 +0200
commit	96a032743339f315ffff13fd8dc9191acffcc636 (patch)
tree	a8b843f07b8249895a5861c3fb5f9c81b3b2e9d4
parent	5c7de51f908e866cdab7dbf4aa22aa48f42dc153 (diff)
reserve space before appending to vector in a loop

https://cgit.freedesktop.org/libreoffice/core/commit/?id=96a032743339f315ffff13fd8dc9191acffcc636
Comment 2 Telesto 2020-06-05 11:14:05 UTC
Created attachment 161647 [details]
Example file
Comment 3 Xisco Faulí 2020-06-22 16:32:00 UTC
it takes 4 minutes to finish the sort operation for me

Version: 7.1.0.0.alpha0+
Build ID: 70479e1f4cb3c120f46239a648e65f035af2922d
CPU threads: 4; OS: Linux 4.19; UI render: default; VCL: gtk3
Locale: en-US (en_US.UTF-8); UI: en-US
Calc: threaded
Comment 4 Xisco Faulí 2020-06-22 16:40:10 UTC
(In reply to Telesto from comment #1)
> Created attachment 161646 [details]
> Bibisect log
> 
> Bisected to
> author	Noel Grandin <noel.grandin@collabora.co.uk>	2018-10-03 15:23:13 +0200
> committer	Noel Grandin <noel.grandin@collabora.co.uk>	2018-10-04 08:15:48
> +0200
> commit	96a032743339f315ffff13fd8dc9191acffcc636 (patch)
> tree	a8b843f07b8249895a5861c3fb5f9c81b3b2e9d4
> parent	5c7de51f908e866cdab7dbf4aa22aa48f42dc153 (diff)
> reserve space before appending to vector in a loop
> 
> https://cgit.freedesktop.org/libreoffice/core/commit/
> ?id=96a032743339f315ffff13fd8dc9191acffcc636

I do confirm sort time increased from 1 minute and 10 seconds ( before the mentioned commit ) to 4 minutes

Adding Cc: to Noel Grandin
Comment 5 Xisco Faulí 2020-06-22 18:54:34 UTC
Created attachment 162321 [details]
flamegraph
Comment 6 Xisco Faulí 2020-06-22 18:59:14 UTC
if my observations are right, 26% of the time is spent on mdds::multi_type_vector<mdds::mtv::custom_block_func1<mdds::mtv::noncopyable_managed_element_block<50, SvtBroadcaster> >, mdds::detail::mtv::event_func>::set_empty_impl
@Luboš Luňák, I thought you might also be interested in this issue
Comment 7 Commit Notification 2020-06-23 11:19:05 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/97965876459d8cfda0b653551708eb14de36e632

tdf#133699 Slow sorting of a column

It will be available in 7.1.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 8 Xisco Faulí 2020-06-23 13:25:05 UTC
back to 1 minute and 10 seconds in

Version: 7.1.0.0.alpha0+
Build ID: 10129e2dfc582915d999e24deed34f7303a6f02e
CPU threads: 4; OS: Linux 4.19; UI render: default; VCL: gtk3
Locale: en-US (en_US.UTF-8); UI: en-US
Calc: threaded

@Noel, thanks for fixing this issue!!
Comment 9 Telesto 2020-06-23 14:33:54 UTC
(In reply to Xisco Faulí from comment #8)
> back to 1 minute and 10 seconds in
> 
> Version: 7.1.0.0.alpha0+
> Build ID: 10129e2dfc582915d999e24deed34f7303a6f02e
> CPU threads: 4; OS: Linux 4.19; UI render: default; VCL: gtk3
> Locale: en-US (en_US.UTF-8); UI: en-US
> Calc: threaded
> 
> @Noel, thanks for fixing this issue!!

@Xisco,
You 1 minute 10 seconds.. ; Noel from 25s to less than 1s.
And I from 1 minute back to 8 seconds (based on comment 0). 

Why is your case so much slower; its far to slow. It should really finish within 25 seconds or so; configuration differences aside. IMHO. Not an older regression or so?
Comment 10 Xisco Faulí 2020-06-23 15:11:40 UTC
(In reply to Telesto from comment #9)
> (In reply to Xisco Faulí from comment #8)
> > back to 1 minute and 10 seconds in
> > 
> > Version: 7.1.0.0.alpha0+
> > Build ID: 10129e2dfc582915d999e24deed34f7303a6f02e
> > CPU threads: 4; OS: Linux 4.19; UI render: default; VCL: gtk3
> > Locale: en-US (en_US.UTF-8); UI: en-US
> > Calc: threaded
> > 
> > @Noel, thanks for fixing this issue!!
> 
> @Xisco,
> You 1 minute 10 seconds.. ; Noel from 25s to less than 1s.
> And I from 1 minute back to 8 seconds (based on comment 0). 
> 
> Why is your case so much slower; its far to slow. It should really finish
> within 25 seconds or so; configuration differences aside. IMHO. Not an older
> regression or so?

I think it's just my computer, (In reply to Telesto from comment #9)
> (In reply to Xisco Faulí from comment #8)
> > back to 1 minute and 10 seconds in
> > 
> > Version: 7.1.0.0.alpha0+
> > Build ID: 10129e2dfc582915d999e24deed34f7303a6f02e
> > CPU threads: 4; OS: Linux 4.19; UI render: default; VCL: gtk3
> > Locale: en-US (en_US.UTF-8); UI: en-US
> > Calc: threaded
> > 
> > @Noel, thanks for fixing this issue!!
> 
> @Xisco,
> You 1 minute 10 seconds.. ; Noel from 25s to less than 1s.
> And I from 1 minute back to 8 seconds (based on comment 0). 
> 
> Why is your case so much slower; its far to slow. It should really finish
> within 25 seconds or so; configuration differences aside. IMHO. Not an older
> regression or so?

I think my computer is just too slow and too old, I should get a new one at some point but it's fine for my daily basic needs
Comment 11 Telesto 2020-06-23 15:27:24 UTC
(In reply to Xisco Faulí from comment #10)
> (In reply to Telesto from comment #9)
> > (In reply to Xisco Faulí from comment #8)
> > > back to 1 minute and 10 seconds in
> > > 
> > > Version: 7.1.0.0.alpha0+
> > > Build ID: 10129e2dfc582915d999e24deed34f7303a6f02e
> > > CPU threads: 4; OS: Linux 4.19; UI render: default; VCL: gtk3
> > > Locale: en-US (en_US.UTF-8); UI: en-US
> > > Calc: threaded
> > > 
> > > @Noel, thanks for fixing this issue!!
> > 
> > @Xisco,
> > You 1 minute 10 seconds.. ; Noel from 25s to less than 1s.
> > And I from 1 minute back to 8 seconds (based on comment 0). 
> > 
> > Why is your case so much slower; its far to slow. It should really finish
> > within 25 seconds or so; configuration differences aside. IMHO. Not an older
> > regression or so?
> 
> I think it's just my computer, (In reply to Telesto from comment #9)
> > (In reply to Xisco Faulí from comment #8)
> > > back to 1 minute and 10 seconds in
> > > 
> > > Version: 7.1.0.0.alpha0+
> > > Build ID: 10129e2dfc582915d999e24deed34f7303a6f02e
> > > CPU threads: 4; OS: Linux 4.19; UI render: default; VCL: gtk3
> > > Locale: en-US (en_US.UTF-8); UI: en-US
> > > Calc: threaded
> > > 
> > > @Noel, thanks for fixing this issue!!
> > 
> > @Xisco,
> > You 1 minute 10 seconds.. ; Noel from 25s to less than 1s.
> > And I from 1 minute back to 8 seconds (based on comment 0). 
> > 
> > Why is your case so much slower; its far to slow. It should really finish
> > within 25 seconds or so; configuration differences aside. IMHO. Not an older
> > regression or so?
> 
> I think my computer is just too slow and too old, I should get a new one at
> some point but it's fine for my daily basic needs

Normally we diverge somewhat, i'm say 35% lets say faster; but difference is not 800%. And my CPU is from Q1 2013
Comment 12 Xisco Faulí 2020-06-23 15:37:21 UTC
I've just checked with a remote win machine which has 16 cores and it takes 2 minutes to sort descending without the fixing patch

Version: 7.0.0.0.alpha1+ (x64)
Build ID: b3c8859cd20bd02adea5d2b026001f67feacc754
CPU threads: 16; OS: Windows 6.3 Build 9600; UI render: Skia/Raster; VCL: win
Locale: en-GB (en_GB); UI: en-US
Calc: threaded

I'm wondering if we are following the same steps:
1. Open the attached document
2. Click on top of column A -> A1:A1048576 is selected
3. Data - Sort Descending - Current Selection.

is that correct ?
Comment 13 Xisco Faulí 2020-06-23 16:04:37 UTC
(In reply to Xisco Faulí from comment #12)
> I've just checked with a remote win machine which has 16 cores and it takes
> 2 minutes to sort descending without the fixing patch
> 
> Version: 7.0.0.0.alpha1+ (x64)
> Build ID: b3c8859cd20bd02adea5d2b026001f67feacc754
> CPU threads: 16; OS: Windows 6.3 Build 9600; UI render: Skia/Raster; VCL: win
> Locale: en-GB (en_GB); UI: en-US
> Calc: threaded
> 
> I'm wondering if we are following the same steps:
> 1. Open the attached document
> 2. Click on top of column A -> A1:A1048576 is selected
> 3. Data - Sort Descending - Current Selection.
> 
> is that correct ?

ok, I tried with previous versions and it seems to be another previous regression. I'll report it in a follow-up ticket
Comment 14 Commit Notification 2020-06-24 07:19:25 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "libreoffice-7-0":

https://git.libreoffice.org/core/commit/0638adcb101d870b169a34d980d41ef4fc742a94

tdf#133699 Slow sorting of a column

It will be available in 7.0.0.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 15 Commit Notification 2020-06-25 13:57:35 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "libreoffice-6-4":

https://git.libreoffice.org/core/commit/150f5cbe108793e427d8106d8cfa60dd6c5c5cb4

tdf#133699 Slow sorting of a column

It will be available in 6.4.6.

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.