Java: signed shift performance on long, putting in maps

Question

I just changed the question a little to get the main focus on shifting.

While I did some shifting, I just recognized that a << 32 is incredibly slower than a << 16 on long.

So I just created a class for testing shifting and I wonder for the results. that huge?

Here the full class if you want to try yourself.

import java.util.HashMap;
import java.util.Map;

public class test {

    public static void main(String[] args) {

        int y_start = 0, x_start = 0;
        int y_runs = 1024, x_runs = 1024;
        int y_end = y_start + y_runs, x_end = x_start + x_runs;
        long time = 0;

        System.out.println(y_runs+" * "+x_runs+" = "+(y_runs+1)*(x_runs+1)+" loops each");
        for (int i = 0; i<=64; i++) {
            Map<Long, String> map = new HashMap<Long, String>();
            time = -System.nanoTime();
            for (int y = y_start; y < y_end; y++){
                for (int x = x_start; x < x_end; x++) {
                    map.put(((long) y << i) + (long) x, "ABCDEF");
                }
            }
            time += System.nanoTime();
            System.out.println("<< "+i+": "+time/1000000+"ms");
        }

    }
}

I run a test with 512 * 512 loops. Whats interesting that on << 29 to << 34 it becomes slower than on any other shift, with a peak at << 32.

When I run the same test with 1024 * 1024 loops (equals to +1 Bit or quadrupling) the numbers become incredibly slow. But only from << 26 to << 37 with the peak at << 32 again.

I guess on doubling the loops per dimension will result in a similar increase. So why are the signed shifts around << 32 so slow?! That really bugs me.

SOLVED: As pointed out, that the problem is actually the put() method of Map. Cause it checks for existant entries using the Longs hashCode(). So the << 32 (and close) actually get the worst out of the hashcode results.

Answer 1

You are not measuring shift, but rather HashMap.put.
Look at Long.hashCode() implementation and you'll see why << 32 is the turning point.