First steps for Calc parallelism

For now, formula group calculations are done in parallel threads when
1) OpenCL is not used, and 2) the environment variable
CPU_THREADED_CALCULATION is set. This commit is a surely broken first
step and does not actually work that well at all.

Change-Id: Ia7e5019703ba89bff0695faef0f7504765061149

6 files changed, 315 insertions, 12 deletions

diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index 0fa0f3d1358b..8e852f856c7a 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -2614,6 +2614,27 @@ copyFirstFormulaBlock(
     return rCxt.setCachedColArray(nTab, nCol, pNumArray, pStrArray);
 }
 
+bool
+DoFormulaBlockForParallelism( const sc::CellStoreType::iterator& itBlk )
+{
+    sc::formula_block::iterator it = sc::formula_block::begin(*itBlk->data);
+    sc::formula_block::iterator itEnd;
+
+    itEnd = it;
+    std::advance(itEnd, itBlk->size);
+    for (; it != itEnd; ++it)
+    {
+        ScFormulaCell& rFC = **it;
+        sc::FormulaResultValue aRes = rFC.GetResult();
+        if (aRes.meType == sc::FormulaResultValue::Invalid || aRes.mnError != FormulaError::NONE)
+        {
+            return false;
+        }
+    }
+
+    return true;
+}
+
 struct NonNullStringFinder
 {
     bool operator() (const rtl_uString* p) const { return p != nullptr; }
@@ -2806,6 +2827,27 @@ formula::VectorRefArray ScColumn::FetchVectorRefArray( SCROW nRow1, SCROW nRow2
     return formula::VectorRefArray(formula::VectorRefArray::Invalid);
 }
 
+bool ScColumn::HandleRefArrayForParallelism( SCROW nRow1, SCROW nRow2 )
+{
+    if (nRow1 > nRow2)
+        return false;
+
+    for (auto itBlk = maCells.begin(); itBlk != maCells.end(); ++itBlk)
+    {
+        switch (itBlk->type)
+        {
+            case sc::element_type_formula:
+            {
+                if (!DoFormulaBlockForParallelism( itBlk))
+                    return false;
+                return true;
+            }
+        }
+    }
+
+    return true;
+}
+
 void ScColumn::SetFormulaResults( SCROW nRow, const double* pResults, size_t nLen )
 {
     sc::CellStoreType::position_type aPos = maCells.position(nRow);
@@ -2862,6 +2904,32 @@ void ScColumn::SetFormulaResults( SCROW nRow, const formula::FormulaConstTokenRe
     }
 }
 
+void ScColumn::CalculateInThread( SCROW nRow, size_t nLen, unsigned nThisThread, unsigned nThreadsTotal)
+{
+    sc::CellStoreType::position_type aPos = maCells.position(nRow);
+    sc::CellStoreType::iterator it = aPos.first;
+    if (it->type != sc::element_type_formula)
+        // This is not a formula block.
+        return;
+
+    size_t nBlockLen = it->size - aPos.second;
+    if (nBlockLen < nLen)
+        // Length is longer than the length of formula cells. Not good.
+        return;
+
+    sc::formula_block::iterator itCell = sc::formula_block::begin(*it->data);
+    std::advance(itCell, aPos.second);
+
+    for (size_t i = 0; i < nLen; ++i, ++itCell)
+    {
+        if (nThreadsTotal > 0 && (i % nThreadsTotal) != nThisThread)
+            continue;
+
+        ScFormulaCell& rCell = **itCell;
+        rCell.InterpretTail(ScFormulaCell::SCITP_NORMAL, false);
+    }
+}
+
 void ScColumn::SetNumberFormat( SCROW nRow, sal_uInt32 nNumberFormat )
 {
     ApplyAttr(nRow, SfxUInt32Item(ATTR_VALUE_FORMAT, nNumberFormat));
diff --git a/sc/source/core/data/documen8.cxx b/sc/source/core/data/documen8.cxx
index c0ee2e8f1b1b..ea5c34b55bc9 100644
--- a/sc/source/core/data/documen8.cxx
+++ b/sc/source/core/data/documen8.cxx
@@ -427,6 +427,15 @@ void ScDocument::SetFormulaResults(
     pTab->SetFormulaResults(rTopPos.Col(), rTopPos.Row(), pResults, nLen);
 }
 
+void ScDocument::CalculateInColumnInThread( const ScAddress& rTopPos, size_t nLen, unsigned nThisThread, unsigned nThreadsTotal)
+{
+    ScTable* pTab = FetchTable(rTopPos.Tab());
+    if (!pTab)
+        return;
+
+    pTab->CalculateInColumnInThread(rTopPos.Col(), rTopPos.Row(), nLen, nThisThread, nThreadsTotal);
+}
+
 void ScDocument::InvalidateTextWidth( const ScAddress* pAdrFrom, const ScAddress* pAdrTo,
                                       bool bNumFormatChanged )
 {
diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx
index 2f9791dc696e..a2f98bb17c7e 100644
--- a/sc/source/core/data/document.cxx
+++ b/sc/source/core/data/document.cxx
@@ -1808,6 +1808,15 @@ void ScDocument::UnlockAdjustHeight()
         --nAdjustHeightLock;
 }
 
+bool ScDocument::HandleRefArrayForParallelism( const ScAddress& rPos, SCROW nLength )
+{
+    SCTAB nTab = rPos.Tab();
+    if (!TableExists(nTab))
+        return false;
+
+    return maTabs[nTab]->HandleRefArrayForParallelism(rPos.Col(), rPos.Row(), rPos.Row()+nLength-1);
+}
+
 bool ScDocument::CanFitBlock( const ScRange& rOld, const ScRange& rNew )
 {
     if ( rOld == rNew )
diff --git a/sc/source/core/data/formulacell.cxx b/sc/source/core/data/formulacell.cxx
index 3dea10f5b6eb..bda1c3cfa07d 100644
--- a/sc/source/core/data/formulacell.cxx
+++ b/sc/source/core/data/formulacell.cxx
@@ -17,6 +17,8 @@
  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  */
 
+#include <config_features.h>
+
 #include <sal/config.h>
 
 #include <cassert>
@@ -45,7 +47,7 @@
 #include <chgtrack.hxx>
 #include <tokenarray.hxx>
 
-#include <config_features.h>
+#include <comphelper/threadpool.hxx>
 #include <formula/errorcodes.hxx>
 #include <formula/vectortoken.hxx>
 #include <svl/intitem.hxx>
@@ -1524,10 +1526,10 @@ void ScFormulaCell::Interpret()
         bool bGroupInterpreted = InterpretFormulaGroup();
         aDC.leaveGroup();
         if (!bGroupInterpreted)
-            InterpretTail( SCITP_NORMAL);
+            InterpretTail( SCITP_NORMAL, true);
 #else
         if (!InterpretFormulaGroup())
-            InterpretTail( SCITP_NORMAL);
+            InterpretTail( SCITP_NORMAL, true);
 #endif
     }
 
@@ -1590,7 +1592,7 @@ void ScFormulaCell::Interpret()
                     bResumeIteration = false;
                     // Close circle once.
                     rRecursionHelper.GetList().back().pCell->InterpretTail(
-                            SCITP_CLOSE_ITERATION_CIRCLE);
+                            SCITP_CLOSE_ITERATION_CIRCLE, true);
                     // Start at 1, init things.
                     rRecursionHelper.StartIteration();
                     // Mark all cells being in iteration.
@@ -1619,7 +1621,7 @@ void ScFormulaCell::Interpret()
                                 pIterCell->GetSeenInIteration())
                         {
                             (*aIter).aPreviousResult = pIterCell->aResult;
-                            pIterCell->InterpretTail( SCITP_FROM_ITERATION);
+                            pIterCell->InterpretTail( SCITP_FROM_ITERATION, true);
                         }
                         rDone = rDone && !pIterCell->IsDirtyOrInTableOpDirty();
                     }
@@ -1689,7 +1691,7 @@ void ScFormulaCell::Interpret()
                         ScFormulaCell* pCell = (*aIter).pCell;
                         if (pCell->IsDirtyOrInTableOpDirty())
                         {
-                            pCell->InterpretTail( SCITP_NORMAL);
+                            pCell->InterpretTail( SCITP_NORMAL, true);
                             if (!pCell->IsDirtyOrInTableOpDirty() && !pCell->IsIterCell())
                                 pCell->bRunning = (*aIter).bOldRunning;
                         }
@@ -1722,7 +1724,7 @@ void ScFormulaCell::Interpret()
 #endif
 }
 
-void ScFormulaCell::InterpretTail( ScInterpretTailParameter eTailParam )
+void ScFormulaCell::InterpretTail( ScInterpretTailParameter eTailParam, bool bUpdateProgress )
 {
     RecursionCounter aRecursionCounter( pDocument->GetRecursionHelper(), this);
     nSeenInIteration = pDocument->GetRecursionHelper().GetIteration();
@@ -1742,7 +1744,6 @@ void ScFormulaCell::InterpretTail( ScInterpretTailParameter eTailParam )
             pCode->SetCodeError( FormulaError::NoCode );
             // This is worth an assertion; if encountered in daily work
             // documents we might need another solution. Or just confirm correctness.
-            OSL_FAIL( "ScFormulaCell::Interpret: no RPN, no error, no token, but hybrid formula string" );
             return;
         }
         CompileTokenArray();
@@ -2103,11 +2104,14 @@ void ScFormulaCell::InterpretTail( ScInterpretTailParameter eTailParam )
         }
 
         // Reschedule slows the whole thing down considerably, thus only execute on percent change
-        ScProgress *pProgress = ScProgress::GetInterpretProgress();
-        if (pProgress && pProgress->Enabled())
+        if (bUpdateProgress)
         {
-            pProgress->SetStateCountDownOnPercent(
-                pDocument->GetFormulaCodeInTree()/MIN_NO_CODES_PER_PROGRESS_UPDATE );
+            ScProgress *pProgress = ScProgress::GetInterpretProgress();
+            if (pProgress && pProgress->Enabled())
+            {
+                pProgress->SetStateCountDownOnPercent(
+                    pDocument->GetFormulaCodeInTree()/MIN_NO_CODES_PER_PROGRESS_UPDATE );
+            }
         }
 
         switch (pInterpreter->GetVolatileType())
@@ -4045,6 +4049,113 @@ int splitup(int N, int K, int& A)
 
 } // anonymous namespace
 
+struct ScDependantsCalculator
+{
+    ScDocument& mrDoc;
+    ScTokenArray& mrCode;
+    ScFormulaCell& mrCell;
+    const ScAddress& mrPos;
+
+    ScDependantsCalculator(ScDocument& rDoc, ScTokenArray& rCode, ScFormulaCell& rCell, const ScAddress& rPos) :
+        mrDoc(rDoc),
+        mrCode(rCode),
+        mrCell(rCell),
+        mrPos(rPos)
+    {
+    }
+
+    // FIXME: copy-pasted from ScGroupTokenConverter. factor out somewhere else
+    bool cellIsSelfReferenceRelative(const ScAddress& rRefPos, SCROW nRelRow)
+    {
+        if (rRefPos.Col() != mrPos.Col())
+            return false;
+
+        SCROW nLen = mrCell.GetCellGroup()->mnLength;
+        SCROW nEndRow = mrPos.Row() + nLen - 1;
+
+        if (nRelRow < 0)
+        {
+            SCROW nTest = nEndRow;
+            nTest += nRelRow;
+            if (nTest >= mrPos.Row())
+                return true;
+        }
+        else if (nRelRow > 0)
+        {
+            SCROW nTest = mrPos.Row(); // top row.
+            nTest += nRelRow;
+            if (nTest <= nEndRow)
+                return true;
+        }
+
+        return false;
+    }
+
+    // FIXME: another copy-paste
+    SCROW trimLength(SCTAB nTab, SCCOL nCol1, SCCOL nCol2, SCROW nRow, SCROW nRowLen)
+    {
+        SCROW nLastRow = nRow + nRowLen - 1; // current last row.
+        nLastRow = mrDoc.GetLastDataRow(nTab, nCol1, nCol2, nLastRow);
+        if (nLastRow < (nRow + nRowLen - 1))
+        {
+            // This can end up negative! Was that the original intent, or
+            // is it accidental? Was it not like that originally but the
+            // surrounding conditions changed?
+            nRowLen = nLastRow - nRow + 1;
+            // Anyway, let's assume it doesn't make sense to return a
+            // negative value here. But should we then return 0 or 1? In
+            // the "Column is empty" case below, we return 1, why!? And,
+            // at the callsites there are tests for a zero value returned
+            // from this function (but not for a negative one).
+            if (nRowLen < 0)
+                nRowLen = 0;
+        }
+        else if (nLastRow == 0)
+            // Column is empty.
+            nRowLen = 1;
+
+        return nRowLen;
+    }
+
+    bool DoIt()
+    {
+// from ScGroupTokenConverter::convert in sc/source/core/data/grouptokenconverter.cxx
+        for (auto p: mrCode.Tokens())
+        {
+            SCROW nLen = mrCell.GetCellGroup()->mnLength;
+            switch (p->GetType())
+            {
+            case svSingleRef:
+                {
+                    ScSingleRefData aRef = *p->GetSingleRef(); // =Sheet1!A1
+                    ScAddress aRefPos = aRef.toAbs(mrPos);
+                    if (aRef.IsRowRel())
+                    {
+                        if (cellIsSelfReferenceRelative(aRefPos, aRef.Row()))
+                            return false;
+
+                        // Trim data array length to actual data range.
+                        SCROW nTrimLen = trimLength(aRefPos.Tab(), aRefPos.Col(), aRefPos.Col(), aRefPos.Row(), nLen);
+                        // Fetch double array guarantees that the length of the
+                        // returned array equals or greater than the requested
+                        // length.
+
+                        if (mrDoc.TableExists(aRefPos.Tab()) && nTrimLen)
+                        {
+                            if (!mrDoc.HandleRefArrayForParallelism(aRefPos, nTrimLen))
+                                return false;
+                        }
+                    }
+                }
+                break;
+            default:
+                break;
+            }
+        }
+        return true;
+    }
+};
+
 bool ScFormulaCell::InterpretFormulaGroup()
 {
     if (!mxGroup || !pCode)
@@ -4081,6 +4192,90 @@ bool ScFormulaCell::InterpretFormulaGroup()
         return false;
     }
 
+    if (!ScCalcConfig::isOpenCLEnabled() && std::getenv("CPU_THREADED_CALCULATION"))
+    {
+        // iterate over code in the formula ...
+        // ensure all input is pre-calculated -
+        // to avoid writing during the calculation
+        ScDependantsCalculator aCalculator(*pDocument, *pCode, *this, mxGroup->mpTopCell->aPos);
+
+        // Disable or hugely enlarge subset for S/W group
+        // threading interpreter
+
+        if (!aCalculator.DoIt())
+        {
+            mxGroup->meCalcState = sc::GroupCalcDisabled;
+            aScope.addMessage("could not do new dependencies calculation thing");
+            return false;
+        }
+
+        // Then do the threaded calculation
+
+        bool result = true;
+        class Executor : public comphelper::ThreadTask
+        {
+        private:
+            const unsigned mnThisThread;
+            const unsigned mnThreadsTotal;
+            ScDocument* mpDocument;
+            const ScAddress& mrTopPos;
+            SCROW mnLength;
+            std::vector<int>& mrResult;
+
+        public:
+            Executor(std::shared_ptr<comphelper::ThreadTaskTag>& rTag,
+                     unsigned nThisThread,
+                     unsigned nThreadsTotal,
+                     ScDocument* pDocument2,
+                     const ScAddress& rTopPos,
+                     SCROW nLength,
+                     std::vector<int>& rResult) :
+                comphelper::ThreadTask(rTag),
+                mnThisThread(nThisThread),
+                mnThreadsTotal(nThreadsTotal),
+                mpDocument(pDocument2),
+                mrTopPos(rTopPos),
+                mnLength(nLength),
+                mrResult(rResult)
+            {
+            }
+
+            virtual void doWork() override
+            {
+                mpDocument->CalculateInColumnInThread(mrTopPos, mnLength, mnThisThread, mnThreadsTotal);
+                // FIXME: How to determine whether it "worked" or not? Does it even have a  meaning? Just
+                // drop this as YAGNI?
+                mrResult[mnThisThread] = static_cast<int>(true);
+            }
+
+        };
+
+        comphelper::ThreadPool& rThreadPool(comphelper::ThreadPool::getSharedOptimalPool());
+        sal_Int32 nThreadCount = rThreadPool.getWorkerCount();
+
+        SAL_INFO("sc.threaded", "Running " << nThreadCount << " threads");
+        // Start nThreadCount new threads
+        std::vector<int> vResult(nThreadCount);
+        std::shared_ptr<comphelper::ThreadTaskTag> aTag = comphelper::ThreadPool::createThreadTaskTag();
+        for (int i = 0; i < nThreadCount; ++i)
+        {
+            rThreadPool.pushTask(new Executor(aTag, i, nThreadCount, pDocument, mxGroup->mpTopCell->aPos, mxGroup->mnLength, vResult));
+        }
+        SAL_INFO("sc.threaded", "Joining threads");
+        rThreadPool.waitUntilDone(aTag);
+        SAL_INFO("sc.threaded", "Done");
+        for (int i = 0; i < nThreadCount; ++i)
+        {
+            if (!vResult[i])
+            {
+                SAL_INFO("sc.threaded", "Thread " << i << " failed");
+                result = false;
+            }
+        }
+
+        return result;
+    }
+
     switch (pCode->GetVectorState())
     {
         case FormulaVectorEnabled:
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index 8c9f30729de0..fdafbbc6c1f8 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -2272,6 +2272,17 @@ formula::VectorRefArray ScTable::FetchVectorRefArray( SCCOL nCol, SCROW nRow1, S
     return aCol[nCol].FetchVectorRefArray(nRow1, nRow2);
 }
 
+bool ScTable::HandleRefArrayForParallelism( SCCOL nCol, SCROW nRow1, SCROW nRow2 )
+{
+    if (nRow2 < nRow1)
+        return false;
+
+    if ( !IsColValid( nCol ) || !ValidRow( nRow1 ) || !ValidRow( nRow2 ) )
+        return false;
+
+    return aCol[nCol].HandleRefArrayForParallelism(nRow1, nRow2);
+}
+
 ScRefCellValue ScTable::GetRefCellValue( SCCOL nCol, SCROW nRow )
 {
     if ( !IsColRowValid( nCol, nRow ) )
@@ -2327,6 +2338,14 @@ void ScTable::SetFormulaResults(
     aCol[nCol].SetFormulaResults(nRow, pResults, nLen);
 }
 
+void ScTable::CalculateInColumnInThread( SCCOL nCol, SCROW nRow, size_t nLen, unsigned nThisThread, unsigned nThreadsTotal)
+{
+    if (!ValidCol(nCol))
+        return;
+
+    aCol[nCol].CalculateInThread( nRow, nLen, nThisThread, nThreadsTotal );
+}
+
 #if DUMP_COLUMN_STORAGE
 void ScTable::DumpColumnStorage( SCCOL nCol ) const
 {
diff --git a/sc/source/core/tool/token.cxx b/sc/source/core/tool/token.cxx
index 696bbe8705cb..0cf7c872f031 100644
--- a/sc/source/core/tool/token.cxx
+++ b/sc/source/core/tool/token.cxx
@@ -1341,6 +1341,9 @@ void ScTokenArray::CheckToken( const FormulaToken& r )
         // It's already disabled.  No more checking needed.
         return;
 
+    if (!ScCalcConfig::isOpenCLEnabled() && std::getenv("CPU_THREADED_CALCULATION"))
+        return;
+
     OpCode eOp = r.GetOpCode();
 
     if (SC_OPCODE_START_FUNCTION <= eOp && eOp < SC_OPCODE_STOP_FUNCTION)