Bug 89387 - improve performance for some matrix operations
Summary: improve performance for some matrix operations
Status: NEW
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Calc (show other bugs)
Version:
(earliest affected)
unspecified
Hardware: Other All
: medium normal
Assignee: Not Assigned
URL:
Whiteboard: target:4.5.0 target:5.1.0 target:5.0....
Keywords: difficultyInteresting, easyHack, perf, skillCpp, topicDebug
Depends on:
Blocks:
 
Reported: 2015-02-14 22:56 UTC by Markus Mohrhard
Modified: 2017-08-28 12:34 UTC (History)
5 users (show)

See Also:
Crash report or crash signature:


Attachments
simple testcase to make NegOp crash (7.27 KB, application/vnd.oasis.opendocument.spreadsheet)
2015-03-31 17:37 UTC, Eike Rathke
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Markus Mohrhard 2015-02-14 22:56:32 UTC
The code for ScInterpreter::ScNot, ScInterpreter::ScNeg and some more methods are not optimal for the matrix case. The current data structures that are used for matrix storage is inefficient when you access every element on its own. Instead you should iterate through the whole storage at once.

The code to do that exists already as part of 3d6cedd70b3c79b3ebb65c2662df420a8acb0818. This would require to reuse the templates that have been written for ScInterpreter::CalculateAddSub and create a functor for ScNot and ScNeg.
Comment 1 Markus Mohrhard 2015-02-14 22:57:22 UTC
Making it an easy hack.
Comment 2 Markus Mohrhard 2015-02-14 23:17:08 UTC
Some more functions that would benefit from that:

ScInterpreter::CalculatePearsonCovar
ScInterpreter::CalculateSlopeIntercept
ScInterpreter::ScForecast
ScInterpreter::ScTTest (at least for the fType == 1.0 case, others need to be checked)
ScInterpreter::ScFTest
ScInterpreter::ScChiTest
ScInterpreter::ScGCD
ScInterpreter:: ScLCM
lcl_MatrixCalculation in interpr5.cxx
ScInterpreter::ScAmpersand
ScInterpreter::ScMul
ScInterpreter::ScDiv
ScInterpreter::ScPow
ScInterpreter::CalculateSumX2MY2SumX2DY2
ScInterpreter::ScSumXMY2
ScInterpreter::CheckMatrix

Please note that many of them may require some more work and may not be as easy as the ones above.
Comment 3 Łukasz Hryniuk 2015-02-27 20:09:54 UTC
I would like to work on this. I'm looking at the code now... and I wonder: is there any test to check performance of these operations? If no, should I write a few before I start (or, maybe, after) or just base on Markus code and everything should be alright?
Comment 4 Markus Mohrhard 2015-03-02 18:59:32 UTC
(In reply to Łukasz Hryniuk from comment #3)
> I would like to work on this. I'm looking at the code now... and I wonder:
> is there any test to check performance of these operations? If no, should I
> write a few before I start (or, maybe, after) or just base on Markus code
> and everything should be alright?

There are no performance tests for this. However you don't need to worry about that. The changes will not cause any performance problems, they will actually improve performance for big array formulas and avoid a lot of stupid calls into mdds.
Comment 5 Commit Notification 2015-03-09 21:32:10 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=1c2405ba44c5a146188c19e235f857ab18ea05f0

tdf#89387 General functor and basic operations

It will be available in 4.5.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 6 Commit Notification 2015-03-14 23:10:16 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=460b17d2712a80331a83329d2951f3e0303835cd

Related to tdf#89387 remove unused stuff

It will be available in 4.5.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 7 Commit Notification 2015-03-23 09:15:24 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=38e247046ec38cdab0f7d56614a183dcfc49389c

tdf#89387 Change summing loop to SumSquare method

It will be available in 4.5.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 8 Commit Notification 2015-03-25 08:58:23 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=9a7959cd63be7b2f36da8af25e7673a525c4d66c

tdf#89387 Add functor for ScAmpersand

It will be available in 4.5.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 9 Commit Notification 2015-03-31 15:52:03 UTC
Eike Rathke committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=e27d7c38ba1de0f4bbb1197bd84c063a0fdee9d1

Revert "tdf#89387 Add functor for ScAmpersand"

It will be available in 4.5.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 10 Eike Rathke 2015-03-31 17:37:39 UTC
Created attachment 114504 [details]
simple testcase to make NegOp crash

Something is seriously wrong with the new MatOp handling, the attached document, calculating a mixed array of one number and one string using NegOp, makes the application immediately crash with a Fatal Error "Data array is too long". Please fix ASAP.
Comment 11 Eike Rathke 2015-03-31 17:38:44 UTC
Furthermore, I noticed that due to the wrapped_iterator value_type& operator() using calcVal() the MatOp operation is executed too many times, i.e. when values are accessed and/or copied in mdds. Not sure if that can be avoided at all with the current design.
Comment 12 Eike Rathke 2015-04-01 12:30:08 UTC
Separate crasher bug 90391 submitted.
Comment 13 Commit Notification 2015-04-01 23:32:28 UTC
Eike Rathke committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=636dd43c1cc10ca5f609fe23ee388d9679a60f2e

use error value instead of string in array/matrix, tdf#89387 tdf#42481 related

It will be available in 4.5.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 14 Commit Notification 2015-04-02 21:37:09 UTC
Eike Rathke committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=a6376855d773282ab680c36002b3037cb0a4a9b1

empty element evaluates to 0, tdf#89387 tdf#42481 related

It will be available in 4.5.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 15 Commit Notification 2015-08-10 21:50:58 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=d5bff1225a6739e8369bacd8392686bd26630d2f

tdf#89387 related, fix SumSquare bug in SumMXMY2

It will be available in 5.1.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 16 Commit Notification 2015-08-10 21:51:02 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=fc71e5b4637ece8822e83c844d191f461b2f0177

tdf#89387 related tests for ScSumXMY2()

It will be available in 5.1.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 17 Commit Notification 2015-08-10 22:02:01 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "libreoffice-5-0":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=e67bbe231f875477b16f3fe51dcf14e3711a73a5&h=libreoffice-5-0

tdf#89387 related, fix SumSquare bug in SumMXMY2

It will be available in 5.0.2.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 18 Commit Notification 2015-08-10 22:27:19 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=066f3132effa9017fe9127e9d311d6ae88d0c729

tdf#89387 a few tests for FTEST function

It will be available in 5.1.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 19 Commit Notification 2015-08-12 10:23:31 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=0a726cb29936b61b8f05b0863e24db212a0e6166

tdf#89387 test for CHITEST function

It will be available in 5.1.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 20 Commit Notification 2015-08-15 21:54:19 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "libreoffice-5-0-1":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=4fed84924adc6afbc03b5458f63fc49ba505dd5a&h=libreoffice-5-0-1

tdf#89387 related, fix SumSquare bug in SumMXMY2

It will be available in 5.0.1.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 21 Commit Notification 2015-08-26 01:43:27 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=8580f4428dbe368acea5d4adfea2cb7b399dfae4

tdf#89387 add some strings to FTEST test

It will be available in 5.1.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 22 Commit Notification 2015-08-26 01:44:40 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=8e0d49e3b6f6e7146477569e635d2c30863c4cfc

tdf#89387 add some strings to CHITEST test

It will be available in 5.1.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 23 Commit Notification 2015-08-26 01:45:52 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=1a5b5750ed4157420bc0e0e9f384d3984dee9acd

tdf#89387 test for SUMX2PY2 function

It will be available in 5.1.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 24 Commit Notification 2015-08-26 01:47:05 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=32950e9089aa323303154156c27f713ba3efdf85

tdf#89387 test for GCD function

It will be available in 5.1.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 25 Commit Notification 2015-08-26 01:47:09 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=4f0bb271c300253d1812c6cccf813eff442a02db

tdf#89387 test for LCM function

It will be available in 5.1.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 26 Commit Notification 2015-10-02 05:18:23 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=20f72678876b080f91310fdeae9fe838032e366c

tdf#89387 Use Collect method in FTest

It will be available in 5.1.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 27 Commit Notification 2015-10-23 17:20:25 UTC
Łukasz Hryniuk committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=526f792d9ae535c2b15929a2eaf976465b02bddb

tdf#89387 test for TTEST function

It will be available in 5.1.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds

Affected users are encouraged to test the fix and report feedback.
Comment 28 Robinson Tryon (qubit) 2015-12-14 06:38:45 UTC Comment hidden (obsolete)
Comment 29 jani 2016-02-17 07:20:53 UTC
A polite ping, are you still working on this ?
Comment 30 Łukasz Hryniuk 2016-02-20 23:02:27 UTC
(In reply to jan iversen from comment #29)
> A polite ping, are you still working on this ?

Yes. For now more than half of functions listed at the beginning are improved and I've written unit and performance tests for few of the rest. I have to implement one thing in mdds - way to work on two matrices at once - and use it in remaining functions. I'll try to do it as soon as possible.
Comment 31 jani 2016-04-12 16:01:18 UTC
Lukasz@ Still working on this patch (otherwise please unsaying yourself) ?
Comment 32 Łukasz Hryniuk 2016-04-12 17:49:48 UTC
(In reply to jan iversen from comment #31)
> Lukasz@ Still working on this patch (otherwise please unsaying yourself) ?
No, I didn't manage to finish a patch I've started. Sorry for keeping it assigned so long.
Comment 33 Tamsil Amani 2016-11-23 21:35:53 UTC
I'm starting to work on it.
Comment 34 filippo 2016-11-24 09:44:25 UTC
hi, I would work on this bug, 'cose I like matrix operation.
I would like to know if the bug requires to optimize algorihtms of matrix operations (in terms of computational cost) or to speed them up on GPU..
furthermore,witch algorithms are still to be modified?
Comment 35 filippo 2016-11-24 09:52:25 UTC
(In reply to Tamsil Amani from comment #33)
> I'm starting to work on it.

sorry I didn't notice youre comment, would you work on it?. If yes I unassigne myself...let me know..
Comment 36 filippo 2016-11-24 09:52:55 UTC Comment hidden (obsolete)
Comment 37 Łukasz Hryniuk 2016-11-24 22:48:24 UTC
(In reply to filippo from comment #34)
> hi, I would work on this bug, 'cose I like matrix operation.
> I would like to know if the bug requires to optimize algorihtms of matrix
> operations (in terms of computational cost) or to speed them up on GPU..
> furthermore,witch algorithms are still to be modified?
(In reply to Tamsil Amani from comment #33)
> I'm starting to work on it.

Hello Filippo and Tamsil,

the main goal of this task is to speed up matrix (ScMatrix) operations using mdds (https://gitlab.com/mdds/mdds) library. You can start with checking how MatrixOpWrapper and MatOp are implemented in (commit 1c2405ba44c5a146188c19e235f857ab18ea05f0)
sc/source/core/tool/scmatrix.cxx

It needs a small refactoring - look for FIXME in this file (e.g. near void ScFullMatrix::NotOp( ScMatrix& rMat)) ;).  It could be good place to start.

I've changed a few functions from the list - you can search for my commits in gerrit to see the details - and as far as I recall these operations still need to be changed:

ScInterpreter::CalculatePearsonCovar
ScInterpreter::CalculateSlopeIntercept
ScInterpreter::ScGCD
ScInterpreter::ScLCM
lcl_MatrixCalculation in interpr5.cxx
ScInterpreter::CheckMatrix

I've used the callgrind for profiling, but I suppose there can be a better tool for that. You can find written tests' results here: http://perf.libreoffice.org/perf_html/suite_cppu_sc.html (e.g. lcm, gcd, ttest, chitest), they can help you too.

Looking forward to your commits :)!
Comment 38 filippo 2016-12-12 15:30:19 UTC
I ' m looking the function ScFullMatrix::MatCopy in /core/sc/source/core/tool/scmatrix.cxx and I wonder how can I try it?.
Comment 39 Markus Mohrhard 2016-12-14 14:54:25 UTC
(In reply to filippo from comment #38)
> I ' m looking the function ScFullMatrix::MatCopy in
> /core/sc/source/core/tool/scmatrix.cxx and I wonder how can I try it?.

Best to take one of the functions that Łukasz mentioned. Also it is a good idea to look at the other commits referenced in this bug report to see what needs to be done.
Comment 40 jani 2017-01-16 07:06:26 UTC Comment hidden (obsolete)
Comment 41 filippo 2017-01-16 10:33:34 UTC
(In reply to jan iversen from comment #40)
> A polite ping, still working on this bug ?

yes. For now I have only changed ScInterpreter::ScGCD ,implementing a method that calculate Gcd in scMatrix,i only have to handle strings error ,but i dont know how..(https://gerrit.libreoffice.org/#/c/32972/5/sc/source/core/tool/scmatrix.cxx).
If this solution is ok I will change ScInterpreter::ScLCM too..
sorry for keeping it so long,any suggestions can help me to goes on with the function above are welcome
Comment 42 Commit Notification 2017-02-16 17:30:16 UTC
giacco committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=c995531d8a7c97f684f2e65707c7b3f87a0ba372

tdf#89387 improve performance for some matrix operations

It will be available in 5.4.0.

The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds

Affected users are encouraged to test the fix and report feedback.
Comment 43 Shinnok 2017-08-28 12:34:06 UTC
A polite ping, still working on this issue?