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

Groups > comp.lang.c++ > #83681 > unrolled thread

qsort() vs. std::sort

Back to article view | Back to comp.lang.c++

Contents

  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

Page 2 of 2 — ← Prev page 1 [2]

#83777

> Perhaps you have biased standard library. For example that online
> compiler <http://coliru.stacked-crooked.com/a/31e2a018eaabe85a>
> With array sizes that matter > 1024 the sorts look about equal:
>   
> 2: 202%
> 4: 420%
> 8: 436%
> 16: 357%
> 32: 530%
> 64: 675%
> 128: 432%
> 256: 421%
> 512: 303%
> 1024: 375%
> 2048: 90%
> 4096: 96%
> 8192: 98%

g++ 11.1.0, Ubuntu 20.04, Ryzen Threadripper 3990X:

2: 229%, 4%
4: 414%, 5%
8: 394%, 6%
16: 419%, 9%
32: 473%, 13%
64: 511%, 28%
128: 465%, 39%
256: 502%, 53%
512: 430%, 66%
1024: 320%, 78%
2048: 233%, 88%
4096: 197%, 97%
8192: 176%, 57%

Still 76% more trhoughput with 8192 elements.
The issue with the shrinking advantage with an increasing size
is that the time to access a cacheline from the L2-cach dominates
and the proportionatly part of C++'s advantage shrinks, but for
sure not below 0%. I'll bet my right hand that you have some
measurement-error because of shared resources.

[toc] | [prev] | [next] | [standalone]

#83781

On Tuesday, 26 April 2022 at 13:28:31 UTC+3, Bonita Montero wrote:
> > Perhaps you have biased standard library. For example that online 
> > compiler <http://coliru.stacked-crooked.com/a/31e2a018eaabe85a> 
> > With array sizes that matter > 1024 the sorts look about equal: 
> > 
> > 2: 202% 
> > 4: 420% 
> > 8: 436% 
> > 16: 357% 
> > 32: 530% 
> > 64: 675% 
> > 128: 432% 
> > 256: 421% 
> > 512: 303% 
> > 1024: 375% 
> > 2048: 90% 
> > 4096: 96% 
> > 8192: 98%
> g++ 11.1.0, Ubuntu 20.04, Ryzen Threadripper 3990X: 
> 
> 2: 229%, 4% 
> 4: 414%, 5% 
> 8: 394%, 6% 
> 16: 419%, 9% 
> 32: 473%, 13% 
> 64: 511%, 28% 
> 128: 465%, 39% 
> 256: 502%, 53% 
> 512: 430%, 66% 
> 1024: 320%, 78% 
> 2048: 233%, 88% 
> 4096: 197%, 97% 
> 8192: 176%, 57% 
> 
> Still 76% more trhoughput with 8192 elements. 
> The issue with the shrinking advantage with an increasing size 
> is that the time to access a cacheline from the L2-cach dominates 
> and the proportionatly part of C++'s advantage shrinks, but for 
> sure not below 0%. I'll bet my right hand that you have some 
> measurement-error because of shared resources.

What I'm supposed to do with your hand? Somehow I got different 
result. It can be because I replaced your bloat lambda that you used
for C:

unsigned
&l = *(unsigned *)left,
&r = *(unsigned *)right;
return l < r ? -1 : l > r ? 1 : 0;

With more sane one: 

return *(unsigned *)left - *(unsigned *)right;

Also it can be that you compile with some odd undisclosed options. What I
did run is all at cited link.
 

[toc] | [prev] | [next] | [standalone]

#83782

Am 26.04.2022 um 13:54 schrieb Öö Tiib:
> On Tuesday, 26 April 2022 at 13:28:31 UTC+3, Bonita Montero wrote:
>>> Perhaps you have biased standard library. For example that online
>>> compiler <http://coliru.stacked-crooked.com/a/31e2a018eaabe85a>
>>> With array sizes that matter > 1024 the sorts look about equal:
>>>
>>> 2: 202%
>>> 4: 420%
>>> 8: 436%
>>> 16: 357%
>>> 32: 530%
>>> 64: 675%
>>> 128: 432%
>>> 256: 421%
>>> 512: 303%
>>> 1024: 375%
>>> 2048: 90%
>>> 4096: 96%
>>> 8192: 98%
>> g++ 11.1.0, Ubuntu 20.04, Ryzen Threadripper 3990X:
>>
>> 2: 229%, 4%
>> 4: 414%, 5%
>> 8: 394%, 6%
>> 16: 419%, 9%
>> 32: 473%, 13%
>> 64: 511%, 28%
>> 128: 465%, 39%
>> 256: 502%, 53%
>> 512: 430%, 66%
>> 1024: 320%, 78%
>> 2048: 233%, 88%
>> 4096: 197%, 97%
>> 8192: 176%, 57%
>>
>> Still 76% more trhoughput with 8192 elements.
>> The issue with the shrinking advantage with an increasing size
>> is that the time to access a cacheline from the L2-cach dominates
>> and the proportionatly part of C++'s advantage shrinks, but for
>> sure not below 0%. I'll bet my right hand that you have some
>> measurement-error because of shared resources.
> 
> What I'm supposed to do with your hand? Somehow I got different
> result. It can be because I replaced your bloat lambda that you used
> for C:
> 
> unsigned
> &l = *(unsigned *)left,
> &r = *(unsigned *)right;
> return l < r ? -1 : l > r ? 1 : 0;
> 
> With more sane one:
> 
> return *(unsigned *)left - *(unsigned *)right;

This doesn't work because the difference might be too large for an int.

[toc] | [prev] | [next] | [standalone]

#83783

On Tuesday, 26 April 2022 at 15:10:51 UTC+3, Bonita Montero wrote:
> Am 26.04.2022 um 13:54 schrieb Öö Tiib: 
> > On Tuesday, 26 April 2022 at 13:28:31 UTC+3, Bonita Montero wrote: 
> >>> Perhaps you have biased standard library. For example that online 
> >>> compiler <http://coliru.stacked-crooked.com/a/31e2a018eaabe85a> 
> >>> With array sizes that matter > 1024 the sorts look about equal: 
> >>> 
> >>> 2: 202% 
> >>> 4: 420% 
> >>> 8: 436% 
> >>> 16: 357% 
> >>> 32: 530% 
> >>> 64: 675% 
> >>> 128: 432% 
> >>> 256: 421% 
> >>> 512: 303% 
> >>> 1024: 375% 
> >>> 2048: 90% 
> >>> 4096: 96% 
> >>> 8192: 98% 
> >> g++ 11.1.0, Ubuntu 20.04, Ryzen Threadripper 3990X: 
> >> 
> >> 2: 229%, 4% 
> >> 4: 414%, 5% 
> >> 8: 394%, 6% 
> >> 16: 419%, 9% 
> >> 32: 473%, 13% 
> >> 64: 511%, 28% 
> >> 128: 465%, 39% 
> >> 256: 502%, 53% 
> >> 512: 430%, 66% 
> >> 1024: 320%, 78% 
> >> 2048: 233%, 88% 
> >> 4096: 197%, 97% 
> >> 8192: 176%, 57% 
> >> 
> >> Still 76% more trhoughput with 8192 elements. 
> >> The issue with the shrinking advantage with an increasing size 
> >> is that the time to access a cacheline from the L2-cach dominates 
> >> and the proportionatly part of C++'s advantage shrinks, but for 
> >> sure not below 0%. I'll bet my right hand that you have some 
> >> measurement-error because of shared resources. 
> > 
> > What I'm supposed to do with your hand? Somehow I got different 
> > result. It can be because I replaced your bloat lambda that you used 
> > for C: 
> > 
> > unsigned 
> > &l = *(unsigned *)left, 
> > &r = *(unsigned *)right; 
> > return l < r ? -1 : l > r ? 1 : 0; 
> > 
> > With more sane one: 
> > 
> > return *(unsigned *)left - *(unsigned *)right;
> This doesn't work because the difference might be too large for an int.

OK, good catch. Replaced with: 

return (*(unsigned *)left > *(unsigned *)right) - (*(unsigned *)left < *(unsigned *)right);

Still similar results: <http://coliru.stacked-crooked.com/a/462b2889dc90f15c>

[toc] | [prev] | [next] | [standalone]

#83788

Am 26.04.2022 um 15:23 schrieb Öö Tiib:
> On Tuesday, 26 April 2022 at 15:10:51 UTC+3, Bonita Montero wrote:
>> Am 26.04.2022 um 13:54 schrieb Öö Tiib:
>>> On Tuesday, 26 April 2022 at 13:28:31 UTC+3, Bonita Montero wrote:
>>>>> Perhaps you have biased standard library. For example that online
>>>>> compiler <http://coliru.stacked-crooked.com/a/31e2a018eaabe85a>
>>>>> With array sizes that matter > 1024 the sorts look about equal:
>>>>>
>>>>> 2: 202%
>>>>> 4: 420%
>>>>> 8: 436%
>>>>> 16: 357%
>>>>> 32: 530%
>>>>> 64: 675%
>>>>> 128: 432%
>>>>> 256: 421%
>>>>> 512: 303%
>>>>> 1024: 375%
>>>>> 2048: 90%
>>>>> 4096: 96%
>>>>> 8192: 98%
>>>> g++ 11.1.0, Ubuntu 20.04, Ryzen Threadripper 3990X:
>>>>
>>>> 2: 229%, 4%
>>>> 4: 414%, 5%
>>>> 8: 394%, 6%
>>>> 16: 419%, 9%
>>>> 32: 473%, 13%
>>>> 64: 511%, 28%
>>>> 128: 465%, 39%
>>>> 256: 502%, 53%
>>>> 512: 430%, 66%
>>>> 1024: 320%, 78%
>>>> 2048: 233%, 88%
>>>> 4096: 197%, 97%
>>>> 8192: 176%, 57%
>>>>
>>>> Still 76% more trhoughput with 8192 elements.
>>>> The issue with the shrinking advantage with an increasing size
>>>> is that the time to access a cacheline from the L2-cach dominates
>>>> and the proportionatly part of C++'s advantage shrinks, but for
>>>> sure not below 0%. I'll bet my right hand that you have some
>>>> measurement-error because of shared resources.
>>>
>>> What I'm supposed to do with your hand? Somehow I got different
>>> result. It can be because I replaced your bloat lambda that you used
>>> for C:
>>>
>>> unsigned
>>> &l = *(unsigned *)left,
>>> &r = *(unsigned *)right;
>>> return l < r ? -1 : l > r ? 1 : 0;
>>>
>>> With more sane one:
>>>
>>> return *(unsigned *)left - *(unsigned *)right;
>> This doesn't work because the difference might be too large for an int.
> 
> OK, good catch. Replaced with:
> 
> return (*(unsigned *)left > *(unsigned *)right) - (*(unsigned *)left < *(unsigned *)right);
> 
> Still similar results: <http://coliru.stacked-crooked.com/a/462b2889dc90f15c>

With ...

	auto cSort = []( vu_it begin, vu_it end )
	{
		qsort( to_address( begin ), end - begin, sizeof(unsigned),
			[]( void const *left, void const *right ) -> int
			{
				unsigned
					&l = *(unsigned *)left,
					&r = *(unsigned *)right;
				return (l > r) - (r > l);
			} );
	};

... I get ...

2: 231%, 4%
4: 423%, 5%
8: 420%, 6%
16: 406%, 9%
32: 471%, 13%
64: 500%, 28%
128: 480%, 40%
256: 507%, 53%
512: 430%, 66%
1024: 320%, 78%
2048: 232%, 88%
4096: 197%, 97%
8192: 175%, 104%

[toc] | [prev] | [next] | [standalone]

#83822

Bonita Montero <Bonita.Montero@gmail.com> wrote:
> I just measured how superior C++'s std::sort is over C's qsort:
<snip>
> These are the results on my computer (Ryzen Threadripper 3990X):
> 
> 2: 279%
> 4: 303%
> 8: 531%
> 16: 611%
> 32: 543%
> 64: 627%
> 128: 536%
> 256: 481%
> 512: 402%
> 1024: 316%
> 2048: 260%
> 4096: 230%
> 
> Up to 6,3 times faster with less coding !

Unsurprising that inlining can improve performance. Your raw numbers are
useless, though, as you're comparing different algorithms (C++ header
template vs libc), which shall be demonstrated below. Also, technically
speaking your gripe is largely with toolchains (particularly wrt the
performance of standard library interfaces like qsort) as there's nothing
preventing toolchains from inlining qsort and the provided callback; for
historical reasons they simply don't. Newer languages and their toolchains,
like Rust, statically compile everything, including the standard library,
which is something C toolchain and runtime environment providers could just
as well do also. Rust Vector's sort API implicitly relies on static
compilation, otherwise it would suffer the same runtime indirect call issue
as in typical C environments.

I'm unable to compile your C++ code on OpenBSD 7.0; it appears to use
features that are too new. I ran the following LTO inlining experiment on
Alpine Linux 3.15 but using the qsort implementation from OpenBSD 7.0, which
was easiest to compile outside its source tree with minimal modifications
(changing qsort and heapsort to openbsd_qsort and openbsd_heapsort,
respectively, and adding a forward declaration for openbsd_heapsort). As you
can see, OpenBSD's qsort is implemented using heapsort. Not sure which
algorithm Alpine Linux's C++ std::sort is using, but it's either a different
algorithm entirely or a significantly different implementation.

alpine-3-15:/tmp$ make qsort-inline qsort-extern
cc -flto -O2 -march=native -Wall   -c -o openbsd-qsort.o openbsd-qsort.c
cc -flto -O2 -march=native -Wall   -c -o openbsd-heapsort.o openbsd-heapsort.c
g++ -o qsort-inline qsort.cc openbsd-qsort.o openbsd-heapsort.o -flto -O2 -march=native -Wall -std=c++2a -fvisibility=hidden
cc -shared -o libopenbsd-qsort.so openbsd-qsort.o openbsd-heapsort.o -flto -O2 -march=native -Wall
g++ -o qsort-extern qsort.cc -flto -O2 -march=native -Wall -std=c++2a -fvisibility=hidden -L. -Wl,-rpath="." -lopenbsd-qsort
alpine-3-15:/tmp$ ./qsort-inline
2: 54%
4: 59%
8: 39%
16: 75%
32: 86%
64: 131%
128: 160%
256: 186%
512: 186%
1024: 180%
2048: 151%
4096: 144%
alpine-3-15:/tmp$ ./qsort-extern
2: 75%
4: 95%
8: 84%
16: 176%
32: 195%
64: 285%
128: 362%
256: 490%
512: 588%
1024: 302%
2048: 246%
4096: 230%

[toc] | [prev] | [next] | [standalone]

#83823

> Unsurprising that inlining can improve performance. Your raw numbers are
> useless, though, as you're comparing different algorithms (C++ header
> template vs libc), ...

No, the numbers aren't useless, they compare the C- and the C++-way
to sort things.

> Also, technically
> speaking your gripe is largely with toolchains (particularly wrt the
> performance of standard library interfaces like qsort) as there's nothing
> preventing toolchains from inlining qsort ...

LOL, there's no C compiler which will do that. The qsort-function is
just a static piece of code and nothing is inlined.

[toc] | [prev] | [next] | [standalone]

#83825

In comp.lang.c++ William Ahern <william@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.

> Your raw numbers are
> useless, though, as you're comparing different algorithms (C++ header
> template vs libc)

That's not a difference in algorithm. That's a difference in implementation.
For all we know std::sort() and qsort() could both use the exact same
sorting algorithm.

Note that making std::sort() a template isn't done primarily because it
makes it more efficient (it's a really nice bonus, but it's not the primary
reason why it's done). The main reason why it's a template is because
swapping elements in C++ may not always be possible by merely swapping
the underlying bytes of those elements. In other words, the swapping
is type-dependent. Achieving this is easiest with a template.

[toc] | [prev] | [next] | [standalone]

#83827

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.
  

[toc] | [prev] | [next] | [standalone]

#83828

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

[toc] | [prev] | [next] | [standalone]

#83830

Juha Nieminen <nospam@thanks.invalid> wrote:
> In comp.lang.c++ William Ahern <william@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.

I posted two sets of benchmarks, one for qsort-inline and another for
qsort-extern. qsort-inline clearly has a substantially different performance
profile, and that could only happen if the comparison callback itself was
inlined into the sort routine. See below for the disassembly.

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

This is exactly what is happening in the qsort-inline trial I posted: the
comparison callback function is inlined into the qsort implementation. The
reason I couldn't just use -flto with the C runtime qsort is that -flto in
clang and GCC require the intermediate code for both the comparison callback
*and* the qsort implementation itself, and that information isn't included
in Alpine's C runtime--neither the dynamic libc.so nor static libc.a. In
theory the intermediate code *could* be included, just like a system C
runtime can ship with debug symbols.

Below is the dissassembly of some relevant portions of qsort-inline proving
inlining. After recompiling qsort-inline with debug symbols (-g), the
fragment was generated using `objdump -drwC -S -l`, which interleaves
assembly blocks with the originating source block.

This first fragment begins inside qsort (at openbsd-qsort.c line 147, inside
the inner introsort routine) and ends with code from the comparator lambda
in the post C++ benchmark code (at qsort.cc line 51, +/- a couple lines from
the original posted code), without any interveaning calls (only jumps),
showing that the comparator function is inlined into the sorting
implementation itself:

  /tmp/comp.lang.c-qsort/openbsd-qsort.c:147
  	if (n > 7) {
      1e40:	48 83 fb 07          	cmp    $0x7,%rbx
      1e44:	74 2c                	je     1e72 <introsort.constprop.0+0x72>
  introsort.constprop.0():
  /tmp/comp.lang.c-qsort/qsort.cc:51
  				return l < r ? -1 : l > r ? 1 : 0;
      1e46:	8b 08                	mov    (%rax),%ecx
      1e48:	8b 32                	mov    (%rdx),%esi

This second fragment begins inside the timedSort lambda, showing that
qsort itself is inlined into the lambda:

  operator()<main()::<lambda(unsigned int*, unsigned int*)> >():
  /tmp/comp.lang.c-qsort/qsort.cc:35
  		while( rounds-- )
      1315:	4c 8d 78 ff          	lea    -0x1(%rax),%r15
      1319:	4c 89 fd             	mov    %r15,%rbp
      131c:	0f 1f 40 00          	nopl   0x0(%rax)
  unsigned int* std::__copy_move<false, true, std::random_access_iterator_tag>::__copy_m<unsigned int>(unsigned int const*, unsigned int const*, unsigned int*):
  /usr/include/c++/10.3.1/bits/stl_algobase.h:426
  	    __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
      1320:	48 8b 7c 24 30       	mov    0x30(%rsp),%rdi
      1325:	48 89 da             	mov    %rbx,%rdx
      1328:	e8 03 fd ff ff       	call   1030 <memmove@plt>
  __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >::__normal_iterator(unsigned int* const&):
  /usr/include/c++/10.3.1/bits/stl_iterator.h:979
        : _M_current(__i) { }
      132d:	48 8b 7c 24 30       	mov    0x30(%rsp),%rdi
  openbsd_qsort():
  /tmp/comp.lang.c-qsort/openbsd-qsort.c:225
  {
  	size_t i, maxdepth = 0;
  	int swaptype;
  
  	/* Approximate 2*ceil(lg(n + 1)) */
  	for (i = n; i > 0; i >>= 1)
      1332:	4c 89 e8             	mov    %r13,%rax

The OpenBSD source code used can be found at

  https://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/qsort.c?annotate=1.18
  https://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/heapsort.c?annotate=1.11

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c++

csiph-web