Re: qsort() vs. std::sort

Message-ID	<082pji-tuv1.ln1@wilbur.25thandClement.com> (permalink)
From	William Ahern <william@25thandClement.com>
Subject	Re: qsort() vs. std::sort
Newsgroups	comp.lang.c++, comp.lang.c
References	<t4092b$des$1@dont-email.me>
Date	2022-04-27 17:03 -0700

Cross-posted to 2 groups.

Show all headers | View raw

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%

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