Seems like a fun project! One thing I stumbled over:
> unsigned char *next = s + len + !len;
> Originally this expression was the return value, computed at the very end of the function. However, after inspecting the compiler’s assembly output, I decided to move it up, and the result was a solid performance boost. That’s because it spreads out dependent instructions. With the address of the next code point known so early, the instructions that decode the next code point can get started early.
If there's no change in the actual logic, I feel like the compiler should be able to move up expressions in order to make them available earlier. I wonder whether this was tested/inspected with some optimizations turned off.
did you mean because computers can do it better? I can't see anything else in their comment that you could have referred to, but the quoted part shows that the author did it better than the compiler output...
No, not really. I meant by the prose description of how to optimise the code. It felt like how chess masters may discuss their strategies after a game of chess. Very high level and far from what a layperson may really understand about chess (or optimising), but very true and distinct nonetheless.
It gives a glimpse into the mind of the chess master (or optimiser) even when you yourself don't possess these skills.
Oh okay. I see the similarity now - it does look like prose discussion of chess games. The analogy can be pretty deep, like strategic considerations ("opposite-colored bishops" vs "spread-out dependent instructions" in the prose you replied to). Thanks for the clarification, this was insightful.
Except in case of profile-guided optimization (which few people use), the compiler has one massive weakness: it doesn't know the "shape" and distribution of your data. If it did, it would be able to do quite a bit more, but it mostly does not.
I also find that people have way too much faith in omnipotence of compilers. If you care about performance, you _have_ to go down to the assembly level and ensure that the compiler did the right thing, at least in the hotspots. Oftentimes it does not, and you have to change your higher level code to make it cooperate.
> Except in case of profile-guided optimization (which few people use), the compiler has one massive weakness: it doesn't know the "shape" and distribution of your data. If it did, it would be able to do quite a bit more, but it mostly does not.
Well, that's only true because programmers define functions in terms of types that are not sufficiently specific wrt their runtime invariants; in a dependently-typed language you could have an optimizing compiler that makes use of type-level information to do better optimizations. For instance, in a dependently-typed language, you could have a type of integers divisible by 11, and it will have no runtime overhead with respect to a machine integer. Of course, this comes with a cost: if you want to use such specific types, you have to prove to the compiler that the data it is getting really does satisfy the property (and yes, you can do such proofs even with data that is only available at runtime, by simply implementing a runtime check).
The example line is just operations of registers, without any dependencies until the function return. The compiler should know to interleave these instructions with the code, so that the CPU can issue them alongside other operations.
Compilers should view operations more like a dependency graph, laying out operations with an interleaving that maximizes multi-issue, while keeping register pressure in check. In my mind, if the human can significantly change the output of the assembly by moving one line, the compiler optimizations may be turned off.
> laying out operations with an interleaving that maximizes multi-issue, while keeping register pressure in check
How to actually do that has been an active research topic for 30 years or so. So far, that research hasn't yielded anything that is simple, efficient, and effective enough to be included in general-purpose compilers. Last time I looked at LLVM's backend, it used to schedule for minimal register pressure because spills are more expensive in general, and because out-of-order execution will undo your careful scheduling anyway. It also has a second scheduler after register allocation, but at that point it's hard to move stuff, especially on x86.
On this particular code, manual scheduling paid off, partly because humans, unlike compilers, can simply try different variants and keep the best. Think of it as survivorship bias.
Edit: BTW, if you actually compile the code from Github and compare the generated assembly to a version where the computation of next is moved to the end, you'll see that moving it to the end causes GCC to allocate a stack frame (on x86-64), which it doesn't do in the manually optimized one.
> unsigned char *next = s + len + !len;
> Originally this expression was the return value, computed at the very end of the function. However, after inspecting the compiler’s assembly output, I decided to move it up, and the result was a solid performance boost. That’s because it spreads out dependent instructions. With the address of the next code point known so early, the instructions that decode the next code point can get started early.
If there's no change in the actual logic, I feel like the compiler should be able to move up expressions in order to make them available earlier. I wonder whether this was tested/inspected with some optimizations turned off.