C++ templates don't require code duplication. Even if the compiler generates multiple functions, if they have identical machine code the linker will combine them into one. If you write the C++ templates as type-safe wrappers around the same void pointers you'd use in C then the machine code will all be the same.
Even if true (I don't know) it appears to be easily defeated by the compiler inserting different NOPs for alignment or whatever stupid reason:
0000000000001351 <_Z5qsortIiEvPT_mPFiPKS0_S3_Em>:
1351: 55 push %rbp
1352: 48 89 e5 mov %rsp,%rbp
1355: 48 83 ec 20 sub $0x20,%rsp
1359: 48 89 7d f8 mov %rdi,-0x8(%rbp)
135d: 48 89 75 f0 mov %rsi,-0x10(%rbp)
1361: 48 89 55 e8 mov %rdx,-0x18(%rbp)
1365: 48 89 4d e0 mov %rcx,-0x20(%rbp)
1369: 48 8b 4d e8 mov -0x18(%rbp),%rcx
136d: 48 8b 55 e0 mov -0x20(%rbp),%rdx
1371: 48 8b 75 f0 mov -0x10(%rbp),%rsi
1375: 48 8b 45 f8 mov -0x8(%rbp),%rax
1379: 48 89 c7 mov %rax,%rdi
137c: e8 cf fc ff ff call 1050 <qsort@plt>
1381: 90 nop
1382: c9 leave
1383: c3 ret
-- snip--
00000000000013c8 <_Z5qsortIfEvPT_mPFiPKS0_S3_Em>:
13c8: 55 push %rbp
13c9: 48 89 e5 mov %rsp,%rbp
13cc: 48 83 ec 20 sub $0x20,%rsp
13d0: 48 89 7d f8 mov %rdi,-0x8(%rbp)
13d4: 48 89 75 f0 mov %rsi,-0x10(%rbp)
13d8: 48 89 55 e8 mov %rdx,-0x18(%rbp)
13dc: 48 89 4d e0 mov %rcx,-0x20(%rbp)
13e0: 48 8b 4d e8 mov -0x18(%rbp),%rcx
13e4: 48 8b 55 e0 mov -0x20(%rbp),%rdx
13e8: 48 8b 75 f0 mov -0x10(%rbp),%rsi
13ec: 48 8b 45 f8 mov -0x8(%rbp),%rax
13f0: 48 89 c7 mov %rax,%rdi
13f3: e8 58 fc ff ff call 1050 <qsort@plt>
13f8: 90 nop
13f9: c9 leave
13fa: c3 ret
13fb: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)And there is obvious objection that you are relying on optimizations that aren't in any way standardized nor guaranteed and will depend on choice of toolchain, optimization/debug level and phase of the moon.
Besides, I don't like wrappers. Instead of all this crap
template <class T>
void qsort(T *ptr, size_t n, int (*cmp)(const T*, const T*), size_t sz = sizeof(T)) {
std::qsort((void*) ptr, n, sz, (int(*)(const void*, const void*)) cmp);
}I want to write
generic <class T>
void qsort(T *ptr, size_t n, int (*cmp)(const T*, const T*), size_t sz = sizeof(T)) {
// honestly type-checked implementation of qsort goes here
// any use of sizeof(T) or T[] transparently employs sz
// sz can't be overriden manually at the call site
// exactly one instance of the function generated in this translation unit and none elsewhere
}Bonus if somebody can figure out how to do type-safe intrusive containers (which are all over the place in Linux, for example).
Even if true (I don't know) it appears to be easily defeated by the compiler inserting different NOPs for alignment or whatever stupid reason:
Depending on the ISA, NOPs are placed to flush the pipeline before taking a long branch. Obviously that, if the
non-templated code does not have them, indeed it is an implementation problem.
I don't know why you got different code, but then I also don't know why you used -O0, which should be banned not the default.
With -O1 I got exactly the same code.
https://godbolt.org/z/da66KT8dxAlso, with such a simple type-safe wrapper template I would normally not prevent the inlining of it.
I can only guess it was a matter of alignment, which could depend on what stuff precedes and succeeds each of the instantiations. Also, one of them was at the end of a section, so maybe it matters somehow. I posted unoptimized code because otherwise everything got inlined and I didn't feel like writing a longer template that wouldn't.
Anyway, it nicely illustrates the point that you can't be 100% sure what you get because it's an optimization. A more reliable (and efficient) way is to have a language mechanism which avoids generating duplicate code in the first place.
ML had parametric polymorphism in the '70s, Java since the '90s (generic containers and
sorting included), Rust designers still haven't heard of it in the 2010s
BTW, speaking of Rust, is it even possible to write a similar wrapper for stdlib's qsort by any means whatsoever in that language?
In C++ I had to resort to function templates and default arguments, not sure if Rust has those...
Why would you want to write a wrapper for the C lib qsort() if you're gonna write a generic sort function in another language?
Sorting is not rocket science.
It doesn't matter. Regardless of implementation language, a generic array sort needs to know element size. So do many containers and other things.
Question is, can it be provided by the compiler automatically each time such a generic function is called.
C++ can do it, with a footgun included (one comma too much and it breaks in most bizarre ways).
Java sidesteps the problem by not having nested objects - containers only hold pointers to heap items.