Hacker News Reader

Comment by flohofwoe | Hacker News Reader

Minor nitpick: if the implementation of qsort() would be visible to the C compiler (for instance if it would be defined as inline code in stdlib.h, or with a statically linked libc and LTO), the compiler would happily "stamp out" a specialized version of the function, just as std::qsort() does in C++ (assuming the right optimization settings).

After all, "zero cost abstraction" (aka "optimizer passes") works just as well in C as in C++ ;)

The actual advantage of generics isn't performance, but less (manual) code duplication.

View on HN

Not only the implementation of qsort would have to be visible to the compiler, but also the implementation of the comparison function, which may be defined in a separately compiled module or passed around dynamically as a function pointer (as might qsort itself, potentially).

> The actual advantage of generics isn't performance, but less (manual) code duplication.

Or type safety, since code duplication will often be shunned. And the benefit of type safety is there regardless of whether the generics implementation performs specialization.

> Not only the implementation of qsort would have to be visible to the compiler, but also the implementation of the comparison function, which may be defined in a separately compiled module or passed around dynamically as a function pointer (as might qsort itself, potentially).

In postgres' case the whole set of comparison functions isn't know at the compile time of the server - new types / operators can be added at runtime by extensions.

Hence the branches for the few most common/performance critical cases. I'd personally prefer if we gradually moved to C++ in postgres, but that'd not change that we'd need to have those explicit branches to benefit from a faster sort.

Of course it'd be a lot less annoying to implement in C++ - manually implementing templates with macro magic is many things, but not fun.

It's pretty straightforward to have a qsort() or bsearch() clone generated by a macro alongside a static inlined comparison function. You will get C++ level performance out of that.

glibc does exactly this for bsearch. The difference with C++ is that the specialized function (bsearch or qsort) does not receive vague linkage, so it is not going to be deduplicated by the link editor. For bsearch, the code size increase is probably not a problem, but qsort tends to be much larger. Basically, intra-procedural constant propagation plus inlining into qsort is very beneficial, but inlining the specialized qsort itself is probably not such a great idea. Presumably LTO with profile feedback could help here, but striking the right balance is going to be difficult (as is with C++, which tends towards code duplication, despite vague linkage and link editors that perform identical code folding).

I'm not sure if specialization is a good argument for generics. Not everyone implements generics through full specialization/monomorphization, and then the performance benefits are not much more likely to emerge than with function pointers or vtables. And many JIT compilers can effectively specialize code involving indirect calls.

In principle yes. With enough constant propagation, inlining and/or intraprocedural optimizations, the compiler can indeed inline the comparator in qsort (and in practice GCC has been capable of it for a few years).

The problem is that it more work for the compiler. For example GCC has an early inliner pass that will exploit all easy "inlining" (like those provided by templates) to simplify the code and to expose more opportunities for later passes. On the other hand, indirect function inlining is only done at later stages. The effect is that indirect function call inlining is much less reliable and sometimes not as effective.

I think "just as well" elides maintainability... I would not want to have to debug a generic sorter written in c preprocessor.

In the case of qsort() at least, there wouldn't be "preprocessor generics" involved, because the comparison is done in a user-provided callback function. But both the comparison function and the qsort implementation must be visible to the compiler (or in case of LTO: the linker) for the "auto-specialization" (via the optimizer) to kick in.

It's a bit brittle of course to depend too much on the optimizer, but the whole idea of "zero cost abstraction" in C++ also puts a lot of trust into the optimizer passes.

The only preprocessor code required for writing 'static inline' header functions is "#pragma once". Inline functions look like normal functions.

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

So here is my C version:

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

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