From a07d0b6b30c95f2d1f8fd687d3bffc7ec433a75d Mon Sep 17 00:00:00 2001 From: Noel Grandin Date: Thu, 22 Dec 2022 18:41:19 +0200 Subject: [PATCH] optimise SUMPRODUCT(IF..) a little Move the AddSub calculation inside ScMatrix so we can use an iterator to walk the matrix and avoid lookup cost for each element. Shaves 50% off the time spent here in my test sheet. Change-Id: I171d7dd4ae86419a563342a4120d14106e8d71db Reviewed-on: https://gerrit.libreoffice.org/c/core/+/144826 Tested-by: Jenkins Reviewed-by: Noel Grandin --- sc/inc/scmatrix.hxx | 5 + sc/source/core/tool/interpr5.cxx | 109 ++++-------------- sc/source/core/tool/scmatrix.cxx | 231 ++++++++++++++++++++++++++++++++++++--- 3 files changed, 243 insertions(+), 102 deletions(-) diff --git a/sc/inc/scmatrix.hxx b/sc/inc/scmatrix.hxx index fdb870f40a1d..8eb4ae7fde76 100644 --- a/sc/inc/scmatrix.hxx +++ b/sc/inc/scmatrix.hxx @@ -118,6 +118,7 @@ public: typedef std::function BoolOpFunction; typedef std::function StringOpFunction; typedef std::function EmptyOpFunction; + typedef std::function CalculateOpFunction; /** * When adding all numerical matrix elements for a scalar result such as @@ -410,6 +411,10 @@ public: void MatConcat(SCSIZE nMaxCol, SCSIZE nMaxRow, const ScMatrixRef& xMat1, const ScMatrixRef& xMat2, SvNumberFormatter& rFormatter, svl::SharedStringPool& rPool) ; + /** Apply binary operation to values from two input matrices, storing result into this matrix. */ + void ExecuteBinaryOp(SCSIZE nMaxCol, SCSIZE nMaxRow, const ScMatrix& rInputMat1, const ScMatrix& rInputMat2, + ScInterpreter* pInterpreter, CalculateOpFunction op); + #if DEBUG_MATRIX void Dump() const; #endif diff --git a/sc/source/core/tool/interpr5.cxx b/sc/source/core/tool/interpr5.cxx index cdb07fa9ca22..b27e27c5e188 100644 --- a/sc/source/core/tool/interpr5.cxx +++ b/sc/source/core/tool/interpr5.cxx @@ -47,45 +47,30 @@ using namespace formula; namespace { -struct MatrixAdd +double MatrixAdd(const double& lhs, const double& rhs) { - double operator() (const double& lhs, const double& rhs) const - { - return ::rtl::math::approxAdd( lhs,rhs); - } -}; + return ::rtl::math::approxAdd( lhs,rhs); +} -struct MatrixSub +double MatrixSub(const double& lhs, const double& rhs) { - double operator() (const double& lhs, const double& rhs) const - { - return ::rtl::math::approxSub( lhs,rhs); - } -}; + return ::rtl::math::approxSub( lhs,rhs); +} -struct MatrixMul +double MatrixMul(const double& lhs, const double& rhs) { - double operator() (const double& lhs, const double& rhs) const - { - return lhs * rhs; - } -}; + return lhs * rhs; +} -struct MatrixDiv +double MatrixDiv(const double& lhs, const double& rhs) { - double operator() (const double& lhs, const double& rhs) const - { - return ScInterpreter::div( lhs,rhs); - } -}; + return ScInterpreter::div( lhs,rhs); +} -struct MatrixPow +double MatrixPow(const double& lhs, const double& rhs) { - double operator() (const double& lhs, const double& rhs) const - { - return ::pow( lhs,rhs); - } -}; + return ::pow( lhs,rhs); +} // Multiply n x m Mat A with m x l Mat B to n x l Mat R void lcl_MFastMult(const ScMatrixRef& pA, const ScMatrixRef& pB, const ScMatrixRef& pR, @@ -1164,66 +1149,18 @@ static SCSIZE lcl_GetMinExtent( SCSIZE n1, SCSIZE n2 ) return n2; } -template static ScMatrixRef lcl_MatrixCalculation( - const ScMatrix& rMat1, const ScMatrix& rMat2, ScInterpreter* pInterpreter) + const ScMatrix& rMat1, const ScMatrix& rMat2, ScInterpreter* pInterpreter, ScMatrix::CalculateOpFunction Op) { - static const Function Op; - SCSIZE nC1, nC2, nMinC; SCSIZE nR1, nR2, nMinR; - SCSIZE i, j; rMat1.GetDimensions(nC1, nR1); rMat2.GetDimensions(nC2, nR2); nMinC = lcl_GetMinExtent( nC1, nC2); nMinR = lcl_GetMinExtent( nR1, nR2); ScMatrixRef xResMat = pInterpreter->GetNewMat(nMinC, nMinR, /*bEmpty*/true); if (xResMat) - { - for (i = 0; i < nMinC; i++) - { - for (j = 0; j < nMinR; j++) - { - bool bVal1 = rMat1.IsValueOrEmpty(i,j); - bool bVal2 = rMat2.IsValueOrEmpty(i,j); - FormulaError nErr; - if (bVal1 && bVal2) - { - double d = Op(rMat1.GetDouble(i,j), rMat2.GetDouble(i,j)); - xResMat->PutDouble( d, i, j); - } - else if (((nErr = rMat1.GetErrorIfNotString(i,j)) != FormulaError::NONE) || - ((nErr = rMat2.GetErrorIfNotString(i,j)) != FormulaError::NONE)) - { - xResMat->PutError( nErr, i, j); - } - else if ((!bVal1 && rMat1.IsStringOrEmpty(i,j)) || (!bVal2 && rMat2.IsStringOrEmpty(i,j))) - { - FormulaError nError1 = FormulaError::NONE; - SvNumFormatType nFmt1 = SvNumFormatType::ALL; - double fVal1 = (bVal1 ? rMat1.GetDouble(i,j) : - pInterpreter->ConvertStringToValue( rMat1.GetString(i,j).getString(), nError1, nFmt1)); - - FormulaError nError2 = FormulaError::NONE; - SvNumFormatType nFmt2 = SvNumFormatType::ALL; - double fVal2 = (bVal2 ? rMat2.GetDouble(i,j) : - pInterpreter->ConvertStringToValue( rMat2.GetString(i,j).getString(), nError2, nFmt2)); - - if (nError1 != FormulaError::NONE) - xResMat->PutError( nError1, i, j); - else if (nError2 != FormulaError::NONE) - xResMat->PutError( nError2, i, j); - else - { - double d = Op( fVal1, fVal2); - xResMat->PutDouble( d, i, j); - } - } - else - xResMat->PutError( FormulaError::NoValue, i, j); - } - } - } + xResMat->ExecuteBinaryOp(nMinC, nMinR, rMat1, rMat2, pInterpreter, Op); return xResMat; } @@ -1337,11 +1274,11 @@ void ScInterpreter::CalculateAddSub(bool _bSub) ScMatrixRef pResMat; if ( _bSub ) { - pResMat = lcl_MatrixCalculation( *pMat1, *pMat2, this); + pResMat = lcl_MatrixCalculation( *pMat1, *pMat2, this, MatrixSub); } else { - pResMat = lcl_MatrixCalculation( *pMat1, *pMat2, this); + pResMat = lcl_MatrixCalculation( *pMat1, *pMat2, this, MatrixAdd); } if (!pResMat) @@ -1537,7 +1474,7 @@ void ScInterpreter::ScMul() } if (pMat1 && pMat2) { - ScMatrixRef pResMat = lcl_MatrixCalculation( *pMat1, *pMat2, this); + ScMatrixRef pResMat = lcl_MatrixCalculation( *pMat1, *pMat2, this, MatrixMul); if (!pResMat) PushNoValue(); else @@ -1609,7 +1546,7 @@ void ScInterpreter::ScDiv() } if (pMat1 && pMat2) { - ScMatrixRef pResMat = lcl_MatrixCalculation( *pMat1, *pMat2, this); + ScMatrixRef pResMat = lcl_MatrixCalculation( *pMat1, *pMat2, this, MatrixDiv); if (!pResMat) PushNoValue(); else @@ -1676,7 +1613,7 @@ void ScInterpreter::ScPow() fVal1 = GetDouble(); if (pMat1 && pMat2) { - ScMatrixRef pResMat = lcl_MatrixCalculation( *pMat1, *pMat2, this); + ScMatrixRef pResMat = lcl_MatrixCalculation( *pMat1, *pMat2, this, MatrixPow); if (!pResMat) PushNoValue(); else @@ -1847,7 +1784,7 @@ void ScInterpreter::ScSumXMY2() PushNoValue(); return; } // if (nC1 != nC2 || nR1 != nR2) - ScMatrixRef pResMat = lcl_MatrixCalculation( *pMat1, *pMat2, this); + ScMatrixRef pResMat = lcl_MatrixCalculation( *pMat1, *pMat2, this, MatrixSub); if (!pResMat) { PushNoValue(); diff --git a/sc/source/core/tool/scmatrix.cxx b/sc/source/core/tool/scmatrix.cxx index 3c0aa14966db..f5d04bdb3fb9 100644 --- a/sc/source/core/tool/scmatrix.cxx +++ b/sc/source/core/tool/scmatrix.cxx @@ -335,6 +335,16 @@ public: void MatConcat(SCSIZE nMaxCol, SCSIZE nMaxRow, const ScMatrixRef& xMat1, const ScMatrixRef& xMat2, SvNumberFormatter& rFormatter, svl::SharedStringPool& rPool); + void ExecuteBinaryOp(SCSIZE nMaxCol, SCSIZE nMaxRow, const ScMatrix& rInputMat1, const ScMatrix& rInputMat2, + ScInterpreter* pInterpreter, ScMatrix::CalculateOpFunction op); + bool IsValueOrEmpty( const MatrixImplType::const_position_type & rPos ) const; + double GetDouble( const MatrixImplType::const_position_type & rPos) const; + FormulaError GetErrorIfNotString( const MatrixImplType::const_position_type & rPos ) const; + bool IsValue( const MatrixImplType::const_position_type & rPos ) const; + FormulaError GetError(const MatrixImplType::const_position_type & rPos) const; + bool IsStringOrEmpty(const MatrixImplType::const_position_type & rPos) const; + svl::SharedString GetString(const MatrixImplType::const_position_type& rPos) const; + #if DEBUG_MATRIX void Dump() const; #endif @@ -644,22 +654,7 @@ svl::SharedString ScMatrixImpl::GetString(SCSIZE nC, SCSIZE nR) const { if (ValidColRowOrReplicated( nC, nR )) { - double fErr = 0.0; - MatrixImplType::const_position_type aPos = maMat.position(nR, nC); - switch (maMat.get_type(aPos)) - { - case mdds::mtm::element_string: - return maMat.get_string(aPos); - case mdds::mtm::element_empty: - return svl::SharedString::getEmptyString(); - case mdds::mtm::element_numeric: - case mdds::mtm::element_boolean: - fErr = maMat.get_numeric(aPos); - [[fallthrough]]; - default: - OSL_FAIL("ScMatrixImpl::GetString: access error, no string"); - } - SetErrorAtInterpreter(GetDoubleErrorValue(fErr)); + return GetString(maMat.position(nR, nC)); } else { @@ -668,6 +663,26 @@ svl::SharedString ScMatrixImpl::GetString(SCSIZE nC, SCSIZE nR) const return svl::SharedString::getEmptyString(); } +svl::SharedString ScMatrixImpl::GetString(const MatrixImplType::const_position_type& rPos) const +{ + double fErr = 0.0; + switch (maMat.get_type(rPos)) + { + case mdds::mtm::element_string: + return maMat.get_string(rPos); + case mdds::mtm::element_empty: + return svl::SharedString::getEmptyString(); + case mdds::mtm::element_numeric: + case mdds::mtm::element_boolean: + fErr = maMat.get_numeric(rPos); + [[fallthrough]]; + default: + OSL_FAIL("ScMatrixImpl::GetString: access error, no string"); + } + SetErrorAtInterpreter(GetDoubleErrorValue(fErr)); + return svl::SharedString::getEmptyString(); +} + svl::SharedString ScMatrixImpl::GetString( SCSIZE nIndex) const { SCSIZE nC, nR; @@ -2788,6 +2803,185 @@ void ScMatrixImpl::MatConcat(SCSIZE nMaxCol, SCSIZE nMaxRow, const ScMatrixRef& } } +bool ScMatrixImpl::IsValueOrEmpty( const MatrixImplType::const_position_type & rPos ) const +{ + switch (maMat.get_type(rPos)) + { + case mdds::mtm::element_boolean: + case mdds::mtm::element_numeric: + case mdds::mtm::element_empty: + return true; + default: + ; + } + return false; +} + +double ScMatrixImpl::GetDouble(const MatrixImplType::const_position_type & rPos) const +{ + double fVal = maMat.get_numeric(rPos); + if ( pErrorInterpreter ) + { + FormulaError nError = GetDoubleErrorValue(fVal); + if ( nError != FormulaError::NONE ) + SetErrorAtInterpreter( nError); + } + return fVal; +} + +FormulaError ScMatrixImpl::GetErrorIfNotString( const MatrixImplType::const_position_type & rPos ) const +{ return IsValue(rPos) ? GetError(rPos) : FormulaError::NONE; } + +bool ScMatrixImpl::IsValue( const MatrixImplType::const_position_type & rPos ) const +{ + switch (maMat.get_type(rPos)) + { + case mdds::mtm::element_boolean: + case mdds::mtm::element_numeric: + return true; + default: + ; + } + return false; +} + +FormulaError ScMatrixImpl::GetError(const MatrixImplType::const_position_type & rPos) const +{ + double fVal = maMat.get_numeric(rPos); + return GetDoubleErrorValue(fVal); +} + +bool ScMatrixImpl::IsStringOrEmpty(const MatrixImplType::const_position_type & rPos) const +{ + switch (maMat.get_type(rPos)) + { + case mdds::mtm::element_empty: + case mdds::mtm::element_string: + return true; + default: + ; + } + return false; +} + +void ScMatrixImpl::ExecuteBinaryOp(SCSIZE nMaxCol, SCSIZE nMaxRow, const ScMatrix& rInputMat1, const ScMatrix& rInputMat2, + ScInterpreter* pInterpreter, ScMatrix::CalculateOpFunction Op) +{ + // Check output matrix size, otherwise output iterator logic will be wrong. + assert(maMat.size().row == nMaxRow && maMat.size().column == nMaxCol + && "the caller code should have sized the output matrix to the passed dimensions"); + auto & rMatImpl1 = *rInputMat1.pImpl; + auto & rMatImpl2 = *rInputMat2.pImpl; + // Check if we can do fast-path, where we have no replication or mis-matched matrix sizes. + if (rMatImpl1.maMat.size() == rMatImpl2.maMat.size() + && rMatImpl1.maMat.size() == maMat.size()) + { + MatrixImplType::position_type aOutPos = maMat.position(0, 0); + MatrixImplType::const_position_type aPos1 = rMatImpl1.maMat.position(0, 0); + MatrixImplType::const_position_type aPos2 = rMatImpl2.maMat.position(0, 0); + for (SCSIZE i = 0; i < nMaxCol; i++) + { + for (SCSIZE j = 0; j < nMaxRow; j++) + { + bool bVal1 = rMatImpl1.IsValueOrEmpty(aPos1); + bool bVal2 = rMatImpl2.IsValueOrEmpty(aPos2); + FormulaError nErr; + if (bVal1 && bVal2) + { + double d = Op(rMatImpl1.GetDouble(aPos1), rMatImpl2.GetDouble(aPos2)); + aOutPos = maMat.set(aOutPos, d); + } + else if (((nErr = rMatImpl1.GetErrorIfNotString(aPos1)) != FormulaError::NONE) || + ((nErr = rMatImpl2.GetErrorIfNotString(aPos2)) != FormulaError::NONE)) + { + aOutPos = maMat.set(aOutPos, CreateDoubleError(nErr)); + } + else if ((!bVal1 && rMatImpl1.IsStringOrEmpty(aPos1)) || + (!bVal2 && rMatImpl2.IsStringOrEmpty(aPos2))) + { + FormulaError nError1 = FormulaError::NONE; + SvNumFormatType nFmt1 = SvNumFormatType::ALL; + double fVal1 = (bVal1 ? rMatImpl1.GetDouble(aPos1) : + pInterpreter->ConvertStringToValue( rMatImpl1.GetString(aPos1).getString(), nError1, nFmt1)); + + FormulaError nError2 = FormulaError::NONE; + SvNumFormatType nFmt2 = SvNumFormatType::ALL; + double fVal2 = (bVal2 ? rMatImpl2.GetDouble(aPos2) : + pInterpreter->ConvertStringToValue( rMatImpl2.GetString(aPos2).getString(), nError2, nFmt2)); + + if (nError1 != FormulaError::NONE) + aOutPos = maMat.set(aOutPos, CreateDoubleError(nError1)); + else if (nError2 != FormulaError::NONE) + aOutPos = maMat.set(aOutPos, CreateDoubleError(nError2)); + else + { + double d = Op( fVal1, fVal2); + aOutPos = maMat.set(aOutPos, d); + } + } + else + aOutPos = maMat.set(aOutPos, CreateDoubleError(FormulaError::NoValue)); + aPos1 = MatrixImplType::next_position(aPos1); + aPos2 = MatrixImplType::next_position(aPos2); + aOutPos = MatrixImplType::next_position(aOutPos); + } + } + } + else + { + // Noting that this block is very hard to optimise to use iterators, because various dodgy + // array function usage relies on the semantics of some of the methods we call here. + // (see unit test testDubiousArrayFormulasFODS). + // These methods are inconsistent in their usage of ValidColRowReplicated() vs. ValidColRowOrReplicated() + // which leads to some very odd results. + MatrixImplType::position_type aOutPos = maMat.position(0, 0); + for (SCSIZE i = 0; i < nMaxCol; i++) + { + for (SCSIZE j = 0; j < nMaxRow; j++) + { + bool bVal1 = rInputMat1.IsValueOrEmpty(i,j); + bool bVal2 = rInputMat2.IsValueOrEmpty(i,j); + FormulaError nErr; + if (bVal1 && bVal2) + { + double d = Op(rInputMat1.GetDouble(i,j), rInputMat2.GetDouble(i,j)); + aOutPos = maMat.set(aOutPos, d); + } + else if (((nErr = rInputMat1.GetErrorIfNotString(i,j)) != FormulaError::NONE) || + ((nErr = rInputMat2.GetErrorIfNotString(i,j)) != FormulaError::NONE)) + { + aOutPos = maMat.set(aOutPos, CreateDoubleError(nErr)); + } + else if ((!bVal1 && rInputMat1.IsStringOrEmpty(i,j)) || (!bVal2 && rInputMat2.IsStringOrEmpty(i,j))) + { + FormulaError nError1 = FormulaError::NONE; + SvNumFormatType nFmt1 = SvNumFormatType::ALL; + double fVal1 = (bVal1 ? rInputMat1.GetDouble(i,j) : + pInterpreter->ConvertStringToValue( rInputMat1.GetString(i,j).getString(), nError1, nFmt1)); + + FormulaError nError2 = FormulaError::NONE; + SvNumFormatType nFmt2 = SvNumFormatType::ALL; + double fVal2 = (bVal2 ? rInputMat2.GetDouble(i,j) : + pInterpreter->ConvertStringToValue( rInputMat2.GetString(i,j).getString(), nError2, nFmt2)); + + if (nError1 != FormulaError::NONE) + aOutPos = maMat.set(aOutPos, CreateDoubleError(nError1)); + else if (nError2 != FormulaError::NONE) + aOutPos = maMat.set(aOutPos, CreateDoubleError(nError2)); + else + { + double d = Op( fVal1, fVal2); + aOutPos = maMat.set(aOutPos, d); + } + } + else + aOutPos = maMat.set(aOutPos, CreateDoubleError(FormulaError::NoValue)); + aOutPos = MatrixImplType::next_position(aOutPos); + } + } + } +} + void ScMatrix::IncRef() const { ++nRefCnt; @@ -3418,4 +3612,9 @@ void ScMatrix::MatConcat(SCSIZE nMaxCol, SCSIZE nMaxRow, pImpl->MatConcat(nMaxCol, nMaxRow, xMat1, xMat2, rFormatter, rPool); } +void ScMatrix::ExecuteBinaryOp(SCSIZE nMaxCol, SCSIZE nMaxRow, const ScMatrix& rInputMat1, const ScMatrix& rInputMat2, + ScInterpreter* pInterpreter, CalculateOpFunction op) +{ + pImpl->ExecuteBinaryOp(nMaxCol, nMaxRow, rInputMat1, rInputMat2, pInterpreter, op); +} /* vim:set shiftwidth=4 softtabstop=4 expandtab: */ -- 2.11.4.GIT