Bug 133835 - Calc autofilter freeze after deselecting an item (in a column containing many unique string values) and pressing OK
Summary: Calc autofilter freeze after deselecting an item (in a column containing many...
Status: VERIFIED FIXED
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Calc (show other bugs)
Version:
(earliest affected)
4.1.0.4 release
Hardware: All All
: medium normal
Assignee: Not Assigned
URL:
Whiteboard: target:7.3.0 target:7.3.0.0.beta2
Keywords: perf
: 133804 136838 145765 (view as bug list)
Depends on:
Blocks: AutoFilter
  Show dependency treegraph
 
Reported: 2020-06-09 20:18 UTC by Telesto
Modified: 2021-12-04 00:27 UTC (History)
8 users (show)

See Also:
Crash report or crash signature:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Telesto 2020-06-09 20:18:13 UTC
Description:
Calc autofilter freeze after deselecting an item and pressing OK

Steps to Reproduce:
1. Open attachment 147829 [details]
2. Click the auto filter dropdown Column B
3. Deselect meta about & press OK


Actual Results:
10 seconds

Expected Results:
1 seconds as in 4.1


Reproducible: Always


User Profile Reset: No



Additional Info:
Found in
Version: 7.0.0.0.beta1+
Build ID: c344de1b9985b6ca10b354e24151d0bdf92dc20e
CPU threads: 2; OS: Linux 5.3; UI render: default; VCL: x11
Locale: en-US (en_US.UTF-8); UI: en-US
Calc: threaded

and in 
4.2

but not in
4.1
Comment 1 BogdanB 2020-09-17 12:40:28 UTC
Confirmed in
Version: 7.0.1.2 (x64)
Build ID: 7cbcfc562f6eb6708b5ff7d7397325de9e764452
CPU threads: 4; OS: Windows 10.0 Build 19041; UI render: Skia/Raster; VCL: win
Locale: ro-RO (ro_RO); UI: en-US
Calc: threaded

12-13 seconds
Comment 2 Kevin Suo 2020-09-17 12:47:53 UTC
I reported bug 136838 before I found this one. Seems a duplicate. I am copy the following from that bug:

Assume a column contains n items. When we open the autofilter and un-selected one, then we have n-1 items selected. Doing this filter with AutoFilter is slow because it seems to be using the "x in n-1" logic. However, doing this filter with Standard Filter is fast if we use "Not Equal" logic.

Steps to Reproduce:

1. Open the attachment 165612 [details].

2. Click the autofilter in column A, and de-select the 1st item (i.e., #N/A), then click OK.
--> Slow, it takes more than 8s.

3. Use Standard Filter, and set condition "POMatch <> #N/A", then click OK.
--> Fast, it takes 1s.

Apparently, if we deselect only one item, the condition is the same as <> that item. It should be more expensive to compare the value to see whether it is in the n-1 list.

Actually, if we de-select several items (e.g., 3 items), it would still be faster to use "(x <> a) and (x <> b) and (x <> c)". However, if the deselected items are quite a lot, the "x in n-1" logic should be faster.
Comment 3 Kevin Suo 2020-09-17 12:48:37 UTC
*** Bug 136838 has been marked as a duplicate of this bug. ***
Comment 4 Cor Nouws 2020-11-23 21:39:43 UTC
possibly the same
  https://bugs.documentfoundation.org/show_bug.cgi?id=78664#c23
Comment 5 Kevin Suo 2020-11-29 13:06:58 UTC
This one is different from bug 78664.

This one may also be different from bug 133878. The patch in https://gerrit.libreoffice.org/c/core/+/106594 fixes bug 133878, but not this one. As a result, Telesto you are correct to report this one separately.

Luboš Luňák: Could you also take a look at this one? It is similar as bug 133878 for which you have submitted a patch.
Comment 6 Luboš Luňák 2021-11-08 18:34:55 UTC
Most of the time spent repeatedly inserting items into SfxPoolItemArray_Impl's sorted_vector containing a million of items.
Comment 7 Commit Notification 2021-11-20 05:40:52 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/66317d3aa5ada5b7c5ea317590730f563bebb77c

tdf#133835 speedup calc autofilter (1)

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 8 Commit Notification 2021-11-20 05:42:03 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/23886b0e023bc27e9ba89f9ab6d1bdf36da022ab

tdf#133835 speedup calc autofilter (2)

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 9 Commit Notification 2021-11-20 07:10:53 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/2aa7aa564f8c8f7d1cd520b3e2d198a17e423a37

tdf#133835 speedup calc autofilter (3)

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 10 BogdanB 2021-11-20 07:46:01 UTC
Noel, you work hard on autofilter speed. I just wait to test the improvements.
Comment 11 Commit Notification 2021-11-21 09:27:49 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/0b46361ef84a61100a0274a007062317607d097a

tdf#133835 speedup calc autofilter (4)

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 Commit Notification 2021-11-21 14:48:22 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

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

tdf#133835 speedup calc autofilter (5)

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 13 Kevin Suo 2021-11-21 15:33:55 UTC
Thank you Noel Grandin for your hard work on fixing the autofilter slowness.

I see most of your merged patches are on the INetURLObject, and I see the test document in attachment 147829 [details] does contain URLs. However, I suggest you also take a look at attachment 165612 [details] as included in bug 136838 (which was marked as a duplicate of *this* one), that attachment does not contain urls in the cell content.
Comment 14 Kevin Suo 2021-11-21 15:54:19 UTC
I provided another test ods file in
https://bugs.documentfoundation.org/show_bug.cgi?id=136838#c2

just for your reference.
Comment 15 Commit Notification 2021-11-22 06:52:08 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/7805a224b96897807e49fd49dd5276d6089b0b5c

tdf#133835 speedup calc autofilter (6)

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 16 Noel Grandin 2021-11-22 07:16:51 UTC
There are several different sources of slowness here.

(1) The INetURLObject stuff, which I am working on

(2) the QueryEvaluator::compareByStringComparator stuff for which I have no suggestion.

(3) Some intermittent issue with millions of SfxPoolItem, which I suspect is a bug because I have seen it only once in about 30 runs.
Comment 17 Commit Notification 2021-11-22 08:52:30 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

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

tdf#133835 speedup calc autofilter (7)

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 18 Commit Notification 2021-11-22 11:20:20 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

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

tdf#133835 speedup calc autofilter (8)

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 19 Commit Notification 2021-11-22 11:21:33 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/1b327e4a33a2a2c575c247ea90365652d6549852

tdf#133835 speedup calc autofilter (9)

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 20 Luboš Luňák 2021-11-22 12:28:51 UTC
(In reply to Noel Grandin from comment #16)
> There are several different sources of slowness here.

Yes, this bugreport mixes several different problems :(.

> (2) the QueryEvaluator::compareByStringComparator stuff for which I have no
> suggestion.

I have some ideas there, the problem is not with QueryEvaluator but rather with ScTable::ValidQuery() being dumb and doing things backwards (comment #2 will result in a query with thousands of items and they'll be all compared against the cell instead of searching the items for whether one of them matches the cell).
 
> (3) Some intermittent issue with millions of SfxPoolItem, which I suspect is
> a bug because I have seen it only once in about 30 runs.

I can reproduce it reliably with attachment #147829 [details].
Comment 21 Commit Notification 2021-11-22 14:47:27 UTC
Luboš Luňák committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/1a32af4192291ea5cfe7c4c143144a5dab1f156e

cache error strings for ScTable::validQuery()  (tdf#133835)

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 22 Noel Grandin 2021-11-23 11:28:44 UTC
So the SfxPoolItem problem is that we create a SvxFieldItem to represent each URL, and since there are tons of URLs, we create tons of pool items.

I don't think there is any easy fix for this - IMO we should not be representing a URL as a pool item at all.
Comment 23 Commit Notification 2021-11-23 11:30:47 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/7566479a7a049d0e65d7506bc563e4d1c664b16d

tdf#133835 speedup calc autofilter (11)

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 24 Luboš Luňák 2021-11-23 17:33:46 UTC
*** Bug 133804 has been marked as a duplicate of this bug. ***
Comment 25 Luboš Luňák 2021-11-23 17:35:09 UTC
https://gerrit.libreoffice.org/c/core/+/125735 (and the preceding changes) should take care of this.
Comment 26 Roman Kuznetsov 2021-11-25 14:28:02 UTC
Verified. Around 1-2 sec in

Version: 7.3.0.0.alpha1+ (x64) / LibreOffice Community
Build ID: 515682539623c9d61921c4f89302ffa0a4cb8d24
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
Comment 27 Kevin Suo 2021-11-25 14:45:13 UTC
This is very nice fix. Autofilter is not instance for all the columns I have tested. This is now much quicker than MSO in my opinion.

Thank you everyone who have worked on this, especially Noel Grandin and  Luboš Luňák! Also thanks to Colan who have worked on the autofilter dropdown/submenu UI related issues.

Next step is to test every corner cases to make sure any regression is captured and fixed in time. Everyone effected by this (and the duplicated bugs) are encouraged to use a daily build to test.
Comment 28 Kevin Suo 2021-11-25 15:43:49 UTC
*** Bug 145765 has been marked as a duplicate of this bug. ***
Comment 29 Commit Notification 2021-11-26 08:15:59 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/0600affd91ca799c75354a8c63d2b40373b08996

tdf#133835 speedup calc autofilter (10)

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 30 Commit Notification 2021-11-26 16:29:52 UTC
Noel Grandin committed a patch related to this issue.
It has been pushed to "libreoffice-7-3":

https://git.libreoffice.org/core/commit/216be5dcd987b5d4a9802791a8f78a8e85eb6a79

tdf#133835 speedup calc autofilter (10)

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.