Thread a group of formula-groups together if possible

Just before about to thread a FG, look to left and right for
"mutually" independent FG's with some restrictions and thread
this group of FG's together treating it as a single but longer
computation load.

For now the restrictions are :-
All formula-groups in a FG "group" must have :-

1. Same length
2. Same relative position.
3. Same weight.

This is very helpful in cases similar to the below :
There are lots of (say 32) consecutive formula-groups
all with same "small" length (say 8) and same weight.
By conventional formula-group-threading the speed-up is
limited to 8x even if we have a 256 core processor, but
with this threading-multiple-formula-groups patch
(in this case) we can get a speed-up of 256x provided
we have a >= 256 core machine. So effectively with this
patch the speed-up is now only limited to the number of
cells in a range consisting of mutually indepdendent
formula-groups rather than number of cells in each
formula-group.

Change-Id: Ib25b5abbb583fa207e8befff9a908d14313f3d51
Reviewed-on: https://gerrit.libreoffice.org/79485
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lunak@collabora.com>

6 files changed, 32 insertions, 7 deletions

diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index 78272c7f4f3b..3b7ffbe645e1 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -593,7 +593,8 @@ public:
 #endif
     void SetFormulaResults( SCROW nRow, const double* pResults, size_t nLen );
 
-    void CalculateInThread( ScInterpreterContext& rContext, SCROW nRow, size_t nLen, unsigned nThisThread, unsigned nThreadsTotal );
+    void CalculateInThread( ScInterpreterContext& rContext, SCROW nRow, size_t nLen, size_t nOffset,
+                            unsigned nThisThread, unsigned nThreadsTotal );
     void HandleStuffAfterParallelCalculation( SCROW nRow, size_t nLen );
 
     void SetNumberFormat( SCROW nRow, sal_uInt32 nNumberFormat );
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index 9ac4bca15288..2b2ae8d99c0c 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -2148,8 +2148,8 @@ public:
      */
     void SC_DLLPUBLIC SetFormulaResults( const ScAddress& rTopPos, const double* pResults, size_t nLen );
 
-    const ScDocumentThreadSpecific& CalculateInColumnInThread( ScInterpreterContext& rContext, const ScAddress& rTopPos, size_t nLen, unsigned nThisThread, unsigned nThreadsTotal);
-    void HandleStuffAfterParallelCalculation( const ScAddress& rTopPos, size_t nLen );
+    const ScDocumentThreadSpecific& CalculateInColumnInThread( ScInterpreterContext& rContext, const ScRange& rCalcRange, unsigned nThisThread, unsigned nThreadsTotal);
+    void HandleStuffAfterParallelCalculation( SCCOL nColStart, SCCOL nColEnd, SCROW nRow, size_t nLen, SCTAB nTab );
 
     /**
      * Transfer a series of contiguous cell values from specified position to
diff --git a/sc/inc/formulacell.hxx b/sc/inc/formulacell.hxx
index fe421508ea18..65a3a4af7733 100644
--- a/sc/inc/formulacell.hxx
+++ b/sc/inc/formulacell.hxx
@@ -146,7 +146,7 @@ private:
     ScFormulaCell( const ScFormulaCell& ) = delete;
 
     bool CheckComputeDependencies(sc::FormulaLogger::GroupScope& rScope, bool fromFirstRow,
-                                  SCROW nStartOffset, SCROW nEndOffset);
+                                  SCROW nStartOffset, SCROW nEndOffset, bool bCalcDependencyOnly = false);
     bool InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope& aScope,
                                         bool& bDependencyComputed,
                                         bool& bDependencyCheckFailed,
diff --git a/sc/inc/interpretercontext.hxx b/sc/inc/interpretercontext.hxx
index 9fb2bc3993c5..c7598fef8cdc 100644
--- a/sc/inc/interpretercontext.hxx
+++ b/sc/inc/interpretercontext.hxx
@@ -28,7 +28,8 @@ struct ScLookupCacheMap;
 // SetNumberFormat() is not thread-safe, so calls to it need to be delayed to the main thread.
 struct DelayedSetNumberFormat
 {
-    SCROW mRow; // Used only with formula groups, so column and tab do not need to be stored.
+    SCROW mCol;
+    SCROW mRow;
     sal_uInt32 mnNumberFormat;
 };
 
diff --git a/sc/inc/recursionhelper.hxx b/sc/inc/recursionhelper.hxx
index 2a72be7b9d76..5962f11eb61a 100644
--- a/sc/inc/recursionhelper.hxx
+++ b/sc/inc/recursionhelper.hxx
@@ -25,6 +25,7 @@
 #include <list>
 #include <vector>
 #include <stack>
+#include <unordered_set>
 
 class ScFormulaCell;
 
@@ -59,7 +60,9 @@ class ScRecursionHelper
     bool                                bDoingRecursion;
     bool                                bInIterationReturn;
     bool                                bConverging;
+    bool                                bGroupsIndependent;
     std::vector< ScFormulaCell* >       aTemporaryGroupCells;
+    std::unordered_set< ScFormulaCellGroup* >* pFGSet;
 
     void Init();
     void ResetIteration();
@@ -111,6 +114,12 @@ public:
 
     void AddTemporaryGroupCell(ScFormulaCell* cell);
     void CleanTemporaryGroupCells();
+
+    void SetFormulaGroupSet(std::unordered_set<ScFormulaCellGroup*>* pSet) { pFGSet = pSet; }
+    bool HasFormulaGroupSet() { return pFGSet != nullptr; }
+    bool CheckFGIndependence(ScFormulaCellGroup* pFG);
+    void SetGroupsIndependent(bool bSet) { bGroupsIndependent = bSet; }
+    bool AreGroupsIndependent() { return bGroupsIndependent; }
 };
 
 /** A class to wrap ScRecursionHelper::PushFormulaGroup(),
@@ -136,6 +145,19 @@ public:
     ~ScFormulaGroupDependencyComputeGuard();
 };
 
+class ScCheckIndependentFGGuard
+{
+    ScRecursionHelper& mrRecHelper;
+    bool mbUsedFGSet;
+public:
+    ScCheckIndependentFGGuard() = delete;
+    ScCheckIndependentFGGuard(ScRecursionHelper& rRecursionHelper,
+                              std::unordered_set<ScFormulaCellGroup*>* pSet);
+    ~ScCheckIndependentFGGuard();
+
+    bool AreGroupsIndependent();
+};
+
 #endif // INCLUDED_SC_INC_RECURSIONHELPER_HXX
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index b3ea9016725e..78bfa854e33d 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -1012,8 +1012,9 @@ public:
 
     void SetFormulaResults( SCCOL nCol, SCROW nRow, const double* pResults, size_t nLen );
 
-    void CalculateInColumnInThread( ScInterpreterContext& rContext, SCCOL nCol, SCROW nRow, size_t nLen, unsigned nThisThread, unsigned nThreadsTotal);
-    void HandleStuffAfterParallelCalculation( SCCOL nCol, SCROW nRow, size_t nLen);
+    void CalculateInColumnInThread( ScInterpreterContext& rContext, SCCOL nColStart, SCCOL nColEnd,
+                                    SCROW nRowStart, SCROW nRowEnd, unsigned nThisThread, unsigned nThreadsTotal);
+    void HandleStuffAfterParallelCalculation( SCCOL nColStart, SCCOL nColEnd, SCROW nRow, size_t nLen);
 
     /**
      * Either start all formula cells as listeners unconditionally, or start