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

Groups > comp.lang.c > #103061

language changes to optimize for speed in qsort?

Show all headers | View raw

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

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

Thread

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

csiph-web