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

Groups > comp.lang.c > #149772

template(ish) qsort() function possible in language standard?

Show all headers | View raw

The C language's standard qsort() function requires a pointer to a 
comparison function.  Of course this works, but the overhead of all 
those function calls can be substantial for a large sort.  Consequently 
explicitly coding a user_qsort() to include that comparison function can 
result in substantial performance increases.  That is also true even if 
the comparison part is coded in a user_qsort() as a function call when 
that function is provided as an inline function in the same module.  (So 
long as the compiler is doing inline functions there is no difference in 
speed between the explicitly coded implementation and the inline coded 
implementation.)

Is there some reason a C standard cannot implement a template(ish) 
qsort() for improved performance?

Something along these lines in a header file (example.h):

inline int my_compare_function(const some_type *A,
    const some_type *B, void *arg){
    //comparison specific for "some_type", where some_type
    // is int, a struct, or whatever
}

//"construct" would be new to the language and operate
//at the preprocessor stage.
#construct qsort_for_some_type(qsort,  my_compare_function)

which expands the qsort code for that function while defining the 
corresponding prototype:

void qsort_for_some_type(some_type *buffer);

which may be used in a source code file like:

include "example.h";

...
some_type *my_array = (some_type *)
       malloc(Number_entries * sizeof(some_type)));
...
    qsort_faster(my_array, Number_entries);

It does not require the usual 3rd argument (element size) because that 
is derived from my_compare_function nor does it need the 4th argument 
(comparison function) because that is coded in already.

The main downside I see to this, like most template-like methods, is 
that there is no explicit source code for the resulting 
qsort_for_some_type function(s), so debugging is awkward.  However, 
since #construct would expand the code in the preprocessor then one 
could always expand that module, save the resulting file, and then 
compile and debug from that.

If the language "knows" about a fixed set of constructable functions 
then the simple syntax for "construct" above is adequate.  If 
"construct" is to be more general, for instance accepting user defined 
template functions on which the construct is based, then it would need a 
more complex syntax and at that point one starts steering into C++ 
territory.


Regards,

David Mathog

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

Thread

template(ish) qsort() function possible in language standard? mathog <dmathog@gmail.com> - 2020-02-05 12:25 -0800
  Re: template(ish) qsort() function possible in language standard? Robert Wessel <robertwessel2@yahoo.com> - 2020-02-05 18:25 -0600
    Re: template(ish) qsort() function possible in language standard? mathog <dmathog@gmail.com> - 2020-02-06 10:02 -0800
      Re: template(ish) qsort() function possible in language standard? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-02-06 13:20 -0800
        Re: template(ish) qsort() function possible in language standard? mathog <dmathog@gmail.com> - 2020-02-06 15:24 -0800
          Re: template(ish) qsort() function possible in language standard? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-02-06 15:38 -0800
  Re: template(ish) qsort() function possible in language standard? Bonita Montero <Bonita.Montero@gmail.com> - 2020-02-06 20:56 +0100
  Re: template(ish) qsort() function possible in language standard? Anton Shepelev <anton.txt@gmail.com> - 2020-02-08 17:50 +0300

csiph-web