Hacker News Reader

Comment by adrianN | Hacker News Reader

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

So here is my C version:

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).

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.

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.

> 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.

> 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

This has nothing to do with C++:

https://godbolt.org/z/zTe8jocsE

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.

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).

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.

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

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

`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.

Reply on news.ycombinator.com