4 ms·

I still see a call instruction here https://godbolt.org/z/GWKdaoEG4 https://godbolt.org/z/GWKdaoEG4. Am I doing something wrong?

flohofwoe 4y ago
Try to define the find() function as inline or static (but in this case the optimizer is actually too aggressive for this example and resolves the entire function call into a constant).
- adrianN 4y ago
  Okay, but as far as I know "inline" is just a suggestion for the compiler. Depending on the complexity of the function or the phase of the moon the compiler can choose not to inline it. I wouldn't want to rely on that for a critical piece of my performance.
  - flohofwoe 4y ago
    True, that's what I mean with depending too much on the optimizer (in a sibling comment). But IME the threshold for inlining code is surprisingly big (which of course also has a downside: potential code bloat). I added a little fix which prevents the compiler from discarding the result completely (just by going through __builtin_printf()): https://godbolt.org/z/W93WrhbaE https://godbolt.org/z/W93WrhbaE PS: another minor tweak (make the comparison function static, so that no extra copy is included in the compiler output): https://godbolt.org/z/5TTM4x193 https://godbolt.org/z/5TTM4x193
  - evmar 4y ago
    `static` also allows it to optimize, and it's more of a code hygiene thing. Your original code as written unintentionally defines `find` as a function that must be preserved (as a separate function) into the compiled output, and `static` undoes that.
uecker 4y ago
So here is my C version: https://godbolt.org/z/zTe8jocsE https://godbolt.org/z/zTe8jocsE Now tell me I need generics for this to get optimized. (Generics are useful for type safety, which you can add using macros in C, but this is then ugly).
- SubjectToChange 4y ago
  You might as well argue that (speculative) devirtualization negates the overhead of virtual functions in C++. >Now tell me I need generics for this to get optimized. Generics are explicit and reliably optimized. Implicit function pointer optimization is non-obvious and optimized unreliably.
  - uecker 4y ago
    Generics can not reliably be optimized. They create specialized inline code by monomorphization (except partially in Go which is a bit smarter). Specialization and inlining can be good if it leads to simplificatons or bad when it leads to a combinatorial explosion, which is why optimizers are careful with it to avoid code bloat. Generics always create the bloat by default. If this were a good strategy, optimizers would always inline. To reliable devirtualize function pointers in C you need to use non-standard extensions. But the best strategy is not let the optimizer decide and apply this very carefully inly for the few selected cases where it matters.
    - SubjectToChange 4y ago
      > Generics can not reliably be optimized. Choose to believe this, it's your loss. The fact is that performance sensitive domains like browsers/HFT/HPC/ML/etc are almost universally written in heavily templated C++. Just look at linear algebra libraries, C can't compete. > They create specialized inline code by monomorphization Neither generics nor monomorphization imply inlining, that's purely a performance optimization. > (except partially in Go which is a bit smarter). Are you joking? Go, already an extremely bloated language, somehow managed to implement generics with runtime overhead. > Generics always create the bloat by default. Generics only generate code you would have manually written/copied otherwise. > But the best strategy is not let the optimizer decide and apply this very carefully inly for the few selected cases where it matters. Two words, heterogeneous programming.
hermitdev 4y ago
> Am I doing something wrong? Yes, you just compiled C code as C++. Actually write it as C++ (get rid of the void* mostly) and your program becomes a constant time evaluation: https://godbolt.org/z/5fedo8s5q https://godbolt.org/z/5fedo8s5q
- uecker 4y ago
  This has nothing to do with C++: https://godbolt.org/z/zTe8jocsE https://godbolt.org/z/zTe8jocsE
- deleted 4y ago
  [deleted]
- adrianN 4y ago
  Well the whole point of the exercise was to see whether the C-version of qsort would be optimized in the same way as templated code when the compiler can see the whole thing instead of just the declaration. That's why I didn't write templated code.

flohofwoe 4y ago

Try to define the find() function as inline or static (but in this case the optimizer is actually too aggressive for this example and resolves the entire function call into a constant).

adrianN 4y ago
Okay, but as far as I know "inline" is just a suggestion for the compiler. Depending on the complexity of the function or the phase of the moon the compiler can choose not to inline it. I wouldn't want to rely on that for a critical piece of my performance.
- flohofwoe 4y ago
  True, that's what I mean with depending too much on the optimizer (in a sibling comment). But IME the threshold for inlining code is surprisingly big (which of course also has a downside: potential code bloat). I added a little fix which prevents the compiler from discarding the result completely (just by going through __builtin_printf()): https://godbolt.org/z/W93WrhbaE https://godbolt.org/z/W93WrhbaE PS: another minor tweak (make the comparison function static, so that no extra copy is included in the compiler output): https://godbolt.org/z/5TTM4x193 https://godbolt.org/z/5TTM4x193
- evmar 4y ago
  `static` also allows it to optimize, and it's more of a code hygiene thing. Your original code as written unintentionally defines `find` as a function that must be preserved (as a separate function) into the compiled output, and `static` undoes that.

uecker 4y ago

So here is my C version: https://godbolt.org/z/zTe8jocsE https://godbolt.org/z/zTe8jocsE Now tell me I need generics for this to get optimized. (Generics are useful for type safety, which you can add using macros in C, but this is then ugly).

SubjectToChange 4y ago
You might as well argue that (speculative) devirtualization negates the overhead of virtual functions in C++. >Now tell me I need generics for this to get optimized. Generics are explicit and reliably optimized. Implicit function pointer optimization is non-obvious and optimized unreliably.
- uecker 4y ago
  Generics can not reliably be optimized. They create specialized inline code by monomorphization (except partially in Go which is a bit smarter). Specialization and inlining can be good if it leads to simplificatons or bad when it leads to a combinatorial explosion, which is why optimizers are careful with it to avoid code bloat. Generics always create the bloat by default. If this were a good strategy, optimizers would always inline. To reliable devirtualize function pointers in C you need to use non-standard extensions. But the best strategy is not let the optimizer decide and apply this very carefully inly for the few selected cases where it matters.
  - SubjectToChange 4y ago
    > Generics can not reliably be optimized. Choose to believe this, it's your loss. The fact is that performance sensitive domains like browsers/HFT/HPC/ML/etc are almost universally written in heavily templated C++. Just look at linear algebra libraries, C can't compete. > They create specialized inline code by monomorphization Neither generics nor monomorphization imply inlining, that's purely a performance optimization. > (except partially in Go which is a bit smarter). Are you joking? Go, already an extremely bloated language, somehow managed to implement generics with runtime overhead. > Generics always create the bloat by default. Generics only generate code you would have manually written/copied otherwise. > But the best strategy is not let the optimizer decide and apply this very carefully inly for the few selected cases where it matters. Two words, heterogeneous programming.

hermitdev 4y ago

> Am I doing something wrong? Yes, you just compiled C code as C++. Actually write it as C++ (get rid of the void* mostly) and your program becomes a constant time evaluation: https://godbolt.org/z/5fedo8s5q https://godbolt.org/z/5fedo8s5q

uecker 4y ago
This has nothing to do with C++: https://godbolt.org/z/zTe8jocsE https://godbolt.org/z/zTe8jocsE
deleted 4y ago
[deleted]
adrianN 4y ago
Well the whole point of the exercise was to see whether the C-version of qsort would be optimized in the same way as templated code when the compiler can see the whole thing instead of just the declaration. That's why I didn't write templated code.