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.

        Gliffy Diagrams

          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: