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

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

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

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

Contents

  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

#149772 — template(ish) qsort() function possible in language standard?

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

[toc] | [next] | [standalone]

#149781

On Wed, 5 Feb 2020 12:25:51 -0800, mathog <dmathog@gmail.com> wrote:

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


As I've pointed out several times, a C compiler, assuming
appropriate visibility of the qsort and the comparison function
implementations, could certainly specialize that at the point of use,
with *no* language extensions.

Plenty of compilers can inline functions, and inlining both a function
and a sub-function called via a pointer (like qsort) is possible.  The
critical item is visibility of all the part to the compiler.  With
LTCG being fairly standard now, the definitions don't have to be in
the same translation unit, although you'd need to "object" file for
(say) qsort distributed in whatever intermediate form is required for
the implementations LTCG support.  I'm not aware that anyone has
actually done that.

A second issue is getting the compiler to actual decide to inline.

Recent versions of MSVC will inline and specialize the both the sort
and comparison function in the following, for example, even if it
needs a little help to convince it to actually do it - so it's clearly
possible.

This has the advantage of not requiring macro games define multiple
sort functions in a single translation unit.  And improving compilers
ability to inline and specialize code is going to be more generally
useful.


#define inline __forceinline  // MS silliness

#include <stddef.h>

static inline void inssort(void* base, size_t num, size_t size,
                          int (*compar)(const void*,const void*))
{
   int i, j, k;
   char *b = base;
   char *p;

   for (i=1; i<num; i++)
       for (j=i-1; j>=0; j--)
           {
           p = b+(j*size);
           if (compar(p, p+size) > 0)
               {
               // swap
               for (k=0; k<size; k++)
                   {
                   char t;
                   t = *(p+k);
                   *(p+k) = *(p+k+size);
                   *(p+k+size) = t;
                   }
               }
           else
               break;
           }
}

static inline int compint(const void* p1, const void* p2)
{
   const int *pi1 = p1;
   const int *pi2 = p2;

   if (*pi1 > *pi2)
       return 1;

   if (*pi1 < *pi2)
       return -1;

   return 0;
}

void f(int *array, int num)
{
   inssort(array, num, sizeof(int), compint);
}

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

#149799

Robert Wessel wrote:
> On Wed, 5 Feb 2020 12:25:51 -0800, mathog <dmathog@gmail.com> wrote:
>> Is there some reason a C standard cannot implement a template(ish)
>> qsort() for improved performance?
>>
> 
> As I've pointed out several times, a C compiler, assuming
> appropriate visibility of the qsort and the comparison function
> implementations, could certainly specialize that at the point of use,
> with *no* language extensions.
> 
> Plenty of compilers can inline functions, and inlining both a function
> and a sub-function called via a pointer (like qsort) is possible.  The
> critical item is visibility of all the part to the compiler.  With
> LTCG being fairly standard now, the definitions don't have to be in
> the same translation unit, although you'd need to "object" file for
> (say) qsort distributed in whatever intermediate form is required for
> the implementations LTCG support.  I'm not aware that anyone has
> actually done that.

That is what I was getting at.  Clearly the concept is possible and it 
would be convenient not to have to recode qsort(), bsearch(), or similar 
functions just to change data types, but until it is part of a language 
standard it won't be safe to include that feature in code which is 
supposed to be portable.

This extension to the languages would make implementations of packages 
like this one (implements a very nice way to do hashes):
   http://attractivechaos.github.io/klib/#Khash%3A%20generic%20hash%20table

easier to understand than is the current preprocessor based method:
https://github.com/attractivechaos/klib/blob/master/khash.h


> A second issue is getting the compiler to actual decide to inline.
Yeah, I know what you mean.  If "construct" was used and the compiler 
silently declined to inline the comparison function the whole exercise 
would be futile.

>                     char t;
>                     t = *(p+k);
>                     *(p+k) = *(p+k+size);
>                     *(p+k+size) = t;

That's another construct I wish would finally be addressed.  C and most 
other languages lack a standard swap() builtin which would reduce the 
preceding to just:

   swap(*(p+k), *(p+k+size));

That is not only shorter than the usual 3 line form but I think it is 
also clearer.  Doubly so when the expressions are quite long.  I would 
prefer swap() to parallel assignment (as in Python):

    a, b := b, a

because every time I encounter that in some language I have to determine 
if that language's standard requires automagically creating a temp 
variable to avoid collisions or not.  If not that expression might be 
equivalent to

    a := b

or

    b := a

depending on what order the assignments are applied.  Neither of those 
is what is desired.

In a similar vein, there is no memswap(), analogous to memcpy() or 
memmove(). For the example above:

    memswap(*(p+k), *(p+k+size), sizeof(char));

Dogma has it that memswap() isn't needed very often, so it need not be 
part of the language.  (Overlaps would also be an issue, with my vote 
being that overlaps would be a fatal error.)  One would hope that if it 
is ever added the language spec would require that for maximum 
efficiency implementations use native types whenever possible, so for 
sizes 1,2,4,8, probably 16, and maybe 32 or higher, only falling back to 
a more general form for other sizes, or if the third parameter is a 
variable.

Regards,

David Mathog

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

#149802

mathog <dmathog@gmail.com> writes:
[...]
> In a similar vein, there is no memswap(), analogous to memcpy() or
> memmove(). For the example above:
>
>    memswap(*(p+k), *(p+k+size), sizeof(char));
>
> Dogma has it that memswap() isn't needed very often, so it need not be
> part of the language.  (Overlaps would also be an issue, with my vote
> being that overlaps would be a fatal error.)

What exactly do you mean by "fatal error"?  Detecting overlap at
compile time is in general not possible.  Detecting overlap at run
time would add overhead; the compiler would have to generate code
to compare the addresses and size (almost certainly in a manner
that would not be guaranteed to work in user-written code).

memcpy() has undefined behavior on overlap.

    If copying takes place between objects that overlap, the behavior is
    undefined.

If memswap() were standardized, it would make sense to do the same
thing.

Note that memcpy()ing an object to itself has undefined behavior, though
I'd guess that it works as expected in most or all implementations.

>                                               One would hope that if
> it is ever added the language spec would require that for maximum
> efficiency implementations use native types whenever possible, so for
> sizes 1,2,4,8, probably 16, and maybe 32 or higher, only falling back
> to a more general form for other sizes, or if the third parameter is a
> variable.

I would hope that the language spec would leave it up to implementations
to optimize it as they choose, as it does now for memcpy().

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

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

#149806

Keith Thompson wrote:
> mathog <dmathog@gmail.com> writes:
> [...]
>> In a similar vein, there is no memswap(), analogous to memcpy() or
>> memmove(). For the example above:
>>
>>     memswap(*(p+k), *(p+k+size), sizeof(char));
>>
>> Dogma has it that memswap() isn't needed very often, so it need not be
>> part of the language.  (Overlaps would also be an issue, with my vote
>> being that overlaps would be a fatal error.)
> 
> What exactly do you mean by "fatal error"?  Detecting overlap at
> compile time is in general not possible.  Detecting overlap at run
> time would add overhead; the compiler would have to generate code
> to compare the addresses and size (almost certainly in a manner
> that would not be guaranteed to work in user-written code).
> 
> memcpy() has undefined behavior on overlap.
> 
>      If copying takes place between objects that overlap, the behavior is
>      undefined.
> 
> If memswap() were standardized, it would make sense to do the same
> thing.

Yes, it would normally be a run time check.  The user can add a check 
before calling memswap() if it might be a problem, as when calling it 
with two pointers to arrays.  The compiler could catch some overlaps 
though and generate a warning if it can tell at compile time that 
memswap() may be called with an overlap.  Like:

    memswap(array, array+M, array_element_size*N)

if there is some execution path where M<N.

> 
> Note that memcpy()ing an object to itself has undefined behavior, though
> I'd guess that it works as expected in most or all implementation

memswap() a pointer to itself should do nothing except waste CPU cycles. 
At least that would be the case for any swap mechanism that uses a 
temporary intermediate value.  Agreed that memswap() two pointers that 
are offset with overlapping data would be undefined.

> I would hope that the language spec would leave it up to implementations
> to optimize it as they choose, as it does now for memcpy().

I will concede that point too.  Probably using a corresponding natural 
type when available like:

     int32_t tmp = *a;
     *a= *bo;
     *b = tmp;

is faster than:

     for(char *aptr=(char *)a,  char *bptr=(char *)b, int i=0;
         i<length_in_bytes;
         i++, aptr++, bptr++){
         char tmp = *atpr;
         *aptr = *bptr;
         *bptr = tmp;
     }

in most instances, but perhaps in some situations that isn't true.  No 
need to hobble the compiler if it can figure that out.  I can think of 
at least one such case.  If there are multiple pairs of swapping 
variables in a loop and the compiler can pack them into two separate 
sets, with each variable in the same relative position in each set, then 
it might be able to use an SSE operation to swap all the variables in 
one operation.

Regards,

David Mathog

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

#149807

mathog <dmathog@gmail.com> writes:
> Keith Thompson wrote:
>> mathog <dmathog@gmail.com> writes:
>> [...]
>>> In a similar vein, there is no memswap(), analogous to memcpy() or
>>> memmove(). For the example above:
>>>
>>>     memswap(*(p+k), *(p+k+size), sizeof(char));
>>>
>>> Dogma has it that memswap() isn't needed very often, so it need not be
>>> part of the language.  (Overlaps would also be an issue, with my vote
>>> being that overlaps would be a fatal error.)
>>
>> What exactly do you mean by "fatal error"?  Detecting overlap at
>> compile time is in general not possible.  Detecting overlap at run
>> time would add overhead; the compiler would have to generate code
>> to compare the addresses and size (almost certainly in a manner
>> that would not be guaranteed to work in user-written code).
>>
>> memcpy() has undefined behavior on overlap.
>>
>>      If copying takes place between objects that overlap, the behavior is
>>      undefined.
>>
>> If memswap() were standardized, it would make sense to do the same
>> thing.
>
> Yes, it would normally be a run time check.  The user can add a check
> before calling memswap() if it might be a problem, as when calling it
> with two pointers to arrays.  The compiler could catch some overlaps
> though and generate a warning if it can tell at compile time that
> memswap() may be called with an overlap.  Like:
>
>    memswap(array, array+M, array_element_size*N)
>
> if there is some execution path where M<N.

How can the user check in general whether the arrays overlap,
given that relational operators on pointers to distinct objects
have undefined behavior?

Sure, an implementation *can* perform a runtime check (and do what
if it fails?).  That's consistent with it having undefined behavior.

>> Note that memcpy()ing an object to itself has undefined behavior, though
>> I'd guess that it works as expected in most or all implementation
>
> memswap() a pointer to itself should do nothing except waste CPU
> cycles. At least that would be the case for any swap mechanism that
> uses a temporary intermediate value.  Agreed that memswap() two
> pointers that are offset with overlapping data would be undefined.

The standard *could* specify, as a special case, that memcpy()
or memswap() with two identical pointers has defined behavior.  It
currently doesn't do so; it just talks about "objects that overlap",
which implies that memcpy(arr, arr, size) has undefined behavior.
(Doing nothing is of course consistent with undefined behavior.)

Note that the xor swap trick fails if you use it to swap an object
with itself.  I doubt that xor would be a good way to implement
memswap(), so this might not matter, but it's something to consider.

[...]

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

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

#149800

C is a poor language. Why not use C++?

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

#149854

mathog:

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

My opinion is that the general qsort() routine is fast
enough for the overwhelming majority of applications,
whereas in the rare cases when one needs as fast a sort as
possible, one is welcome to write a specific function of
one's own.  Swaps, by the way, may be long too if the
elements are large, so you may want to sort pointers or
array indices.

An alternative semi-generic implementation without a
comparison function is possible, i.e.:

    sort
    (  void*   data,    /* data to be sorted          */
       size_t  count    /* number of elements         */
       size_t  elemsz   /* element size               */
       size_t  cmp_ofs, /* offset of comparison field */
       size_t  cmp_len  /* size   of comparison field */
       char    invert   /* inverse order (descending) */
    )

Such a funciton would compare elements via something like:

    strncmp( elem_a + cmp_ofs, elem_b + cmp_ofs, cmp_len )

Is it not, also, possible to write a macro-based generic
sort that would accept the comparison code as another macro
and expand into a specialised sort routine?

-- 
()  ascii ribbon campaign -- against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

[toc] | [prev] | [standalone]

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

csiph-web