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

Groups > comp.lang.c > #103104

Re: language changes to optimize for speed in qsort?

Show all headers | View raw

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

Back to comp.lang.c | Previous | Next — Previous in thread | 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