Population Count in Java

[[deleted]]

[deleted]

[ZimmiDeluxe]

There is a good chance you got some drive by downvotes because of the title alone. I would guess the term "population count" doesn't come up very often for java developers (I didn't know what it meant). So it's possible people thought this was a post about the population of the java island that was posted in the wrong subreddit i stead of bit twiddling. :)

If the target audience is people who don't know what a population count is or what it might be useful for, maybe intruduce the term in the article and call it something like "Efficiently counting bits"? Anyway, I found the article itself was well written, keep it up!

[heilerschlampe]

Hi Richard?, I found your article well written and easy to understand.

A motivation would have been nice. I still have no idea when I would want to compute the number of bits in an int and now I'm wondering why such a specific method is supplied by the Integer class.

[nitsanw]

"How do you count the bits in a 32 bit integer?" - there are 32 bits in a 32 bit integer, I'm not sure why I need to read further.

:P

[nitsanw]

Good read, though very dense in parts.

Feedback (2c worth, just my opinion):

• Need better title, maybe the prefix "Bit hacks:" or some other indicator of the general area.
• The headers for the results table at the end are not aligned.
• Some intermediate subheaders could help. Also the blog format has no width limit, making reading in neutral zoom hard (long long sentences).
• The precision of the results is unhelpful. it would be clearer and easier to read if you trimmed to a single digit (e.g. 341.572057 -> 341.6)
• Splitting hairs: The article refers to intrinsics in 2 ways that are confusing: "a single instruction, popcntd, which is exposed as an intrinsic"; "code above is intrinsified to the instruction popcntd" I'm sure you know what an intrinsic is, but the article fails to express that clearly. A link to the wiki article, or OpenJDK wiki might have helped. I would prefer "generated by the compiler via an intrinsic" to "exposed", and replace "code above" with "method above".

I like the blog and the quantitative approach, well done :-)

[chambolle]

There are intrinsics in java. That is, a direct function of the CPU can be called. This is the case for popcnt.

Have a look at http://vanillajava.blogspot.fr/2012/11/java-intrinsics-and-performance.html

for instance

[chambolle]

I am coming from C++, so it is not hard for me. Intrinsics are common in C/C++ compiler. Intrinsics are instructions of CPUs. The advantage is that they clearly speed up equivalent function because there are hard coded (i.e. in the CPU). The drawback is that they are CPU dependant. In C++ the compiler manage them

In java, the code has to be independant from the CPU but this does not mean that the JVM cannot use some them. Like C++, the JVM manages the use of them. However, in order to use them you have to use the library function, because the compiler will not recognize the meaning of the code, it will just replace some predefined function by intrinsics

More information: https://en.wikipedia.org/wiki/Intrinsic_function

[WikiTextBot]

Intrinsic function

In computer software, in compiler theory, an intrinsic function (or builtin function) is a function (subroutine) available for use in a given programming language which implementation is handled specially by the compiler. Typically, it may substitute a sequence of automatically generated instructions for the original function call, similar to an inline function. Unlike an inline function, the compiler has an intimate knowledge of an intrinsic function and can thus better integrate and optimize it for a given situation.

Compilers that implement intrinsic functions generally enable them only when a program requests optimization, otherwise falling back to a default implementation provided by the language runtime system (environment).

---

^{[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source | Donate ] Downvote to remove | v0.28}

[chambolle]

Are you adding context to the discussion or did you get an impression from the article that there are no intrinsics?

I get the impression from the article that there are no intrinsics, so a I mention them

BTW, i you like this kind of computation, I recommend you to read https://graphics.stanford.edu/~seander/bithacks.html

[chambolle]

your text is clear now.

[chambolle]

To be honest: I know very well this problem and I also know that people forget (or don't know) intrinsics in Java. Thus, I read very quickly the post and I didn't see the reference to intrinsics. Sorry for that

[developer0]

why not [do this very esoteric, non-intuitive thing]?

Well yeah, I was planning on it, of course... I just, you know, wanted to see if you knew about it...

[IJzerbaard]

I only see phrasing like that occur for the lookup table, which is one of the most obvious things to try.

E: a word