Use less memory for ScMatrix::Collect

The old definition would have unused mnCount s.
The template has been modified to expand functionality.
Redefined operator for sum and sum square.

Memory usage change explanation:

The old code would use an array of IterateResultMultiple.
Then use them to iterate.
The count is stored in a last IterateResultMultiple.

So if we are inputed N operators we are:
Wasting N counters.
Wasting 1 accumulator.

Solution:
We move the array to the accumulator place (inside the structure).
Then we use only N accumulators.
The structure with the array has only 1 counter.


Change-Id: I76de74214d9bcb245f009e1226020bfe4dce40d8
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/115542
Tested-by: Mike Kaganski <mike.kaganski@collabora.com>
Reviewed-by: Mike Kaganski <mike.kaganski@collabora.com>

5 files changed, 75 insertions, 86 deletions

diff --git a/sc/inc/matrixoperators.hxx b/sc/inc/matrixoperators.hxx
index 813813626350..7d994bc6067c 100644
--- a/sc/inc/matrixoperators.hxx
+++ b/sc/inc/matrixoperators.hxx
@@ -11,12 +11,13 @@
 
 
 #include <functional>
+#include <vector>
 #include "math.hxx"
 
 namespace sc::op {
 
 
-template<typename T>
+template<typename T, typename tRes>
 struct Op_
 {
     const double mInitVal;
@@ -25,13 +26,21 @@ struct Op_
         mInitVal(InitVal), maOp(aOp)
     {
     }
-    void operator()(double& rAccum, double fVal) const
+    void operator()(tRes& rAccum, double fVal) const
     {
         maOp(rAccum, fVal);
     }
 };
 
-using Op = Op_<std::function<void(double&, double)>>;
+using Op = Op_<std::function<void(double&, double)>, double>;
+using kOp = Op_<std::function<void(KahanSum&, double)>, KahanSum>;
+
+void fkOpSum(KahanSum& rAccum, double fVal);
+void fkOpSumSquare(KahanSum& rAccum, double fVal);
+
+extern kOp kOpSum;
+extern kOp kOpSumSquare;
+extern std::vector<kOp> kOpSumAndSumSquare;
 
 struct Sum
 {
diff --git a/sc/inc/scmatrix.hxx b/sc/inc/scmatrix.hxx
index c91253811398..827d500edd24 100644
--- a/sc/inc/scmatrix.hxx
+++ b/sc/inc/scmatrix.hxx
@@ -140,15 +140,17 @@ public:
      * summation algorithm,
      * https://en.wikipedia.org/wiki/Kahan_summation_algorithm
      */
+    template<typename tRes>
     struct IterateResultMultiple
     {
-        double mfFirst;
-        double mfRest;
+        std::vector<tRes> maAccumulator;
         size_t mnCount;
 
-        IterateResultMultiple(double fFirst, double fRest, size_t nCount) :
-            mfFirst(fFirst), mfRest(fRest), mnCount(nCount) {}
+        IterateResultMultiple(size_t nCount) :
+            maAccumulator(0), mnCount(nCount) {}
     };
+    typedef IterateResultMultiple<KahanSum> KahanIterateResultMultiple;
+    typedef IterateResultMultiple<double> DoubleIterateResultMultiple;
 
     /**
       * Iterator for executing one operation with the matrix data.
@@ -411,7 +413,8 @@ public:
     void DivOp(bool bFlag, double fVal, const ScMatrix& rMat) ;
     void PowOp(bool bFlag, double fVal, const ScMatrix& rMat) ;
 
-    std::vector<ScMatrix::IterateResultMultiple> Collect(const std::vector<sc::op::Op>& aOp) ;
+    DoubleIterateResultMultiple Collect(const std::vector<sc::op::Op>& aOp) ;
+    KahanIterateResultMultiple CollectKahan(const std::vector<sc::op::kOp>& aOp) ;
 
     void ExecuteOperation(const std::pair<size_t, size_t>& rStartPos, const std::pair<size_t, size_t>& rEndPos,
             DoubleOpFunction aDoubleFunc, BoolOpFunction aBoolFunc, StringOpFunction aStringFunc,
diff --git a/sc/source/core/tool/interpr3.cxx b/sc/source/core/tool/interpr3.cxx
index e8937f4501e2..9f5812a787a1 100644
--- a/sc/source/core/tool/interpr3.cxx
+++ b/sc/source/core/tool/interpr3.cxx
@@ -2739,38 +2739,23 @@ void ScInterpreter::ScFTest()
         PushIllegalParameter();
         return;
     }
-    SCSIZE nC1, nC2;
-    SCSIZE nR1, nR2;
-    pMat1->GetDimensions(nC1, nR1);
-    pMat2->GetDimensions(nC2, nR2);
-    double fCount1  = 0.0;
-    double fCount2  = 0.0;
-    double fSum1    = 0.0;
-    double fSumSqr1 = 0.0;
-    double fSum2    = 0.0;
-    double fSumSqr2 = 0.0;
-
-    std::vector<sc::op::Op> aOp;
-    aOp.emplace_back(sc::op::Op(0.0, [](double& rAccum, double fVal){rAccum += fVal;}));
-    aOp.emplace_back(sc::op::Op(0.0, [](double& rAccum, double fVal){rAccum += fVal * fVal;}));
-
-    auto aVal1 = pMat1->Collect(aOp);
-    fSum1 = aVal1[0].mfFirst + aVal1[0].mfRest;
-    fSumSqr1 = aVal1[1].mfFirst + aVal1[1].mfRest;
-    fCount1 = aVal1[2].mnCount;
-
-    auto aVal2 = pMat2->Collect(aOp);
-    fSum2 = aVal2[0].mfFirst + aVal2[0].mfRest;
-    fSumSqr2 = aVal2[1].mfFirst + aVal2[1].mfRest;
-    fCount2 = aVal2[2].mnCount;
+
+    auto aVal1 = pMat1->CollectKahan(sc::op::kOpSumAndSumSquare);
+    auto aVal2 = pMat2->CollectKahan(sc::op::kOpSumAndSumSquare);
+    double fCount1  = aVal1.mnCount;
+    double fCount2  = aVal2.mnCount;
+    KahanSum fSum1    = aVal1.maAccumulator[0];
+    KahanSum fSumSqr1 = aVal1.maAccumulator[1];
+    KahanSum fSum2    = aVal2.maAccumulator[0];
+    KahanSum fSumSqr2 = aVal2.maAccumulator[1];
 
     if (fCount1 < 2.0 || fCount2 < 2.0)
     {
         PushNoValue();
         return;
     }
-    double fS1 = (fSumSqr1-fSum1*fSum1/fCount1)/(fCount1-1.0);
-    double fS2 = (fSumSqr2-fSum2*fSum2/fCount2)/(fCount2-1.0);
+    double fS1 = (fSumSqr1-fSum1*fSum1/fCount1).get() / (fCount1-1.0);
+    double fS2 = (fSumSqr2-fSum2*fSum2/fCount2).get() / (fCount2-1.0);
     if (fS1 == 0.0 || fS2 == 0.0)
     {
         PushNoValue();
diff --git a/sc/source/core/tool/matrixoperators.cxx b/sc/source/core/tool/matrixoperators.cxx
index 780f789ed94f..9406d09255c4 100644
--- a/sc/source/core/tool/matrixoperators.cxx
+++ b/sc/source/core/tool/matrixoperators.cxx
@@ -11,6 +11,8 @@
 
 namespace sc::op
 {
+/* Simple operators */
+
 void Sum::operator()(KahanSum& rAccum, double fVal) const { rAccum += fVal; }
 
 const double Sum::InitVal = 0.0;
@@ -22,6 +24,18 @@ const double SumSquare::InitVal = 0.0;
 void Product::operator()(double& rAccum, double fVal) const { rAccum *= fVal; }
 
 const double Product::InitVal = 1.0;
+
+/* Op operators */
+
+void fkOpSum(KahanSum& rAccum, double fVal) { rAccum += fVal; }
+
+kOp kOpSum(0.0, fkOpSum);
+
+void fkOpSumSquare(KahanSum& rAccum, double fVal) { rAccum += fVal * fVal; }
+
+kOp kOpSumSquare(0.0, fkOpSumSquare);
+
+std::vector<kOp> kOpSumAndSumSquare = { kOpSum, kOpSumSquare };
 }
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/tool/scmatrix.cxx b/sc/source/core/tool/scmatrix.cxx
index d3c8667c66c1..06e1da42e079 100644
--- a/sc/source/core/tool/scmatrix.cxx
+++ b/sc/source/core/tool/scmatrix.cxx
@@ -327,8 +327,8 @@ public:
             const ScMatrix::BoolOpFunction& aBoolFunc, const ScMatrix::StringOpFunction& aStringFunc,
             const ScMatrix::EmptyOpFunction& aEmptyFunc) const;
 
-    template<typename T>
-    std::vector<ScMatrix::IterateResultMultiple> ApplyCollectOperation(const std::vector<T>& aOp);
+    template<typename T, typename tRes>
+    ScMatrix::IterateResultMultiple<tRes> ApplyCollectOperation(const std::vector<T>& aOp);
 
     void MatConcat(SCSIZE nMaxCol, SCSIZE nMaxRow, const ScMatrixRef& xMat1, const ScMatrixRef& xMat2,
             SvNumberFormatter& rFormatter, svl::SharedStringPool& rPool);
@@ -1169,38 +1169,37 @@ public:
     }
 };
 
-template<typename Op>
+template<typename Op, typename tRes>
 class WalkElementBlocksMultipleValues
 {
     const std::vector<Op>* mpOp;
-    std::vector<ScMatrix::IterateResultMultiple> maRes;
-    bool mbFirst:1;
+    ScMatrix::IterateResultMultiple<tRes> maRes;
 public:
     WalkElementBlocksMultipleValues(const std::vector<Op>& aOp) :
-        mpOp(&aOp), mbFirst(true)
+        mpOp(&aOp), maRes(0)
     {
         for (const auto& rpOp : *mpOp)
-        {
-            maRes.emplace_back(rpOp.mInitVal, rpOp.mInitVal, 0);
-        }
-        maRes.emplace_back(0.0, 0.0, 0); // count
+            maRes.maAccumulator.emplace_back(rpOp.mInitVal);
     }
 
     WalkElementBlocksMultipleValues( const WalkElementBlocksMultipleValues& ) = delete;
     WalkElementBlocksMultipleValues& operator= ( const WalkElementBlocksMultipleValues& ) = delete;
 
-    WalkElementBlocksMultipleValues(WalkElementBlocksMultipleValues&& r) noexcept :
-        mpOp(r.mpOp), maRes(std::move(r.maRes)), mbFirst(r.mbFirst) {}
+    WalkElementBlocksMultipleValues(WalkElementBlocksMultipleValues&& r) noexcept
+    : mpOp(r.mpOp), maRes(r.maRes.mnCount)
+    {
+        maRes.maAccumulator = std::move(r.maRes.maAccumulator);
+    }
 
     WalkElementBlocksMultipleValues& operator=(WalkElementBlocksMultipleValues&& r) noexcept
     {
         mpOp = r.mpOp;
-        maRes = std::move(r.maRes);
-        mbFirst = r.mbFirst;
+        maRes.maAccumulator = std::move(r.maRes.maAccumulator);
+        maRes.mnCount = r.maRes.mnCount;
         return *this;
     }
 
-    const std::vector<ScMatrix::IterateResultMultiple>& getResult() const { return maRes; }
+    const ScMatrix::IterateResultMultiple<tRes>& getResult() const { return maRes; }
 
     void operator() (const MatrixImplType::element_block_node_type& node)
     {
@@ -1214,23 +1213,10 @@ public:
                 block_type::const_iterator itEnd = block_type::end(*node.data);
                 for (; it != itEnd; ++it)
                 {
-                    if (mbFirst)
-                    {
-                        for (size_t i = 0u; i < mpOp->size(); ++i)
-                        {
-                            (*mpOp)[i](maRes[i].mfFirst, *it);
-                        }
-                        mbFirst = false;
-                    }
-                    else
-                    {
-                        for (size_t i = 0u; i < mpOp->size(); ++i)
-                        {
-                            (*mpOp)[i](maRes[i].mfRest, *it);
-                        }
-                    }
+                    for (size_t i = 0u; i < mpOp->size(); ++i)
+                        (*mpOp)[i](maRes.maAccumulator[i], *it);
                 }
-                maRes.back().mnCount += node.size;
+                maRes.mnCount += node.size;
             }
             break;
             case mdds::mtm::element_boolean:
@@ -1241,23 +1227,10 @@ public:
                 block_type::const_iterator itEnd = block_type::end(*node.data);
                 for (; it != itEnd; ++it)
                 {
-                    if (mbFirst)
-                    {
-                        for (size_t i = 0u; i < mpOp->size(); ++i)
-                        {
-                            (*mpOp)[i](maRes[i].mfFirst, *it);
-                        }
-                        mbFirst = false;
-                    }
-                    else
-                    {
-                        for (size_t i = 0u; i < mpOp->size(); ++i)
-                        {
-                            (*mpOp)[i](maRes[i].mfRest, *it);
-                        }
-                    }
+                    for (size_t i = 0u; i < mpOp->size(); ++i)
+                        (*mpOp)[i](maRes.maAccumulator[i], *it);
                 }
-                maRes.back().mnCount += node.size;
+                maRes.mnCount += node.size;
             }
             break;
             case mdds::mtm::element_string:
@@ -2422,10 +2395,10 @@ void ScMatrixImpl::ApplyOperation(T aOp, ScMatrixImpl& rMat)
     maMat.walk(aFunc);
 }
 
-template<typename T>
-std::vector<ScMatrix::IterateResultMultiple> ScMatrixImpl::ApplyCollectOperation(const std::vector<T>& aOp)
+template<typename T, typename tRes>
+ScMatrix::IterateResultMultiple<tRes> ScMatrixImpl::ApplyCollectOperation(const std::vector<T>& aOp)
 {
-    WalkElementBlocksMultipleValues<T> aFunc(aOp);
+    WalkElementBlocksMultipleValues<T, tRes> aFunc(aOp);
     aFunc = maMat.walk(std::move(aFunc));
     return aFunc.getResult();
 }
@@ -3425,9 +3398,14 @@ void ScMatrix::ExecuteOperation(const std::pair<size_t, size_t>& rStartPos,
     pImpl->ExecuteOperation(rStartPos, rEndPos, aDoubleFunc, aBoolFunc, aStringFunc, aEmptyFunc);
 }
 
-std::vector<ScMatrix::IterateResultMultiple> ScMatrix::Collect(const std::vector<sc::op::Op>& aOp)
+ScMatrix::DoubleIterateResultMultiple ScMatrix::Collect(const std::vector<sc::op::Op>& aOp)
+{
+    return pImpl->ApplyCollectOperation<sc::op::Op, double>(aOp);
+}
+
+ScMatrix::KahanIterateResultMultiple ScMatrix::CollectKahan(const std::vector<sc::op::kOp>& aOp)
 {
-    return pImpl->ApplyCollectOperation(aOp);
+    return pImpl->ApplyCollectOperation<sc::op::kOp, KahanSum>(aOp);
 }
 
 #if DEBUG_MATRIX