You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Cyril de Catheu (Jira)" <ji...@apache.org> on 2023/03/04 10:27:00 UTC
[jira] [Updated] (MATH-1654) Matrix implementations of getEntry are slow
[ https://issues.apache.org/jira/browse/MATH-1654?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Cyril de Catheu updated MATH-1654:
----------------------------------
Description:
Inspecting BOBYQA performance, I see a lot of the time is spent into the [getEntry]([https://github.com/apache/commons-math/blob/889d27b5d7b23eaf1ee984e93b892b5128afc454/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/linear/Array2DRowRealMatrix.java#L300]) method of `{color:#000000}Array2DRowRealMatrix`.
At each getEntry, a costly `MatrixUtils.checkMatrixIndex(this, row, column);` is performed.
See flamegraph.
{color}{color:#000000}!bobyqa_matrix_getentry_slow.png|width=865,height=263!{color}
{color:#000000}It seems other implementations of `RealMatrix` also start by the `checkMatrixIndex`.
I did not check for complex matrices.
It is very likely using a try and catch IndexOutOfBoundsException will be way faster in the nominal case than checking indexes before accessing the array.
All consumers of `RealMatrix#getEntry` could benefit from this optimization.
See [benchmark]([https://github.com/cyrilou242/commons-math/commit/241e89f23574660d1fbaa7cdb567552c1a26a7f6]) for a simple BOBYQA workload.
For this workload the performance gain is ~10%.
Before: [^bobyqa_matrix_getEntry_current.txt]
After: [^bobyqa_matrix_getEntry_withOpti.txt]
See [example fix commit here]([https://github.com/cyrilou242/commons-math/commit/41b268ea6ebb165f978f2f8802c90401278653bd]). (not final)
{color}
was:
Inspecting BOBYQA performance, I see a lot of the time is spent into the [getEntry](https://github.com/apache/commons-math/blob/889d27b5d7b23eaf1ee984e93b892b5128afc454/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/linear/Array2DRowRealMatrix.java#L300) method of `{color:#000000}Array2DRowRealMatrix`.
At each getEntry, a costly `MatrixUtils.checkMatrixIndex(this, row, column);` is performed.
See flamegraph.
{color}{color:#000000}!bobyqa_matrix_getentry_slow.png!
{color}
{color:#000000}It seems other implementations of `RealMatrix` also start by the `checkMatrixIndex`.
I did not check for complex matrices.
It is very likely using a try and catch IndexOutOfBoundsException will be way faster in the nominal case than checking indexes before accessing the array.
All consumers of `RealMatrix#getEntry` could benefit from this optimization.
See [benchmark](https://github.com/cyrilou242/commons-math/commit/241e89f23574660d1fbaa7cdb567552c1a26a7f6) for a simple BOBYQA workload.
For this workload the performance gain is ~10%.
Before: [^bobyqa_matrix_getEntry_current.txt]
After: [^bobyqa_matrix_getEntry_withOpti.txt]
See [example fix commit here](https://github.com/cyrilou242/commons-math/commit/41b268ea6ebb165f978f2f8802c90401278653bd). (not final)
{color}
> Matrix implementations of getEntry are slow
> -------------------------------------------
>
> Key: MATH-1654
> URL: https://issues.apache.org/jira/browse/MATH-1654
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.6.1, 4.X
> Environment: master branch
> 3.6.1
> Reporter: Cyril de Catheu
> Priority: Major
> Attachments: bobyqa_matrix_getEntry_current.txt, bobyqa_matrix_getEntry_withOpti.txt, bobyqa_matrix_getentry_slow.png
>
>
> Inspecting BOBYQA performance, I see a lot of the time is spent into the [getEntry]([https://github.com/apache/commons-math/blob/889d27b5d7b23eaf1ee984e93b892b5128afc454/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/linear/Array2DRowRealMatrix.java#L300]) method of `{color:#000000}Array2DRowRealMatrix`.
> At each getEntry, a costly `MatrixUtils.checkMatrixIndex(this, row, column);` is performed.
> See flamegraph.
> {color}{color:#000000}!bobyqa_matrix_getentry_slow.png|width=865,height=263!{color}
>
> {color:#000000}It seems other implementations of `RealMatrix` also start by the `checkMatrixIndex`.
> I did not check for complex matrices.
> It is very likely using a try and catch IndexOutOfBoundsException will be way faster in the nominal case than checking indexes before accessing the array.
> All consumers of `RealMatrix#getEntry` could benefit from this optimization.
> See [benchmark]([https://github.com/cyrilou242/commons-math/commit/241e89f23574660d1fbaa7cdb567552c1a26a7f6]) for a simple BOBYQA workload.
> For this workload the performance gain is ~10%.
> Before: [^bobyqa_matrix_getEntry_current.txt]
> After: [^bobyqa_matrix_getEntry_withOpti.txt]
> See [example fix commit here]([https://github.com/cyrilou242/commons-math/commit/41b268ea6ebb165f978f2f8802c90401278653bd]). (not final)
> {color}
--
This message was sent by Atlassian Jira
(v8.20.10#820010)