[
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 {{Array2DRowRealMatrix}}.
At each getEntry, a costly {{MatrixUtils.checkMatrixIndex}} is performed.
See flamegraph.
{color}{color:#000000}!bobyqa_matrix_getentry_slow.png|width=865,height=263!{color}
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] --> 120 ± 5 ms/operations
After: [^bobyqa_matrix_getEntry_withOpti.txt] --> 106 ± 8 ms/operations
See [example fix commit
here|https://github.com/cyrilou242/commons-math/commit/41b268ea6ebb165f978f2f8802c90401278653bd].{color}
Other options:
1. replace {{matrix.getEntry(row, column)}} by
{{matrix.getDataRef()[row][column]}} inside the Bobyqa implementation.
According to my (very limited) benchmark results this is the fastest. But this
would be specific to Bobyqa, and this makes the code harder to read, so this
can be taken as a different task I guess.
2. add something like a {{fastGetEntry}} to the {{RealMatrix}} interface. This
method would not perform the indexes checks. But I guess changing the interface
is overkill.
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 {{Array2DRowRealMatrix}}.
At each getEntry, a costly {{MatrixUtils.checkMatrixIndex}} is performed.
See flamegraph.
{color}{color:#000000}!bobyqa_matrix_getentry_slow.png|width=865,height=263!{color}
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] --> 120 ± 5 ms/operations
After: [^bobyqa_matrix_getEntry_withOpti.txt] --> 106 ± 8 ms/operations
See [example fix commit
here|https://github.com/cyrilou242/commons-math/commit/41b268ea6ebb165f978f2f8802c90401278653bd].{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 {{Array2DRowRealMatrix}}.
> At each getEntry, a costly {{MatrixUtils.checkMatrixIndex}} is performed.
> See flamegraph.
> {color}{color:#000000}!bobyqa_matrix_getentry_slow.png|width=865,height=263!{color}
>
> 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] --> 120 ± 5 ms/operations
> After: [^bobyqa_matrix_getEntry_withOpti.txt] --> 106 ± 8 ms/operations
> See [example fix commit
> here|https://github.com/cyrilou242/commons-math/commit/41b268ea6ebb165f978f2f8802c90401278653bd].{color}
> Other options:
> 1. replace {{matrix.getEntry(row, column)}} by
> {{matrix.getDataRef()[row][column]}} inside the Bobyqa implementation.
> According to my (very limited) benchmark results this is the fastest. But
> this would be specific to Bobyqa, and this makes the code harder to read, so
> this can be taken as a different task I guess.
> 2. add something like a {{fastGetEntry}} to the {{RealMatrix}} interface.
> This method would not perform the indexes checks. But I guess changing the
> interface is overkill.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
