[
https://issues.apache.org/jira/browse/MATH-1654?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17696487#comment-17696487
]
Gilles Sadowski commented on MATH-1654:
---------------------------------------
{quote}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.
{quote}
It may have something to do with the [points made
there|https://stackoverflow.com/questions/16451777/is-it-expensive-to-use-try-catch-blocks-even-if-an-exception-is-never-thrown].
Using the above "trick" would also prevent moving to an alternative
implementation (as there is no guarantee that the underlying layout would be a
{{{}double[][]{}}}), or at the cost of an unbearable loss of performance, if in
the worst case the bridge API has to create a {{double[][]}} for each entry
access!
{quote}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.
{quote}
IIRC, I went through the tedium of turning all the arrays (from the original
auto-translation from C, or Fortran) into the Commons Math's matrix
implementation. Clearly, there is balance between advantages and drawbacks of
using the "matrix" concept rather than the low-level {{{}double[][]{}}}.
>From a long time, we've suspected that the Commons Math's matrix
>implementation might be too bloated for some uses (cf. related issues in JIRA
>and the "dev" ML archive).
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).
{quote}2. add something like a fastGetEntry to the RealMatrix interface. This
method would not perform the indexes checks.
{quote}
Checks are always performed by the JVM anyways; so sure there is a cost in
doing it twice.
For example, if the underlying matrix were a {{{}double[]{}}}, there would be
twice fewer checks (but that layout may then entail other costs, perhaps not
present with a {{{}double[][]{}}}...).
All possibilities are worth checking, but given the lack of human resources
here to maintain such a large code base, the delegation to other projects (that
focus on linear algebra implementations) seems the more promising approach, IMO
(the devil being in the details, of course).
{quote}But I guess changing the interface is overkill.
{quote}
As indicated above, more drastic changes are considered, so...
> 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)
