Commons Math
  1. Commons Math
  2. MATH-990

Improve performance of MathArrays.sortInPlace

    Details

    • Type: Improvement Improvement
    • Status: Resolved
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: 3.2
    • Fix Version/s: 4.0, 3.6
    • Labels:

      Description

      Performance suffers from lots of copying.

      1. patch
        3 kB
        Otmar Ertl

        Activity

        Hide
        Gilles added a comment -

        New implementation committed in revision 1489871.

        The larger the number of arrays to be sorted "in parallel", the more the performance would suffer in the previous implementation.
        Benchmark for arrays containing 200 elements:

        Number of arrays to be |      Time ratio
         sorted "in parallel"  | New impl. / Old impl.
        -----------------------+-----------------------
                     10        |         0.89
                    100        |         0.56
        
        Show
        Gilles added a comment - New implementation committed in revision 1489871. The larger the number of arrays to be sorted "in parallel", the more the performance would suffer in the previous implementation. Benchmark for arrays containing 200 elements: Number of arrays to be | Time ratio sorted "in parallel" | New impl. / Old impl. -----------------------+----------------------- 10 | 0.89 100 | 0.56
        Hide
        Gilles added a comment -

        Comparison with another code indicates that further improvement is possible, at the cost of explicitly implementing the sorting procedure (on arrays of primitive types) instead of relying on "Collections.sort".

        Show
        Gilles added a comment - Comparison with another code indicates that further improvement is possible, at the cost of explicitly implementing the sorting procedure (on arrays of primitive types) instead of relying on "Collections.sort".
        Hide
        Thomas Neidhart added a comment -

        Added entry in changelog in r1566021.

        Can we close this issue for 3.3? Further improvements can be done later I guess?

        Show
        Thomas Neidhart added a comment - Added entry in changelog in r1566021. Can we close this issue for 3.3? Further improvements can be done later I guess?
        Hide
        Otmar Ertl added a comment -

        The performance can be further improved while still using Collections.sort by avoiding the generic Pair class (see attached patch). A reduction of costs by a factor of 0.8 was observed in case of 2 parallel arrays.

        Show
        Otmar Ertl added a comment - The performance can be further improved while still using Collections.sort by avoiding the generic Pair class (see attached patch). A reduction of costs by a factor of 0.8 was observed in case of 2 parallel arrays.
        Hide
        Gilles added a comment -

        Hi Otmar.

        Somehow I missed this comment.
        Unless someone else objects, feel free to make the proposed modifications (and reassign this issue to yourself).
        Thanks.

        Show
        Gilles added a comment - Hi Otmar. Somehow I missed this comment. Unless someone else objects, feel free to make the proposed modifications (and reassign this issue to yourself). Thanks.
        Hide
        Otmar Ertl added a comment -

        I think I do not have the rights to reassign this issue.

        Show
        Otmar Ertl added a comment - I think I do not have the rights to reassign this issue.
        Hide
        Otmar Ertl added a comment -

        Applied patch in following commits:

        • 72a46babeb0da02071e47425ebd55da915b98178 (4.0)
        • 32c5f86125ea0ce1741a386eff0da5f8455f879c (3.6)
        Show
        Otmar Ertl added a comment - Applied patch in following commits: 72a46babeb0da02071e47425ebd55da915b98178 (4.0) 32c5f86125ea0ce1741a386eff0da5f8455f879c (3.6)

          People

          • Assignee:
            Otmar Ertl
            Reporter:
            Gilles
          • Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development