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

Groups > comp.lang.c > #103061 > unrolled thread

language changes to optimize for speed in qsort?

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

Contents

  language changes to optimize for speed in qsort? mathog <dmathog@gmail.com> - 2017-02-03 10:36 -0800
    Re: language changes to optimize for speed in qsort? Robert Wessel <robertwessel2@yahoo.com> - 2017-02-03 17:15 -0600
      Re: language changes to optimize for speed in qsort? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-02-03 16:26 -0800
        Re: language changes to optimize for speed in qsort? Robert Wessel <robertwessel2@yahoo.com> - 2017-02-05 02:58 -0600
          Re: language changes to optimize for speed in qsort? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-02-05 03:01 -0800
            Re: language changes to optimize for speed in qsort? Gareth Owen <gwowen@gmail.com> - 2017-02-05 13:03 +0000
            Re: language changes to optimize for speed in qsort? Robert Wessel <robertwessel2@yahoo.com> - 2017-02-06 04:30 -0600
          Re: language changes to optimize for speed in qsort? supercat@casperkitty.com - 2017-02-05 10:07 -0800
    Re: language changes to optimize for speed in qsort? supercat@casperkitty.com - 2017-02-03 16:42 -0800
      Re: language changes to optimize for speed in qsort? Ian Collins <ian-news@hotmail.com> - 2017-02-04 13:46 +1300
        Re: language changes to optimize for speed in qsort? supercat@casperkitty.com - 2017-02-03 16:57 -0800
          Re: language changes to optimize for speed in qsort? Keith Thompson <kst-u@mib.org> - 2017-02-03 18:39 -0800
      Re: language changes to optimize for speed in qsort? Tim Rentsch <txr@alumni.caltech.edu> - 2017-02-04 11:28 -0800

#103061 — language changes to optimize for speed in qsort?

ANSI C provides the qsort() function which is very general and 
convenient.  Unfortunately the generality part comes from passing in a 
comparison function, and for large sorts it is often factors of 2 or 3 
slower than one's own quicksort with the comparison operations coded 
directly in the function (so that no comparison function is passed or 
called).  It would be nice to have the speed of the specifically coded
qsorts - without having to code them specifically.

qsort() is also single threaded (presumably, probably that is an 
implementation dependent choice, but there is no way to specify the 
number of threads if more than 1 is used).  When pretty much every 
machine where a huge sort must run is likely to have many threads 
available this seems kind of archaic.  It would be much more convenient 
to just paste N into a standard function to split the work across N 
threads, rather than having to pull in some nonstandard code.  Even if
the sort does not scale linearly for large N.

Have the language developers given any thought to providing souped up 
qsorts that would resolve either of these two issues?

C doesn't have templates, unless it is in one of the newer language 
standards, and this is one of the few places in C where something like 
that might be really useful.  (This despite my loathing of C++ templates 
because of the agony they can induce when one needs to debug inside a 
template.)

This is what we have now (for discussion sake,
C2_DATA has c1,c2 which are both int, array is an array of C2_DATA
structs):

int c2_compare(const void *a, const void *b){
    C2_DATA *sa = (C2_DATA *)a;
    C2_DATA *sb = (C2_DATA *)b;
    int ret = sa->c1 - sb->c1;
    if(!ret){
       ret = sa->c2 - sb->c2;
    }
    return(ret);
}
qsort(array,  members, sizeof(C2_DATA), c2_compare);

For this very specific template case one would still have the same 
compare function code but in the some compilation module one would 
invoke a slightly different qsort

qsort_type_specific((C2_DATA *)array,  size_t members,
    sizeof(C2_DATA), c2_compare,"qsort_C2");

which would take the innards of c2_compare(), paste it into
the quicksort source code everywhere  *c2_compare was employed before,
compile that, to produce a function

void qsort_C2((C2_DATA *)array,  size_t members);

which could then be called or used like any other function.

While this would be a way to easily produce a type optimized qsort for 
the end user, even I don't at all like the syntax described above for 
qsort_type_specific() because it does something completely unexpected 
compared to usual C code.  Something similar could be done now using 
defines and include files, however that isn't the most convenient of 
methods and code like that is often a pain to read and maintain.

As for parallel quicksort, there a solution need not require a new C 
syntax, just a new function or two, for instance:

void tqsort(void *base, size_t nmemb, size_t size,
                   int(*compar)(const void *, const void *),
                   int threads);
int threads_available(void);

and the details of how the thread count is obtained, and how many 
threads tqsort actually uses, even which parallel quicksort algorithm is 
used, is entirely up to the compiler.  Except it must always run, even 
if it must do so with one thread.

Are there any other standard functions which would benefit from threads? 
  The same argument might apply there too.  The thing is,
while it might be useful for memcpy() or memset() it isn't clear to me 
that the performance gain would be worth the effort.   Sorts, on the 
other hand, are often rate limiting in real world code.

Regards,

David Mathog

[toc] | [next] | [standalone]

#103092

On Fri, 3 Feb 2017 10:36:04 -0800, mathog <dmathog@gmail.com> wrote:

>ANSI C provides the qsort() function which is very general and 
>convenient.  Unfortunately the generality part comes from passing in a 
>comparison function, and for large sorts it is often factors of 2 or 3 
>slower than one's own quicksort with the comparison operations coded 
>directly in the function (so that no comparison function is passed or 
>called).  It would be nice to have the speed of the specifically coded
>qsorts - without having to code them specifically.
>
>qsort() is also single threaded (presumably, probably that is an 
>implementation dependent choice, but there is no way to specify the 
>number of threads if more than 1 is used).  When pretty much every 
>machine where a huge sort must run is likely to have many threads 
>available this seems kind of archaic.  It would be much more convenient 
>to just paste N into a standard function to split the work across N 
>threads, rather than having to pull in some nonstandard code.  Even if
>the sort does not scale linearly for large N.
>
>Have the language developers given any thought to providing souped up 
>qsorts that would resolve either of these two issues?
>
>C doesn't have templates, unless it is in one of the newer language 
>standards, and this is one of the few places in C where something like 
>that might be really useful.  (This despite my loathing of C++ templates 
>because of the agony they can induce when one needs to debug inside a 
>template.)
>
>This is what we have now (for discussion sake,
>C2_DATA has c1,c2 which are both int, array is an array of C2_DATA
>structs):
>
>int c2_compare(const void *a, const void *b){
>    C2_DATA *sa = (C2_DATA *)a;
>    C2_DATA *sb = (C2_DATA *)b;
>    int ret = sa->c1 - sb->c1;
>    if(!ret){
>       ret = sa->c2 - sb->c2;
>    }
>    return(ret);
>}
>qsort(array,  members, sizeof(C2_DATA), c2_compare);
>
>For this very specific template case one would still have the same 
>compare function code but in the some compilation module one would 
>invoke a slightly different qsort
>
>qsort_type_specific((C2_DATA *)array,  size_t members,
>    sizeof(C2_DATA), c2_compare,"qsort_C2");
>
>which would take the innards of c2_compare(), paste it into
>the quicksort source code everywhere  *c2_compare was employed before,
>compile that, to produce a function
>
>void qsort_C2((C2_DATA *)array,  size_t members);
>
>which could then be called or used like any other function.
>
>While this would be a way to easily produce a type optimized qsort for 
>the end user, even I don't at all like the syntax described above for 
>qsort_type_specific() because it does something completely unexpected 
>compared to usual C code.  Something similar could be done now using 
>defines and include files, however that isn't the most convenient of 
>methods and code like that is often a pain to read and maintain.
>
>As for parallel quicksort, there a solution need not require a new C 
>syntax, just a new function or two, for instance:
>
>void tqsort(void *base, size_t nmemb, size_t size,
>                   int(*compar)(const void *, const void *),
>                   int threads);
>int threads_available(void);
>
>and the details of how the thread count is obtained, and how many 
>threads tqsort actually uses, even which parallel quicksort algorithm is 
>used, is entirely up to the compiler.  Except it must always run, even 
>if it must do so with one thread.
>
>Are there any other standard functions which would benefit from threads? 
>  The same argument might apply there too.  The thing is,
>while it might be useful for memcpy() or memset() it isn't clear to me 
>that the performance gain would be worth the effort.   Sorts, on the 
>other hand, are often rate limiting in real world code.


As I've pointed out several times, the (in)ability to specialize a
copy of qsort and inline the passed comparison function (at least if
the function passed is known at compile time), is more an
implementation issue than anything else.  Several compilers can get
pretty close now.  In many cases this is more an issue to convince the
compiler to actually inline a large-ish routine.

That being said, something template-like for C would help there as
well, especially for less sophisticated compilers.  OTOH, there's
little preventing you from specifying the entire implementation of
qsort in a macro, and then invoking it that way (and at that point the
compiler just needs to inline the comparison function).

OTOH, (good) parallel sorts are usually fairly code heavy, so having
many specializations of those would be a bit problematic.  OTOH,
there's little to prevent someone for doing that in say C++ by
replacing std:sort with a parallel version, although you'd just end up
with a pretty big chuck of code being specialized.  And you could do
the same for qsort as well.  In both cases, though, the sort would
likely no longer be Quicksort, as Quicksort does not parallelize well
(even with an infinite number of processors, you can't get better than
lg(n)/2 speedup).

As to the number of threads, well, at least both C and C++ now sort of
support threads, so that's there, but in most cases trying to specify
the exact number of threads is a mistake - usually it's better to let
the sort implementation make that decision.  OTOH, the vast majority
of sorts that fit in memory aren't really big enough to justify much
parallelism, and most sorts that are big enough end up being external
sorts, which adds a whole different level of complexity to the task,
and is clearly outside of what qsort or std::sort attempt to do.

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

#103097

On Friday, February 3, 2017 at 11:15:11 PM UTC, robert...@yahoo.com wrote:
> On Fri, 3 Feb 2017 10:36:04 -0800, mathog <dmathog@gmail.com> wrote:
> 
> >ANSI C provides the qsort() function which is very general and 
> >convenient.  Unfortunately the generality part comes from passing in a 
> >comparison function, and for large sorts it is often factors of 2 or 3 
> >slower than one's own quicksort with the comparison operations coded 
> >directly in the function (so that no comparison function is passed or 
> >called).  It would be nice to have the speed of the specifically coded
> >qsorts - without having to code them specifically.
> 
It used to be the case than many mainframes spent 70% or so of
their cycles on sorting. I doubt that is still true. A database
with 50 million entries would cover pretty much every adult in
the UK, and a modern machine will just slice through that sort
without any special optimisations.

But C does allow you to code your own sort. quicksort isn't always
the fastest. With football league type data (after each day's 
matches positions can change, but rarely by more than one or two
positions) bubblesort is very fast, for example.
>
> >C doesn't have templates, unless it is in one of the newer language 
> >standards, and this is one of the few places in C where something like 
> >that might be really useful.  (This despite my loathing of C++ templates 
> >because of the agony they can induce when one needs to debug inside a 
> >template.)
>>
C has void *s. void *s abstract away payload from structures. 

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

#103184

On Fri, 3 Feb 2017 16:26:16 -0800 (PST), Malcolm McLean
<malcolm.mclean5@btinternet.com> wrote:

>On Friday, February 3, 2017 at 11:15:11 PM UTC, robert...@yahoo.com wrote:
>> On Fri, 3 Feb 2017 10:36:04 -0800, mathog <dmathog@gmail.com> wrote:
>> 
>> >ANSI C provides the qsort() function which is very general and 
>> >convenient.  Unfortunately the generality part comes from passing in a 
>> >comparison function, and for large sorts it is often factors of 2 or 3 
>> >slower than one's own quicksort with the comparison operations coded 
>> >directly in the function (so that no comparison function is passed or 
>> >called).  It would be nice to have the speed of the specifically coded
>> >qsorts - without having to code them specifically.
>> 
>It used to be the case than many mainframes spent 70% or so of
>their cycles on sorting. I doubt that is still true. A database
>with 50 million entries would cover pretty much every adult in
>the UK, and a modern machine will just slice through that sort
>without any special optimisations.


Statistics like that have been often quoted, but I have my doubts if
that was ever generally true (certainly there would have been specific
cases, but in general?).  But it's certainly no longer true.


>But C does allow you to code your own sort. quicksort isn't always
>the fastest. With football league type data (after each day's 
>matches positions can change, but rarely by more than one or two
>positions) bubblesort is very fast, for example.


OTOH, bubblesort will not be all that much faster, even under the best
of circumstances - a factor of lg(n) at best.  And it would have the
nasty little property that it might go quadratic on a bad input (let's
say the first and last place teams swapped positions - the resulting
bubble sort will take O(n**2), where as a nice heapsort would take the
same O(n*lg(n)) it always takes).  Insertion sort would work at least
somewhat better (and pretty much never worse), which is again, a
reason to essentially never use bubblesort.  Further if that's the
nature of the datasets, other sorts can be adapted to take advantage
of large swaths of already sorted data (mergesort, for example, can be
trivially adapted).

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

#103190

On Sunday, February 5, 2017 at 8:58:00 AM UTC, robert...@yahoo.com wrote:
> On Fri, 3 Feb 2017 16:26:16 -0800 (PST), Malcolm McLean
> <malcolm.mclean5@btinternet.com> wrote:
> 
> OTOH, bubblesort will not be all that much faster, even under the best
> of circumstances - a factor of lg(n) at best.  And it would have the
> nasty little property that it might go quadratic on a bad input (let's
> say the first and last place teams swapped positions - 
>
In a real football league that can only happen after the second match
(assuming sane results, you could have 100% draws until on the last
day of the season someone finally wins a match and thus the league),
but the teams will move about quite a bit for the first few matches
when only a few points can separate top and bottom.

However once league-type data is established, often it is impossible
or almost impossible for anything to move more than one or two places
on each pass. Sorting a football league will be done in microseconds 
even with an N**2 sort of course, because you only have 20 or so
teams in a league. But you can get other data with that characteristic,
one example is polygon z-order in a  world of static or slowly moving
objects relative to a slowly panning camera.

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

#103196

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:

> However once league-type data is established, often it is impossible
> or almost impossible for anything to move more than one or two places
> on each pass. Sorting a football league will be done in microseconds 
> even with an N**2 sort of course

Sorting a football league will take microseconds, because football
leagues tend to have 20-30 teams in them.  So, as long as you avoid
bogosort(), it almost certainly doesn't matter. On those occasions when
it does matter (e.g. your league secretary insists on processing match
results using an 16-bit micro running at 1Mhz), the only way to choose
the best algorithm is by measurement on typical data.

If you're using asymptotic analysis to determine how to sort thirty
items, then you do not understand the puropose or limitations of
asymptotic analysis.

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

#103282

On Sun, 5 Feb 2017 03:01:37 -0800 (PST), Malcolm McLean
<malcolm.mclean5@btinternet.com> wrote:

>On Sunday, February 5, 2017 at 8:58:00 AM UTC, robert...@yahoo.com wrote:
>> On Fri, 3 Feb 2017 16:26:16 -0800 (PST), Malcolm McLean
>> <malcolm.mclean5@btinternet.com> wrote:
>> 
>> OTOH, bubblesort will not be all that much faster, even under the best
>> of circumstances - a factor of lg(n) at best.  And it would have the
>> nasty little property that it might go quadratic on a bad input (let's
>> say the first and last place teams swapped positions - 
>>
>In a real football league that can only happen after the second match
>(assuming sane results, you could have 100% draws until on the last
>day of the season someone finally wins a match and thus the league),
>but the teams will move about quite a bit for the first few matches
>when only a few points can separate top and bottom.
>
>However once league-type data is established, often it is impossible
>or almost impossible for anything to move more than one or two places
>on each pass. Sorting a football league will be done in microseconds 
>even with an N**2 sort of course, because you only have 20 or so
>teams in a league. But you can get other data with that characteristic,
>one example is polygon z-order in a  world of static or slowly moving
>objects relative to a slowly panning camera.


Obviously no real football league will have enough data to make any of
this meaningful, I assumed you were using this to illustrate the
concept.  In any event, unusual events even in something a structured
as a football league results table can occur.  Consider the late
season discovery that the first place team has been cheating in some
fashion, and has most of its wins that season nullified, and then that
team may fall from first to last place on the next update cycle.

Which just gets back to a pet point of mine - unusual data and even
maliciously* constructed data, must be anticipated in systems.
Consider that instead of a football league table you had something
similar but for millions or billions of items.  Now consider an
unexpected event that causes the first place rank to drop to the
bottom, and this can even be an unusual event - just so long as it
isn't impossible.  The sort phase suddenly taking 10**12 or 10**18
time instead of 10**6 or 10**9, may well have serious consequences.


*This is 2017 - anyone not expecting maliciously constructed input
datasets had damn well better be able to *prove* that it's impossible
for such a thing to occur, or simply not care if the application
fails, perhaps catastrophically.

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

#103219

On Sunday, February 5, 2017 at 2:58:00 AM UTC-6, robert...@yahoo.com wrote:
> >It used to be the case than many mainframes spent 70% or so of
> >their cycles on sorting. I doubt that is still true. A database
> >with 50 million entries would cover pretty much every adult in
> >the UK, and a modern machine will just slice through that sort
> >without any special optimisations.

Whether that is true or not would almost certainly depend upon the
definitions of "many" and "sorting".

> Statistics like that have been often quoted, but I have my doubts if
> that was ever generally true (certainly there would have been specific
> cases, but in general?).  But it's certainly no longer true.

Some machines do spend the majority of their time maintaining databases and
the indices therefor.  Databases seldom arrange records physically in sorted
logical order, but I would say that maintenance of the structures necessary
to make a database behave as though records are in sorted order could be
viewed as a form of "sorting".

> >But C does allow you to code your own sort. quicksort isn't always
> >the fastest. With football league type data (after each day's 
> >matches positions can change, but rarely by more than one or two
> >positions) bubblesort is very fast, for example.
> 
> OTOH, bubblesort will not be all that much faster, even under the best
> of circumstances - a factor of lg(n) at best.  And it would have the
> nasty little property that it might go quadratic on a bad input (let's
> say the first and last place teams swapped positions - the resulting
> bubble sort will take O(n**2), where as a nice heapsort would take the
> same O(n*lg(n)) it always takes).  Insertion sort would work at least
> somewhat better (and pretty much never worse), which is again, a
> reason to essentially never use bubblesort.  Further if that's the
> nature of the datasets, other sorts can be adapted to take advantage
> of large swaths of already sorted data (mergesort, for example, can be
> trivially adapted).

If one had billions of items which were in sorted order, and could only
change by small amounts, the optimal sort would probably be a special
hybrid which identified areas that were out of order and then handled
each using a method based upon the size of the area in question.  If the
maximum change was small relative to the granularity of the value being
sorted, a variation of radix/bucket sort might also be helpful (if one
is sorting 64-bit integers, one could maintain lists of records that are
15 below the highest value yet observed, 14 below, 13 below, etc. and
write out each list whenever a record is seen whose value exceeds that
of the list's items by more than 15).

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

#103102

On Friday, February 3, 2017 at 12:38:11 PM UTC-6, mathog wrote:
> ANSI C provides the qsort() function which is very general and 
> convenient.  Unfortunately the generality part comes from passing in a 
> comparison function, and for large sorts it is often factors of 2 or 3 
> slower than one's own quicksort with the comparison operations coded 
> directly in the function (so that no comparison function is passed or 
> called).  It would be nice to have the speed of the specifically coded
> qsorts - without having to code them specifically.

In addition to having to use a comparison function, qsort() also suffers
from the need to perform all swaps using something equivalent to memmove()
or memcpy() even if the things being sorted are pointers.  On platforms
which use the same representation for all types of pointers it should be
possible to write a qsort() routine which is specialized for sorting
pointers, but given two double-indirect pointers the only "optimization-
proof" way of swapping the pointers identified thereby is to use memmove
or memcpy, or else copy them as sequences of bytes.

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

#103104

On 02/ 4/17 01:42 PM, supercat@casperkitty.com wrote:
> On Friday, February 3, 2017 at 12:38:11 PM UTC-6, mathog wrote:
>> ANSI C provides the qsort() function which is very general and
>> convenient.  Unfortunately the generality part comes from passing in a
>> comparison function, and for large sorts it is often factors of 2 or 3
>> slower than one's own quicksort with the comparison operations coded
>> directly in the function (so that no comparison function is passed or
>> called).  It would be nice to have the speed of the specifically coded
>> qsorts - without having to code them specifically.
>
> In addition to having to use a comparison function, qsort() also suffers
> from the need to perform all swaps using something equivalent to memmove()
> or memcpy() even if the things being sorted are pointers.  On platforms
> which use the same representation for all types of pointers it should be
> possible to write a qsort() routine which is specialized for sorting
> pointers, but given two double-indirect pointers the only "optimization-
> proof" way of swapping the pointers identified thereby is to use memmove
> or memcpy, or else copy them as sequences of bytes.

If you want C++, you know where to find it :)

-- 
Ian

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

#103108

On Friday, February 3, 2017 at 6:46:12 PM UTC-6, Ian Collins wrote:
> On 02/ 4/17 01:42 PM, supercat wrote:
> > On Friday, February 3, 2017 at 12:38:11 PM UTC-6, mathog wrote:
> >> ANSI C provides the qsort() function which is very general and
> >> convenient.  Unfortunately the generality part comes from passing in a
> >> comparison function, and for large sorts it is often factors of 2 or 3
> >> slower than one's own quicksort with the comparison operations coded
> >> directly in the function (so that no comparison function is passed or
> >> called).  It would be nice to have the speed of the specifically coded
> >> qsorts - without having to code them specifically.
> >
> > In addition to having to use a comparison function, qsort() also suffers
> > from the need to perform all swaps using something equivalent to memmove()
> > or memcpy() even if the things being sorted are pointers.  On platforms
> > which use the same representation for all types of pointers it should be
> > possible to write a qsort() routine which is specialized for sorting
> > pointers, but given two double-indirect pointers the only "optimization-
> > proof" way of swapping the pointers identified thereby is to use memmove
> > or memcpy, or else copy them as sequences of bytes.
> 
> If you want C++, you know where to find it :)

The necessary feature also existed in just about almost every compiler
around 1990--treat any access performed via void** as potential access to
any other pointer type.  Today, however, it's fashionable for compilers to
say that if the Standard doesn't require them to recognize aliasing even in
cases where it would obviously be useful, they should assume that code won't
rely upon it even in cases where it obviously does.

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

#103116

supercat@casperkitty.com writes:
[...]
> The necessary feature also existed in just about almost every compiler
> around 1990--treat any access performed via void** as potential access to
> any other pointer type.  Today, however, it's fashionable for compilers to
> say that if the Standard doesn't require them to recognize aliasing even in
> cases where it would obviously be useful, they should assume that code won't
> rely upon it even in cases where it obviously does.

Yes, yes, we heard you the 23rd time.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#103165

supercat@casperkitty.com writes:

> On Friday, February 3, 2017 at 12:38:11 PM UTC-6, mathog wrote:
>> ANSI C provides the qsort() function which is very general and
>> convenient.  Unfortunately the generality part comes from passing in a
>> comparison function, and for large sorts it is often factors of 2 or 3
>> slower than one's own quicksort with the comparison operations coded
>> directly in the function (so that no comparison function is passed or
>> called).  It would be nice to have the speed of the specifically coded
>> qsorts - without having to code them specifically.
>
> In addition to having to use a comparison function, qsort()
> also suffers from the need to perform all swaps using something
> equivalent to memmove() or memcpy() even if the things being
> sorted are pointers.  [...]

Not so.  qsort() is part of the standard library, and as such it
can take advantage of information known to the implementation but
not available to regular C programs.

[toc] | [prev] | [standalone]

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

csiph-web