Bug 144777 - countifs() in Calc is slower than Excel's countifs()
Summary: countifs() in Calc is slower than Excel's countifs()
Status: NEW
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:
Keywords: perf
: 146546 (view as bug list)
Depends on:
Blocks:
 
Reported: 2021-09-28 17:03 UTC by adnanbaloch
Modified: 2022-01-14 17:13 UTC (History)
7 users (show)

See Also:
Crash report or crash signature:


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