Uploaded image for project: 'Commons Math'
  1. Commons Math
  2. MATH-1654

Matrix implementations of getEntry are slow

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Open
    • Major
    • Resolution: Unresolved
    • 3.6.1, 4.X
    • None
    • None
    • master branch
      3.6.1

    • Easy

    Description

      Inspecting BOBYQA performance, I see a lot of the time is spent into the getEntry method of Array2DRowRealMatrix.
      At each getEntry, a costly MatrixUtils.checkMatrixIndex is performed.
      See flamegraph.

       

      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 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.

      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.

      Attachments

        1. bobyqa_matrix_getEntry_withOpti.txt
          3 kB
          Cyril de Catheu
        2. bobyqa_matrix_getentry_slow.png
          578 kB
          Cyril de Catheu
        3. bobyqa_matrix_getEntry_current.txt
          3 kB
          Cyril de Catheu

        Issue Links

          Activity

            People

              Unassigned Unassigned
              cyrilou242 Cyril de Catheu
              Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

                Created:
                Updated: