4 ms·

inlining only goes so far. You won't get full of qsort to be inlined, and if it's not inlined, it needs to be at least cloned to be on par with std::sort, so th

inlining only goes so far. You won't get full of qsort to be inlined, and if it's not inlined, it needs to be at least cloned to be on par with std::sort, so the comparator function could get const-propagated. AFAIK out of the major compilers, gcc has the most aggressive cloning, but it's still nowhere near to const propagate the comparator from qsort. With std::sort with a stateless comparator function object (such as std::less, which is the default), you get this for free*. * of course this is not entirely free, as this is more prone to code bloat. But, you can always type-erase the comparator, and use a function pointer, or std::function, if this ever becomes a problem. But you can't convince a C compiler to const propagate the comparator in qsort all the way through, if the optimizer chooses that it doesn't worth it.

enqk 4y ago
check this out: https://github.com/WebKit/WebKit/blob/main/Source/bmalloc/libpas/Documentation.md https://github.com/WebKit/WebKit/blob/main/Source/bmalloc/li...
- temac 4y ago
  Interesting but I'm not sure about the relevancy to the above comment. On a sidenote, it has weird claims: > obviating the need for ownership type systems or other compiler approaches to fixing the type-safety of use-after-frees. This means that we need one heap per type, and be 100% strict about it.
  - enqk 4y ago
    I guess I have to quote from it, then: --- C lets you do most of what C++ can if you rely on always_inline. This didn't used to be the case, but modern C compilers will meat-grind the code with repeated application of the following things: - Inlining any always_inline call except if it's recursive or the function uses some very weird features that libpas doesn't use (like goto pointer). - Copy-propagating the values from the callsite into the function that uses the value. Consequently, passing a function pointer (or struct of function pointers), where the pointer points to an always_inline function and the callee is always_inline results in specialization akin to template monomorphization. This works to any depth; the compiler won't be satisfied until there are no more always_inline function calls. This fortuitous development in compilers allowed me to write very nice template code in C. Libpas achieves templates in C using config structs that contain function pointers -- sometimes to always_inline functions (when we want specialization and inlining) and sometimes to out-of-line functions (when we want specialization but not inlining). Additionally, the C template style allows us to have true polymorphic functions. Lots of libpas slow paths are huge and not at all hot. We don't want that code specialized for every config. Luckily, this works just fine in C templates -- those polymorphic functions just pass around a pointer to the config they are using, and dynamically load and call things in that config, almost exactly the same way that the specialized code would do. This saves a lot of code size versus C++ templates.
camel-cdr 4y ago
qsort only isn't inline, because libcs don't supply an inline definition. If you write your own qsort, then you'll see it getting inlined and/or function cloned for different types.
yakubin 4y ago
glibc qsort's implementation is in libc.so, not in the header. GCC doesn't have anything to work with. It's also an apples-to-oranges comparison, since std::sort and qsort implement different algorithms. A lot of std::sort's performance is actually from using the version without any callbacks. If you pass a comparator function which just compares two integers the obvious way, it gets much slower. So one of std::sort's biggest advantages is actually not that it uses templates, but that it's specialized for the common case of not needing a custom callback. Theoretically the compiler should make the two cases the same, but apparently GCC is too dumb (that's not a slight on GCC; I think people expect too much from compilers): ------------------------------------------------------------------------ Benchmark Time CPU Iterations ------------------------------------------------------------------------ std_sort_random 52881299 ns 52873089 ns 14 std_sort_with_callback_random 63319633 ns 63307876 ns 11 qsort_random 106803314 ns 106784567 ns 7 external_sort_random 97642851 ns 97640888 ns 7 std_sort_sorted 8433311 ns 8432564 ns 82 std_sort_with_callback_sorted 13868016 ns 13865170 ns 50 qsort_sorted 28098439 ns 28093720 ns 26 external_sort_sorted 33629020 ns 33628108 ns 21 external_sort is just std::sort hidden behind an extern function implemented in a separate .o file. Those benchmarks are from sorting 1MB of random and already-sorted data (as indicated in the names). I think it's important to test such cases, because often online people benchmark code which is written all in a single file, whereas real-life C++ projects are usually organized in such a way that every little class is in its own little file, which gets compiled into a separated object file, and then it all gets linked together without LTO. And then those same people go on to claim performance benefits of their language without actually using the setup which enables those benefits, which IMO is a bit dishonest. When I drill further down into everything I want to drill into, maybe I'll publish the source for the benchmarks somewhere.
- planede 4y ago
  > If you pass a comparator function which just compares two integers the obvious way, it gets much slower. So one of std::sort's biggest advantages is actually not that it uses templates, but that it's specialized for the common case of not needing a custom callback. This is not true. `std::sort`'s default comparator is a `std::less` object. The advantage comes from using a stateless callback functor object. If you pass a capture-less lambda instead of a function pointer, you can reap the same benefits as using the default comparator. Even if that capture-less lambda just forwards to a specific free function anyway. In short, `std::sort(beg, end, [](auto x, auto y) { return foo(x,y); })` can be faster than `std::sort(beg, end, &foo)`.

enqk 4y ago

check this out: https://github.com/WebKit/WebKit/blob/main/Source/bmalloc/libpas/Documentation.md https://github.com/WebKit/WebKit/blob/main/Source/bmalloc/li...

temac 4y ago
Interesting but I'm not sure about the relevancy to the above comment. On a sidenote, it has weird claims: > obviating the need for ownership type systems or other compiler approaches to fixing the type-safety of use-after-frees. This means that we need one heap per type, and be 100% strict about it.
- enqk 4y ago
  I guess I have to quote from it, then: --- C lets you do most of what C++ can if you rely on always_inline. This didn't used to be the case, but modern C compilers will meat-grind the code with repeated application of the following things: - Inlining any always_inline call except if it's recursive or the function uses some very weird features that libpas doesn't use (like goto pointer). - Copy-propagating the values from the callsite into the function that uses the value. Consequently, passing a function pointer (or struct of function pointers), where the pointer points to an always_inline function and the callee is always_inline results in specialization akin to template monomorphization. This works to any depth; the compiler won't be satisfied until there are no more always_inline function calls. This fortuitous development in compilers allowed me to write very nice template code in C. Libpas achieves templates in C using config structs that contain function pointers -- sometimes to always_inline functions (when we want specialization and inlining) and sometimes to out-of-line functions (when we want specialization but not inlining). Additionally, the C template style allows us to have true polymorphic functions. Lots of libpas slow paths are huge and not at all hot. We don't want that code specialized for every config. Luckily, this works just fine in C templates -- those polymorphic functions just pass around a pointer to the config they are using, and dynamically load and call things in that config, almost exactly the same way that the specialized code would do. This saves a lot of code size versus C++ templates.

camel-cdr 4y ago

qsort only isn't inline, because libcs don't supply an inline definition. If you write your own qsort, then you'll see it getting inlined and/or function cloned for different types.

yakubin 4y ago

glibc qsort's implementation is in libc.so, not in the header. GCC doesn't have anything to work with. It's also an apples-to-oranges comparison, since std::sort and qsort implement different algorithms. A lot of std::sort's performance is actually from using the version without any callbacks. If you pass a comparator function which just compares two integers the obvious way, it gets much slower. So one of std::sort's biggest advantages is actually not that it uses templates, but that it's specialized for the common case of not needing a custom callback. Theoretically the compiler should make the two cases the same, but apparently GCC is too dumb (that's not a slight on GCC; I think people expect too much from compilers): ------------------------------------------------------------------------ Benchmark Time CPU Iterations ------------------------------------------------------------------------ std_sort_random 52881299 ns 52873089 ns 14 std_sort_with_callback_random 63319633 ns 63307876 ns 11 qsort_random 106803314 ns 106784567 ns 7 external_sort_random 97642851 ns 97640888 ns 7 std_sort_sorted 8433311 ns 8432564 ns 82 std_sort_with_callback_sorted 13868016 ns 13865170 ns 50 qsort_sorted 28098439 ns 28093720 ns 26 external_sort_sorted 33629020 ns 33628108 ns 21 external_sort is just std::sort hidden behind an extern function implemented in a separate .o file. Those benchmarks are from sorting 1MB of random and already-sorted data (as indicated in the names). I think it's important to test such cases, because often online people benchmark code which is written all in a single file, whereas real-life C++ projects are usually organized in such a way that every little class is in its own little file, which gets compiled into a separated object file, and then it all gets linked together without LTO. And then those same people go on to claim performance benefits of their language without actually using the setup which enables those benefits, which IMO is a bit dishonest. When I drill further down into everything I want to drill into, maybe I'll publish the source for the benchmarks somewhere.

planede 4y ago
> If you pass a comparator function which just compares two integers the obvious way, it gets much slower. So one of std::sort's biggest advantages is actually not that it uses templates, but that it's specialized for the common case of not needing a custom callback. This is not true. `std::sort`'s default comparator is a `std::less` object. The advantage comes from using a stateless callback functor object. If you pass a capture-less lambda instead of a function pointer, you can reap the same benefits as using the default comparator. Even if that capture-less lambda just forwards to a specific free function anyway. In short, `std::sort(beg, end, [](auto x, auto y) { return foo(x,y); })` can be faster than `std::sort(beg, end, &foo)`.