5 ms·

Seems like a fun project! One thing I stumbled over: > unsigned char *next = s + len + !len; > Originally this expression was the return value, computed

by ant6n 9y ago

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.

jacobush 9y ago
So optimising code feels like playing chess now?
- logicallee 9y ago
  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...
  - jacobush 9y ago
    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.
    - logicallee 9y ago
      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.
- qznc 9y ago
  It is not "optimising" because nobody even hopes for something "optimal". Now? For a long time x86/amd64 performance is quite unpredictable because the CPUs are so complex. It is not like chess. More like Poker because more uncertainty.
  - thethirdone 9y ago
    > It is not "optimising" because nobody even hopes for something "optimal". Optimizing doesn't need to reach the optimal, just improve. > It is not like chess. More like Poker because more uncertainty. I would say the uncertainty is similar to chess. It isn't feasible to know the best option in any given situation, but it is deterministic.
0xbear 9y ago
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.
- taktoa 9y ago
  > 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).
- ant6n 9y ago
  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.
  - tom_mellior 9y ago

by ant6n 9y ago

jacobush 9y ago

So optimising code feels like playing chess now?

logicallee 9y ago
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...
- jacobush 9y ago
  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.
  - logicallee 9y ago
    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.
qznc 9y ago
It is not "optimising" because nobody even hopes for something "optimal". Now? For a long time x86/amd64 performance is quite unpredictable because the CPUs are so complex. It is not like chess. More like Poker because more uncertainty.
- thethirdone 9y ago
  > It is not "optimising" because nobody even hopes for something "optimal". Optimizing doesn't need to reach the optimal, just improve. > It is not like chess. More like Poker because more uncertainty. I would say the uncertainty is similar to chess. It isn't feasible to know the best option in any given situation, but it is deterministic.

0xbear 9y ago

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.

taktoa 9y ago
> 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).
ant6n 9y ago
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.
- tom_mellior 9y ago