Bug 144777 - countifs() in Calc is slower than Excel's countifs()
Summary: countifs() in Calc is slower than Excel's countifs()
Status: VERIFIED FIXED
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Calc (show other bugs)
Version:
(earliest affected)
7.3.0.0 alpha0+
Hardware: All All
: medium enhancement
Assignee: Not Assigned
URL:
Whiteboard: target:7.4.0
Keywords: perf
: 144205 144257 146546 (view as bug list)
Depends on:
Blocks:
 
Reported: 2021-09-28 17:03 UTC by adnanbaloch
Modified: 2022-05-21 18:16 UTC (History)
10 users (show)

See Also:
Crash report or crash signature:
Regression By:


Attachments
sample document (14.45 MB, application/vnd.openxmlformats-officedocument.spreadsheetml.sheet)
2021-09-30 09:36 UTC, Xisco Faulí
Details
perf flamegraph (231.31 KB, image/svg+xml)
2021-09-30 18:12 UTC, Julien Nabet
Details
Flamegraph (146.91 KB, image/svg+xml)
2021-12-03 20:52 UTC, Julien Nabet
Details
Flamegraph (195.44 KB, image/svg+xml)
2021-12-07 20:05 UTC, Julien Nabet
Details

Note You need to log in before you can comment on or make changes to this bug.
Description adnanbaloch 2021-09-28 17:03:26 UTC
Calc's countifs() is almost 3 times slower than its Excel counterpart, even though Excel does not benefit from OpenCL. It would be greatly appreciated if the algorithm can be tuned to extract even better performance than Excel since Excel lacks GPU acceleration.
Comment 1 Michael Warner 2021-09-28 17:21:45 UTC Comment hidden (obsolete)
Comment 2 Michael Warner 2021-09-28 17:26:07 UTC Comment hidden (obsolete)
Comment 3 adnanbaloch 2021-09-28 20:24:31 UTC Comment hidden (obsolete)
Comment 4 QA Administrators 2021-09-29 04:04:01 UTC Comment hidden (obsolete)
Comment 5 Xisco Faulí 2021-09-29 15:30:49 UTC Comment hidden (obsolete)
Comment 6 adnanbaloch 2021-09-30 09:30:49 UTC
Hi Xisco,

Just wanted to point out that this is a request for enhancement and not really a duplicate of 144159. I was hoping that someone could explore possibilities of further improving the performance of countifs() because Excel seems to do it faster without using GPU acceleration so maybe Calc can do it even faster.
Comment 7 Xisco Faulí 2021-09-30 09:32:34 UTC Comment hidden (obsolete)
Comment 8 Xisco Faulí 2021-09-30 09:33:58 UTC Comment hidden (obsolete)
Comment 9 Xisco Faulí 2021-09-30 09:36:52 UTC
Created attachment 175389 [details]
sample document
Comment 10 Xisco Faulí 2021-09-30 09:47:52 UTC
Reproduced in

Version: 7.3.0.0.alpha0+ / LibreOffice Community
Build ID: ac34bafb6cad056f843ff3ff0dee293bf1e18c56
CPU threads: 4; OS: Linux 5.10; UI render: default; VCL: gtk3
Locale: en-US (en_US.UTF-8); UI: en-US
Calc: threaded

Steps:
1. Open attached document
2. Copy H2
3. Paste it in H3:H187282

-> I killed LibreOffice after 5 minutes
Comment 11 Xisco Faulí 2021-09-30 09:48:21 UTC
@Julien, would it be possible to have a perf graph for this issue ?
Comment 12 Julien Nabet 2021-09-30 18:12:56 UTC
Created attachment 175430 [details]
perf flamegraph

Here's a Flamegraph retrieved on pc Debian x86-64 with master sources updated today + gen rendering.
Comment 13 Julien Nabet 2021-09-30 19:00:03 UTC
Eike/Noel: the Flamegraph shows that a lot of time is in ScTable::ValidQuery
See https://opengrok.libreoffice.org/xref/core/sc/source/core/data/table3.cxx?r=b60b6bfa#2979

I noticed in the loop "for (const auto& rItem : rItems)" at line 3039 that perhaps changing the order of test may help.
For example, I thought about putting:
3069                  else if (rParam.mbRangeLookup)
3070                  {
3071                      std::pair<bool,bool> aThisRes =
3072                          aEval.compareByRangeLookup(aCell, nCol, nRow, rEntry, rItem);
3073                      aRes.first |= aThisRes.first;
3074                      aRes.second |= aThisRes.second;
3075                  }
3076  
3077                  if (aRes.first && aRes.second)
3078                      break;

just after:
3041                  if (rItem.meType == ScQueryEntry::ByTextColor)
3042                  {
3043                      std::pair<bool, bool> aThisRes
3044                          = aEval.compareByTextColor(nCol, nRow, nTab, rItem);
3045                      aRes.first |= aThisRes.first;
3046                      aRes.second |= aThisRes.second;
3047                  }
3048                  else if (rItem.meType == ScQueryEntry::ByBackgroundColor)
3049                  {
3050                      std::pair<bool,bool> aThisRes =
3051                          aEval.compareByBackgroundColor(nCol, nRow, nTab, rItem);
3052                      aRes.first |= aThisRes.first;
3053                      aRes.second |= aThisRes.second;
3054                  }

so these would be at the end:
3055                  else if (aEval.isQueryByValue(rItem, nCol, nRow, aCell))
3056                  {
3057                      std::pair<bool,bool> aThisRes =
3058                          aEval.compareByValue(aCell, nCol, nRow, rEntry, rItem, pContext);
3059                      aRes.first |= aThisRes.first;
3060                      aRes.second |= aThisRes.second;
3061                  }
3062                  else if (aEval.isQueryByString(rEntry, rItem, nCol, nRow, aCell))
3063                  {
3064                      std::pair<bool,bool> aThisRes =
3065                          aEval.compareByString(aCell, nRow, rEntry, rItem, pContext);
3066                      aRes.first |= aThisRes.first;
3067                      aRes.second |= aThisRes.second;
3068                  }

So we would call "isQueryByValue" and/or "isQueryByString" only if necessary.

Now, I don't know if the order of evaluation matters and could change the final result.
Comment 14 Julien Nabet 2021-09-30 19:01:39 UTC
Forget about of course:
3077                  if (aRes.first && aRes.second)
3078                      break;
it's not in the if/else if part.
Comment 15 Eike Rathke 2021-09-30 19:48:24 UTC
Order of evaluation matters, as compareByValue() and compareByString() may deliver an exact match and only if they didn't then compareByRangeLookup() is to be tried; see also its comment at https://opengrok.libreoffice.org/xref/core/sc/source/core/data/table3.cxx?r=b60b6bfa#2941

Apart from that, COUNTIFS() doesn't do range lookups, only LOOKUP, MATCH and [HV]LOOKUP do.
Comment 16 Eike Rathke 2021-09-30 19:52:48 UTC
> compareByValue() and compareByString

Bah, of course I meant isQueryByValue() and isQueryByString() as it's also documented.
Comment 17 adnanbaloch 2021-10-16 17:27:44 UTC
The daily build shows some improvement, with total calculation time for 10,000 rows reduced from 238 seconds to 203 seconds. I have noticed that in some calculations, when the string "Adapt row height" appears, a green colored progress bar is shown. But with countifs, the green progress bar does not appear. Can this be fixed?

Version: 7.3.0.0.alpha0+ (x64) / LibreOffice Community
Build ID: 459f9de8a87373c826eadab142850cc3fa578fca
CPU threads: 8; OS: Windows 10.0 Build 19042; UI render: Skia/Raster; VCL: win
Locale: en-AE (en_AE); UI: en-US
Calc: CL
Comment 18 adnanbaloch 2021-12-02 07:49:14 UTC
Calculation time has regressed to twice as slow since Build ID 459f9de8a87373c826eadab142850cc3fa578fca.

Version: 7.3.0.0.beta1+ (x64) / LibreOffice Community
Build ID: 8c137ff0e201c2d0ecd1bb567496dbed8e5eced7
CPU threads: 8; OS: Windows 10.0 Build 19043; UI render: Skia/Raster; VCL: win
Locale: en-AE (en_AE); UI: en-US
Calc: CL
Comment 19 Julien Nabet 2021-12-03 20:52:24 UTC
Created attachment 176681 [details]
Flamegraph

I retrieved a new Flamegraph on pc Debian x86-64 with master sources updated today (gen rendering)
Comment 20 Julien Nabet 2021-12-03 20:54:51 UTC
Luboš: noticing your recent patches on this area, thought you might be interested in this one.
Comment 21 adnanbaloch 2021-12-07 10:58:52 UTC
It would be nice to have some performance based unit tests to avoid such regressions in future.
Comment 22 Julien Nabet 2021-12-07 20:05:02 UTC
Created attachment 176778 [details]
Flamegraph

Here's a new Flamegraph on pc Debian x86-64 with master sources updated today (7e5af164b7d293dd410710bed411e1ca64bbecf7) + gen rendering + non debug build.
Comment 23 adnanbaloch 2021-12-28 11:49:50 UTC
Situation as of today:

372 seconds in LO 7.3.0.1
355 seconds in LO 7.4.0.0.alpha0+
185 seconds in LO 7.3.0.0alpha0+
28 seconds in Office 2021 LTSC v2111 14701.20226

Version: 7.3.0.1 (x64) / LibreOffice Community
Build ID: 840fe2f57ae5ad80d62bfa6e25550cb10ddabd1d
CPU threads: 8; OS: Windows 10.0 Build 19043; UI render: Skia/Raster; VCL: win
Locale: en-AE (en_AE); UI: en-US
Calc: CL

Version: 7.4.0.0.alpha0+ (x64) / LibreOffice Community
Build ID: 9e8c1da64fa8a520730ce0aea0f7199cd75c892f
CPU threads: 8; OS: Windows 10.0 Build 19043; UI render: Skia/Raster; VCL: win
Locale: en-AE (en_AE); UI: en-US
Calc: CL
Comment 24 Luboš Luňák 2022-01-12 14:18:44 UTC
*** Bug 146546 has been marked as a duplicate of this bug. ***
Comment 25 Shad Sterling 2022-01-14 17:13:22 UTC
I'm not sure bug 146546 is a duplicate of this; see bug 146546 comment 5
Comment 26 Shad Sterling 2022-01-29 07:39:11 UTC
The problem I reported in bug 146546 seems to be triggered by selecting a cell that contains the triggering formula, but not when recalculating that same cell in response to changes in referenced cells.  It makes LibreOffice unusable for several hours, sometimes across killing and relaunching the app
Comment 27 Shad Sterling 2022-01-29 19:28:26 UTC
It's even weirder than that: if reopening the file doesn't hang immediately, if I click on the cell it hangs, but if I use the keyboard to navigate to the cell it does not hang; I can use the keyboard to extend the column (with copy, move, paste...), but I can't use the mouse to extend the column (with click & drag the corner)
Comment 28 Luboš Luňák 2022-05-03 14:49:11 UTC
*** Bug 144205 has been marked as a duplicate of this bug. ***
Comment 29 Commit Notification 2022-05-11 09:52:18 UTC
Luboš Luňák committed a patch related to this issue.
It has been pushed to "master":

https://git.libreoffice.org/core/commit/248e49d3f409d414331945ba91b3083406d59f78

no PerformQuery() with ScSortedRangeCache if not needed (tdf#144777)

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 30 Commit Notification 2022-05-11 09:53:27 UTC
Luboš Luňák committed a patch related to this issue.
It has been pushed to "master":

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

reduce size of *IFS conditions array (tdf#144777)

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 31 Commit Notification 2022-05-11 09:53:37 UTC
Luboš Luňák committed a patch related to this issue.
It has been pushed to "master":

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

search faster an array where most elements do not match (tdf#144777)

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 32 Luboš Luňák 2022-05-11 10:00:56 UTC
*** Bug 144257 has been marked as a duplicate of this bug. ***
Comment 33 stragu 2022-05-14 23:14:39 UTC Comment hidden (obsolete)
Comment 34 stragu 2022-05-14 23:16:55 UTC
Following the steps in comment 10, it took about 15 seconds to paste 187,280 cells with COUNTIFS(), in the latest LO 7.4 alpha on Ubuntu 20.04.

I don't have a GPU.

Marking as VERIFIED FIXED.

Version: 7.4.0.0.alpha1+ / LibreOffice Community
Build ID: 4bd8eb13e1e2693961fdb9c19c403fde9d163de1
CPU threads: 8; OS: Linux 5.13; UI render: default; VCL: gtk3
Locale: en-AU (en_AU.UTF-8); UI: en-US
Calc: threaded
Comment 35 adnanbaloch 2022-05-21 18:16:20 UTC
26 seconds in Office 2021 LTSC v2111 14701.20226

This time is for 10,000 rows. The daily build I downloaded is now doing it in roughly 2 seconds! I'm speechless. AMAZING WORK, GUYS!

I hope in future this performance will not regress. Thank you once again!

Version: 7.4.0.0.alpha0+ (x64) / LibreOffice Community
Build ID: fe687d1b8f5305edfb167152a4fb19ffa20c5404
CPU threads: 8; OS: Windows 10.0 Build 19043; UI render: Skia/Raster; VCL: win
Locale: en-AE (en_AE); UI: en-US
Calc: CL