(int) Math.sqrt(n) much slower than (int) Math.floor(Math.sqrt(n))

Question

I was looking at my code, hoping to improve its performance and then i saw this:

int sqrt = (int) Math.floor(Math.sqrt(n));

Oh, ok, i don't really need the call to Math.floor, as casting the double returned from Math.sqrt(n) will be effectively flooring the number too (as sqrt will never return a negative number). So i went and dropped the call to Math.floor:

int sqrt = (int) Math.sqrt(n)

sat back and complacently watched the code run and perform roughly 10% ! worse than its previous version. This came to me as a shock. Any ideas anyone?

Math.floor javadocs: "Returns the largest (closest to positive infinity) double value that is less than or equal to the argument and is equal to a mathematical integer."

EDIT in my case n is a long. Any chance cast-floor-sqrt would ever produce a different int than cast-sqrt? I personally can't see why it ever would... all numbers involved are positive.

Solution 1

The Math.floor method just delegates the call to the StrictMath.floor method (as seen on java.lang.StrictMath's source code). This method is a native method. After this method the cast does not have to do anything because it is already a number that is equal to an integer (so no decimal places).

Maybe the native implementation of floor is faster than the cast of a double value to an int value.

Solution 2

I cannot reproduce the same results. Using this simple Java code below, the function without the call to Math.floor is consistently faster:

with floor elapsed milliseconds: 7354
without floor elapsed milliseconds: 4252


public class TestCast {
    private static final int REPS = Integer.MAX_VALUE / 4;

    private static void withFloor() {
        long sum = 0;
        long start = System.currentTimeMillis();
        for (int i = REPS;  i != 0;  --i) {
            sum += (int)Math.floor(Math.sqrt(i));
        }
        long end = System.currentTimeMillis();
        long elapsed = end - start;
        System.out.println("with floor elapsed milliseconds: " + elapsed);
        System.out.println(sum);
    }

    private static void withoutFloor() {
        long sum = 0;
        long start = System.currentTimeMillis();
        for (int i = REPS;  i != 0;  --i) {
            sum += (int)Math.sqrt(i);
        }
        long end = System.currentTimeMillis();
        long elapsed = end - start;
        System.out.println("without floor elapsed milliseconds: " + elapsed);
        System.out.println(sum);
    }

    public static void main(String[] args) {
        withFloor();
        withoutFloor();
    }
}

Also, looking at the disassembled byte code we can clearly see the call to Math.floor in the first function and no call in the second. There must be something else going on in your code. Perhaps you can post your code or a shortened version of it that shows the results that you are seeing.

private static void withFloor();
  Code:
     0: lconst_0      
     1: lstore_0      
     2: invokestatic  #2                  // Method java/lang/System.currentTimeMillis:()J
     5: lstore_2      
     6: ldc           #3                  // int 536870911
     8: istore        4
    10: iload         4
    12: ifeq          35
    15: lload_0       
    16: iload         4
    18: i2d           
    19: invokestatic  #4                  // Method java/lang/Math.sqrt:(D)D
    22: invokestatic  #5                  // Method java/lang/Math.floor:(D)D
    25: d2i           
    26: i2l           
    27: ladd          
    28: lstore_0      
    29: iinc          4, -1
    32: goto          10
    35: invokestatic  #2                  // Method java/lang/System.currentTimeMillis:()J
    38: lstore        4
    40: lload         4
    42: lload_2       
    43: lsub          
    44: lstore        6
    46: getstatic     #6                  // Field java/lang/System.out:Ljava/io/PrintStream;
    49: new           #7                  // class java/lang/StringBuilder
    52: dup           
    53: invokespecial #8                  // Method java/lang/StringBuilder."<init>":()V
    56: ldc           #9                  // String with floor elapsed milliseconds: 
    58: invokevirtual #10                 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
    61: lload         6
    63: invokevirtual #11                 // Method java/lang/StringBuilder.append:(J)Ljava/lang/StringBuilder;
    66: invokevirtual #12                 // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
    69: invokevirtual #13                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
    72: getstatic     #6                  // Field java/lang/System.out:Ljava/io/PrintStream;
    75: lload_0       
    76: invokevirtual #14                 // Method java/io/PrintStream.println:(J)V
    79: return        

private static void withoutFloor();
  Code:
     0: lconst_0      
     1: lstore_0      
     2: invokestatic  #2                  // Method java/lang/System.currentTimeMillis:()J
     5: lstore_2      
     6: ldc           #3                  // int 536870911
     8: istore        4
    10: iload         4
    12: ifeq          32
    15: lload_0       
    16: iload         4
    18: i2d           
    19: invokestatic  #4                  // Method java/lang/Math.sqrt:(D)D
    22: d2i           
    23: i2l           
    24: ladd          
    25: lstore_0      
    26: iinc          4, -1
    29: goto          10
    32: invokestatic  #2                  // Method java/lang/System.currentTimeMillis:()J
    35: lstore        4
    37: lload         4
    39: lload_2       
    40: lsub          
    41: lstore        6
    43: getstatic     #6                  // Field java/lang/System.out:Ljava/io/PrintStream;
    46: new           #7                  // class java/lang/StringBuilder
    49: dup           
    50: invokespecial #8                  // Method java/lang/StringBuilder."<init>":()V
    53: ldc           #15                 // String without floor elapsed milliseconds: 
    55: invokevirtual #10                 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
    58: lload         6
    60: invokevirtual #11                 // Method java/lang/StringBuilder.append:(J)Ljava/lang/StringBuilder;
    63: invokevirtual #12                 // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
    66: invokevirtual #13                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
    69: getstatic     #6                  // Field java/lang/System.out:Ljava/io/PrintStream;
    72: lload_0       
    73: invokevirtual #14                 // Method java/io/PrintStream.println:(J)V
    76: return        

Comments

[Peter Perháč]

but the call to .floor still returns a double and i still do the cast... it just looks like the cost of this cast now has been... optimized away or something.

[mvieghofer]

Yes, that's what I think. Maybe this is optimized because the returned double is basically an integer. So e.g. 4.00 and the cast just drops the .00. Maybe this is that much faster when there are no actual decimal places...

[Holger]

Don’t get fooled by how the methods inside java.lang.Math might look like in the source code. The JVM might replace all of them by an intrinsic function (i.e. CPU instruction) at runtime.