Difference in time complexity in array addressing in Java

So I have a random question when coding the image processing function that involves time complexity. The following is my original snippet of code:

    long start = System.currentTimeMillis();

    for (int i = 0; i < newWidth; i++) {
        for (int j = 0; j < newHeight; j++) {

            double x = i * scaleX;
            double y = j * scaleY;

            double xdiff = x - (int) x;
            double ydiff = y - (int) y;

            int xf = (int) Math.floor(x);
            int xc = (int) Math.ceil(x);
            int yf = (int) Math.floor(y);
            int yc = (int) Math.ceil(y);

            double out = inputArray[xf][yf] * (1 - xdiff) * (1 - ydiff)
                    + inputArray[xc][yf] * xdiff * (1 - ydiff)
                    + inputArray[xf][yc] * (1 - xdiff) * ydiff
                    + inputArray[xc][yc] * xdiff * ydiff;

            outputArray[i][j] = (int) out;
        }
    }

    long elapsed = System.currentTimeMillis() - start;
    System.out.println("Time used: " + elapsed);

And after coming out with that code, I was wondering whether it would be faster not to create 4 temporary variables for floor and ceiling values but, instead, calculate them directly in array indexing. So I modified it this way:

    long start = System.currentTimeMillis();

    for (int i = 0; i < newWidth; i++) {
        for (int j = 0; j < newHeight; j++) {

            double x = i * scaleX;
            double y = j * scaleY;

            double xdiff = x - (int) x;
            double ydiff = y - (int) y;

            double out = inputArray[(int) Math.floor(x)][(int) Math.floor(y)] * (1 - xdiff) * (1 - ydiff)
                    + inputArray[(int) Math.ceil(x)][(int) Math.floor(y)] * xdiff * (1 - ydiff)
                    + inputArray[(int) Math.floor(x)][(int) Math.ceil(y)] * (1 - xdiff) * ydiff
                    + inputArray[(int) Math.ceil(x)][(int) Math.ceil(y)] * xdiff * ydiff;

            outputArray[i][j] = (int) out;
        }
    }

    long elapsed = System.currentTimeMillis() - start;
    System.out.println("Time used: " + elapsed);

I was expecting the later to be faster (because you don't have to write to a temporary variab开发者_如何转开发le and then access it) but it turned out that the later is, at least, 2.5 times slower than the former code. Test case used is 3x zoom of 1024x768 img.

former code: Time used: 812 later code: Time used: 2140

So what is cause of the time difference?

You have 8 Math.floor() / Math.ceil() calculation in the later code instead of 4. That's the problem.

The calculation is much slower than allocating space for a local variable.

Q: How many times are you calling "floor" and "ceil" in the first case? The second case? ;)

Q: I'm wondering if this would run any faster than the first case:

    long start = System.currentTimeMillis();

    for (int i = 0; i < newWidth; i++) {
        double x = i * scaleX;
        double xdiff = x - (int) x;
        int xf = (int) Math.floor(x);
        int xc = (int) Math.ceil(x);
        for (int j = 0; j < newHeight; j++) {
            double y = j * scaleY;
            double ydiff = y - (int) y;

            int yf = (int) Math.floor(y);
            int yc = (int) Math.ceil(y);

            double out = inputArray[xf][yf] * (1 - xdiff) * (1 - ydiff)
                    + inputArray[xc][yf] * xdiff * (1 - ydiff)
                    + inputArray[xf][yc] * (1 - xdiff) * ydiff
                    + inputArray[xc][yc] * xdiff * ydiff;

            outputArray[i][j] = (int) out;
        }
    }

    long elapsed = System.currentTimeMillis() - start;
    System.out.println("Time used: " + elapsed);

floor and ceil have a performance cost.

Your second case calls them twice as often.

In the second one you are repeating calculations. By capturing this in a variable in the first example you avoid repeating calculations.

The later is likely to be slower because its doing more work. Setting a temporary variable is trivial, but calculating floor and ceil can be surprisingly expensive.

BTW: When x is positive, (int) Math.floor(x) is the same as (int) x so you don't need to calculate it twice.

Also, you can assume that xc = xf + 1 in this situation and similar for y

The miniscule operations of saving and looking up a local variable pale in comparison to Math.floor and Math.ceil. Also, you are casting to int more often in the second snippet.

You can simply cast double to int instead of using Math.floor(). It will be faster.

instead of:

inputArray[(int) Math.floor(x)]

just:

inputArray[(int) x]