[
https://issues.apache.org/jira/browse/MATH-1654?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17696496#comment-17696496
]
Cyril de Catheu commented on MATH-1654:
---------------------------------------
Ok thanks for the context.
Inside bobyqa I'd also prefer to code against vectors and matrix interfaces
rather than manipulate arrays directly.
bq. IMHO, it would be very interesting to indeed check the performance, in this
particular case, when using an alternative implementation. If it turns out that
other projects offer greater performance and flexibility, it might be worth
abstracting the matrix interface, allowing callers to bridge with the
implementation of their choice. Each bridge could be maintained as a separate
"Commons Math" module with its specific dependency on the external library (so
that it can be relatively easily included/excluded from a "Commons Math"
release in case of issues).
Agree. I've had success with this approach with a Timeseries interface.
bq. From a long time, we've suspected that the Commons Math's matrix
implementation might be too bloated for some uses
I had a quick look today, there is still a lot of optimization opportunities in
{{Array2DRowRealMatrix}} and {{ArrayRealVector}}. So I think - for bobyqa -
it's safe going for this first. Every optimization made to these classes will
benefit to many consumers.
So if it makes sense to you I'll do the following:
1. create a PR to optimize getEntry of the {{Array2DRowRealMatrix}} - this is a
quickwin and it solves my work issue
2. start refactoring bobyqa:
a. generic code quality
b. use matrices and vectors interfaces as much as possible
c. refactor the switch that simulates a goto
3. introduce benchmarks
4. see if a custom matrix/vector implementation would make bobyqa faster
I should be able to spend 3-4 hours/week on this.
Notes:
With 1. and 2.a I can get used to the review and Apache commons processes.
During 2.b., the performance of bobyqa may get worse. Given we have a win with
1 I don't think it'll be an issue.
For 3 maybe for training I'll start with something different than bobyqa - eg
https://issues.apache.org/jira/browse/MATH-1585
> 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)
