Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #83828

Re: qsort() vs. std::sort

Show all headers | View raw

Öö Tiib <ootiib@hot.ee> wrote:
> On Thursday, 28 April 2022 at 09:34:08 UTC+3, Juha Nieminen wrote:
>> In comp.lang.c++ William Ahern <wil...@25thandclement.com> wrote: 
>> > Unsurprising that inlining can improve performance.
>> 
>> The performance boost doesn't come from inlining. One single function call 
>> wouldn't make a difference when it comes to sorting. It doesn't matter if 
>> the std::sort() function gets inlined into the calling code or whether 
>> the compiler decides to make it a separate function. That would only be 
>> a difference of a few clock cycles at most. 
>> 
>> The difference comes from what could perhaps be called "reverse inlining" 
>> (which happens thanks to std::sort() being a template). In other words, 
>> rather than std::sort() being embedded into the calling code, data from 
>> the calling code gets embedded into the std::sort() implementation. 
>> (In other words, we are doing the "inlining" kind of in reverse.) 
>> 
>> This means that when std::sort() needs to, for example, compare two 
>> elements, it knows exactly the type of the element and can do the 
>> comparison "inlined" in its own code, rather than having to call some 
>> external function provided by the caller.
> 
> Are you sure that gcc option -flto is not meant for doing that kind of
> things during linking? I am not claiming that it is actually doing it 
> with qsort but its documentation is stating it to apply interprocedural
> optimizations like inlining even between files written in different
> languages.

My point is that the efficiency advantage of std::sort() would be there
even if it doesn't get inlined into the calling code at all. Even if that
instance of std::sort() would end up in a completely different compilation
unit and doesn't get inlined in any way, it would be equally fast. In this
sense its advantage over qsort doesn't come from inlining. (It comes from
the sort of "reverse inlining" I mention.)

I suppose it could theoretically be that qsort() could get the same
benefit with link-time optimization. However, I think it would require
a bit smarter inlining from the compiler, as it needs to see which
function the function pointer is pointing to, inline said function
into the qsort implementation, and optimize away all the conversions
to and from void pointers. (And this, of course, depends largely on
how the comparison function has been implemented.)

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

qsort() vs. std::sort Bonita Montero <Bonita.Montero@gmail.com> - 2022-04-23 09:15 +0200
  Re: qsort() vs. std::sort Bonita Montero <Bonita.Montero@gmail.com> - 2022-04-23 09:31 +0200
  Re: qsort() vs. std::sort Juha Nieminen <nospam@thanks.invalid> - 2022-04-25 05:56 +0000
    Re: qsort() vs. std::sort Bonita Montero <Bonita.Montero@gmail.com> - 2022-04-25 08:27 +0200
  Re: qsort() vs. std::sort Öö Tiib <ootiib@hot.ee> - 2022-04-25 01:16 -0700
    Re: qsort() vs. std::sort Bonita Montero <Bonita.Montero@gmail.com> - 2022-04-25 12:59 +0200
      Re: qsort() vs. std::sort Bonita Montero <Bonita.Montero@gmail.com> - 2022-04-25 13:32 +0200
        Re: qsort() vs. std::sort Öö Tiib <ootiib@hot.ee> - 2022-04-25 05:26 -0700
          Re: qsort() vs. std::sort Bonita Montero <Bonita.Montero@gmail.com> - 2022-04-25 17:41 +0200
            Re: qsort() vs. std::sort Öö Tiib <ootiib@hot.ee> - 2022-04-26 00:46 -0700
              Re: qsort() vs. std::sort Bonita Montero <Bonita.Montero@gmail.com> - 2022-04-26 12:19 +0200
      Re: qsort() vs. std::sort Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-04-25 05:24 -0700
        Re: qsort() vs. std::sort Bonita Montero <Bonita.Montero@gmail.com> - 2022-04-25 17:42 +0200
    Re: qsort() vs. std::sort Juha Nieminen <nospam@thanks.invalid> - 2022-04-26 05:26 +0000
      Re: qsort() vs. std::sort Öö Tiib <ootiib@hot.ee> - 2022-04-26 00:19 -0700
      Re: qsort() vs. std::sort scott@slp53.sl.home (Scott Lurndal) - 2022-04-26 14:03 +0000
        Re: qsort() vs. std::sort Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-04-26 08:50 -0700
        Re: qsort() vs. std::sort Öö Tiib <ootiib@hot.ee> - 2022-04-29 01:38 -0700
          Re: qsort() vs. std::sort Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-04-29 02:39 -0700
            Re: qsort() vs. std::sort Öö Tiib <ootiib@hot.ee> - 2022-04-29 04:06 -0700
    Re: qsort() vs. std::sort Bonita Montero <Bonita.Montero@gmail.com> - 2022-04-26 12:28 +0200
      Re: qsort() vs. std::sort Öö Tiib <ootiib@hot.ee> - 2022-04-26 04:54 -0700
        Re: qsort() vs. std::sort Bonita Montero <Bonita.Montero@gmail.com> - 2022-04-26 14:10 +0200
          Re: qsort() vs. std::sort Öö Tiib <ootiib@hot.ee> - 2022-04-26 06:23 -0700
            Re: qsort() vs. std::sort Bonita Montero <Bonita.Montero@gmail.com> - 2022-04-26 16:26 +0200
  Re: qsort() vs. std::sort William Ahern <william@25thandClement.com> - 2022-04-27 17:03 -0700
    Re: qsort() vs. std::sort Bonita Montero <Bonita.Montero@gmail.com> - 2022-04-28 06:58 +0200
    Re: qsort() vs. std::sort Juha Nieminen <nospam@thanks.invalid> - 2022-04-28 06:33 +0000
      Re: qsort() vs. std::sort Öö Tiib <ootiib@hot.ee> - 2022-04-28 01:08 -0700
        Re: qsort() vs. std::sort Juha Nieminen <nospam@thanks.invalid> - 2022-04-28 08:23 +0000
      Re: qsort() vs. std::sort William Ahern <william@25thandClement.com> - 2022-04-28 02:55 -0700

csiph-web