Rust's integer intrinsics are impressive
41 comments
I like that it compiles to a single instruction, but lots of languages already have this; it's pretty common.
Even boring old Java has had Integer.bitCount for many years.
Even boring old Java has had Integer.bitCount for many years.
I don't know if http://grepcode.com/file/repository.grepcode.com/java/root/j... is representative of all the implementations of bitCount in Java, but it's probably obvious that it's not going to use the popcnt opcode instruction.
I think the point is that Rust makes it much easier to use that opcode instruction. It's possible but hard with GCC using __builtin_popcount(), but, I'd guess totally impossible in Java due to lack of a JVM instruction for the same.
I think the point is that Rust makes it much easier to use that opcode instruction. It's possible but hard with GCC using __builtin_popcount(), but, I'd guess totally impossible in Java due to lack of a JVM instruction for the same.
That's just the placeholder implementation that will work on any platform and even with the interpreter.
If you look at the openjdk9 sources you will notice that it is annotated as intrinsic candidate[0]. But earlier versions also have intrinsics for that[1], it's just not annotated as such.
[0] http://hg.openjdk.java.net/jdk9/jdk9/jdk/file/23721aa1d87f/s... [1] https://gist.github.com/apangin/7a9b7062a4bd0cd41fcc#file-ho...
If you look at the openjdk9 sources you will notice that it is annotated as intrinsic candidate[0]. But earlier versions also have intrinsics for that[1], it's just not annotated as such.
[0] http://hg.openjdk.java.net/jdk9/jdk9/jdk/file/23721aa1d87f/s... [1] https://gist.github.com/apangin/7a9b7062a4bd0cd41fcc#file-ho...
> obvious that it's not going to use the popcnt opcode instruction ... I'd guess totally impossible in Java
I don't understand why you would guess at what Java can do when you can find out for certain?
I don't understand why you would guess at what Java can do when you can find out for certain?
public class Test {
private static int bitCount(int a) {
return Integer.bitCount(a);
}
public static void main(String[] args) {
while (true) {
bitCount(14);
}
}
}
0x000000011e637980: sub rsp,0x18
0x000000011e637987: mov QWORD PTR [rsp+0x10],rbp ;*synchronization entry
; - Test::bitCount@-1 (line 4)
0x000000011e63798c: popcnt eax,esi ;*invokestatic bitCount
; - Test::bitCount@1 (line 4)
0x000000011e637990: add rsp,0x10
0x000000011e637994: pop rbp
0x000000011e637995: test DWORD PTR [rip+0xfffffffff10ed665],eax # 0x000000010f725000
; {poll_return}
0x000000011e63799b: ret
There are methods in Java which have special vm implementations to take advantage of instructions like this. They methods have an ordinary Java code version for the interpreter and on jit compilation are replaced with the other version. For a complete list of these types of functions see http://hg.openjdk.java.net/jdk8/jdk8/hotspot/file/87ee5ee275...
JIT-compiler might recognize this call and replace it with popcnt instruction. I'm not sure if it does that, though.
Yea, this is really nothing special—I'd imagine anything that compiles to native code would need all the
I did some experimentation with popcnt in C++ six years ago and was impressed to find that the intrinsic in gcc was faster than the best inline assembly I could come up with using the popcnt instruction:
https://github.com/bobbyi/Fast-Bit-Counting
https://github.com/bobbyi/Fast-Bit-Counting
Now that most CPUs have population count, it may as well be exposed at the language level.
Doing it by table lookup results in questions such as "am I wasting too much cache space on this?" and "is a 64K table causing cache misses".
Doing it by table lookup results in questions such as "am I wasting too much cache space on this?" and "is a 64K table causing cache misses".
Fortran 2008 added a number of bit twiddling intrinsics[0].
Here are a few of the scalar intrinsics for bit counting.
Edited to fix formatting.
Here are a few of the scalar intrinsics for bit counting.
popcnt() - population count
leadz() - leading zero
trailz() - trailing zero
poppar() - parity
Edited to fix formatting.
> be exposed at the library level.
TFTFY :-)
TFTFY :-)
Exactly what purpose does the surrounding instructions serve in this and similar simple cases? Is it compiler dogma or a missed uncommon optimization?
push rbp
mov rbp, rsp
popcnt eax, edi
pop rbp
retIt's a function invocation following x86 C calling convention in assembly. push ebp pushes the base stack pointer of the caller of count() onto the stack, and mov ebp, esp sets the base stack pointer for the callee count(). pop ebp pops the base stack pointer and ret pops the return address into the program counter. count_ones() is replaced with its assembly counterpart, which stores the result in return register eax. This is as optimized as count() as a user-created function can be in assembly given the calling convention.
https://en.m.wikipedia.org/wiki/X86_calling_conventions
Correction: rsp and rbp are 64-bit registers storing 64-bit stack memory addresses, while popcount eax, edi is taking the 32-bit parameter as input and returning the 32-bit return value. The calling convention is x64 C.
GCC, for example, allows a "-fomit-frame-pointer" [1] optimization option which would get rid of this. I'm not sure why this isn't done by default in optimized builds. Maybe it has something to do with stack unwinding: if the functions panics for some reason, or triggers a CPU fault, there's no way to get the correct backtrace if you don't have the frame pointers on the stack.
[1]: https://gcc.gnu.org/onlinedocs/gcc-3.4.4/gcc/Optimize-Option...
[1]: https://gcc.gnu.org/onlinedocs/gcc-3.4.4/gcc/Optimize-Option...
A function is being called, so it gets a stack frame at the start of the call and that stack frame goes away when it returns.
rbp points to the base of the current stack frame (register base pointer) and rsp points to the top of the current stack frame (register stack pointer).
What the function actually does is just the single popcnt instruction.
rbp points to the base of the current stack frame (register base pointer) and rsp points to the top of the current stack frame (register stack pointer).
What the function actually does is just the single popcnt instruction.
Yes, I get the reserve space for local variables and so on.
But this is a leaf-function and one that has no register trashing or temporary variables. Could this be inlined later on via link-time optimizations? Will the linker then remove that function prologue and epilogue?
But this is a leaf-function and one that has no register trashing or temporary variables. Could this be inlined later on via link-time optimizations? Will the linker then remove that function prologue and epilogue?
Yeah, it can certainly be inlined or optimized away with various compiler options. However, as you might surmise, debugging without stack frames becomes rather difficult as functions corresponding to source code disappear into a goo of assembly.
The example with slightly different options (as mentioned in another comment) gives what you're looking for: https://godbolt.org/g/GlkEQK
The example with slightly different options (as mentioned in another comment) gives what you're looking for: https://godbolt.org/g/GlkEQK
gcc has the -fomit-leaf-frame-pointer option at least.
Those are the function prologue and function epilogue. https://en.wikipedia.org/wiki/Function_prologue
[deleted]
It's exposed as an intrinsic in llvm. C(99? I think) surfaces these in math.h, although the standard is silent on some edge cases (all zeros), and numbers are autopromoted to 32 bit integer. Julia surfaces these as well.
In case you're wondering what this could be useful for besides super secret NSA stuff, and Bitcoin mining, here are a few suggestions:
1) hyperloglog. (Similar to Bitcoin). Keep an estimated count of items streaming by by hashing them and store the highest lzcount of the hashes for each category you're tracking. This will be ~ log2(category count)
2) converting from fixed point to floating point. The number of zeros in front of your value represents the exponent of your value (or ones in the case of a 2's complement negative fixed point), which is critical to deducting the float representation.
Along those lines, one of the things I've done is implemented floating point-like datatypes, which extensively uses lzcount and locount for tracking values and also will use tzcount to measure if the values are exact or not.
https://github.com/Etaphase/FastSigmoids.jl/blob/master/READ...
In case you're wondering what this could be useful for besides super secret NSA stuff, and Bitcoin mining, here are a few suggestions:
1) hyperloglog. (Similar to Bitcoin). Keep an estimated count of items streaming by by hashing them and store the highest lzcount of the hashes for each category you're tracking. This will be ~ log2(category count)
2) converting from fixed point to floating point. The number of zeros in front of your value represents the exponent of your value (or ones in the case of a 2's complement negative fixed point), which is critical to deducting the float representation.
Along those lines, one of the things I've done is implemented floating point-like datatypes, which extensively uses lzcount and locount for tracking values and also will use tzcount to measure if the values are exact or not.
https://github.com/Etaphase/FastSigmoids.jl/blob/master/READ...
I've been using bit population count to traverse packed sparse arrays since the CDC 6600, so it's handy for more things than Hamming distance. Always nice to have in hardware, but pretty cheap to synthesize when it isn't.
Reading http://0x80.pl/articles/sse-popcount.html, I would think the hardware instruction is slower than the best software implementation. Or has that changed on newer hardware?
This would not apply to the Rust method shown in the OP, since that one is operating on only 32 bits at a time.
It's unclear how well the benchmarks in this linked article generalize to other applications. If you are just popcounting in a tight loop, probably pretty well, but who does that? In reality you have other things going on, so if this method is occupying too many execution units or polluting your cache, you would see the effect of that on the rest of the program. But it's program-dependent, thus unclear.
It's unclear how well the benchmarks in this linked article generalize to other applications. If you are just popcounting in a tight loop, probably pretty well, but who does that? In reality you have other things going on, so if this method is occupying too many execution units or polluting your cache, you would see the effect of that on the rest of the program. But it's program-dependent, thus unclear.
> since that one is operating on only 32 bits at a time.
https://doc.rust-lang.org/std/primitive.u64.html#method.coun...
https://doc.rust-lang.org/std/primitive.u128.html#method.cou...
Of course to benefit from the SSE optimizations you would still have to call it in a loop and the optimizer would have to recognize that and replace it with a vectorized approach.
https://doc.rust-lang.org/std/primitive.u64.html#method.coun...
https://doc.rust-lang.org/std/primitive.u128.html#method.cou...
Of course to benefit from the SSE optimizations you would still have to call it in a loop and the optimizer would have to recognize that and replace it with a vectorized approach.
you can do the simd intrinsics explicitly as well
This submission originally linked to a blog post whose author (not the HN submitter) asked us to delete it. We don't want to kill the thread, so we removed the URL above.
I was once asked to come up with a table lookup method for popcount on the spot and could not come up with a solution.
Oh, Hacker News.
If someone can't solve a problem like this off the top of their head, does it not act as a strong signal that they are a beginner and you should probably look elsewhere for quality information?
Oh, Hacker News.
If someone can't solve a problem like this off the top of their head, does it not act as a strong signal that they are a beginner and you should probably look elsewhere for quality information?
Whoa. Some links (with sometimes not-very-well-thought-out allegations):
https://groups.google.com/forum/#!topic/comp.arch/UXEi7G6WHu...
https://www.schneier.com/blog/archives/2014/05/the_nsa_is_no...