Java Intrinsics and Performance
Join the DZone community and get the full member experience.
Join For FreeThe original question was How to count the number of 1's a number will have in binary? I
included a performance comparison of using Integer.bitCount() which can
be turned into an intrinic i.e. a single machine code instruction POPCNT and the Java code which does the same thing.
Question
How do I count the number of1
's a number will have in binary?So let's say I have the number
45
, which is equal to 101101
in binary and has 4 1
's in it. What's the most efficient way to write an algorithm to do this?Answer
Instead of writing an algorithm to do this it's best to use the built in function. Integer.bitCount()What makes this especially efficient is that the JVM can treat this as an intrinsic. i.e. recognise and replace the whole thing with a single machine code instruction on a platform which supports it e.g. Intel/AMD
To demonstrate how effective this optimization is
public static void main(String... args) { perfTestIntrinsic(); perfTestACopy(); } private static void perfTestIntrinsic() { long start = System.nanoTime(); long countBits = 0; for (int i = 0; i < Integer.MAX_VALUE; i++) countBits += Integer.bitCount(i); long time = System.nanoTime() - start; System.out.printf("Intrinsic: Each bit count took %.1f ns, countBits=%d%n", (double) time / Integer.MAX_VALUE, countBits); } private static void perfTestACopy() { long start2 = System.nanoTime(); long countBits2 = 0; for (int i = 0; i < Integer.MAX_VALUE; i++) countBits2 += myBitCount(i); long time2 = System.nanoTime() - start2; System.out.printf("Copy of same code: Each bit count took %.1f ns, countBits=%d%n", (double) time2 / Integer.MAX_VALUE, countBits2); } // Copied from Integer.bitCount() public static int myBitCount(int i) { // HD, Figure 5-2 i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; } prints Intrinsic: Each bit count took 0.4 ns, countBits=33285996513 Copy of same code: Each bit count took 2.4 ns, countBits=33285996513Each bit count using the intrinsic version and loop takes just 0.4 nano-second on average. Using a copy of the same code takes 6x longer (gets the same result)
Java (programming language)
Published at DZone with permission of Peter Lawrey, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
Comments