I just measured how superior C++'s std::sort is over C's qsort:

#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <cstdlib>
#include <algorithm>
#include <memory>
#include <atomic>

using namespace std;
using namespace chrono;

atomic_uint auNonOptimize;

int main()
{ constexpr size_t
V_MAX = 0x1000,
V_MAX_ROUNDS = 0x4000;
vector<unsigned>
vu( V_MAX, 0 ),
vuSort( V_MAX, 0 );
mt19937_64 mt;
uniform_int_distribution<unsigned> uid( 0, -1 );
for( unsigned &u : vu )
u = uid( mt );
auto timedSort = [&]<typename SortFn>( SortFn sortFn, size_t n, size_t
rounds ) -> double
requires requires( SortFn sortFn, unsigned *p ) { { sortFn( p, p ) }; }
{
auto start = high_resolution_clock::now();
unsigned sum = 0;
while( rounds-- )
copy( vu.begin(), vu.begin() + n, vuSort.begin() ),
sortFn( to_address( vuSort.begin() ), to_address( vuSort.begin() ) + n ),
sum += vu[0];
::auNonOptimize = sum;
return (int64_t)duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() / 1.0e9;
};
auto cSort = []( unsigned *begin, unsigned *end )
{
qsort( begin, end - begin, sizeof(unsigned),
[]( void const *left, void const *right ) -> int
{
unsigned
&l = *(unsigned *)left,
&r = *(unsigned *)right;
return l < r ? -1 : l > r ? 1 : 0;
} );
};
auto cppSort = []( unsigned *begin, unsigned *end )
{
sort( begin, end );
};
double tC, tCpp, rel;
for( size_t s = 2, rounds; s <= V_MAX; s *= 2 )
rounds = (V_MAX_ROUNDS / s) * V_MAX_ROUNDS,
tC = timedSort( cSort, s, rounds ),
tCpp = timedSort( cppSort, s, rounds ),
rel = tC / tCpp * 100.0,
cout << s << ": " << (int)(rel + 0.5) << "%" << endl;
}

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 !

Am 23.04.2022 um 09:15 schrieb Bonita Montero:
> I just measured how superior C++'s std::sort is over C's qsort:
>
> #include <iostream>
> #include <vector>
> #include <random>
> #include <chrono>
> #include <cstdlib>
> #include <algorithm>
> #include <memory>
> #include <atomic>
>
> using namespace std;
> using namespace chrono;
>
> atomic_uint auNonOptimize;
>
> int main()
> {
>     constexpr size_t
>         V_MAX = 0x1000,
>         V_MAX_ROUNDS = 0x4000;
>     vector<unsigned>
>         vu( V_MAX, 0 ),
>         vuSort( V_MAX, 0 );
>     mt19937_64 mt;
>     uniform_int_distribution<unsigned> uid( 0, -1 );
>     for( unsigned &u : vu )
>         u = uid( mt );
>     auto timedSort = [&]<typename SortFn>( SortFn sortFn, size_t n,
> size_t rounds ) -> double
>         requires requires( SortFn sortFn, unsigned *p ) { { sortFn( p,
> p ) }; }
>     {
>         auto start = high_resolution_clock::now();
>         unsigned sum = 0;
>         while( rounds-- )
>             copy( vu.begin(), vu.begin() + n, vuSort.begin() ),
>             sortFn( to_address( vuSort.begin() ), to_address(
> vuSort.begin() ) + n ),
>             sum += vu[0];
sum += vusort[0];
>         ::auNonOptimize = sum;
>         return (int64_t)duration_cast<nanoseconds>(
> high_resolution_clock::now() - start ).count() / 1.0e9;
>     };
>     auto cSort = []( unsigned *begin, unsigned *end )
>     {
>         qsort( begin, end - begin, sizeof(unsigned),
>             []( void const *left, void const *right ) -> int
>             {
>                 unsigned
>                     &l = *(unsigned *)left,
>                     &r = *(unsigned *)right;
>                 return l < r ? -1 : l > r ? 1 : 0;
>             } );
>     };
>     auto cppSort = []( unsigned *begin, unsigned *end )
>     {
>         sort( begin, end );
>     };
>     double tC, tCpp, rel;
>     for( size_t s = 2, rounds; s <= V_MAX; s *= 2 )
>         rounds = (V_MAX_ROUNDS / s) * V_MAX_ROUNDS,
>         tC = timedSort( cSort, s, rounds ),
>         tCpp = timedSort( cppSort, s, rounds ),
>         rel = tC / tCpp * 100.0,
>         cout << s << ": " << (int)(rel + 0.5) << "%" << endl;
> }
>
> 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 !

sobota, 23 kwietnia 2022 o 09:15:38 UTC+2 Bonita Montero napisał(a):
> I just measured how superior C++'s std::sort is over C's qsort:
>
> #include <iostream>
> #include <vector>
> #include <random>
> #include <chrono>
> #include <cstdlib>
> #include <algorithm>
> #include <memory>
> #include <atomic>
>
> using namespace std;
> using namespace chrono;
>
> atomic_uint auNonOptimize;
>
> int main()
> {
> constexpr size_t
> V_MAX = 0x1000,
> V_MAX_ROUNDS = 0x4000;
> vector<unsigned>
> vu( V_MAX, 0 ),
> vuSort( V_MAX, 0 );
> mt19937_64 mt;
> uniform_int_distribution<unsigned> uid( 0, -1 );
> for( unsigned &u : vu )
> u = uid( mt );
> auto timedSort = [&]<typename SortFn>( SortFn sortFn, size_t n, size_t
> rounds ) -> double
> requires requires( SortFn sortFn, unsigned *p ) { { sortFn( p, p ) }; }
> {
> auto start = high_resolution_clock::now();
> unsigned sum = 0;
> while( rounds-- )
> copy( vu.begin(), vu.begin() + n, vuSort.begin() ),
> sortFn( to_address( vuSort.begin() ), to_address( vuSort.begin() ) + n ),
> sum += vu[0];
> ::auNonOptimize = sum;
> return (int64_t)duration_cast<nanoseconds>(
> high_resolution_clock::now() - start ).count() / 1.0e9;
> };
> auto cSort = []( unsigned *begin, unsigned *end )
> {
> qsort( begin, end - begin, sizeof(unsigned),
> []( void const *left, void const *right ) -> int
> {
> unsigned
> &l = *(unsigned *)left,
> &r = *(unsigned *)right;
> return l < r ? -1 : l > r ? 1 : 0;
> } );
> };
> auto cppSort = []( unsigned *begin, unsigned *end )
> {
> sort( begin, end );
> };
> double tC, tCpp, rel;
> for( size_t s = 2, rounds; s <= V_MAX; s *= 2 )
> rounds = (V_MAX_ROUNDS / s) * V_MAX_ROUNDS,
> tC = timedSort( cSort, s, rounds ),
> tCpp = timedSort( cppSort, s, rounds ),
> rel = tC / tCpp * 100.0,
> cout << s << ": " << (int)(rel + 0.5) << "%" << endl;
> }
>
> 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 !

try radix sort, i once measured that things (on 10-yo old machine) and testing sorting 1MB of integers and remember c quicksort (like that from wikipedia) have 150 ms , c++ std:sort 111 ms,
c insertsort 111 ms also or 2 ms worse something like that, c-radix sort (taken from stack overflow) 17 ms beating c++:stdsort more than 3 times
for more details search "quicksort" in this group (the search in google groups work)..i only remember vagually that some version of quicksort i tested had some error which i made by trials of revritting but i dont know which one - the conclusions i remember were btw that quicksort is not so good people belive, insertsort was better afair and especially radix sort smashes c++ sort in pieces
(hovever this research then was tiring and i dont want to go beck into it..untill i would really needet it again)

> >
> > Up to 6,3 times faster with less coding !
> try radix sort, i once measured that things (on 10-yo old machine) and testing sorting 1MB of integers and remember c quicksort (like that from wikipedia) have 150 ms , c++ std:sort 111 ms,
> c insertsort 111 ms also or 2 ms worse something like that, c-radix sort (taken from stack overflow) 17 ms beating c++:stdsort more than 3 times

sorry mnistype i wanted to type 27 ms (not 17 ms)

> for more details search "quicksort" in this group (the search in google groups work)..i only remember vagually that some version of quicksort i tested had some error which i made by trials of revritting but i dont know which one - the conclusions i remember were btw that quicksort is not so good people belive, insertsort was better afair and especially radix sort smashes c++ sort in pieces
> (hovever this research then was tiring and i dont want to go beck into it...untill i would really needet it again)

On Saturday, 23 April 2022 at 08:15:38 UTC+1, Bonita Montero wrote:
> I just measured how superior C++'s std::sort is over C's qsort:
>
> #include <iostream>
> #include <vector>
> #include <random>
> #include <chrono>
> #include <cstdlib>
> #include <algorithm>
> #include <memory>
> #include <atomic>
>
> using namespace std;
> using namespace chrono;
>
> atomic_uint auNonOptimize;
>
> int main()
> {
> constexpr size_t
> V_MAX = 0x1000,
> V_MAX_ROUNDS = 0x4000;
> vector<unsigned>
> vu( V_MAX, 0 ),
> vuSort( V_MAX, 0 );
> mt19937_64 mt;
> uniform_int_distribution<unsigned> uid( 0, -1 );
> for( unsigned &u : vu )
> u = uid( mt );
> auto timedSort = [&]<typename SortFn>( SortFn sortFn, size_t n, size_t
> rounds ) -> double
> requires requires( SortFn sortFn, unsigned *p ) { { sortFn( p, p ) }; }
> {
> auto start = high_resolution_clock::now();
> unsigned sum = 0;
> while( rounds-- )
> copy( vu.begin(), vu.begin() + n, vuSort.begin() ),
> sortFn( to_address( vuSort.begin() ), to_address( vuSort.begin() ) + n ),
> sum += vu[0];
> ::auNonOptimize = sum;
> return (int64_t)duration_cast<nanoseconds>(
> high_resolution_clock::now() - start ).count() / 1.0e9;
> };
> auto cSort = []( unsigned *begin, unsigned *end )
> {
> qsort( begin, end - begin, sizeof(unsigned),
> []( void const *left, void const *right ) -> int
> {
> unsigned
> &l = *(unsigned *)left,
> &r = *(unsigned *)right;
> return l < r ? -1 : l > r ? 1 : 0;
> } );
> };
> auto cppSort = []( unsigned *begin, unsigned *end )
> {
> sort( begin, end );
> };
> double tC, tCpp, rel;
> for( size_t s = 2, rounds; s <= V_MAX; s *= 2 )
> rounds = (V_MAX_ROUNDS / s) * V_MAX_ROUNDS,
> tC = timedSort( cSort, s, rounds ),
> tCpp = timedSort( cppSort, s, rounds ),
> rel = tC / tCpp * 100.0,
> cout << s << ": " << (int)(rel + 0.5) << "%" << endl;
> }
>
> 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 !
>
But the advantage is tailing off as N gets larger. Probably because the runtime starts to be
dominated by cache misses rather than by overhead in the comparison function.

sobota, 23 kwietnia 2022 o 13:00:33 UTC+2 Malcolm McLean napisał(a):
> On Saturday, 23 April 2022 at 08:15:38 UTC+1, Bonita Montero wrote:
> > I just measured how superior C++'s std::sort is over C's qsort:
> >
> > #include <iostream>
> > #include <vector>
> > #include <random>
> > #include <chrono>
> > #include <cstdlib>
> > #include <algorithm>
> > #include <memory>
> > #include <atomic>
> >
> > using namespace std;
> > using namespace chrono;
> >
> > atomic_uint auNonOptimize;
> >
> > int main()
> > {
> > constexpr size_t
> > V_MAX = 0x1000,
> > V_MAX_ROUNDS = 0x4000;
> > vector<unsigned>
> > vu( V_MAX, 0 ),
> > vuSort( V_MAX, 0 );
> > mt19937_64 mt;
> > uniform_int_distribution<unsigned> uid( 0, -1 );
> > for( unsigned &u : vu )
> > u = uid( mt );
> > auto timedSort = [&]<typename SortFn>( SortFn sortFn, size_t n, size_t
> > rounds ) -> double
> > requires requires( SortFn sortFn, unsigned *p ) { { sortFn( p, p ) }; }
> > {
> > auto start = high_resolution_clock::now();
> > unsigned sum = 0;
> > while( rounds-- )
> > copy( vu.begin(), vu.begin() + n, vuSort.begin() ),
> > sortFn( to_address( vuSort.begin() ), to_address( vuSort.begin() ) + n ),
> > sum += vu[0];
> > ::auNonOptimize = sum;
> > return (int64_t)duration_cast<nanoseconds>(
> > high_resolution_clock::now() - start ).count() / 1.0e9;
> > };
> > auto cSort = []( unsigned *begin, unsigned *end )
> > {
> > qsort( begin, end - begin, sizeof(unsigned),
> > []( void const *left, void const *right ) -> int
> > {
> > unsigned
> > &l = *(unsigned *)left,
> > &r = *(unsigned *)right;
> > return l < r ? -1 : l > r ? 1 : 0;
> > } );
> > };
> > auto cppSort = []( unsigned *begin, unsigned *end )
> > {
> > sort( begin, end );
> > };
> > double tC, tCpp, rel;
> > for( size_t s = 2, rounds; s <= V_MAX; s *= 2 )
> > rounds = (V_MAX_ROUNDS / s) * V_MAX_ROUNDS,
> > tC = timedSort( cSort, s, rounds ),
> > tCpp = timedSort( cppSort, s, rounds ),
> > rel = tC / tCpp * 100.0,
> > cout << s << ": " << (int)(rel + 0.5) << "%" << endl;
> > }
> >
> > 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 !
> >
> But the advantage is tailing off as N gets larger. Probably because the runtime starts to be
> dominated by cache misses rather than by overhead in the comparison function.

nobody should compare sorting to the qsort that probably comes from 80-ties or something, this
passing this 'predicates' as callbacs (if this predicate goiod word ) is obvious this is not effective

more surprising for me was that c++ ponys clain std::sort is ofc best, thousands od c++ pane care for that and simple routine you cpy and paste beats it 3-4 times (which is very notable)

but i could treat it like old-school anecdote as participating in that pony vars is generally not the best thing man can do imo (though defending C its ok though)

Am 23.04.2022 um 13:00 schrieb Malcolm McLean:
> On Saturday, 23 April 2022 at 08:15:38 UTC+1, Bonita Montero wrote:
>> I just measured how superior C++'s std::sort is over C's qsort:
>>
>> #include <iostream>
>> #include <vector>
>> #include <random>
>> #include <chrono>
>> #include <cstdlib>
>> #include <algorithm>
>> #include <memory>
>> #include <atomic>
>>
>> using namespace std;
>> using namespace chrono;
>>
>> atomic_uint auNonOptimize;
>>
>> int main()
>> {
>> constexpr size_t
>> V_MAX = 0x1000,
>> V_MAX_ROUNDS = 0x4000;
>> vector<unsigned>
>> vu( V_MAX, 0 ),
>> vuSort( V_MAX, 0 );
>> mt19937_64 mt;
>> uniform_int_distribution<unsigned> uid( 0, -1 );
>> for( unsigned &u : vu )
>> u = uid( mt );
>> auto timedSort = [&]<typename SortFn>( SortFn sortFn, size_t n, size_t
>> rounds ) -> double
>> requires requires( SortFn sortFn, unsigned *p ) { { sortFn( p, p ) }; }
>> {
>> auto start = high_resolution_clock::now();
>> unsigned sum = 0;
>> while( rounds-- )
>> copy( vu.begin(), vu.begin() + n, vuSort.begin() ),
>> sortFn( to_address( vuSort.begin() ), to_address( vuSort.begin() ) + n ),
>> sum += vu[0];
>> ::auNonOptimize = sum;
>> return (int64_t)duration_cast<nanoseconds>(
>> high_resolution_clock::now() - start ).count() / 1.0e9;
>> };
>> auto cSort = []( unsigned *begin, unsigned *end )
>> {
>> qsort( begin, end - begin, sizeof(unsigned),
>> []( void const *left, void const *right ) -> int
>> {
>> unsigned
>> &l = *(unsigned *)left,
>> &r = *(unsigned *)right;
>> return l < r ? -1 : l > r ? 1 : 0;
>> } );
>> };
>> auto cppSort = []( unsigned *begin, unsigned *end )
>> {
>> sort( begin, end );
>> };
>> double tC, tCpp, rel;
>> for( size_t s = 2, rounds; s <= V_MAX; s *= 2 )
>> rounds = (V_MAX_ROUNDS / s) * V_MAX_ROUNDS,
>> tC = timedSort( cSort, s, rounds ),
>> tCpp = timedSort( cppSort, s, rounds ),
>> rel = tC / tCpp * 100.0,
>> cout << s << ": " << (int)(rel + 0.5) << "%" << endl;
>> }
>>
>> 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 !
>>
> But the advantage is tailing off as N gets larger. Probably because the runtime starts to be
> dominated by cache misses ...

Maybe you're right.

Radix-sort is significantly slower because of the memory-allocations:

#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <cstdlib>
#include <algorithm>
#include <memory>
#include <atomic>
#include "radix_sort.h"

using namespace std;
using namespace chrono;

atomic_uint auNonOptimize;

int main()
{ constexpr size_t
V_MAX = 0x1000,
V_MAX_ROUNDS = 0x1000;
using vu_t = vector<unsigned>;
using vu_it = vu_t::iterator;
vu_t
vu( V_MAX, 0 ),
vuSort( V_MAX, 0 );
mt19937_64 mt;
uniform_int_distribution<unsigned> uid( 0, -1 );
for( unsigned &u : vu )
u = uid( mt );
auto timedSort = [&]<typename SortFn>( SortFn sortFn, size_t n, size_t
rounds ) -> double
requires requires( SortFn sortFn, vu_it it ) { { sortFn( it, it ) }; }
{
auto start = high_resolution_clock::now();
unsigned sum = 0;
while( rounds-- )
copy( vu.begin(), vu.begin() + n, vuSort.begin() ),
sortFn( vuSort.begin(), vuSort.begin() + n ),
sum += vuSort[0];
::auNonOptimize = sum;
return (int64_t)duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() / 1.0e9;
};
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 ? -1 : l > r ? 1 : 0;
} );
};
auto cppSort = []( vu_it begin, vu_it end )
{
sort( begin, end );
};
auto rdxSort = []( vu_it begin, vu_it end )
{
radix_sort( begin, end );
};
auto rel = []( double tC, double tRel ) -> int { return (int)(tC /
tRel * 100.0 + 0.5); };
double tC, tCpp, tRdx;
for( size_t s = 2, rounds; s <= V_MAX; s *= 2 )
rounds = (V_MAX_ROUNDS / s) * V_MAX_ROUNDS,
tC = timedSort( cSort, s, rounds ),
tCpp = timedSort( cppSort, s, rounds ),
tRdx = timedSort( rdxSort, s, rounds ),
cout << s << ": " << rel( tC, tCpp ) << "%, " << rel( tC, tRdx ) <<
"%" << endl;
}

// radix_sort.h:

#pragma once
#include <iterator>
#include <vector>
#include <array>
#include <climits>
#include <algorithm>
#include <type_traits>

template<std::forward_iterator ForwardIt>
requires std::is_integral_v<typename
std::iterator_traits<ForwardIt>::value_type>
void radix_sort( ForwardIt begin, ForwardIt end )
{ using namespace std;
if( begin == end )
return;
using elem_t = typename iterator_traits<ForwardIt>::value_type;
array<vector<elem_t>, 2> partitions;
for( unsigned bit = 0; bit != sizeof(elem_t) * CHAR_BIT; ++bit )
{
for( ForwardIt it = begin; it != end; ++it )
partitions[(*it >> bit) & 1].push_back( *it );
auto end0 = copy( partitions[0].begin(), partitions[0].end(), begin );
copy( partitions[1].begin(), partitions[1].end(), end0 );
partitions[0].clear();
partitions[1].clear();
}
}

2: 120%, 1%
4: 210%, 2%
8: 498%, 5%
16: 561%, 10%
32: 433%, 13%
64: 535%, 26%
128: 511%, 37%
256: 448%, 39%
512: 400%, 47%
1024: 321%, 55%
2048: 258%, 61%
4096: 225%, 68%

The first number is std::sort vs. qsort, the second number
is radix_sort vs. qsort. I think I could speed up radix_sort
significantly by allocating the buffer on the stack with alloca().

sobota, 23 kwietnia 2022 o 14:32:24 UTC+2 Bonita Montero napisał(a):
> Radix-sort is significantly slower because of the memory-allocations:
> #include <iostream>
> #include <vector>
> }
>
> 2: 120%, 1%
> 4: 210%, 2%
> 8: 498%, 5%
> 16: 561%, 10%
> 32: 433%, 13%
> 64: 535%, 26%
> 128: 511%, 37%
> 256: 448%, 39%
> 512: 400%, 47%
> 1024: 321%, 55%
> 2048: 258%, 61%
> 4096: 225%, 68%
>
> The first number is std::sort vs. qsort, the second number
> is radix_sort vs. qsort. I think I could speed up radix_sort
> significantly by allocating the buffer on the stack with alloca().

you better give miliseconds - like those numbers i gave
the radix sort i took is here in this thread

https://groups.google.com/g/comp.lang.c/c/I4lJSh45EJ0/m/ezGwgnvWDgAJ

hovever i dont want to get back to this now, this is low lewel of coding and optimisation
and this is wearing, note any time im ready to get down and involved, esp as those algorithms are hard to understand to the bone and being able to do it own way

Am 23.04.2022 um 14:41 schrieb fir:
> sobota, 23 kwietnia 2022 o 14:32:24 UTC+2 Bonita Montero napisał(a):
>> Radix-sort is significantly slower because of the memory-allocations:
>> #include <iostream>
>> #include <vector>
>> }
>>
>> 2: 120%, 1%
>> 4: 210%, 2%
>> 8: 498%, 5%
>> 16: 561%, 10%
>> 32: 433%, 13%
>> 64: 535%, 26%
>> 128: 511%, 37%
>> 256: 448%, 39%
>> 512: 400%, 47%
>> 1024: 321%, 55%
>> 2048: 258%, 61%
>> 4096: 225%, 68%
>>
>> The first number is std::sort vs. qsort, the second number
>> is radix_sort vs. qsort. I think I could speed up radix_sort
>> significantly by allocating the buffer on the stack with alloca().
>
> you better give miliseconds - like those numbers i gave
> the radix sort i took is here in this thread
>
> https://groups.google.com/g/comp.lang.c/c/I4lJSh45EJ0/m/ezGwgnvWDgAJ
>
> hovever i dont want to get back to this now, this is low lewel of coding and optimisation
> and this is wearing, note any time im ready to get down and involved, esp as those algorithms are hard to understand to the bone and being able to do it own way

I output the relative speed vs. the C's qsort.
There's nothing to optimize further with my radix_sort
except from the memory-allocations.

sobota, 23 kwietnia 2022 o 14:52:23 UTC+2 Bonita Montero napisał(a):
> Am 23.04.2022 um 14:41 schrieb fir:
> > sobota, 23 kwietnia 2022 o 14:32:24 UTC+2 Bonita Montero napisał(a):
> >> Radix-sort is significantly slower because of the memory-allocations:
> >> #include <iostream>
> >> #include <vector>
> >> }
> >>
> >> 2: 120%, 1%
> >> 4: 210%, 2%
> >> 8: 498%, 5%
> >> 16: 561%, 10%
> >> 32: 433%, 13%
> >> 64: 535%, 26%
> >> 128: 511%, 37%
> >> 256: 448%, 39%
> >> 512: 400%, 47%
> >> 1024: 321%, 55%
> >> 2048: 258%, 61%
> >> 4096: 225%, 68%
> >>
> >> The first number is std::sort vs. qsort, the second number
> >> is radix_sort vs. qsort. I think I could speed up radix_sort
> >> significantly by allocating the buffer on the stack with alloca().
> >
> > you better give miliseconds - like those numbers i gave
> > the radix sort i took is here in this thread
> >
> > https://groups.google.com/g/comp.lang.c/c/I4lJSh45EJ0/m/ezGwgnvWDgAJ
> >
> > hovever i dont want to get back to this now, this is low lewel of coding and optimisation
> > and this is wearing, note any time im ready to get down and involved, esp as those algorithms are hard to understand to the bone and being able to do it own way
> I output the relative speed vs. the C's qsort.
> There's nothing to optimize further with my radix_sort
> except from the memory-allocations.

qsort is nothing to compare as it calls those predicates by pointers (if im not wrong pasing its arguments back and forth on stack, maybe in case of x64 its not but this is overally stupid, besides quicksort si probably not the good alghoritm.. as far as i remember needed to improve it by insertion sort for short partitons etc... i dont want top get back to that)

you should giove miliseconds as it is reall life information which is kinda 'physical thus most interesting and most infromative.. if also could compare this result with rest of the world not some % relative to one of your code to other...giving miliseconds (and soem information on machine and settings) gave much more sense

if you want go pro on sorting handmade solutions will always be fastests imo becouse you may use soem assumptions on what your data and what you need which generall cal cant use... goint this specific way is most fun though its most hardcore too

Am 23.04.2022 um 14:59 schrieb fir:
> sobota, 23 kwietnia 2022 o 14:52:23 UTC+2 Bonita Montero napisał(a):
>> Am 23.04.2022 um 14:41 schrieb fir:
>>> sobota, 23 kwietnia 2022 o 14:32:24 UTC+2 Bonita Montero napisał(a):
>>>> Radix-sort is significantly slower because of the memory-allocations:
>>>> #include <iostream>
>>>> #include <vector>
>>>> }
>>>>
>>>> 2: 120%, 1%
>>>> 4: 210%, 2%
>>>> 8: 498%, 5%
>>>> 16: 561%, 10%
>>>> 32: 433%, 13%
>>>> 64: 535%, 26%
>>>> 128: 511%, 37%
>>>> 256: 448%, 39%
>>>> 512: 400%, 47%
>>>> 1024: 321%, 55%
>>>> 2048: 258%, 61%
>>>> 4096: 225%, 68%
>>>>
>>>> The first number is std::sort vs. qsort, the second number
>>>> is radix_sort vs. qsort. I think I could speed up radix_sort
>>>> significantly by allocating the buffer on the stack with alloca().
>>>
>>> you better give miliseconds - like those numbers i gave
>>> the radix sort i took is here in this thread
>>>
>>> https://groups.google.com/g/comp.lang.c/c/I4lJSh45EJ0/m/ezGwgnvWDgAJ
>>>
>>> hovever i dont want to get back to this now, this is low lewel of coding and optimisation
>>> and this is wearing, note any time im ready to get down and involved, esp as those algorithms are hard to understand to the bone and being able to do it own way
>> I output the relative speed vs. the C's qsort.
>> There's nothing to optimize further with my radix_sort
>> except from the memory-allocations.
>
> qsort is nothing to compare as it calls those predicates by pointers ...

It doesn't matter to what I compare, even if I'd compare to bubblesort
since you can compre the relative numbers among each other.

> you should giove miliseconds ...

Irrelevant since I have relative numbers.

sobota, 23 kwietnia 2022 o 15:05:07 UTC+2 Bonita Montero napisał(a):
> Am 23.04.2022 um 14:59 schrieb fir:
>
> > you should giove miliseconds ...
>
> Irrelevant since I have relative numbers.

if you say so....

In comp.lang.c++ Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Up to 6,3 times faster with less coding !

std::sort() benefits a lot from being templated and not requiring callback
functions for comparing elements. (Many of the other operations are also
likely to benefit from directly seeing and handling the element type.)

I am curious to know if qsort() in the major standard library
implementations use the same algorithm as std::sort().

> std::sort() benefits a lot from being templated and not requiring callback
> functions for comparing elements. ...

Obvious, but you can't guess the actual difference from that.

> I am curious to know if qsort() in the major standard library
> implementations use the same algorithm as std::sort().

Basically yes, bt there are minor improvements over quicksorts which
give a slight improved performance.

On Monday, 25 April 2022 at 06:56:28 UTC+1, Juha Nieminen wrote:
> In comp.lang.c++ Bonita Montero <Bonita....@gmail.com> wrote:
> > Up to 6,3 times faster with less coding !
> std::sort() benefits a lot from being templated and not requiring callback
> functions for comparing elements. (Many of the other operations are also
> likely to benefit from directly seeing and handling the element type.)
>
It's a general problem with C. Most elements are aligned on hardware
word boundaries. However it is awkward to test for or require that. So you
end up writing inefficient byte-copying loops for portability and convenience.

The other issue is that many compilers won't inline an indirect call, even if
it appears only once and is passed in directly.

On Saturday, April 23, 2022 at 4:15:38 AM UTC-3, Bonita Montero wrote:
> I just measured how superior C++'s std::sort is over C's qsort:
>
> #include <iostream>
> #include <vector>
> #include <random>
> #include <chrono>
> #include <cstdlib>
> #include <algorithm>
> #include <memory>
> #include <atomic>
>
> using namespace std;
> using namespace chrono;
>
> atomic_uint auNonOptimize;
>
> int main()
> {
> constexpr size_t
> V_MAX = 0x1000,
> V_MAX_ROUNDS = 0x4000;
> vector<unsigned>
> vu( V_MAX, 0 ),
> vuSort( V_MAX, 0 );
> mt19937_64 mt;
> uniform_int_distribution<unsigned> uid( 0, -1 );
> for( unsigned &u : vu )
> u = uid( mt );
> auto timedSort = [&]<typename SortFn>( SortFn sortFn, size_t n, size_t
> rounds ) -> double
> requires requires( SortFn sortFn, unsigned *p ) { { sortFn( p, p ) }; }
> {
> auto start = high_resolution_clock::now();
> unsigned sum = 0;
> while( rounds-- )
> copy( vu.begin(), vu.begin() + n, vuSort.begin() ),
> sortFn( to_address( vuSort.begin() ), to_address( vuSort.begin() ) + n ),
> sum += vu[0];
> ::auNonOptimize = sum;
> return (int64_t)duration_cast<nanoseconds>(
> high_resolution_clock::now() - start ).count() / 1.0e9;
> };
> auto cSort = []( unsigned *begin, unsigned *end )
> {
> qsort( begin, end - begin, sizeof(unsigned),
> []( void const *left, void const *right ) -> int
> {
> unsigned
> &l = *(unsigned *)left,
> &r = *(unsigned *)right;
> return l < r ? -1 : l > r ? 1 : 0;
> } );
> };
> auto cppSort = []( unsigned *begin, unsigned *end )
> {
> sort( begin, end );
> };
> double tC, tCpp, rel;
> for( size_t s = 2, rounds; s <= V_MAX; s *= 2 )
> rounds = (V_MAX_ROUNDS / s) * V_MAX_ROUNDS,
> tC = timedSort( cSort, s, rounds ),
> tCpp = timedSort( cppSort, s, rounds ),
> rel = tC / tCpp * 100.0,
> cout << s << ": " << (int)(rel + 0.5) << "%" << endl;
> }
>
> 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 !

If a C programmer has concerns about qsort performance he just
make it inline removing the function comparison pointer and using
the function directly.

Am 27.04.2022 um 13:21 schrieb Thiago Adams:
> On Saturday, April 23, 2022 at 4:15:38 AM UTC-3, Bonita Montero wrote:
>> I just measured how superior C++'s std::sort is over C's qsort:
>>
>> #include <iostream>
>> #include <vector>
>> #include <random>
>> #include <chrono>
>> #include <cstdlib>
>> #include <algorithm>
>> #include <memory>
>> #include <atomic>
>>
>> using namespace std;
>> using namespace chrono;
>>
>> atomic_uint auNonOptimize;
>>
>> int main()
>> {
>> constexpr size_t
>> V_MAX = 0x1000,
>> V_MAX_ROUNDS = 0x4000;
>> vector<unsigned>
>> vu( V_MAX, 0 ),
>> vuSort( V_MAX, 0 );
>> mt19937_64 mt;
>> uniform_int_distribution<unsigned> uid( 0, -1 );
>> for( unsigned &u : vu )
>> u = uid( mt );
>> auto timedSort = [&]<typename SortFn>( SortFn sortFn, size_t n, size_t
>> rounds ) -> double
>> requires requires( SortFn sortFn, unsigned *p ) { { sortFn( p, p ) }; }
>> {
>> auto start = high_resolution_clock::now();
>> unsigned sum = 0;
>> while( rounds-- )
>> copy( vu.begin(), vu.begin() + n, vuSort.begin() ),
>> sortFn( to_address( vuSort.begin() ), to_address( vuSort.begin() ) + n ),
>> sum += vu[0];
>> ::auNonOptimize = sum;
>> return (int64_t)duration_cast<nanoseconds>(
>> high_resolution_clock::now() - start ).count() / 1.0e9;
>> };
>> auto cSort = []( unsigned *begin, unsigned *end )
>> {
>> qsort( begin, end - begin, sizeof(unsigned),
>> []( void const *left, void const *right ) -> int
>> {
>> unsigned
>> &l = *(unsigned *)left,
>> &r = *(unsigned *)right;
>> return l < r ? -1 : l > r ? 1 : 0;
>> } );
>> };
>> auto cppSort = []( unsigned *begin, unsigned *end )
>> {
>> sort( begin, end );
>> };
>> double tC, tCpp, rel;
>> for( size_t s = 2, rounds; s <= V_MAX; s *= 2 )
>> rounds = (V_MAX_ROUNDS / s) * V_MAX_ROUNDS,
>> tC = timedSort( cSort, s, rounds ),
>> tCpp = timedSort( cppSort, s, rounds ),
>> rel = tC / tCpp * 100.0,
>> cout << s << ": " << (int)(rel + 0.5) << "%" << endl;
>> }
>>
>> 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 !
>
> If a C programmer has concerns about qsort performance he just
> make it inline removing the function comparison pointer and using
> the function directly.

1. You can't inline a function with arbitrary recursion.
2. The comparison-function for qsort() is never inlined.

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%

Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 27.04.2022 um 13:21 schrieb Thiago Adams:
<snip>
>> If a C programmer has concerns about qsort performance he just
>> make it inline removing the function comparison pointer and using
>> the function directly.
>
> 1. You can't inline a function with arbitrary recursion.

The same is true in C++.

> 2. The comparison-function for qsort() is never inlined.

That's a toolchain issue. Nothing prevents C environments from inlining
qsort and it's callback; most simply haven't done so historically. Other
language environments like Rust implicitly rely on static compilation to
avoid the cost of an indirect function call on every comparison.

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

Am 28.04.2022 um 02:10 schrieb William Ahern:
> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> Am 27.04.2022 um 13:21 schrieb Thiago Adams:
> <snip>
>>> If a C programmer has concerns about qsort performance he just
>>> make it inline removing the function comparison pointer and using
>>> the function directly.
>>
>> 1. You can't inline a function with arbitrary recursion.
>
> The same is true in C++.
>
>> 2. The comparison-function for qsort() is never inlined.
>
> That's a toolchain issue. Nothing prevents C environments from inlining
> qsort and it's callback; ...

The qsort-function is a static piece of code and the comparison
-function is never inlined.

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.

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

Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 28.04.2022 um 02:10 schrieb William Ahern:
>> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>> Am 27.04.2022 um 13:21 schrieb Thiago Adams:
>> <snip>
>>>> If a C programmer has concerns about qsort performance he just
>>>> make it inline removing the function comparison pointer and using
>>>> the function directly.
>>>
>>> 1. You can't inline a function with arbitrary recursion.
>>
>> The same is true in C++.
>>
>>> 2. The comparison-function for qsort() is never inlined.
>>
>> That's a toolchain issue. Nothing prevents C environments from inlining
>> qsort and it's callback; ...
>
> The qsort-function is a static piece of code and the comparison
> -function is never inlined.

See disassembly posted elsethread. I've given all the information needed to
quickly reproduce this for yourself, assuming some minimal familiarity with
GCC.

Alpine Linux isn't even needed, it's just what I started with out of
caution. I just now reproduced the distinctive benchmark profiles between
qsort-inline and qsort-extern on macOS 12.3.1 after removing -Wl,-rpath from
CFLAGS. (The macOS/mach-O linker doesn't recognize the -rpath option, but
it's linker embeds and uses the original location by default, anyhow.) I
don't know off-hand how to get a proper disassembly on macOS (-flto
complicates things considerably), but there's no reason to believe that the
comparator wasn't inlined like it was on Linux.

As another poster mentioned, templates are good for much more than
performance inlining. But I've always had a gripe with the qsort vs
std::qsort meme in particular: it confuses C toolchains and historical
linking semantics with the language itself. It should be clear, now, that C
language semantics don't prevent inlining of a comparator passed to a
sorting function; now even one defined externally to the invoking source
unit. (Unless somehow I've missed that a standard routine can't be inlined
without violating the standard--e.g. that the symbol has to have a unique
address.)