Cache the vConditions array...

used in ScInterpreter::IterateParameterIfs(). Store this
cache as a member of ScInterpreterContext (maConditions).

Create a static pool of ScInterpreterContext's so that
the embedded maConditions is reused everytime a formula-group/
formula-cell is calculated. There needs to be two separate
static pools - one for threading, one for non-threaded
computation of formula-cells. With this, we can have better
performance of the cached maConditions as well as
mScLookupCache. In threaded case there is no recursive
computation of cells as dependencies are all pre-computed.

The thread-indexed lookup cache array in ScDocument is
removed as now the lookup caches on context lives as long
in the static context pools.

This cached vConditions array can take advantage
when there are lots of SUMIFS/COUNTIFS with arguments of
similar dimensions in the document. Otherwise it will be
allocated from scratch for every COUNTIFS/SUMIFS formula-cell.

Change-Id: I654b05e55035ce6efcf07d32d36623c9d76b0ff6
Reviewed-on: https://gerrit.libreoffice.org/63066
Tested-by: Jenkins
Reviewed-by: Dennis Francis <dennis.francis@collabora.com>

7 files changed, 268 insertions, 35 deletions

diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index 22ce96e010ef..603d9590033a 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -457,7 +457,6 @@ private:
     mutable ScInterpreterContext maInterpreterContext;
 
     osl::Mutex mScLookupMutex; // protection for thread-unsafe parts of handling ScLookup
-    std::vector<ScLookupCacheMap*> mThreadStoredScLookupCaches; // temporarily stored for computation threads
 
     static const sal_uInt16 nSrcVer;                        // file version (load/save)
     sal_uInt16              nFormulaTrackCount;
diff --git a/sc/inc/interpretercontext.hxx b/sc/inc/interpretercontext.hxx
index b12bf17410a4..2b690e311b8c 100644
--- a/sc/inc/interpretercontext.hxx
+++ b/sc/inc/interpretercontext.hxx
@@ -11,6 +11,7 @@
 #define INCLUDED_SC_INC_INTERPRETERCONTEXT_HXX
 
 #include <vector>
+#include <memory>
 #include "types.hxx"
 
 namespace formula
@@ -31,17 +32,22 @@ struct DelayedSetNumberFormat
     sal_uInt32 mnNumberFormat;
 };
 
+class ScInterpreterContextPool;
+
 struct ScInterpreterContext
 {
-    const ScDocument& mrDoc;
+    const ScDocument* mpDoc;
     SvNumberFormatter* mpFormatter;
     size_t mnTokenCachePos;
     std::vector<formula::FormulaToken*> maTokens;
     std::vector<DelayedSetNumberFormat> maDelayedSetNumberFormat;
     ScLookupCacheMap* mScLookupCache; // cache for lookups like VLOOKUP and MATCH
+    // Allocation cache for "aConditions" array in ScInterpreter::IterateParameterIfs()
+    // This is populated/used only when formula-group threading is enabled.
+    std::vector<sal_uInt32> maConditions;
 
     ScInterpreterContext(const ScDocument& rDoc, SvNumberFormatter* pFormatter)
-        : mrDoc(rDoc)
+        : mpDoc(&rDoc)
         , mpFormatter(pFormatter)
         , mnTokenCachePos(0)
         , maTokens(TOKEN_CACHE_SIZE, nullptr)
@@ -49,9 +55,94 @@ struct ScInterpreterContext
     {
     }
 
+    ScInterpreterContext() = delete;
+
     ~ScInterpreterContext();
 
     SvNumberFormatter* GetFormatTable() const { return mpFormatter; }
+
+private:
+    friend class ScInterpreterContextPool;
+    void ResetTokens();
+    void SetDocAndFormatter(const ScDocument& rDoc, SvNumberFormatter* pFormatter);
+    void Cleanup();
+    void ClearLookupCache();
+};
+
+class ScThreadedInterpreterContextGetterGuard;
+class ScInterpreterContextGetterGuard;
+
+class ScInterpreterContextPool
+{
+    friend class ScThreadedInterpreterContextGetterGuard;
+    friend class ScInterpreterContextGetterGuard;
+
+    std::vector<std::unique_ptr<ScInterpreterContext>> maPool;
+    size_t mnNextFree;
+    bool mbThreaded;
+
+    ScInterpreterContextPool(bool bThreaded)
+        : mnNextFree(0)
+        , mbThreaded(bThreaded)
+    {
+    }
+
+    ~ScInterpreterContextPool() {}
+
+    static ScInterpreterContextPool aThreadedInterpreterPool;
+    static ScInterpreterContextPool aNonThreadedInterpreterPool;
+
+    // API for threaded case
+
+    // Ensures nNumThreads elements in pool.
+    void Init(size_t nNumThreads, const ScDocument& rDoc, SvNumberFormatter* pFormatter);
+
+    // Returns ScInterpreterContext* for thread index nThreadIdx
+    ScInterpreterContext* GetInterpreterContextForThreadIdx(size_t nThreadIdx) const;
+
+    // API for non-threaded
+
+    // Ensures there is one unused element in the pool.
+    void Init(const ScDocument& rDoc, SvNumberFormatter* pFormatter);
+
+    // Returns ScInterpreterContext* for non-threaded use.
+    ScInterpreterContext* GetInterpreterContext() const;
+
+    // Common API for threaded/non-threaded
+
+    // Cleans up the contexts prepared by call to immediately previous Init() and
+    // marks them all as unused.
+    void ReturnToPool();
+
+public:
+    // Only to be used to clear lookup cache in all pool elements
+    static void ClearLookupCaches();
+};
+
+class ScThreadedInterpreterContextGetterGuard
+{
+    ScInterpreterContextPool& rPool;
+
+public:
+    ScThreadedInterpreterContextGetterGuard(size_t nNumThreads, const ScDocument& rDoc,
+                                            SvNumberFormatter* pFormatter);
+    ~ScThreadedInterpreterContextGetterGuard();
+
+    // Returns ScInterpreterContext* for thread index nThreadIdx
+    ScInterpreterContext* GetInterpreterContextForThreadIdx(size_t nThreadIdx) const;
+};
+
+class ScInterpreterContextGetterGuard
+{
+    ScInterpreterContextPool& rPool;
+    size_t nContextIdx;
+
+public:
+    ScInterpreterContextGetterGuard(const ScDocument& rDoc, SvNumberFormatter* pFormatter);
+    ~ScInterpreterContextGetterGuard();
+
+    // Returns ScInterpreterContext* for non-threaded use.
+    ScInterpreterContext* GetInterpreterContext() const;
 };
 
 #endif // INCLUDED_SC_INC_INTERPRETERCONTEXT_HXX
diff --git a/sc/source/core/data/documen2.cxx b/sc/source/core/data/documen2.cxx
index 9d8d8c5115bf..8ca890344a74 100644
--- a/sc/source/core/data/documen2.cxx
+++ b/sc/source/core/data/documen2.cxx
@@ -1163,9 +1163,8 @@ void ScDocument::ClearLookupCaches()
 {
     assert(!IsThreadedGroupCalcInProgress());
     DELETEZ(GetNonThreadedContext().mScLookupCache);
-    for( ScLookupCacheMap* cacheMap : mThreadStoredScLookupCaches )
-        delete cacheMap;
-    mThreadStoredScLookupCaches.clear();
+    // Clear lookup cache in all interpreter-contexts in the (threaded/non-threaded) pools.
+    ScInterpreterContextPool::ClearLookupCaches();
 }
 
 bool ScDocument::IsCellInChangeTrack(const ScAddress &cell,Color *pColCellBorder)
diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx
index 7dc5998643f3..abda9f677f36 100644
--- a/sc/source/core/data/document.cxx
+++ b/sc/source/core/data/document.cxx
@@ -6751,20 +6751,12 @@ void ScDocumentThreadSpecific::MergeBackIntoNonThreadedData(ScDocumentThreadSpec
     // What about recursion helper and lookup cache?
 }
 
-void ScDocument::SetupFromNonThreadedContext(ScInterpreterContext& threadedContext, int threadNumber)
+void ScDocument::SetupFromNonThreadedContext(ScInterpreterContext& /*threadedContext*/, int /*threadNumber*/)
 {
-    if(int(mThreadStoredScLookupCaches.size()) >= threadNumber + 1 ) // 0-indexed
-    {
-        // It is necessary to store the VLOOKUP cache between threaded formula runs, because the results
-        // are to be shared between different formula group cells (it caches the same row for different
-        // columns). Therefore also use the thread index to make sure each thread gets back its cache,
-        // as it is decided based on thread number which rows in a formula group it handles.
-        threadedContext.mScLookupCache = mThreadStoredScLookupCaches[ threadNumber ];
-        mThreadStoredScLookupCaches[ threadNumber ] = nullptr;
-    }
+    // lookup cache is now only in pooled ScInterpreterContext's
 }
 
-void ScDocument::MergeBackIntoNonThreadedContext(ScInterpreterContext& threadedContext, int threadNumber)
+void ScDocument::MergeBackIntoNonThreadedContext(ScInterpreterContext& threadedContext, int /*threadNumber*/)
 {
     // Move data from a context used by a calculation thread to the main thread's context.
     // Called from the main thread after the calculation thread has already finished.
@@ -6773,13 +6765,7 @@ void ScDocument::MergeBackIntoNonThreadedContext(ScInterpreterContext& threadedC
         maInterpreterContext.maDelayedSetNumberFormat.end(),
         std::make_move_iterator(threadedContext.maDelayedSetNumberFormat.begin()),
         std::make_move_iterator(threadedContext.maDelayedSetNumberFormat.end()));
-    if( threadedContext.mScLookupCache )
-    {
-        if(int(mThreadStoredScLookupCaches.size()) < threadNumber + 1 ) // 0-indexed
-            mThreadStoredScLookupCaches.resize( threadNumber + 1 );
-        mThreadStoredScLookupCaches[ threadNumber ] = threadedContext.mScLookupCache;
-        threadedContext.mScLookupCache = nullptr;
-    }
+    // lookup cache is now only in pooled ScInterpreterContext's
 }
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/formulacell.cxx b/sc/source/core/data/formulacell.cxx
index 5297c42afe12..187007f83b79 100644
--- a/sc/source/core/data/formulacell.cxx
+++ b/sc/source/core/data/formulacell.cxx
@@ -1605,7 +1605,8 @@ void ScFormulaCell::Interpret()
             }
 
             ScFormulaGroupCycleCheckGuard aCycleCheckGuard(rRecursionHelper, this);
-            InterpretTail( pDocument->GetNonThreadedContext(), SCITP_NORMAL);
+            ScInterpreterContextGetterGuard aContextGetterGuard(*pDocument, pDocument->GetFormatTable());
+            InterpretTail( *aContextGetterGuard.GetInterpreterContext(), SCITP_NORMAL);
         }
 
         pDocument->DecInterpretLevel();
@@ -1679,8 +1680,9 @@ void ScFormulaCell::Interpret()
                             ((pLastCell = rRecursionHelper.GetList().back().pCell) != this))
                     {
                         pDocument->IncInterpretLevel();
+                        ScInterpreterContextGetterGuard aContextGetterGuard(*pDocument, pDocument->GetFormatTable());
                         pLastCell->InterpretTail(
-                                pDocument->GetNonThreadedContext(), SCITP_CLOSE_ITERATION_CIRCLE);
+                            *aContextGetterGuard.GetInterpreterContext(), SCITP_CLOSE_ITERATION_CIRCLE);
                         pDocument->DecInterpretLevel();
                     }
                     // Start at 1, init things.
@@ -1716,7 +1718,8 @@ void ScFormulaCell::Interpret()
                         {
                             (*aIter).aPreviousResult = pIterCell->aResult;
                             pDocument->IncInterpretLevel();
-                            pIterCell->InterpretTail( pDocument->GetNonThreadedContext(), SCITP_FROM_ITERATION);
+                            ScInterpreterContextGetterGuard aContextGetterGuard(*pDocument, pDocument->GetFormatTable());
+                            pIterCell->InterpretTail( *aContextGetterGuard.GetInterpreterContext(), SCITP_FROM_ITERATION);
                             pDocument->DecInterpretLevel();
                         }
                         if (bFirst)
@@ -1810,7 +1813,8 @@ void ScFormulaCell::Interpret()
                         if (pCell->IsDirtyOrInTableOpDirty())
                         {
                             pDocument->IncInterpretLevel();
-                            pCell->InterpretTail( pDocument->GetNonThreadedContext(), SCITP_NORMAL);
+                            ScInterpreterContextGetterGuard aContextGetterGuard(*pDocument, pDocument->GetFormatTable());
+                            pCell->InterpretTail( *aContextGetterGuard.GetInterpreterContext(), SCITP_NORMAL);
                             pDocument->DecInterpretLevel();
                             if (!pCell->IsDirtyOrInTableOpDirty() && !pCell->IsIterCell())
                                 pCell->bRunning = (*aIter).bOldRunning;
@@ -4679,12 +4683,13 @@ bool ScFormulaCell::InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope
 
             // Start nThreadCount new threads
             std::shared_ptr<comphelper::ThreadTaskTag> aTag = comphelper::ThreadPool::createThreadTaskTag();
-            std::vector<ScInterpreterContext*> contexts(nThreadCount);
+            ScThreadedInterpreterContextGetterGuard aContextGetterGuard(nThreadCount, *pDocument, pNonThreadedFormatter);
+            ScInterpreterContext* context = nullptr;
             for (int i = 0; i < nThreadCount; ++i)
             {
-                contexts[i] = new ScInterpreterContext(*pDocument, pNonThreadedFormatter);
-                pDocument->SetupFromNonThreadedContext(*contexts[i], i);
-                rThreadPool.pushTask(o3tl::make_unique<Executor>(aTag, i, nThreadCount, pDocument, contexts[i], mxGroup->mpTopCell->aPos, mxGroup->mnLength));
+                context = aContextGetterGuard.GetInterpreterContextForThreadIdx(i);
+                pDocument->SetupFromNonThreadedContext(*context, i);
+                rThreadPool.pushTask(o3tl::make_unique<Executor>(aTag, i, nThreadCount, pDocument, context, mxGroup->mpTopCell->aPos, mxGroup->mnLength));
             }
 
             SAL_INFO("sc.threaded", "Joining threads");
@@ -4694,9 +4699,9 @@ bool ScFormulaCell::InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope
 
             for (int i = 0; i < nThreadCount; ++i)
             {
+                context = aContextGetterGuard.GetInterpreterContextForThreadIdx(i);
                 // This is intentionally done in this main thread in order to avoid locking.
-                pDocument->MergeBackIntoNonThreadedContext(*contexts[i], i);
-                delete contexts[i];
+                pDocument->MergeBackIntoNonThreadedContext(*context, i);
             }
 
             SAL_INFO("sc.threaded", "Done");
diff --git a/sc/source/core/tool/interpr1.cxx b/sc/source/core/tool/interpr1.cxx
index f752ff00841a..8ba1e6e32338 100644
--- a/sc/source/core/tool/interpr1.cxx
+++ b/sc/source/core/tool/interpr1.cxx
@@ -5835,7 +5835,12 @@ void ScInterpreter::IterateParametersIfs( double(*ResultFunc)( const sc::ParamIf
     sal_uInt8 nParamCount = GetByte();
     sal_uInt8 nQueryCount = nParamCount / 2;
 
-    std::vector<sal_uInt32> vConditions;
+    std::vector<sal_uInt32>& vConditions = mrContext.maConditions;
+    // vConditions is cached, although it is clear'ed after every cell is interpreted,
+    // if the SUMIFS/COUNTIFS are part of a matrix formula, then that is not enough because
+    // with a single InterpretTail() call it results in evaluation of all the cells in the
+    // matrix formula.
+    vConditions.clear();
     double fVal = 0.0;
     SCCOL nDimensionCols = 0;
     SCROW nDimensionRows = 0;
diff --git a/sc/source/core/tool/interpretercontext.cxx b/sc/source/core/tool/interpretercontext.cxx
index e7fe0fef6593..076ed25a0fc2 100644
--- a/sc/source/core/tool/interpretercontext.cxx
+++ b/sc/source/core/tool/interpretercontext.cxx
@@ -20,13 +20,161 @@
 #include <interpretercontext.hxx>
 #include <formula/token.hxx>
 #include <lookupcache.hxx>
+#include <algorithm>
+
+ScInterpreterContextPool ScInterpreterContextPool::aThreadedInterpreterPool(true);
+ScInterpreterContextPool ScInterpreterContextPool::aNonThreadedInterpreterPool(false);
 
 ScInterpreterContext::~ScInterpreterContext()
 {
+    ResetTokens();
+    delete mScLookupCache;
+}
+
+void ScInterpreterContext::ResetTokens()
+{
     for (auto p : maTokens)
         if (p)
             p->DecRef();
+
+    mnTokenCachePos = 0;
+    std::fill(maTokens.begin(), maTokens.end(), nullptr);
+}
+
+void ScInterpreterContext::SetDocAndFormatter(const ScDocument& rDoc, SvNumberFormatter* pFormatter)
+{
+    mpDoc = &rDoc;
+    mpFormatter = pFormatter;
+}
+
+void ScInterpreterContext::Cleanup()
+{
+    // Do not disturb mScLookupCache
+    maConditions.clear();
+    maDelayedSetNumberFormat.clear();
+    ResetTokens();
+}
+
+void ScInterpreterContext::ClearLookupCache()
+{
     delete mScLookupCache;
+    mScLookupCache = nullptr;
+}
+
+/* ScInterpreterContextPool */
+
+// Threaded version
+void ScInterpreterContextPool::Init(size_t nNumThreads, const ScDocument& rDoc,
+                                    SvNumberFormatter* pFormatter)
+{
+    assert(mbThreaded);
+    size_t nOldSize = maPool.size();
+    maPool.resize(nNumThreads);
+    for (size_t nIdx = 0; nIdx < nNumThreads; ++nIdx)
+    {
+        if (nIdx >= nOldSize)
+            maPool[nIdx].reset(new ScInterpreterContext(rDoc, pFormatter));
+        else
+            maPool[nIdx]->SetDocAndFormatter(rDoc, pFormatter);
+    }
+}
+
+ScInterpreterContext*
+ScInterpreterContextPool::GetInterpreterContextForThreadIdx(size_t nThreadIdx) const
+{
+    assert(mbThreaded);
+    assert(nThreadIdx < maPool.size());
+    return maPool[nThreadIdx].get();
+}
+
+// Non-Threaded version
+void ScInterpreterContextPool::Init(const ScDocument& rDoc, SvNumberFormatter* pFormatter)
+{
+    assert(!mbThreaded);
+    assert(mnNextFree <= maPool.size());
+    bool bCreateNew = (maPool.size() == mnNextFree);
+    size_t nCurrIdx = mnNextFree;
+    if (bCreateNew)
+    {
+        maPool.resize(maPool.size() + 1);
+        maPool[nCurrIdx].reset(new ScInterpreterContext(rDoc, pFormatter));
+    }
+    else
+        maPool[nCurrIdx]->SetDocAndFormatter(rDoc, pFormatter);
+
+    ++mnNextFree;
+}
+
+ScInterpreterContext* ScInterpreterContextPool::GetInterpreterContext() const
+{
+    assert(!mbThreaded);
+    assert(mnNextFree && (mnNextFree <= maPool.size()));
+    return maPool[mnNextFree - 1].get();
+}
+
+void ScInterpreterContextPool::ReturnToPool()
+{
+    if (mbThreaded)
+    {
+        for (size_t nIdx = 0; nIdx < maPool.size(); ++nIdx)
+            maPool[nIdx]->Cleanup();
+    }
+    else
+    {
+        assert(mnNextFree && (mnNextFree <= maPool.size()));
+        --mnNextFree;
+        maPool[mnNextFree]->Cleanup();
+    }
+}
+
+// static
+void ScInterpreterContextPool::ClearLookupCaches()
+{
+    for (auto& rPtr : aThreadedInterpreterPool.maPool)
+        rPtr->ClearLookupCache();
+    for (auto& rPtr : aNonThreadedInterpreterPool.maPool)
+        rPtr->ClearLookupCache();
+}
+
+/* ScThreadedInterpreterContextGetterGuard */
+
+ScThreadedInterpreterContextGetterGuard::ScThreadedInterpreterContextGetterGuard(
+    size_t nNumThreads, const ScDocument& rDoc, SvNumberFormatter* pFormatter)
+    : rPool(ScInterpreterContextPool::aThreadedInterpreterPool)
+{
+    rPool.Init(nNumThreads, rDoc, pFormatter);
+}
+
+ScThreadedInterpreterContextGetterGuard::~ScThreadedInterpreterContextGetterGuard()
+{
+    rPool.ReturnToPool();
+}
+
+ScInterpreterContext*
+ScThreadedInterpreterContextGetterGuard::GetInterpreterContextForThreadIdx(size_t nThreadIdx) const
+{
+    return rPool.GetInterpreterContextForThreadIdx(nThreadIdx);
+}
+
+/* ScInterpreterContextGetterGuard */
+
+ScInterpreterContextGetterGuard::ScInterpreterContextGetterGuard(const ScDocument& rDoc,
+                                                                 SvNumberFormatter* pFormatter)
+    : rPool(ScInterpreterContextPool::aNonThreadedInterpreterPool)
+    , nContextIdx(rPool.mnNextFree)
+{
+    rPool.Init(rDoc, pFormatter);
+}
+
+ScInterpreterContextGetterGuard::~ScInterpreterContextGetterGuard()
+{
+    assert(nContextIdx == (rPool.mnNextFree - 1));
+    rPool.ReturnToPool();
+}
+
+ScInterpreterContext* ScInterpreterContextGetterGuard::GetInterpreterContext() const
+{
+    return rPool.GetInterpreterContext();
 }
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */