Uploaded image for project: 'JikesRVM'
  1. JikesRVM
  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
    • Status: Closed
    • Priority: Low
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 2.9.1
    • Component/s: Runtime: Class Library
    • Labels:
      None
    • Environment:

      All

      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.

        Attachments

          Activity

          dgrove David Grove created issue -
          Hide
          ianrogers 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
          ianrogers 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
          ianrogers 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
          ianrogers 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.
          Hide
          gnu_andrew 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
          gnu_andrew 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
          dgrove David Grove added a comment -

          we've switched to 0.96.

          Show
          dgrove David Grove added a comment - we've switched to 0.96.
          dgrove David Grove made changes -
          Field Original Value New Value
          Workflow jira [ 18006 ] X10 Workflow [ 19130 ]
          dgrove David Grove made changes -
          Priority Minor [ 7 ] Low [ 4 ]

            People

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

              Dates

              • Created:
                Updated:
                Resolved: