RVM
  1. RVM
  2. RVM-26

Float.compare(float, float) and Double.compare(double, double) are very expensive and in the heart of key loops

    Details

    • Type: Improvement Improvement
    • Status: Closed Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 2.9.1
    • Component/s: Runtime: Class Library
    • Labels:
      None
    • Environment:
      All
    • Number of attachments :
      0

      Description

      In Arrays.qsort the methods Float.compare and Double.compare are used depending on the values in the array. The compare operations perform the following (copied from GNU Classpath):

      if (isNaN)
      return isNaN ? 0 : 1;
      if (isNaN)
      return -1;
      // recall that 0.0 == -0.0, so we convert to infinites and try again
      if (x == 0 && y == 0)
      return (int) (1 / x - 1 / y);
      if (x == y)
      return 0;
      return x > y ? 1 : -1;

      In the normal case we're going to hit 6 floating point compares. The case of 0, 0 is common due to using qsort on branch profiles, and this results in 2 divides and 1 subtract. Given we're just comparing to values we should be able to do this substantially cheaper in a VM specific/magic version.

        Activity

        Ian Rogers made changes -
        Field Original Value New Value
        Assignee Ian Rogers [ ianrogers ]
        Hide
        Ian Rogers added a comment -

        A partial fix to this issue is to use floatToIntBits to inspect the sign bit of the float. By dismissing the case where the two values have identical bit patterns and NaNs, we can do a cheap test of whether the sign bits differ where it doesn't matter whether x and y are 0.0 or not (in the following code this is ix_sign - iy_sign). This code removes one compare from the normal path as well as making 2 of the compares int rather than float comparisons:

        public static int compare(float x, float y)
        {
        int ix = floatToIntBits;
        int iy = floatToIntBits;
        if (ix == iy) return 0;
        if (isNaN) return 1;
        if (isNaN) return -1;
        int ix_sign = ix>>31;
        int iy_sign = iy>>31;
        if (ix_sign == iy_sign)

        { return x > y ? 1 : -1; }

        else

        { return ix_sign - iy_sign; }

        }

        this code speeds up an optimizing compiler build on IA32 by a little under 8%. It slows a baseline compiler build because of the method call overhead. I will make and submit a Classpath patch for this and for the Double case. We're still not fully exploiting the fact that a comparison of x and y would give us NaN information on both of them. NaN's are the uncommon case but they take precedence here in order to maintain correct semantics

        Show
        Ian Rogers added a comment - A partial fix to this issue is to use floatToIntBits to inspect the sign bit of the float. By dismissing the case where the two values have identical bit patterns and NaNs, we can do a cheap test of whether the sign bits differ where it doesn't matter whether x and y are 0.0 or not (in the following code this is ix_sign - iy_sign). This code removes one compare from the normal path as well as making 2 of the compares int rather than float comparisons: public static int compare(float x, float y) { int ix = floatToIntBits ; int iy = floatToIntBits ; if (ix == iy) return 0; if (isNaN ) return 1; if (isNaN ) return -1; int ix_sign = ix>>31; int iy_sign = iy>>31; if (ix_sign == iy_sign) { return x > y ? 1 : -1; } else { return ix_sign - iy_sign; } } this code speeds up an optimizing compiler build on IA32 by a little under 8%. It slows a baseline compiler build because of the method call overhead. I will make and submit a Classpath patch for this and for the Double case. We're still not fully exploiting the fact that a comparison of x and y would give us NaN information on both of them. NaN's are the uncommon case but they take precedence here in order to maintain correct semantics
        Hide
        Ian Rogers added a comment -

        This is partially resolved by the patch to Classpath contained in r12854. In the longer term we should move this out to magic code, but at least this patch removes two floating point divides, a subtract and f2i out of an important path in the opt compiler.

        Show
        Ian Rogers added a comment - This is partially resolved by the patch to Classpath contained in r12854. In the longer term we should move this out to magic code, but at least this patch removes two floating point divides, a subtract and f2i out of an important path in the opt compiler.
        Ian Rogers made changes -
        Fix Version/s 2.9.1 [ 13529 ]
        Status Open [ 1 ] Resolved [ 5 ]
        Resolution Fixed [ 1 ]
        Hide
        Andrew John Hughes added a comment -

        Patch committed to GNU Classpath:

        http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33741

        2007-10-12 Ian Rogers <ian.rogers@manchester.ac.uk>
        2007-10-12 Andrew Haley <aph@redhat.com>

        PR classpath/33741:

        • java/lang/Double.java:
          (compare(double,double)): Increase performance
          of this method.
        • java/lang/Float.java:
          (compare(float,float)): Likewise.
        Show
        Andrew John Hughes added a comment - Patch committed to GNU Classpath: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33741 2007-10-12 Ian Rogers <ian.rogers@manchester.ac.uk> 2007-10-12 Andrew Haley <aph@redhat.com> PR classpath/33741: java/lang/Double.java: (compare(double,double)): Increase performance of this method. java/lang/Float.java: (compare(float,float)): Likewise.
        Hide
        David Grove added a comment -

        we've switched to 0.96.

        Show
        David Grove added a comment - we've switched to 0.96.
        David Grove made changes -
        Status Resolved [ 5 ] Closed [ 6 ]

          People

          • Assignee:
            Ian Rogers
            Reporter:
            Ian Rogers
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved: