6 ms·
I feel like the problem isn't really with intrinsics. Rather, the problem is that compilers just aren't very good at optimizing for the last 30-50% of performan
by nkurz 12y ago
I feel like the problem isn't really with intrinsics. Rather, the problem is that compilers just aren't very good at optimizing for the last 30-50% of performance. One notices this when using intrinsics because if you are using them you probably are concentrating on performance. But if you were to look closely at the non-intrinsic code, I think you'd see a lot of the same problems: bad register allocation leading to unnecessary moves and spills, failure to take advantage of flags already set by arithmetic and logic operations, and awkward code layout leading to unnecessary jumps and branches.
Obviously, this isn't because compiler writers are stupid or ignorant. Instead, it's just a really difficult problem to optimize for one target in a way that doesn't hurt performance on another. Still, I think there's a lot of room for improvement, if only because comparing the output from GCC, CLang, and ICC often shows that one compiler does a much better job than the others[1]. But even once you know (definitively) that the code could be faster, it's often really tough to convince a given compiler to generate the code that you want. And coming up with a single construct that works well for multiple compilers and remains readable is often impossible.
I'd love it if there was a good way to "lock down" the output for a given function, without needing to depend on the whims of individual compilers. Other than distributing only pre-compiled binaries, there doesn't seem to be a great way to do this. Looking at Dan's example code, he has a solution that's twice as fast as the non-inline-ASM alternatives. But it's still depending on the compiler to do register allocation, and adding a global variable somewhere else in the program might well cause the whole thing to blow up, spilling to stack and triggering the popcnt false dependency that he's working hard to avoid.
What's the best way to do this --- to keep optimized code optimized across the mix of compilers in the current ecosystem?
[1] I'm Linux based, but I probably should start adding MSVC to the mix. I'm sure there are cases where it does something better than the others. Is there a good way to do this? Perhaps an equivalent to http://gcc.godbolt.org/ http://gcc.godbolt.org/ for MSVC?
- WalterBright 12y agoGenerating optimal code is much like the travelling salesman problem. Optimization algorithms will lead the result to a local minima, while missing a global minima.
- Ono-Sendai 12y agoIf the function is defined on a finite domain, you can (in theory) find the fastest algorithm for it: http://www.forwardscattering.org/post/13 http://www.forwardscattering.org/post/13 In practice, something like hill climbing will be done, as you said. Actually it's not even hill climbing, since some of the changes will be pessimisations. (as per the original post)
- WalterBright 12y agoMany optimizations in isolation are pessimizations, they only produce net improvement when used in combination with other optimizations.
- userbinator 12y agoOptimization algorithms will lead the result to a local minima, while missing a global minima. I think this is the one of the huge differences between humans and compilers that leads to suboptimal code - the compiler is completely unaware of what the programmer intended in the HLL source, so the best it can do is to generate code which it "knows" is the fastest way to implement exactly those statements; on the other hand, if you are a human writing an algorithm in Asm, you probably have things like instruction selection and register allocation already in mind and are willing to slightly change the "semantics" of your algorithm if it results in e.g. a better use of registers or the possibility to use a faster/smaller instruction. In other words, the compiler starts with something horribly unoptimised but following the semantics of the source language, and tries to make that as fast/small as it can while still maintaining the same semantics - and so this is the "local minima" it can reach. The human starts with a concept of an algorithm and its intended result, and everything in-between is flexible, so this is a more "global" view of the problem of code generation. The human isn't restricted by the semantics of the HLL, but can fully express the intended algorithm by exploiting the full capabilities of the processor.
- WalterBright 12y agoThe human also knows things that the compiler doesn't - such as which branches of the code are speed critical and which aren't. This matters for things like where precious registers get allocated.
- daniel-cussen 12y ago> But even once you know (definitively) that the code could be faster, it's often really tough to convince a given compiler to generate the code that you want. And coming up with a single construct that works well for multiple compilers and remains readable is often impossible. I once struggled with GCC to output the code I wanted (I wanted indirect unconditional jumps) and I finally found that the way to tell GCC (and perhaps other compilers) to do this is to use goto's (of the "considered harmful variety") with function pointers. And it was, IIRC, twice as fast, and didn't involve any assembler. I think the deeper problem with compilers is they target code and algorithms that are already known. If you compile anything it hasn't seen before, you're really throwing it a curveball.