ScInterpreter::ScGCD and ScInterpreter::ScLCM

classic Classic list List threaded Threaded
7 messages Options
Filippo giacchè Filippo giacchè
Reply | Threaded
Open this post in threaded view
|

ScInterpreter::ScGCD and ScInterpreter::ScLCM

Hi to everyone,
I m trying to optimize ScInterpreter::ScGCD and ScInterpreter::ScLCM (in /core/sc/source/core/tool/interpr5.cxx) as mentioned in bug tdf#89387..
From what I understood , these function are not optimal in the matrix case (evenif the algorithms look good in my opinion) and need to be changed. So my question is how can I do it? If I create function in /core/sc/source/core/tool/ScMatrix.cxx that take as input a matrix and retuns the GCD(or LCM) I'll do ok?or is not the right way to proceed? thanks ,I welcome any advice that you can give me.

Kind regards,
filippo giacchè

_______________________________________________
LibreOffice mailing list
[hidden email]
https://lists.freedesktop.org/mailman/listinfo/libreoffice
Mike Kaganski Mike Kaganski
Reply | Threaded
Open this post in threaded view
|

Re: ScInterpreter::ScGCD and ScInterpreter::ScLCM

Hi,

On 12/30/2016 2:56 PM, Filippo giacchè wrote:
I m trying to optimize ScInterpreter::ScGCD and ScInterpreter::ScLCM (in /core/sc/source/core/tool/interpr5.cxx) as mentioned in bug tdf#89387..
From what I understood , these function are not optimal in the matrix case (evenif the algorithms look good in my opinion) and need to be changed. So my question is how can I do it? If I create function in /core/sc/source/core/tool/ScMatrix.cxx that take as input a matrix and retuns the GCD(or LCM) I'll do ok?or is not the right way to proceed? thanks ,I welcome any advice that you can give me.

I would suggest you to suggest your vision as a change posted to gerrit for review, and let others to discuss the implementation: that could be much more productive IMO.
If I'm wrong, I hope others will correct me.

--
Best regards,
Mike Kaganski

_______________________________________________
LibreOffice mailing list
[hidden email]
https://lists.freedesktop.org/mailman/listinfo/libreoffice
Markus Mohrhard Markus Mohrhard
Reply | Threaded
Open this post in threaded view
|

Re: ScInterpreter::ScGCD and ScInterpreter::ScLCM

In reply to this post by Filippo giacchè
Hey,

On Fri, Dec 30, 2016 at 12:56 PM, Filippo giacchè <[hidden email]> wrote:
Hi to everyone,
I m trying to optimize ScInterpreter::ScGCD and ScInterpreter::ScLCM (in /core/sc/source/core/tool/interpr5.cxx) as mentioned in bug tdf#89387..
From what I understood , these function are not optimal in the matrix case (evenif the algorithms look good in my opinion) and need to be changed. So my question is how can I do it? If I create function in /core/sc/source/core/tool/ScMatrix.cxx that take as input a matrix and retuns the GCD(or LCM) I'll do ok?or is not the right way to proceed? thanks ,I welcome any advice that you can give me.



The task is not about changing the algorithm. The new matrix backend does not have O(1) index based access any more so stuff like:

for (int i = 0; i < n; ++i)
{
    matrix.set(i, y, value);
}

is not a O(n) algorithm anymore.

However the new matrix backend provides some alternatives that allow to write more efficient implementations (that are even faster -- by a constant factor) than the old one. For that we need to use some of the constructs written as part of this bug by . As an example for such a change look at https://cgit.freedesktop.org/libreoffice/core/commit/?id=9a7959cd63be7b2f36da8af25e7673a525c4d66c and try to understand how ApplyOperation and the operator play together. All of this should make sense if you realize that we have no O(n) index access but that iterator access is in O(1).

If you need a bit more details after looking at some of the commits in the bug report you can ping me again.

Regards,
Markus


_______________________________________________
LibreOffice mailing list
[hidden email]
https://lists.freedesktop.org/mailman/listinfo/libreoffice
Filippo giacchè Filippo giacchè
Reply | Threaded
Open this post in threaded view
|

Re: ScInterpreter::ScGCD and ScInterpreter::ScLCM

hi,
I have another question:

Kind regards,
filippo giacchè

2016-12-30 12:41 GMT+00:00 Markus Mohrhard <[hidden email]>:
Hey,

On Fri, Dec 30, 2016 at 12:56 PM, Filippo giacchè <[hidden email]> wrote:
Hi to everyone,
I m trying to optimize ScInterpreter::ScGCD and ScInterpreter::ScLCM (in /core/sc/source/core/tool/interpr5.cxx) as mentioned in bug tdf#89387..
From what I understood , these function are not optimal in the matrix case (evenif the algorithms look good in my opinion) and need to be changed. So my question is how can I do it? If I create function in /core/sc/source/core/tool/ScMatrix.cxx that take as input a matrix and retuns the GCD(or LCM) I'll do ok?or is not the right way to proceed? thanks ,I welcome any advice that you can give me.



The task is not about changing the algorithm. The new matrix backend does not have O(1) index based access any more so stuff like:

for (int i = 0; i < n; ++i)
{
    matrix.set(i, y, value);
}

is not a O(n) algorithm anymore.

However the new matrix backend provides some alternatives that allow to write more efficient implementations (that are even faster -- by a constant factor) than the old one. For that we need to use some of the constructs written as part of this bug by . As an example for such a change look at https://cgit.freedesktop.org/libreoffice/core/commit/?id=9a7959cd63be7b2f36da8af25e7673a525c4d66c and try to understand how ApplyOperation and the operator play together. All of this should make sense if you realize that we have no O(n) index access but that iterator access is in O(1).

If you need a bit more details after looking at some of the commits in the bug report you can ping me again.

Regards,
Markus



_______________________________________________
LibreOffice mailing list
[hidden email]
https://lists.freedesktop.org/mailman/listinfo/libreoffice
Eike Rathke-2 Eike Rathke-2
Reply | Threaded
Open this post in threaded view
|

Re: ScInterpreter::ScGCD and ScInterpreter::ScLCM

Hi Filippo,

On Monday, 2017-01-02 17:46:51 +0000, Filippo giacchè wrote:

> What are commit like this ?
> http://cgit.freedesktop.org/libreoffice/core/commit/?id=32950e9089aa323303154156c27f713ba3efdf85

That implements a unit test for the GCD() function, which is executed
during build time to ensure the function works as intended.

  Eike

--
LibreOffice Calc developer. Number formatter stricken i18n transpositionizer.
GPG key "ID" 0x65632D3A - 2265 D7F3 A7B0 95CC 3918  630B 6A6C D5B7 6563 2D3A
Better use 64-bit 0x6A6CD5B765632D3A here is why: https://evil32.com/
Care about Free Software, support the FSFE https://fsfe.org/support/?erack

_______________________________________________
LibreOffice mailing list
[hidden email]
https://lists.freedesktop.org/mailman/listinfo/libreoffice

signature.asc (836 bytes) Download Attachment
Filippo giacchè Filippo giacchè
Reply | Threaded
Open this post in threaded view
|

Re: ScInterpreter::ScGCD and ScInterpreter::ScLCM


> What are commit like this ?
> http://cgit.freedesktop.org/libreoffice/core/commit/?id=32950e9089aa323303154156c27f713ba3efdf85

That implements a unit test for the GCD() function, which is executed
during build time to ensure the function works as intended.

if i change the function I also reimplement the test?


_______________________________________________
LibreOffice mailing list
[hidden email]
https://lists.freedesktop.org/mailman/listinfo/libreoffice
Eike Rathke-2 Eike Rathke-2
Reply | Threaded
Open this post in threaded view
|

Re: ScInterpreter::ScGCD and ScInterpreter::ScLCM

Hi Filippo,

On Wednesday, 2017-01-04 15:15:08 +0000, Filippo giacchè wrote:

> > > What are commit like this ?
> > > http://cgit.freedesktop.org/libreoffice/core/commit/?id=
> > 32950e9089aa323303154156c27f713ba3efdf85
> >
> > That implements a unit test for the GCD() function, which is executed
> > during build time to ensure the function works as intended.
> >
>
> if i change the function I also reimplement the test?

No, you keep the test untouched. If it fails after changes then it
usually means the change was wrong. Only adding more specific test cases
could be appropriate.

However, as already mentioned in this thread, the task is less about
changing individual interpreter functions but rather work on the
ScMatrix internal representation accesses.

  Eike

--
LibreOffice Calc developer. Number formatter stricken i18n transpositionizer.
GPG key "ID" 0x65632D3A - 2265 D7F3 A7B0 95CC 3918  630B 6A6C D5B7 6563 2D3A
Better use 64-bit 0x6A6CD5B765632D3A here is why: https://evil32.com/
Care about Free Software, support the FSFE https://fsfe.org/support/?erack

_______________________________________________
LibreOffice mailing list
[hidden email]
https://lists.freedesktop.org/mailman/listinfo/libreoffice

signature.asc (836 bytes) Download Attachment