Java - Big O of bitCount()?

Question

What is the Big O of bit count? I'm not sure how the method works, but I would assume it is done in O(logn).

Specifically with this code (where x = 4, y = 1):

return Integer.bitCount(x^y);

Autumn

What's n in your O(log n)? The total number of bits in the integer? When talking about Big O we set some arbitrary operation to have cost 1, and it's fair to assume bitCount has cost 1. – Pirandello

Actually I'd imagine it's O(1), see e.g. #1458814 – Garnierite

Answer 1

Given its implementation, the method consists of six O(1) statements performed in sequence, so it's O(1).

public static int bitCount(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;
}

Topotype

The JVM is free to implement it differently than the code you see in the JDK source, and in fact it does since it is a "known function". Usually it compiles down to a single popcnt instruction on platforms that support it (most of the interesting ones). Doesn't really change the conclusion though (although it does mean that Integer.bitCount() and Long.bitCount() usually take the same time - which wouldn't be the your conclusion if you looked at the source. – Darkle

Answer 2

It is O(1), here is its implementation for JDK 1.5+:

public static int bitCount(int i) {
    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;
}

Viewer

In practice, this implementation isn't used because on most platforms Integer.bitCount and several other simple methods in the Integer, Long, etc classes are implemented as JVM intrinsics which usually result in a single popcnt type instruction being emitted. Still O(1) though :) – Darkle

That sounds reasonable but can you point to some source code that implements this using JVM intristics (I have found source code which uses exactly the code pasted)? – Viewer

Yes, you have do dig into the C++ source of the JVM. To see if a method is intrinsified check out the vmSymbols.hpp for your version of the JVM and look for the function name. In this case you find a line like do_intrinsic(_bitCount_i, java_lang_Integer, bitCount_name, int_int_signature, F_S) which indicates that the function is potentially an intrinsic. – Darkle

At this point you'd have to dig into the .cpp source to see if it actually is on the platform of interest (usually it is once you find it in the .hpp but it may not be for several reasons such as the lack of support on a particular platform, etc). In the case of bitCount it usually ends up being an instrinsic on modern platforms of interest. Another approach is just to execute the method in question in a hot loop and then use something like perf top to check out the instruction(s) being executed. See also this question. – Darkle

Thanks, that's interesting. – Viewer

... and since I'm being exhaustive, another approach is to copy paste the JDK into a renamed function and then benchmark the original copy and exact copy. If it's normal, not intrinsic code you should get the same time. I tried it now and for Integer.bitCount() I get ~2.0 billion calls to bitCount per second, while for an exact copy of the JDK code I get only 0.4 billion calls/second. – Darkle

@Darkle I didn't know the JVM could supersede an existing source implementation. Is the concept covered in the JLS? Also, what exactly is the difference between intrinsic and native methods? – Rubbing

@Rubbing - as far as I know all intrinsic methods also have a JDK implementation, so that's actually the general rule. The implementation needs to be there since (a) not all platforms may support the intrinsic version (b) there are times when the intrinsic is not used (e.g., in the interpreter) or when debugging and (c) in principle the JDK source is portable to JVM implementations that don't intrinsify stuff. You won't find any mention of this in the JLS - it's at a much lower level. Even the JVM spec won't mention it. It's like how C++ compilers recognize memcpy and replace it, often. – Darkle

@Rubbing - native methods are very different. This is part of the JVM spec (probably the native keyword is briefly mentioned in the JLS as well) for implementing JNI methods. Basically you have a C-like function in some binary, and that function is called and does its work and returns. There are rules for how parameters are passed and various other things. It should work on any platform, etc - although of course you need to include different libraries for different architectures. – Darkle

Intrinsic "methods" on the other hand are quite different in that they are replaced by the JIT in the compiled assembly code. There is no native code sitting around and no function is called. There are just some instructions inside the implemenation of the JIT compiler that says, "hey there is this popcnt assembly instruction, use it when you are compiling code that uses Integer.bitCount. There is effectively zero overhead, while native calls have an overhead of 20 cycles or more, usually. @Rubbing – Darkle

You can think of intrinsic methods as a way of extending java bytecode to cover more primitive operations without actually extending the bytecode (making it operational). There is no popcnt bytecode, but by telling the JIT about the special methods in the Integer class it's almost like there was. Some methods pretty much have to be implemented as an intrinsic, like the methods in the Atomic* classes: those methods have the native keyword but they are actually instrinsics under the covers... – Darkle

Answer 3

Any algorithm that work on input of limited size have complexity of O(1).

bitCount works with input of limited size.

Therefore bitCount have complexity of O(1).

Artificiality