4 ms·
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 st
by flohofwoe 4y ago
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.
- throwawaymaths 4y agoI think "just as well" elides maintainability... I would not want to have to debug a generic sorter written in c preprocessor.
- flohofwoe 4y agoIn 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.
- randbox 4y agoThe only preprocessor code required for writing 'static inline' header functions is "#pragma once". Inline functions look like normal functions.
- adrianN 4y agoI still see a call instruction here https://godbolt.org/z/GWKdaoEG4 https://godbolt.org/z/GWKdaoEG4. Am I doing something wrong?
- flohofwoe 4y agoTry 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 agoOkay, 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 agoTrue, 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 agoSo 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).
- fweimer 4y agoglibc 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.
- layer8 4y agoNot 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.
- anarazel 4y ago> 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.
- kevin_thibedeau 4y agoIt'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.
- gpderetta 4y agoIn 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.