danluu knows much more about the subject matter than me. Meanwhile...
If I take the main.cpp from http://www.strchr.com/media/crc32_popcnt.zip that he comparing and paste it into a new, default, VC2010 project. Then compile it as a Release build, then the mixed disassembly for the inner loop of POPCNT_HardwareSubbuN() looks like
This also has the false dependency problem (using eax as the popcnt destination register three times), and neither one of your VC examples is using the 8 byte popcnt instruction.
In writing a fast Hamming distance library in Go, dropping inline popcnt64 in using cgo was far slower than good, old-fashioned lookup table method for a single byte on a Haswell mobile processor. For the uint64 case, bitfolding was still faster than popcnt64. Perhaps for the vector buffer case, popcnt64 is faster.
Actually, it's not as good, because it doesn't take into account the false dependency issue - the register ebx is reused for three of the popcnts, making it impossible for them to execute in parallel on the buggy processors.
But it's not out of the question that MSVC is better with intrinsics in general... I don't have any experience with it myself.
One thing that has always interested me, how is backwards compatibility done for older CPU instruction set?
Like the new VFMADD* instructions. So if I wanted to write a binary which supports post-2013 CPUs as well as previous ones, my way of doing this would be:
1) have a huge array of function pointers for every function that could use said instructions
2) in main() check if the CPU supports the instructions, if yes: populate array with fast functions, if not, populate with backwards-compatible functions.
Naturally this comes with a performance hit at every call as at least one (or two, if you fill the arrays at compiletime, and in main just switch the array pointer) indirections. Is this really how stuff gets done?
If you're using shared libraries in your program, you already have this extra indirection - at compilation/link time the compiler/linker doesn't know where in memory the shared library will be when the program is run, so every call into a library goes through the procedure linkage table (PLT), which works by looking up the 'real' function pointer in the global offset table (GOT).
So yea, populating this at runtime depending on the CPU features supported by your CPU is possible, and the linux dynamic linker does this: http://man7.org/linux/man-pages/man8/ld.so.8.html (check out the section on hardware capabilities).
Two implementations are compiled (one is optimized using instructions only available on certain processors), and the decision of which one to use is made at program startup.
As far as I know you can do stuff like dynamic linking the right libraries as needed, or use different code paths / function points / virtual functions for those instructions.
Linux on ARM used to have an ABI called OABI which would assume the CPU had FPU support, in case it didn't the kernel would catch the exception, perform the FPU operation in the kernel and return the result back to the program. This ended up being incredible slow however, with performance penalties for hardfpu machines as well. The new ABI (EABI) requires that the binary be built either for soft or hard float, which no longer requires the kernel to get involved.
What you describe is exactly what's done by most software. In fact, there are often several versions of each function, for each variety of CPU instructions supported. Take a look at x264 or libvpx for an example.
Even more ideally you wouldn't need intrinsics. You'd just say what you want, with all constraits. E.g. I have two integers, this is their signedness, this is the range of expected inputs, this is the probability of the inputs, and this is what I want with them, nothing more... now you compiler figure it out.
Now the compiler too often generates suboptimal code because it has to take edge cases that it doesn't know don't matter here into account.
And then you have only those limited not actually well specified operators of C (something as simple as "+" is not fully specified on signed integers), so you can tell even less well what you actually want to the compiler... You can't even do a simple overflow check without bordering on undefined behaviour that allows compilers to do whatever they want.
If you could tell better what you want, the compiler could better choose the perfect CPU instructions for it.
So imho, a programmer shouldn't choose the CPU instruction as that doesn't allow portability, but the programmer should have the ability to specify things better than C now allows :)
You can convey some of that information to the compiler by using __builtin_unreachable(), e.g.:
#define ASSUME(x) if(!(x))__builtin_unreachable()
This is compiler-specific, of course, and introduces undefined behavior if the assumption is violated. There's also no guarantee that the compiler will use the information well. But, it's almost guaranteed to not generate any extra code based on it.
Seems like the under-definedness of integer addition would allow the compiler to emit better code, not worse, because it doesn't have to check for overflow.
The optimal compiler with perfect knowledge theory never really comes true, and it's been around for a long long time. Many years ago some people said that java would be faster than C, because it can optimize based on information learned at run-time, and there was even a microbenchmark or two to prove it (against naive c of course). They also said that Itanium's crazy VLIW architecture would allow compilers to make more efficient use of processor resources than hardware out-of-order instruction schedulers could. It's been a decade since the height of java and Itanium, and the results speak for themselves.
This popcount thing is a great example. All your layers of abstraction didn't save you from a bug in the lowest layer! (Granted, the only result is some inefficiency, and we sacrifice that all the time.) Keep it simple, you can use abstractions but keep them transparent and debugable. Or not. But don't tell me I should use a high level language and trust the compiler and runtime. Never trust...
Not all the purposes. Abstractions can still make the complexity more manageable. Linux kernel developers write the vast majority of their code in C but very often inspect the assembly instructions generated by the compiler. Web developers have many templating languages with macro capabilities (or sass for css), but still want the generated html to be basically readable, so they can verify the templating is doing what they want, and they can debug things.
Some people really can and do ignore things below a particular abstraction, but then there are others who must service that layer transition. And not just the original authors of it. If you have an effective web company of more than, perhaps, 30 developers, at least one of them is dealing with server connection state statistics, occasionally problematic internet routes, occasionally problematic switch configuration or hardware (even on an opaque cloud platform). Someone has to deal with it, or else stuff is kinda flaky, and no one seems to know why...
Before dropping down to assembly or even intrinsics, check out ISPC. It's a little tricky to learn how to use varying and uniform and the compiler crashes here and there, but my god if it doesn't produce crazy fast programs.
24 comments
[ 3.0 ms ] story [ 63.6 ms ] threadIf I take the main.cpp from http://www.strchr.com/media/crc32_popcnt.zip that he comparing and paste it into a new, default, VC2010 project. Then compile it as a Release build, then the mixed disassembly for the inner loop of POPCNT_HardwareSubbuN() looks like
which looks to me to be as good or better than his inline asm And does not have the odd He was complaining about.Maybe there's some compiler issue about arrays that makes using "int cnt[4];" as the accumulator induce the seemingly extraneous movls?
But it's not out of the question that MSVC is better with intrinsics in general... I don't have any experience with it myself.
Like the new VFMADD* instructions. So if I wanted to write a binary which supports post-2013 CPUs as well as previous ones, my way of doing this would be:
1) have a huge array of function pointers for every function that could use said instructions
2) in main() check if the CPU supports the instructions, if yes: populate array with fast functions, if not, populate with backwards-compatible functions.
Naturally this comes with a performance hit at every call as at least one (or two, if you fill the arrays at compiletime, and in main just switch the array pointer) indirections. Is this really how stuff gets done?
So yea, populating this at runtime depending on the CPU features supported by your CPU is possible, and the linux dynamic linker does this: http://man7.org/linux/man-pages/man8/ld.so.8.html (check out the section on hardware capabilities).
Two implementations are compiled (one is optimized using instructions only available on certain processors), and the decision of which one to use is made at program startup.
Linux on ARM used to have an ABI called OABI which would assume the CPU had FPU support, in case it didn't the kernel would catch the exception, perform the FPU operation in the kernel and return the result back to the program. This ended up being incredible slow however, with performance penalties for hardfpu machines as well. The new ABI (EABI) requires that the binary be built either for soft or hard float, which no longer requires the kernel to get involved.
Nearly impossible to do in a high-level language, but it's the way an Asm programmer would probably think of doing it.
Now the compiler too often generates suboptimal code because it has to take edge cases that it doesn't know don't matter here into account.
And then you have only those limited not actually well specified operators of C (something as simple as "+" is not fully specified on signed integers), so you can tell even less well what you actually want to the compiler... You can't even do a simple overflow check without bordering on undefined behaviour that allows compilers to do whatever they want.
If you could tell better what you want, the compiler could better choose the perfect CPU instructions for it.
So imho, a programmer shouldn't choose the CPU instruction as that doesn't allow portability, but the programmer should have the ability to specify things better than C now allows :)
This popcount thing is a great example. All your layers of abstraction didn't save you from a bug in the lowest layer! (Granted, the only result is some inefficiency, and we sacrifice that all the time.) Keep it simple, you can use abstractions but keep them transparent and debugable. Or not. But don't tell me I should use a high level language and trust the compiler and runtime. Never trust...
Wouldn't it defeat the purpose of abstraction?
Some people really can and do ignore things below a particular abstraction, but then there are others who must service that layer transition. And not just the original authors of it. If you have an effective web company of more than, perhaps, 30 developers, at least one of them is dealing with server connection state statistics, occasionally problematic internet routes, occasionally problematic switch configuration or hardware (even on an opaque cloud platform). Someone has to deal with it, or else stuff is kinda flaky, and no one seems to know why...