Jacob's mention of his library reminds me of my own
suggestion to help with software reusability.

Much software has the form
  High Level -- application-specific code
    Mid Level -- application-specific code
      Low Level -- FREQUENT FUNCTION, use library

But often one encounters
  High Level -- application-specific code
    Mid Level -- FREQUENT FUNCTION
      Low Level -- application-specific code

A familiar example where this form is encountered and
dealt with is qsort(), with the low-level handled
simply with a function pointer.

If the qsort() source were recompiled with the
application-dependent comparison etc. it would speed
up, perhaps by 25%.  The qsort.c source wouldn't
even change; instead the variation would be provided
by a very simple application-dependent header included
by qsort.c.

For example, make this definition:
  #define COMP(x,y)      \
     (((struct elem *)x)->key - ((struct elem *)y)->key)
visible to qsort.c, rather than just pass a pointer
to the function
  int ecomp(const void *x, const void *y)
  { return COMP(x,y); }

I mention this simple case to make the idea clear,
but if all I wanted to do is speed-up qsort() by 25%
I wouldn't be posting this.  Instead I'm thinking
of cases where the common function CAN'T BE USED
AT ALL, without this flexibility.

In these interesting cases, the application-dependent
variations are much too complicated to be represented
with a few function arguments, but a common source
code could still be used, with any variations
coming from #define's in an application-dependent header.
(I have specific examples in mind, but won't mention
them.  I want to focus on the idea of reusing
source code in the way I imply, rather than any
specific example.)

How about it?  Anybody do this, or want to do it?
(There are examples of it *within* a buildable
library, but I'm talking about library source where
the user is encouraged to recompile a routine,
like qsort() but probably more complicated, using
his own application-specific header.)

James Dow Allen

James Dow Allen wrote:
> ... ... ...
> How about it?  Anybody do this, or want to do it?
> (There are examples of it *within* a buildable
> library, but I'm talking about library source where
> the user is encouraged to recompile a routine,
> like qsort() but probably more complicated, using
> his own application-specific header.)

I read your post twice but had a little trouble following it.  That's my 
problem so I'd like to ask for clarification, please: Are you asking if 
there's a common way to override library routines with one's own code? 
Are you asking if there ought to be a common way?

On Sep 7, 1:17=A0am, Shao Miller <sha0.mil...@gmail.com> wrote:
> I read your post twice but had a little trouble following it. =A0That's m=
y
> problem so I'd like to ask for clarification, please: Are you asking if
> there's a common way to override library routines with one's own code?
> Are you asking if there ought to be a common way?

You're trying to find my QUESTION.  My post isn't
a question; it's a RECOMMENDATION.

I'm not asking HOW to do what I describe.  That's easy.
I already do it in some of my own source code.

What I AM asking is: Why aren't the rest of you doing this?
  :-)

Hope this clarifies.
James

In article <201d0119-1080-41b4-bdf7-bd6355533685@b4g2000pra.googlegroups.com>,
James Dow Allen  <jdallen2000@yahoo.com> wrote:
>On Sep 7, 1:17�am, Shao Miller <sha0.mil...@gmail.com> wrote:
>> I read your post twice but had a little trouble following it. �That's my
>> problem so I'd like to ask for clarification, please: Are you asking if
>> there's a common way to override library routines with one's own code?
>> Are you asking if there ought to be a common way?
>
>You're trying to find my QUESTION.  My post isn't
>a question; it's a RECOMMENDATION.
>
>I'm not asking HOW to do what I describe.  That's easy.
>I already do it in some of my own source code.
>
>What I AM asking is: Why aren't the rest of you doing this?
>  :-)
>
>Hope this clarifies.
>James
>

Those kinds of posts don't fly well in newsgroups like this.

Once you deviate from:

    Student: Oh master, oh holy of holies, how do I do X?  (And what is
    wrong with the way a poor wretch like me is doing it?)

    Master: You are subhuman slime, but I shall deign to answer thee.

the newsgroup falls off the rails.  Sad, but true.

-- 
Just for a change of pace, this sig is *not* an obscure reference to
comp.lang.c...

On Sep 6, 3:57=A0pm, gaze...@shell.xmission.com (Kenny McCormack) wrote:
> In article <201d0119-1080-41b4-bdf7-bd6355533...@b4g2000pra.googlegroups.=
com>,
> James Dow Allen =A0<jdallen2...@yahoo.com> wrote:
>
>
>
> >On Sep 7, 1:17=A0am, Shao Miller <sha0.mil...@gmail.com> wrote:
> >> I read your post twice but had a little trouble following it. =A0That'=
s my
> >> problem so I'd like to ask for clarification, please: Are you asking i=
f
> >> there's a common way to override library routines with one's own code?
> >> Are you asking if there ought to be a common way?
>
> >You're trying to find my QUESTION. =A0My post isn't
> >a question; it's a RECOMMENDATION.
>
> >I'm not asking HOW to do what I describe. =A0That's easy.
> >I already do it in some of my own source code.
>
> >What I AM asking is: Why aren't the rest of you doing this?
> > =A0:-)
>
> >Hope this clarifies.
> >James
>
> Those kinds of posts don't fly well in newsgroups like this.
>
> Once you deviate from:
>
> =A0 =A0 Student: Oh master, oh holy of holies, how do I do X? =A0(And wha=
t is
> =A0 =A0 wrong with the way a poor wretch like me is doing it?)
>
> =A0 =A0 Master: You are subhuman slime, but I shall deign to answer thee.
>
> the newsgroup falls off the rails. =A0Sad, but true.

usually when a newb comes into a group [any group] and says things
like "why not we do everything while standing on our heads?" it's
because they don't know what they're talking about.

This doesn't mean we don't listen to the newbs, it just means we don't
follow them.  It's not our fault you can't tell the difference.

As to the specifics here, the solution to the OPs problem is called a
"processor cache" and "stack opcode optimizations" [something modern
high performance processors have] making the need to inline your
compare function rather moot.

Also, sometimes paying a small penalty in performance to make
something 100x generic/scalable is worth it in the end.  I'd rather
have a standard generic qsort() like in the C lib than a 100 different
ones for all sorts of different data types.

And you can accomplish all sorts of "anonymous" code in C through the
use of structs with pointers to functions.  I've written entire
libraries based on the concept.  It allows me to construct very
modular/customizable applications out of standard C code without re-
inventing the wheel all the time.

Tom

James Dow Allen wrote:
> On Sep 7, 1:17 am, Shao Miller <sha0.mil...@gmail.com> wrote:
>> I read your post twice but had a little trouble following it.  That's my
>> problem so I'd like to ask for clarification, please: Are you asking if
>> there's a common way to override library routines with one's own code?
>> Are you asking if there ought to be a common way?
> 
> You're trying to find my QUESTION.  My post isn't
> a question; it's a RECOMMENDATION.
> 
> I'm not asking HOW to do what I describe.  That's easy.
> I already do it in some of my own source code.
> 
> What I AM asking is: Why aren't the rest of you doing this?
>   :-)
> 
> Hope this clarifies.

Ok.  Sorry for my misinterpretation.  I was trying to understand:

James Dow Allen wrote:
> ... ... ...
> How about it?  Anybody do this, or want to do it?
> (There are examples of it *within* a buildable
> library, but I'm talking about library source where
> the user is encouraged to recompile a routine,
> like qsort() but probably more complicated, using
> his own application-specific header.)

And mistook it to include two questions.

So I'd like to ask for a little bit more clarification:  Are you 
recommending a particular method for overriding library functions with 
one's own code, via this header-inclusion strategy?  Are you suggesting 
that overriding library functions with one's own code is a pretty handy 
thing to do, in general, to achieve performance benefits?

In article <a1f0d42a-a83f-4df1-9e92-7f2721b55e41@i31g2000yqm.googlegroups.com>,
Tom St Denis  <tom@iahu.ca> wrote:
....
>usually when a newb comes into a group [any group] and says things
>like "why not we do everything while standing on our heads?" it's
>because they don't know what they're talking about.

Yup.  James Dow Allen is a newb here.  Never seen him post before, no
siree!  He's got some nerve comin' in here and stirin' things up!

Thanks for proving my point.

-- 
But the Bush apologists hope that you won't remember all that. And they
also have a theory, which I've been hearing more and more - namely,
that President Obama, though not yet in office or even elected, caused the
2008 slump. You see, people were worried in advance about his future
policies, and that's what caused the economy to tank. Seriously.

    (Paul Krugman - Addicted to Bush)

On 9/6/2010 1:48 PM, James Dow Allen wrote:
> Jacob's mention of his library reminds me of my own
> suggestion to help with software reusability.
>
> Much software has the form
>    High Level -- application-specific code
>      Mid Level -- application-specific code
>        Low Level -- FREQUENT FUNCTION, use library
>
> But often one encounters
>    High Level -- application-specific code
>      Mid Level -- FREQUENT FUNCTION
>        Low Level -- application-specific code
>
> A familiar example where this form is encountered and
> dealt with is qsort(), with the low-level handled
> simply with a function pointer.
>
> If the qsort() source were recompiled with the
> application-dependent comparison etc. it would speed
> up, perhaps by 25%.

     Aside: Did you know that 84.6% of all stated percentages
are made up out of thin air?

>  The qsort.c source wouldn't
> even change; instead the variation would be provided
> by a very simple application-dependent header included
> by qsort.c.
>
> For example, make this definition:
>    #define COMP(x,y)      \
>       (((struct elem *)x)->key - ((struct elem *)y)->key)
> visible to qsort.c, rather than just pass a pointer
> to the function
>    int ecomp(const void *x, const void *y)
>    { return COMP(x,y); }
>
> I mention this simple case to make the idea clear,
> but if all I wanted to do is speed-up qsort() by 25%
> I wouldn't be posting this.  Instead I'm thinking
> of cases where the common function CAN'T BE USED
> AT ALL, without this flexibility.

     A concrete example might be helpful here, despite
the misgivings you state below.  In particular, I'd like
to understand the "CAN'T BE USED AT ALL" part.

> In these interesting cases, the application-dependent
> variations are much too complicated to be represented
> with a few function arguments, but a common source
> code could still be used, with any variations
> coming from #define's in an application-dependent header.
> (I have specific examples in mind, but won't mention
> them.  I want to focus on the idea of reusing
> source code in the way I imply, rather than any
> specific example.)
>
> How about it?  Anybody do this, or want to do it?
> (There are examples of it *within* a buildable
> library, but I'm talking about library source where
> the user is encouraged to recompile a routine,
> like qsort() but probably more complicated, using
> his own application-specific header.)

     It's done occasionally.  I've seen a sort implementation
packaged as an #include file.  You did something like

	#define SORT_NAME mySort
	#define SORT_TYPE struct frazzle
	#define SORT_COMP(s,t) strcmp((s).key, (t).key)
	#include "sort.h"

.... and got a `void mySort(struct frazzle *data, size_t nitems)'
function built for you.  At a PPOE, a colleague put together a 
serialization library that worked similarly: You #define'd a
bunch of stuff to describe the data structure you wanted to
serialize, then you invoked a macro from his header to generate
the actual code.  So, variations on this theme are certainly
playable.

     As to why they don't get more air time -- well, I'm sure
there are lots of reasons.  Lack of direct support from the tools
that go along with the language has to be one of them: Lots of
debuggers, for example, have trouble stepping from line to line
through a function generated by a one-line macro invocation.
Mistakes by the client/user may well elicit compiler diagnostics
that are confusing at best, misleading at worst -- after the
#include or whatever you get a cascade of syntax errors and no
further clue.  Testing becomes more laborious, because the innards
of the "module" are exposed to the surrounding code rather than
isolated from it, meaning that there are vastly more client/module
interactions to worry about.

     My (vague) understanding of C++ templates is that they're a
kind of a way to regularize such an approach and give it some
help from the language itself and its tool set.  But lacking such
support, the technique carries some disincentives that (it seems)
outweigh many of its advantages in the estimation of the coders.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

"James Dow Allen" <jdallen2000@yahoo.com> wrote in message 
news:1d233e49-8bb1-450c-8ac6-73e7294ce784@u4g2000prn.googlegroups.com...
> Jacob's mention of his library reminds me of my own
> suggestion to help with software reusability.
>
> Much software has the form
>  High Level -- application-specific code
>    Mid Level -- application-specific code
>      Low Level -- FREQUENT FUNCTION, use library
>
> But often one encounters
>  High Level -- application-specific code
>    Mid Level -- FREQUENT FUNCTION
>      Low Level -- application-specific code
>
> A familiar example where this form is encountered and
> dealt with is qsort(), with the low-level handled
> simply with a function pointer.
>
> If the qsort() source were recompiled with the
> application-dependent comparison etc. it would speed
> up, perhaps by 25%.  The qsort.c source wouldn't
> even change; instead the variation would be provided
> by a very simple application-dependent header included
> by qsort.c.
>

it is unlikely to be that large.

rarely do most micro-optimizations really effect that much, which is part of 
why optimizations in optimizing compilers make notable alterations to the 
structure typically for only modest speedups in most cases.


> For example, make this definition:
>  #define COMP(x,y)      \
>     (((struct elem *)x)->key - ((struct elem *)y)->key)
> visible to qsort.c, rather than just pass a pointer
> to the function
>  int ecomp(const void *x, const void *y)
>  { return COMP(x,y); }
>
> I mention this simple case to make the idea clear,
> but if all I wanted to do is speed-up qsort() by 25%
> I wouldn't be posting this.  Instead I'm thinking
> of cases where the common function CAN'T BE USED
> AT ALL, without this flexibility.
>
> In these interesting cases, the application-dependent
> variations are much too complicated to be represented
> with a few function arguments, but a common source
> code could still be used, with any variations
> coming from #define's in an application-dependent header.
> (I have specific examples in mind, but won't mention
> them.  I want to focus on the idea of reusing
> source code in the way I imply, rather than any
> specific example.)
>
> How about it?  Anybody do this, or want to do it?
> (There are examples of it *within* a buildable
> library, but I'm talking about library source where
> the user is encouraged to recompile a routine,
> like qsort() but probably more complicated, using
> his own application-specific header.)
>

problems like this rarely come up, and usually are better solved via other 
means (for example, vtable structures, ... are a common solution, ...).

in one case where a similar problem did pop up (though mostly due to a 
poorly designed mass of code), I had basically ended up having to beat 
together a somewhat modified C preprocessor to pull it off, as the stock C 
preprocessor was too weak to really do these sorts of things...


but, as a general rule, likely the main reason things are not done this way 
is because it is generally not very a good way to design ones' code... 
(modularized decomposition of the problem space is typically a much cleaner 
option, then followed by the use of vtables, ...).


or such...

On 09/ 7/10 09:50 AM, Eric Sosman wrote:
> On 9/6/2010 1:48 PM, James Dow Allen wrote:
>>
>> How about it? Anybody do this, or want to do it?
>> (There are examples of it *within* a buildable
>> library, but I'm talking about library source where
>> the user is encouraged to recompile a routine,
>> like qsort() but probably more complicated, using
>> his own application-specific header.)
>
> It's done occasionally. I've seen a sort implementation
> packaged as an #include file. You did something like
>
> #define SORT_NAME mySort
> #define SORT_TYPE struct frazzle
> #define SORT_COMP(s,t) strcmp((s).key, (t).key)
> #include "sort.h"
>
> .... and got a `void mySort(struct frazzle *data, size_t nitems)'
> function built for you. At a PPOE, a colleague put together a
> serialization library that worked similarly: You #define'd a
> bunch of stuff to describe the data structure you wanted to
> serialize, then you invoked a macro from his header to generate
> the actual code. So, variations on this theme are certainly
> playable.
>
> As to why they don't get more air time -- well, I'm sure
> there are lots of reasons. Lack of direct support from the tools
> that go along with the language has to be one of them: Lots of
> debuggers, for example, have trouble stepping from line to line
> through a function generated by a one-line macro invocation.
> Mistakes by the client/user may well elicit compiler diagnostics
> that are confusing at best, misleading at worst -- after the
> #include or whatever you get a cascade of syntax errors and no
> further clue. Testing becomes more laborious, because the innards
> of the "module" are exposed to the surrounding code rather than
> isolated from it, meaning that there are vastly more client/module
> interactions to worry about.

Based on my experience of the projects I've worked on in recent decades 
macro trickery has gone out of favour.  While a lot of these tracks can 
be done with with the preprocessor, it's much cleaner (from a tool and 
language support and maintenance perspective) to generate the code with 
a code generator.

> My (vague) understanding of C++ templates is that they're a
> kind of a way to regularize such an approach and give it some
> help from the language itself and its tool set. But lacking such
> support, the technique carries some disincentives that (it seems)
> outweigh many of its advantages in the estimation of the coders.

Indeed.  It is much easier to do something the language supports!

-- 
Ian Collins

I almost prefaced my message wtih a disclaimer
that SPEED WAS **NOT** MY CONCERN, but felt that a
simple speed-up case led to a clear example.
It seemed unnecessary -- I mention the point when
I mention speed.

But the only one to make a joke about the speed-up
was also the only one who grasped that speed
performance was not my primary concern!

On Sep 7, 4:50=A0am, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
> On 9/6/2010 1:48 PM, James Dow Allen wrote:
> > If the qsort() source were recompiled with the
> > application-dependent comparison etc. it would speed
> > up, perhaps by 25%.
>
> =A0 =A0 =A0Aside: Did you know that 84.6% of all stated percentages
> are made up out of thin air?

Aside:  Did you suspect that, although any speedup was peripheral
to my main point, I actually did the implied experiment,
using glibc's qsort source, with constanted num, size,
compare?  The element was
    struct { int a, key, c, d; }
Speedup was 25%.

> =A0 =A0 =A0A concrete example might be helpful here, despite
> the misgivings you state below. =A0In particular, I'd like
> to understand the "CAN'T BE USED AT ALL" part.

One example is hash-table management.  If space-efficiency
is important, low-level details essential to the table
handling will vary, while higher-level functionality
(collision handling, resizing) may be invariant.
If this isn't clear, note that a space-efficient table
may pack key AND payload into 2 or 3 bytes, while
off-the-shelf hashtables often dictate 12 bytes PLUS key.

Hash-tables are the one example most clear to me.
(I posted the idea several years ago, but discussion
was diverted solely to hash-tables, with no discussion
of the reusable source code concept.)

Another place where the concept might work nicely
(though I've not tried it) would be alpha-beta
game-tree solving.

> > How about it? =A0Anybody do this, or want to do it?
>
> =A0 =A0 =A0It's done occasionally....
>
> =A0 =A0 =A0As to why they don't get more air time -- well, I'm sure
> there are lots of reasons. =A0Lack of direct support from the tools
> that go along with the language has to be one of them: Lots of
> debuggers, for example, have trouble stepping from line to line
> through a function generated by a one-line macro invocation.
> Mistakes by the client/user may well elicit compiler diagnostics
> that are confusing at best, misleading at worst -- after the
> #include or whatever you get a cascade of syntax errors and no
> further clue. =A0Testing becomes more laborious, because the innards
> of the "module" are exposed to the surrounding code rather than
> isolated from it, meaning that there are vastly more client/module
> interactions to worry about.

I'm assuming the user is an expert programmer.

Please note that there are two quite distinct approaches:

(1) common source is in header, often in the form of
#define'd code fragments, and invoked by application
via macros.
(2) common source is in .c file, application-specific
stuff is presented to .c via user-specific .h defines.
The .c is compiled (with its user-specific header) and
then behaves just as an ordinary .c/.o.

I'm thinking of (2) specifically, but Eric's comments
apply mostly to (1).

James Dow Allen

On 09/ 7/10 03:05 PM, James Dow Allen wrote:
> On Sep 7, 4:50 am, Eric Sosman<esos...@ieee-dot-org.invalid>  wrote:
>>
>>       As to why they don't get more air time -- well, I'm sure
>> there are lots of reasons.  Lack of direct support from the tools
>> that go along with the language has to be one of them: Lots of
>> debuggers, for example, have trouble stepping from line to line
>> through a function generated by a one-line macro invocation.
>> Mistakes by the client/user may well elicit compiler diagnostics
>> that are confusing at best, misleading at worst -- after the
>> #include or whatever you get a cascade of syntax errors and no
>> further clue.  Testing becomes more laborious, because the innards
>> of the "module" are exposed to the surrounding code rather than
>> isolated from it, meaning that there are vastly more client/module
>> interactions to worry about.
>
> I'm assuming the user is an expert programmer.

What difference does that make?  Do experts not make mistakes?  Don't 
they test?

> Please note that there are two quite distinct approaches:
>
> (1) common source is in header, often in the form of
> #define'd code fragments, and invoked by application
> via macros.
> (2) common source is in .c file, application-specific
> stuff is presented to .c via user-specific .h defines.
> The .c is compiled (with its user-specific header) and
> then behaves just as an ordinary .c/.o.

How would you specialise a function like qsort using 2?

-- 
Ian Collins

On 06/09/2010 23:51, BGB / cr88192 wrote:
> "James Dow Allen" <jdallen2000@yahoo.com> wrote in message 
> news:1d233e49-8bb1-450c-8ac6-73e7294ce784@u4g2000prn.googlegroups.com...
>> Jacob's mention of his library reminds me of my own
>> suggestion to help with software reusability.
>>
>> Much software has the form
>>  High Level -- application-specific code
>>    Mid Level -- application-specific code
>>      Low Level -- FREQUENT FUNCTION, use library
>>
>> But often one encounters
>>  High Level -- application-specific code
>>    Mid Level -- FREQUENT FUNCTION
>>      Low Level -- application-specific code
>>
>> A familiar example where this form is encountered and
>> dealt with is qsort(), with the low-level handled
>> simply with a function pointer.
>>
>> If the qsort() source were recompiled with the
>> application-dependent comparison etc. it would speed
>> up, perhaps by 25%.  The qsort.c source wouldn't
>> even change; instead the variation would be provided
>> by a very simple application-dependent header included
>> by qsort.c.
>>
> 
> it is unlikely to be that large.
> 
> rarely do most micro-optimizations really effect that much, which is part of 
> why optimizations in optimizing compilers make notable alterations to the 
> structure typically for only modest speedups in most cases.

The generality of qsort comes at a high performance cost
in two areas
- the comparison thru a user-supplied function;
- the exchange.

The performance drop of library qsort versus a straight
equivalent specialized to the type sorted is usually way
*MORE* than 25%; I once tried and got a factor near 3
in a real case where I was sorting pointers to struct with
the sorting key a long, the first member of the struct.

Look at how your qsort performs the necessary exchange,
you'll probably be horrified by the complexity or/and
the lack of performance, unless qsort is defined inline
in <stdlib.h> (is that common ?), or the compiler/linker
is smarter than anything I own.

  Francois Grieu

On Sep 7, 10:22=A0am, Ian Collins <ian-n...@hotmail.com> wrote:
> On 09/ 7/10 03:05 PM, James Dow Allen wrote:
> > (2) common source is in .c file, application-specific
> > stuff is presented to .c via user-specific .h defines.
>
> How would you specialise a function like qsort using 2?

In OP, I already presented the #define COMP I used,
which is the only non-trivial part of the answer to your question.
Obviously it would have a struct declaration in scope.

You would also want
  #define QS_NAME SallySort /* or whatever */
And the .c would replace
   void qsort_variant(...)
with
   void QS_NAME(...)
so that you could use more than one instance of the
specialized qsort_variant() in a given executable.

But please remember:  Speeding up qsort() is not my
major purpose.  I used that as a simple well-known example.
My original purpose in the idea was to avoid rewriting
a hash-table manager even though all the low-level details changed.

James

"Francois Grieu" <fgrieu@gmail.com> wrote in message 
news:4c85b96b$0$20159$426a74cc@news.free.fr...
> On 06/09/2010 23:51, BGB / cr88192 wrote:
>> "James Dow Allen" <jdallen2000@yahoo.com> wrote in message
>> news:1d233e49-8bb1-450c-8ac6-73e7294ce784@u4g2000prn.googlegroups.com...
>>> Jacob's mention of his library reminds me of my own
>>> suggestion to help with software reusability.
>>>
>>> Much software has the form
>>>  High Level -- application-specific code
>>>    Mid Level -- application-specific code
>>>      Low Level -- FREQUENT FUNCTION, use library
>>>
>>> But often one encounters
>>>  High Level -- application-specific code
>>>    Mid Level -- FREQUENT FUNCTION
>>>      Low Level -- application-specific code
>>>
>>> A familiar example where this form is encountered and
>>> dealt with is qsort(), with the low-level handled
>>> simply with a function pointer.
>>>
>>> If the qsort() source were recompiled with the
>>> application-dependent comparison etc. it would speed
>>> up, perhaps by 25%.  The qsort.c source wouldn't
>>> even change; instead the variation would be provided
>>> by a very simple application-dependent header included
>>> by qsort.c.
>>>
>>
>> it is unlikely to be that large.
>>
>> rarely do most micro-optimizations really effect that much, which is part 
>> of
>> why optimizations in optimizing compilers make notable alterations to the
>> structure typically for only modest speedups in most cases.
>
> The generality of qsort comes at a high performance cost
> in two areas
> - the comparison thru a user-supplied function;
> - the exchange.
>
> The performance drop of library qsort versus a straight
> equivalent specialized to the type sorted is usually way
> *MORE* than 25%; I once tried and got a factor near 3
> in a real case where I was sorting pointers to struct with
> the sorting key a long, the first member of the struct.
>
> Look at how your qsort performs the necessary exchange,
> you'll probably be horrified by the complexity or/and
> the lack of performance, unless qsort is defined inline
> in <stdlib.h> (is that common ?), or the compiler/linker
> is smarter than anything I own.
>

interesting, I wouldn't have thought it would have been that large...

although, admittedly, if I do custom sorts, often I am lazy and just do 
bubble sort or selection sort, and usually only beat together a quicksort if 
I feel performance may be an issue...


>  Francois Grieu 

James Dow Allen <jdallen2000@yahoo.com> writes:

> On Sep 7, 10:22 am, Ian Collins <ian-n...@hotmail.com> wrote:
>> On 09/ 7/10 03:05 PM, James Dow Allen wrote:
>> > (2) common source is in .c file, application-specific
>> > stuff is presented to .c via user-specific .h defines.
>>
>> How would you specialise a function like qsort using 2?
>
> In OP, I already presented the #define COMP I used,
> which is the only non-trivial part of the answer to your question.
> Obviously it would have a struct declaration in scope.
>
> You would also want
>   #define QS_NAME SallySort /* or whatever */
> And the .c would replace
>    void qsort_variant(...)
> with
>    void QS_NAME(...)
> so that you could use more than one instance of the
> specialized qsort_variant() in a given executable.
>
> But please remember:  Speeding up qsort() is not my
> major purpose.  I used that as a simple well-known example.
> My original purpose in the idea was to avoid rewriting
> a hash-table manager even though all the low-level details changed.

I can see problems with (2) [a supplied .c file, a user created .h file
that contains the specific stuff, to generate a suitable .o that you link in]
in those circumstances when you want more than one sort (or whatever) in
your program.  You'll end up with sub-directories and fancy make files
(or whatever) as I can't see any way to have string_sort.c include
string_sort.h and integer_sort.c include integer_sort.h without hacking
on the .c files - in which case you don't need the .h files at all.

I can see times when you might want to do this, but I'm inclined to
agree with those who say that when you are getting to this complexity
it's often easy to move outside the C standard tools and generate code
in some other way.
-- 
Online waterways route planner            | http://canalplan.eu
Plan trips, see photos, check facilities  | http://canalplan.org.uk

On Sep 6, 8:48=A0pm, James Dow Allen <jdallen2...@yahoo.com> wrote:
>
> But often one encounters
> =A0 High Level -- application-specific code
> =A0 =A0 Mid Level -- FREQUENT FUNCTION
> =A0 =A0 =A0 Low Level -- application-specific code
>
Function pointers are one answer.

Another answer is "boilerplate" code. You do this every time you write
a new small program for Windows - you take the standard startup and
message pump routines, and then add in calls to your own program-
specific code.

On Sep 7, 1:17=A0pm, Nick <3-nos...@temporary-address.org.uk> wrote:
> You'll end up with sub-directories and fancy make files

  sallysort.o:  sallysort.c
       rm qspecif.h
       ln sallysort.h qspecif.h
       cc -O -c -o sallysort.o qvariant.c
Much simpler than many makefiles.

> I can see times when you might want to do this, but I'm inclined to
> agree with those who say that when you are getting to this complexity
> it's often easy to move outside the C standard tools and generate code
> in some other way.

No.  I've posted code to demonstrate the contrary.
Might post again if I get an indication anyone knows what
I'm talking about.

Hope this helps.
James

On Sep 7, 2:25=A0pm, James Dow Allen <jdallen2...@yahoo.com> wrote:
> =A0 sallysort.o: =A0sallysort.c

sed ss/c/h/

On 09/ 7/10 04:35 PM, James Dow Allen wrote:
> On Sep 7, 10:22 am, Ian Collins<ian-n...@hotmail.com>  wrote:
>> On 09/ 7/10 03:05 PM, James Dow Allen wrote:
>>> (2) common source is in .c file, application-specific
>>> stuff is presented to .c via user-specific .h defines.
>>
>> How would you specialise a function like qsort using 2?
>
> In OP, I already presented the #define COMP I used,
> which is the only non-trivial part of the answer to your question.
> Obviously it would have a struct declaration in scope.
>
> You would also want
>    #define QS_NAME SallySort /* or whatever */
> And the .c would replace
>     void qsort_variant(...)
> with
>     void QS_NAME(...)
> so that you could use more than one instance of the
> specialized qsort_variant() in a given executable.

I still think you are better off generating code another way.  Certainly 
if I find I need something repeated that's almost, but not quite the 
same as something else I'll write some code to write the code.  Although 
I must admit I frequently use a code generator that emits macros to 
generate code (test stubs)!

> But please remember:  Speeding up qsort() is not my
> major purpose.  I used that as a simple well-known example.
> My original purpose in the idea was to avoid rewriting
> a hash-table manager even though all the low-level details changed.

That sound like a great candidate for code generation.

-- 
Ian Collins

Tom St Denis <tom@iahu.ca> writes:

> On Sep 6, 3:57 pm, gaze...@shell.xmission.com (Kenny McCormack) wrote:
>> In article <201d0119-1080-41b4-bdf7-bd6355533...@b4g2000pra.googlegroups.com>,
>> James Dow Allen  <jdallen2...@yahoo.com> wrote:
>>
>>
>>
>> >On Sep 7, 1:17 am, Shao Miller <sha0.mil...@gmail.com> wrote:
>> >> I read your post twice but had a little trouble following it.  That's my
>> >> problem so I'd like to ask for clarification, please: Are you asking if
>> >> there's a common way to override library routines with one's own code?
>> >> Are you asking if there ought to be a common way?
>>
>> >You're trying to find my QUESTION.  My post isn't
>> >a question; it's a RECOMMENDATION.
>>
>> >I'm not asking HOW to do what I describe.  That's easy.
>> >I already do it in some of my own source code.
>>
>> >What I AM asking is: Why aren't the rest of you doing this?
>> >  :-)
>>
>> >Hope this clarifies.
>> >James
>>
>> Those kinds of posts don't fly well in newsgroups like this.
>>
>> Once you deviate from:
>>
>>     Student: Oh master, oh holy of holies, how do I do X?  (And what is
>>     wrong with the way a poor wretch like me is doing it?)
>>
>>     Master: You are subhuman slime, but I shall deign to answer thee.
>>
>> the newsgroup falls off the rails.  Sad, but true.
>
> usually when a newb comes into a group [any group] and says things
> like "why not we do everything while standing on our heads?" it's
> because they don't know what they're talking about.

His suggestions didnt sound too nOObish to me.

>
> This doesn't mean we don't listen to the newbs, it just means we don't
> follow them.  It's not our fault you can't tell the difference.


Who is "we"?

I can see you've been left to run around establishing your "reg"
credentials for a little too long...

When we see that, we tend to react ;)

I really should *not* post when I'm feeling
irritated.  But ... whatever!  :-)

On Sep 7, 3:31 am, Tom St Denis <t...@iahu.ca> wrote:
> usually when a newb comes into a group [any group] and says things
> like "why not we do everything while standing on our heads?" it's
> because they don't know what they're talking about.

I don't want to brag about creeping senility, but
I've been a professional programmer since before many
or most of you were BORN.  I've consulted for over a dozen
companies, written OS'es, the world's fastest Jpeg, etc.,
earned enough to retire early and happily.  There's a good
chance that somewhere in your house right now there is a
chip whose hardware algorithm or firmware was designed by me.

But whatever.

> As to the specifics here, the solution to the OPs problem is called a
> "processor cache" and "stack opcode optimizations" [something modern
> high performance processors have] making the need to inline your
> compare function rather moot.

I specifically said speed performance was not my main
motive.  Some should spend less time flaunting their
arrogance and actually reading the posts they respond to.

But whatever.

Incidentally, your comments about qsort's compare
performance display surprising ignorance.

But whatever.

> Also, sometimes paying a small penalty in performance to make
> something 100x generic/scalable is worth it in the end.  I'd rather
> have a standard generic qsort() like in the C lib than a 100 different
> ones for all sorts of different data types.

I outlined an approach to "have your cake and eat it too"
on this *precise* issue -- except that source simplicity
and maintainability is my goal -- not speed.
Obviously I must have articulated it poorly.  :-)
Still, it strikes me as odd that with the specifics I
gave, a competent programmer couldn't understand the point.

But whatever.

On Sep 7, 1:17 pm, Nick <3-nos...@temporary-address.org.uk> wrote:
> I can see problems ... You'll end up with sub-directories and
> fancy make files ...

If you actually need more than one instance of any of these
"reusable source code modules" in the same directory
(and this is relatively unlikely), then you can solve the
problem with a single line in the makefile:
    ln -f sallysort.h qspecific.h

The result is a very simple system, with the "reusable
source module" eventually requiring ZERO further modifications.
All variations are encapsulated in the .h interface.

But whatever.

On Sep 7, 4:51 am, "BGB / cr88192" <cr88...@hotmail.com> wrote:
> it is unlikely to be that large.
>
> rarely do most micro-optimizations really effect that much, which is part=
 of
> why optimizations in optimizing compilers make notable alterations to the
> structure typically for only modest speedups in most cases.

One needn't be a qsort() internals man to understand it spends
its time doing swaps (which will have either variable or
fixed total size depending on whether the suggestion is adopted)
and calling (*cmp)().  One doesn't have to be a compiler
expert to know that inlining doesn't affect pre-compiled
object files.  One doesn't need to run a profiler to guess that
the described speed boost in qsort() will be significant.  And
one doesn't have to be an algorithm complexity expert to know
that very many otherwise O(n) procedures are
dominated by O(n log n) sort.

*And especially*, one doesn't need expertise in English grammar to
read OP and see qsort() was chosen only as a simple example,
and that any question of speed performance was disclaimed.

But whatever.

On Sep 7, 1:22=A0pm, Malcolm McLean <malcolm.mcle...@btinternet.com>
wrote:
> On Sep 6, 8:48=A0pm, James Dow Allen <jdallen2...@yahoo.com> wrote:
>
> > But often one encounters
> > =A0 High Level -- application-specific code
> > =A0 =A0 Mid Level -- FREQUENT FUNCTION
> > =A0 =A0 =A0 Low Level -- application-specific code

> Another answer is "boilerplate" code. You do this every time you write
> a new small program for Windows - you take the standard startup and
> message pump routines, and then add in calls to your own program-
> specific code.

I added the otherwise-irrelevant "High-level application",
placing FREQUENT FUNCTION at mid-level *precisely* to avoid
this digression.

But whatever.

Thanks to all for the oh-so-careful attention!  :-)
James Dow Allen

James Dow Allen wrote:
> On Sep 7, 1:17 pm, Nick <3-nos...@temporary-address.org.uk> wrote:
>> You'll end up with sub-directories and fancy make files
> 
>   sallysort.o:  sallysort.c
>        rm qspecif.h
>        ln sallysort.h qspecif.h
>        cc -O -c -o sallysort.o qvariant.c
> Much simpler than many makefiles.

Well yes, but you won't be able to run a parallel make if there are 
several instances of qvariant. I think it would be better to use an 
instance-specific subdirectory, say sallysort/qspecif.h, and a -I option 
on the "cc".

Alternatively, use a macro processor (perhaps even the C preprocessor) 
to generate sallysort.c from qvariant.c and sallysort.h, then compile.

That said, I do think that James' suggestion can be useful to configure 
and reuse C source code, or code in other languages (where it may be 
necessary to separate the macro expansion step from the compilation step).

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

On Sep 6, 5:29=A0pm, gaze...@shell.xmission.com (Kenny McCormack) wrote:
> In article <a1f0d42a-a83f-4df1-9e92-7f2721b55...@i31g2000yqm.googlegroups=
..com>,
> Tom St Denis =A0<t...@iahu.ca> wrote:
> ...
>
> >usually when a newb comes into a group [any group] and says things
> >like "why not we do everything while standing on our heads?" it's
> >because they don't know what they're talking about.
>
> Yup. =A0James Dow Allen is a newb here. =A0Never seen him post before, no
> siree! =A0He's got some nerve comin' in here and stirin' things up!
>
> Thanks for proving my point.

If you had actually read what I wrote, I said we [most regulars]
**DO** read what they write.  We just don't have to agree with it
because you say so.

That's how civil discussions work.  Everyone gets a turn a the
microphone but at the end of the day we don't have to keep listening
[or follow whatever they say].

Tom

On Sep 7, 4:22=A0am, Richard <rgrd...@gmail.com> wrote:
> Tom St Denis <t...@iahu.ca> writes:
>
>
>
>
>
> > On Sep 6, 3:57=A0pm, gaze...@shell.xmission.com (Kenny McCormack) wrote=
:
> >> In article <201d0119-1080-41b4-bdf7-bd6355533...@b4g2000pra.googlegrou=
ps.com>,
> >> James Dow Allen =A0<jdallen2...@yahoo.com> wrote:
>
> >> >On Sep 7, 1:17=A0am, Shao Miller <sha0.mil...@gmail.com> wrote:
> >> >> I read your post twice but had a little trouble following it. =A0Th=
at's my
> >> >> problem so I'd like to ask for clarification, please: Are you askin=
g if
> >> >> there's a common way to override library routines with one's own co=
de?
> >> >> Are you asking if there ought to be a common way?
>
> >> >You're trying to find my QUESTION. =A0My post isn't
> >> >a question; it's a RECOMMENDATION.
>
> >> >I'm not asking HOW to do what I describe. =A0That's easy.
> >> >I already do it in some of my own source code.
>
> >> >What I AM asking is: Why aren't the rest of you doing this?
> >> > =A0:-)
>
> >> >Hope this clarifies.
> >> >James
>
> >> Those kinds of posts don't fly well in newsgroups like this.
>
> >> Once you deviate from:
>
> >> =A0 =A0 Student: Oh master, oh holy of holies, how do I do X? =A0(And =
what is
> >> =A0 =A0 wrong with the way a poor wretch like me is doing it?)
>
> >> =A0 =A0 Master: You are subhuman slime, but I shall deign to answer th=
ee.
>
> >> the newsgroup falls off the rails. =A0Sad, but true.
>
> > usually when a newb comes into a group [any group] and says things
> > like "why not we do everything while standing on our heads?" it's
> > because they don't know what they're talking about.
>
> His suggestions didnt sound too nOObish to me.
>
>
>
> > This doesn't mean we don't listen to the newbs, it just means we don't
> > follow them. =A0It's not our fault you can't tell the difference.
>
> Who is "we"?
>
> I can see you've been left to run around establishing your "reg"
> credentials for a little too long...

I've been an on-and-off poster for a long time.

What I don't get about you trolls is why you think there is a
hierarchy here.  There isn't.  I consider a few people here more
knowledgeable about the ISO C spec than myself but it's not like I pay
homage to them or something, or seek their approval or whatever.

All I was saying is out of a matter of respect we [general mob here]
tend to give new [and often incorrect] posters their due attention.
But doesn't mean we agree with it.  So when someone comes around
trying to "radically alter our software paradigms" we listen, but if
they don't offer anything useful we file it away and don't act on it.

I for one, will keep developing against the standard C and POSIX.1
libraries since for industry they tend to work just fine.  Even
though, for instance, I'm not going to use Navia's code doesn't mean I
think he shouldn't be able to post about it [note: I'm not judging the
quality of his project, I just don't want to use it is all].

The trolls here tend to think there is some sort of hierarchy and
unwritten rule, that if you're not a member of the club you get the
raw end of the deal.  The reality is people who they think "aren't in
the club" then to be students/newbs coming around and asking
questions.  They get schooled [more often than naught fairly politely
I might add] which then infuriates the trolls because how dare there
be disagreement!!!

You trolls really, really, really need to get a life.  Look at what
you're doing.  You're trolling "computers languages C" ... can you get
any nerdier and less useful than that?  For all that is decent in this
world, seriously, go outside.

Tom

In article <16bfb267-4beb-4519-bfc9-e37635fd3467@m15g2000yqm.googlegroups.com>,
Tom St Denis  <tom@iahu.ca> wrote:
>On Sep 6, 5:29�pm, gaze...@shell.xmission.com (Kenny McCormack) wrote:
>> In article
><a1f0d42a-a83f-4df1-9e92-7f2721b55...@i31g2000yqm.googlegroups.com>,
>> Tom St Denis �<t...@iahu.ca> wrote:
>> ...
>>
>> >usually when a newb comes into a group [any group] and says things
>> >like "why not we do everything while standing on our heads?" it's
>> >because they don't know what they're talking about.
>>
>> Yup. �James Dow Allen is a newb here. �Never seen him post before, no
>> siree! �He's got some nerve comin' in here and stirin' things up!
>>
>> Thanks for proving my point.
>
>If you had actually read what I wrote, I said we [most regulars]
>**DO** read what they write.  We just don't have to agree with it
>because you say so.

There is no "we".

There is no committee.

There is no organization.

There is no central authority.

There is no funding body.

-- 
> No, I haven't, that's why I'm asking questions. If you won't help me,
> why don't you just go find your lost manhood elsewhere.

CLC in a nutshell.

On Sep 7, 7:46=A0am, gaze...@shell.xmission.com (Kenny McCormack) wrote:
> There is no "we".
>
> There is no committee.
>
> There is no organization.
>
> There is no central authority.
>
> There is no funding body.

There are regulars, and regular trolls [e.g., you].

Also I have to question what you think you're fighting against.  I
pity thee.

Tom

Tom St Denis <tom@iahu.ca> writes:

> On Sep 7, 7:46 am, gaze...@shell.xmission.com (Kenny McCormack) wrote:
>> There is no "we".
>>
>> There is no committee.
>>
>> There is no organization.
>>
>> There is no central authority.
>>
>> There is no funding body.
>
> There are regulars, and regular trolls [e.g., you].
>
> Also I have to question what you think you're fighting against.  I
> pity thee.
>
> Tom

Could it be your withering put down of James' posts and an attempt to
belittle him?

In case you forgot what you said in reply here it is in all its "regs"
glory:-

,----
| usually when a newb comes into a group [any group] and says things
| like "why not we do everything while standing on our heads?" it's
| because they don't know what they're talking about.
| 
| This doesn't mean we don't listen to the newbs, it just means we don't
| follow them.  It's not our fault you can't tell the difference.
`----

and as for this nonsense :-

,----
| Also, sometimes paying a small penalty in performance to make
| something 100x generic/scalable is worth it in the end.  I'd rather
| have a standard generic qsort() like in the C lib than a 100 different
| ones for all sorts of different data types.
`----

Pfft. People C for efficiency. And if someone is using C to implement
something which talks to HW and they want every cpu cycle to count then
a specific processor version is EXACTLY what they want. Since there is
probably about, err, ONE (maybe 2..) CPU *most* people code for, your
concerns are neither here not there. And how to meet these type of
issues is WHY this group is here.

-- 
"Avoid hyperbole at all costs, its the most destructive argument on
the planet" - Mark McIntyre in comp.lang.c

In article <i65emt$d1v$1@news.eternal-september.org>,
Richard  <rgrdev_@gmail.com> wrote:
....
>Could it be your withering put down of James' posts and an attempt to
>belittle him?

Well, yeah, there was that.  But, like with Republicans, it's always:
Don't look there.  Look over here.  Don't look at that!

>In case you forgot what you said in reply here it is in all its "regs"
>glory:-
>
>,----
>| usually when a newb comes into a group [any group] and says things
>| like "why not we do everything while standing on our heads?" it's
>| because they don't know what they're talking about.
>| 
>| This doesn't mean we don't listen to the newbs, it just means we don't
>| follow them.  It's not our fault you can't tell the difference.
>`----

Indeed.  Frankly, I was *amazed* at the extent to which TSD stepped in shit
with that comment.

>and as for this nonsense :-
>
>,----
>| Also, sometimes paying a small penalty in performance to make
>| something 100x generic/scalable is worth it in the end.  I'd rather
>| have a standard generic qsort() like in the C lib than a 100 different
>| ones for all sorts of different data types.
>`----

Yup.  Toeing the party line.

-- 
"The anti-regulation business ethos is based on the charmingly naive notion
that people will not do unspeakable things for money." - Dana Carpender

Quoted by Paul Ciszek (pciszek at panix dot com).  But what I want to know
is why is this diet/low-carb food author doing making pithy political/economic
statements?

Nevertheless, the above quote is dead-on, because, the thing is - business
in one breath tells us they don't need to be regulated (which is to say:
that they can morally self-regulate), then in the next breath tells us that
corporations are amoral entities which have no obligations to anyone except
their officers and shareholders, then in the next breath they tell us they
don't need to be regulated (that they can morally self-regulate) ...

On Sep 7, 9:29=A0am, Richard <rgrd...@gmail.com> wrote:
> Could it be your withering put down of James' posts and an attempt to
> belittle him?

My reply was to Kenny not James.

> In case you forgot what you said in reply here it is in all its "regs"
> glory:-
>
> ,----
> | usually when a newb comes into a group [any group] and says things
> | like "why not we do everything while standing on our heads?" it's
> | because they don't know what they're talking about.
> |
> | This doesn't mean we don't listen to the newbs, it just means we don't
> | follow them. =A0It's not our fault you can't tell the difference.
> `----

If they can't have some humility it's not my fault.  All I'm saying
here is I listen to people even if I don't agree with them.  Calling a
novice a "newb" isn't derogatory.  It's just a way of saying someone
who doesn't know what they're doing [yet].  And despite what you're
trying to read into this I'm not trying to silence or humiliate
anyone.

> ,----
> | Also, sometimes paying a small penalty in performance to make
> | something 100x generic/scalable is worth it in the end. =A0I'd rather
> | have a standard generic qsort() like in the C lib than a 100 different
> | ones for all sorts of different data types.
> `----
>
> Pfft. People C for efficiency. And if someone is using C to implement
> something which talks to HW and they want every cpu cycle to count then
> a specific processor version is EXACTLY what they want. Since there is
> probably about, err, ONE (maybe 2..) CPU *most* people code for, your
> concerns are neither here not there. And how to meet these type of
> issues is WHY this group is here.

Ok, stop reading into it.  I never said finding ways to optimize the
standard C library is off topic nor un-interesting.  All I said is
that under most circumstances I'd rather have standard portable code,
even if it's marginally slower, than highly platform specific [or
bloated] code.  Not everyone calling qsort() is doing so on a time-
critical operations.  And I'd rather have developers use qsort() for
their fallback sorting than rolling their own [and most likely getting
it wrong].

In this particular case I disagree.  I think the callback method that
qsort uses is fine enough for most purposes.  In highly time sensitive
operations qsort() might not even be the most optimal solution anyways
[regardless of whether your compare function is inlined or not].  So
premature optimization [re: making the 100s of qsort variants part of
the C standard] is a bad idea.

Tom

On Sep 7, 9:54=A0am, gaze...@shell.xmission.com (Kenny McCormack) wrote:
> >Could it be your withering put down of James' posts and an attempt to
> >belittle him?
>
> Well, yeah, there was that. =A0But, like with Republicans, it's always:
> Don't look there. =A0Look over here. =A0Don't look at that!

Except my reply was to you not James.  Do you even read your own
posts?

> Indeed. =A0Frankly, I was *amazed* at the extent to which TSD stepped in =
shit
> with that comment.

If that's stepping in shit ... Wow.

I guess you take all of your life advice from 4 yr olds too right?

You:  "Son, what should we have for dinner?"
Son:  "An entire bowl of ice cream and skittles!"
You:  "I listen to everyone egalitarian-like therefore ice cream and
skittles for dinner!"

Sounds about right.

So let me get this right, in your world I should follow the advice of
EVERYONE who is capable of posting to usenet?

> Yup. =A0Toeing the party line.

If by party line you mean that of people who "write software for a
living" then sure.  I guess I am.

Tom

On Sep 7, 4:29=A0pm, Richard <rgrd...@gmail.com> wrote:
> Tom St Denis <t...@iahu.ca> writes:
>=A0I'd rather
> | have a standard generic qsort() like in the C lib than a 100 different
> | ones for all sorts of different data types.
> `----
>
> Pfft. People C for efficiency. And if someone is using C to implement
> something which talks to HW and they want every cpu cycle to count then
> a specific processor version is EXACTLY what they want. Since there is
> probably about, err, ONE (maybe 2..) CPU *most* people code for, your
> concerns are neither here not there. And how to meet these type of
> issues is WHY this group is here.
>
Generally you want to put the program together as quickly as possible
to prove that it works, does what the client wants, doesn't have
homunculi in the requirements specification, and so on. That means
plugging most of it together from standard parts.

Then it's very rare for every CPU cycle to count. Usually there are
ten or twenty of them in functions which are called once, as opposed
to several billion in functions in deep loops. So you focus
optimisation efforts on the loops. That's the point at which a call to
qsort() might be replaced with a hand-coded routine. Often there's
algorithmic improvement as well as micro-optimisation. Say, for
instnace, we have a camera moving slowly though a scene,, and we want
to sort the ploygons by depth. The vast majority of polygons won't
move from frame to frame, and those that do can only move a few
places. So we can store the results of the previous sort and use a
bubblesort. Whilst we're at it we can replace the byte copying loop in
qsort with a clean swap of pointers and fold in the indirected call to
the comparision function.

On Sep 7, 10:38=A0am, Malcolm McLean <malcolm.mcle...@btinternet.com>
wrote:
> On Sep 7, 4:29=A0pm, Richard <rgrd...@gmail.com> wrote:> Tom St Denis <t.=
...@iahu.ca> writes:
> >=A0I'd rather
> > | have a standard generic qsort() like in the C lib than a 100 differen=
t
> > | ones for all sorts of different data types.
> > `----
>
> > Pfft. People C for efficiency. And if someone is using C to implement
> > something which talks to HW and they want every cpu cycle to count then
> > a specific processor version is EXACTLY what they want. Since there is
> > probably about, err, ONE (maybe 2..) CPU *most* people code for, your
> > concerns are neither here not there. And how to meet these type of
> > issues is WHY this group is here.
>
> Generally you want to put the program together as quickly as possible
> to prove that it works, does what the client wants, doesn't have
> homunculi in the requirements specification, and so on. That means
> plugging most of it together from standard parts.
>
> Then it's very rare for every CPU cycle to count. Usually there are
> ten or twenty of them in functions which are called once, as opposed
> to several billion in functions in deep loops. So you focus
> optimisation efforts on the loops. That's the point at which a call to
> qsort() might be replaced with a hand-coded routine. Often there's
> algorithmic improvement as well as micro-optimisation. Say, for
> instnace, we have a camera moving slowly though a scene,, and we want
> to sort the ploygons by depth. The vast majority of polygons won't
> move from frame to frame, and those that do can only move a few
> places. So we can store the results of the previous sort and use a
> bubblesort. Whilst we're at it we can replace the byte copying loop in
> qsort with a clean swap of pointers and fold in the indirected call to
> the comparision function.

Agreed, though to clarify in context of my OP...

I didn't mean that discussion about optimized qsort instances is a bad
idea.  I just meant that I wouldn't prefer that the standard C library
had 100s of qsort functions for every possible data type/structure.
That in many cases it's more worthwhile to build out of portable
constructs than fast ones.

Reminds me a bit of some work I did at a company a few years back
where their server would launch a daemon process that would prevent
multiple instances of services from running.  To do this they attached
an ID to every service (at this point they only had one) and would
check that the ID doesn't exist before launching.

Sounds simple.  Effective and gets the job done.

That is until a recent masters grad showed up, re-wrote the function
using a hash table which used inline assembler to perform a UMAC and a
C++ template to perform the hashing (they only ever instantiated the
class once with a single type).  Not only was it incredible overkill
for a function that even if written with a linear search would take
less than a millisecond, but their assembler code was incorrect AND
produced different results with GCC [they used ICC at the time].
Because of such simple task, "check if application already running",
being optimized so fool-heartedly the porting effort to GCC was
stalled by weeks [to figure out why the hell the service would fail to
load].

Anyways, optimization is a good idea, it just can't be done a priori
which is what a standard C library is.

On Sep 7, 4:51 am, "BGB / cr88192" <cr88...@hotmail.com> wrote:
> it is unlikely to be that large.
>
> rarely do most micro-optimizations really effect that much, which is part 
> of
> why optimizations in optimizing compilers make notable alterations to the
> structure typically for only modest speedups in most cases.

<--
One needn't be a qsort() internals man to understand it spends
its time doing swaps (which will have either variable or
fixed total size depending on whether the suggestion is adopted)
and calling (*cmp)().  One doesn't have to be a compiler
expert to know that inlining doesn't affect pre-compiled
object files.  One doesn't need to run a profiler to guess that
the described speed boost in qsort() will be significant.  And
one doesn't have to be an algorithm complexity expert to know
that very many otherwise O(n) procedures are
dominated by O(n log n) sort.

*And especially*, one doesn't need expertise in English grammar to
read OP and see qsort() was chosen only as a simple example,
and that any question of speed performance was disclaimed.

But whatever.
-->


admittedly, I had underestimated the time cost of qsort it seems, fair 
enough, I don't really tend to use it anyways...

but, in my general experience, inlining vs not inlining rarely seems to make 
much difference to overall performance, as IME, things like "if" and 
"switch" tend to be the main time wasters (going by profilers and other 
things), as in tight loops, there is often a big pile of timer samples or 
similar piled up around either the conditional jump or the instructions just 
following it or its target.

the cost of a call tends to largely fade away IME...

although, admittedly, I haven't really tried profiling tight loops of calls 
through function pointers, as maybe this is more expensive than a direct 
call via a "call" instruction...

hell, I have not even observed much of a notable speed difference between 
memory copies using SIMD vectors and memory copies using "rep movsb" and 
similar (it seems like the difference should be drastic, but it seems to go 
extra fast somehow...).


similarly, turning on optimizations (to usually high settings) often only 
seems to result in a 25%-50% speedup in my experience (at least with MSVC, 
with GCC it is often closer to 75%-150% IME).


part may be due to coding style though:
I tend to fairly rarely use leaf functions, as most logic tends to be 
contained in functions which call other functions (I have large numbers of 
functions which often only contain maybe 2-3 LOC, and an average case is <15 
loc, and others which serve essentially as trampolines...).

basically, I have a special style for these 1-line trampolines:
int foo(int x)
    { return(bar(x, 0)); }
where otherwise it would take 2 more lines...


also vtable structures, ... are not exactly rare either, and in many cases, 
make use of dynamic typing (implemented via API calls, ...).


but, anyways, besides speed, I have tried using preprocessor based 
templating before, but ran into problems with the limitations of the C 
preprocessor (actually, most notably, with MSVC's preprocessor, and my 
understanding of what the C99 spec says it should do, but maybe I 
misinterpret, I don't know...). so, I had ended up needing a secondary 
preprocessor which was capable of more powerful macro expansions.

"generic" logic is more often pulled off by passing functions complex types 
or vtables (typically a struct full of function pointers or similar...). 
often, these structs/vtables are wrapped, such that they look more like 
ordinary function calls, and so can abstract the internal vtable away from 
the client.


for example:
void fooDoSomething(fooHandle obj)
    { ((fooObjectType)obj)->vtable->DoSomething((fooObjectType)obj); }

similar has been used to deal with interfacing between statically compiled 
code and VM-managed code, and also to provide a nicer looking API for COM 
bindings, ...

or such...

gazelle@shell.xmission.com (Kenny McCormack) writes:

> In article <i65emt$d1v$1@news.eternal-september.org>,
> Richard  <rgrdev_@gmail.com> wrote:
> ...
>>Could it be your withering put down of James' posts and an attempt to
>>belittle him?
>
> Well, yeah, there was that.  But, like with Republicans, it's always:
> Don't look there.  Look over here.  Don't look at that!

Standard practice.

>
>>In case you forgot what you said in reply here it is in all its "regs"
>>glory:-
>>
>>,----
>>| usually when a newb comes into a group [any group] and says things
>>| like "why not we do everything while standing on our heads?" it's
>>| because they don't know what they're talking about.
>>| 
>>| This doesn't mean we don't listen to the newbs, it just means we don't
>>| follow them.  It's not our fault you can't tell the difference.
>>`----
>
> Indeed.  Frankly, I was *amazed* at the extent to which TSD stepped in shit
> with that comment.

I wasn't. Been there before with The Saint. As I mentioned before, some
"regs", when allowed to run wild and unchecked, simply become a God in
their own small Universe. NK telling people to "slow down" and "think
about it a minute" is another example albeit not quite so repugnant as
this case. I blame you for not nipping it in the bud ....

>
>>and as for this nonsense :-
>>
>>,----
>>| Also, sometimes paying a small penalty in performance to make
>>| something 100x generic/scalable is worth it in the end.  I'd rather
>>| have a standard generic qsort() like in the C lib than a 100 different
>>| ones for all sorts of different data types.
>>`----
>
> Yup.  Toeing the party line.

What next? "Dont consider performance until its done" or "I prefer to
read 50,000,000 lines of c code on paper than set a simple HW breakpoint
because Brian Kernighan once said, on his single man 100 line project,
that debugging is twice as hard as getting it right in the first
place". Pfft. PS where's the boss? Havent seen any RH posts.


-- 
"Avoid hyperbole at all costs, its the most destructive argument on
the planet" - Mark McIntyre in comp.lang.c

On Sep 7, 11:26=A0am, Richard <rgrd...@gmail.com> wrote:
> gaze...@shell.xmission.com (Kenny McCormack) writes:
> > In article <i65emt$d1...@news.eternal-september.org>,
> > Richard =A0<rgrd...@gmail.com> wrote:
> > ...
> >>Could it be your withering put down of James' posts and an attempt to
> >>belittle him?
>
> > Well, yeah, there was that. =A0But, like with Republicans, it's always:
> > Don't look there. =A0Look over here. =A0Don't look at that!
>
> Standard practice.
>
>
>
> >>In case you forgot what you said in reply here it is in all its "regs"
> >>glory:-
>
> >>,----
> >>| usually when a newb comes into a group [any group] and says things
> >>| like "why not we do everything while standing on our heads?" it's
> >>| because they don't know what they're talking about.
> >>|
> >>| This doesn't mean we don't listen to the newbs, it just means we don'=
t
> >>| follow them. =A0It's not our fault you can't tell the difference.
> >>`----
>
> > Indeed. =A0Frankly, I was *amazed* at the extent to which TSD stepped i=
n shit
> > with that comment.
>
> I wasn't. Been there before with The Saint. As I mentioned before, some
> "regs", when allowed to run wild and unchecked, simply become a God in
> their own small Universe. NK telling people to "slow down" and "think
> about it a minute" is another example albeit not quite so repugnant as
> this case. I blame you for not nipping it in the bud ....

Are you guys just filling in the other side of the conversation?  I
guess I'm not needed in this thread.

> What next? "Dont consider performance until its done" or "I prefer to
> read 50,000,000 lines of c code on paper than set a simple HW breakpoint
> because Brian Kernighan once said, on his single man 100 line project,
> that debugging is twice as hard as getting it right in the first
> place". Pfft. PS where's the boss? Havent seen any RH posts.

Yup, it follows from my comment about writing portable code that I
don't use debuggers ...

Anyways, since you guys are just inventing the conversation this is my
last post in this thread.

Tom

On 2010-09-07, Tom St Denis <tom@iahu.ca> wrote:
> On Sep 7, 11:26?am, Richard <rgrd...@gmail.com> wrote:
>> gaze...@shell.xmission.com (Kenny McCormack) writes:

> Anyways, since you guys are just inventing the conversation this is my
> last post in this thread.

I take it you've never encountered "Kenny" and "Richard Nolastname" before?
They're regular trolls.  Kenny's particularly proud of the fact that he
cannot conceive of any activity which is not primarily focused on achieving
social status, and holds engineers who try to make things work even if it
makes them look bad in utter contempt.

-s
-- 
Copyright 2010, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.

"Richard" <rgrdev_@gmail.com> ha scritto nel messaggio
news:i65lii$fb8$2@news.eternal-september.org...
> What next? "Dont consider performance until its done" or "I prefer to
> read 50,000,000 lines of c code on paper than set a simple HW breakpoint
> because Brian Kernighan once said, on his single man 100 line project,
> that debugging is twice as hard as getting it right in the first
> place". Pfft. PS where's the boss? Havent seen any RH posts.

pheraps Brian Kernighan not do errors
but for me that doing errors debugging is right not only because resolve
problem in bug, but too for understand the code:
if there is some code i not understand 100% i go to debug it

"James Dow Allen" <jdallen2000@yahoo.com> ha scritto nel messaggio
news:1d233e49-8bb1-450c-8ac6-73e7294ce784@u4g2000prn.googlegroups.com...
> Jacob's mention of his library reminds me of my own
> suggestion to help with software reusability.
>
> Much software has the form
>  High Level -- application-specific code
>    Mid Level -- application-specific code
>      Low Level -- FREQUENT FUNCTION, use library

what does it mean "High Level"?
is it mean one High Level language?

> But often one encounters
>  High Level -- application-specific code
>    Mid Level -- FREQUENT FUNCTION
>      Low Level -- application-specific code


> A familiar example where this form is encountered and
> dealt with is qsort(), with the low-level handled
> simply with a function pointer.
>
> If the qsort() source were recompiled with the
> application-dependent comparison etc. it would speed
> up, perhaps by 25%.  The qsort.c source wouldn't
> even change; instead the variation would be provided
> by a very simple application-dependent header included
> by qsort.c.
>
> For example, make this definition:
>  #define COMP(x,y)      \
>     (((struct elem *)x)->key - ((struct elem *)y)->key)
> visible to qsort.c, rather than just pass a pointer
> to the function
>  int ecomp(const void *x, const void *y)
>  { return COMP(x,y); }

for me the only right define are
#define  name  number
#define  name  nameTooThatIsOneNumber
because it is not easy to follow in a debugger
some other defines

> I mention this simple case to make the idea clear,
> but if all I wanted to do is speed-up qsort() by 25%
> I wouldn't be posting this.  Instead I'm thinking
> of cases where the common function CAN'T BE USED
> AT ALL, without this flexibility.

and where came from that 25%?
i think general
qsort can be fast if using the right pointers
in the right places as args

> In these interesting cases, the application-dependent
> variations are much too complicated to be represented
> with a few function arguments, but a common source
> code could still be used, with any variations
> coming from #define's in an application-dependent header.
> (I have specific examples in mind, but won't mention
> them.  I want to focus on the idea of reusing
> source code in the way I imply, rather than any
> specific example.)

i'm nobody but i not agree, when i meet some define
with macro parameters in C i begin to not understand

> How about it?  Anybody do this, or want to do it?

i use pointers in my library qsort function
but not have used it much

the last qsort i wrote is for order element in a
buffer of 64 bits, each elment is one array of 5bit
the buffer has the first 4 bits element that
say how many element the array has
the remain are all 5Bits element until bit 63

for write that i rewrite the qsort of K&R2 for one array
of integer and change something when find the one
run ok
so i not see my qsort version i wrote;
i rewrite it from 0
and never test it for the speed
test it only for correct results

and too i cancel the
"swap(v, left, (left+right)/2);"
line;
in what that line is useful?

> (There are examples of it *within* a buildable
> library, but I'm talking about library source where
> the user is encouraged to recompile a routine,
> like qsort() but probably more complicated, using
> his own application-specific header.)

i did read there is one people say library are not ok
because each code must be rewrite because each program
has need his peculiar routines
i think this is not right, for example printf()
can be used in many programs
yes algo are different and one has to rewrite
if the data or other not fit the general one of the
library

> James Dow Allen

On Sep 7, 10:16=A0pm, "BGB / cr88192" <cr88...@hotmail.com> wrote:
> admittedly, I had underestimated the time cost of qsort it seems, fair
> enough, I don't really tend to use it anyways...

Sorry if my rejoinder to you was abrasive.  There was a pompous
asshole intruding in the thread who got my ire up.  I made
a hasty omnibus response.

On the (tangential) topic of qsort speed, an important point
is that many applications will have a time cost of
    k_1 O(N) + k_2 O(N log N)
where qsort *is* the time-important routine.  A O(1) improvement
in its speed *is* often important.

Another point (and I hope the pompous asshole gets someone to
show him how to display this in a larger font, as his reading
comprehension is poor) is that the source changes envisioned to
convert qsort.c to qsort_adaptable.c are AMAZINGLY trivial.
Most instances of "(*cmp)" in the source change to "COMP"
and that's the "hardest" change of all.  Whether this should
be made visible to any standard library is a separate question,
but Mr. Asshole's concept ("making the 100s of qsort variants
part of the C standard" ????) shows bizarrely poor understanding:
My objective was to *reduce* the number of source code variants,
not increase them.

As I stated over and over and OVER, time speedup was never the
goal (qsort just presented itself as an easily understood
example).  The goal was *reusing source modules* so that, for
example, three hash-table managers whose differences are so
great that normally three different source modules would be
needed can instead share a source module.  Code generators
have their place, but (unless one wants to apply the term to
these "reusable .c files") will be inferior in the cases I envision.
(Consider the triviality of changing qsort.c to qsort_adaptable.c.)

James Dow Allen

PS:  On a separate topic,
On Sep 7, 8:55 pm, Tom St Denis <t...@iahu.ca> wrote:
> If they can't have some humility it's not my fault.

I wonder if Saint Dennis knows how preciously arrogant
this sounds.

On 2010-09-07, James Dow Allen <jdallen2000@yahoo.com> wrote:
> As I stated over and over and OVER,

I think you have GRAVELY overestimated the reading comprehension skills
of Usenet.

> The goal was *reusing source modules* so that, for
> example, three hash-table managers whose differences are so
> great that normally three different source modules would be
> needed can instead share a source module.  Code generators
> have their place, but (unless one wants to apply the term to
> these "reusable .c files") will be inferior in the cases I envision.
> (Consider the triviality of changing qsort.c to qsort_adaptable.c.)

I'm actually totally surprised that this makes a significant difference,
because I wouldn't have expected it to be even measurable, since the
callback idiom is so common.  I've done a ton of things that use a
function pointer for their inner loop processing, and it never occurred
to me to try to figure out a way to inline them.

That actually leads to an interesting question, to me, which is where
the inefficiency is.  Is it in the indirection through a function pointer?
The argument passing?  The lack of optimization because the comparison
argument can't be inlined?  In particular, I'm wondering how much of it
comes down to the extra argument to qsort(), since a lot of qsort()
implementations are presumably recursive, meaning every layer of the
call tree has a function pointer argument.  If you could strip that away,
I wonder whether it would noticably improve performance.

I guess, to me, it doesn't seem like replacing the callback model with
this #define/inlining stuff model is enough of a conceptual improvement to
be significant -- it doesn't strike me as making things much easier to
understand.  But if it's making a big speed difference, maybe that IS
worth looking at.  But it surprises me that it'd matter much!  It would
be interesting to come up with some reasonable test cases to experiment
with and see where the efficiency is coming from -- whether it's the
inlining or the argument lists or what.

-s
-- 
Copyright 2010, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.

Tom St Denis wrote:

> On Sep 7, 9:54�am, gaze...@shell.xmission.com (Kenny McCormack) wrote:
>> Indeed. �Frankly, I was *amazed* at the extent to which TSD stepped in
>> shit with that comment.
> 
> If that's stepping in shit ... Wow.

Well, what do you expect from a troll who can't even spell the name of
his anal-retentive favorite toon.

On Sep 7, 8:40=A0am, Tom St Denis <t...@iahu.ca> wrote:
> Anyways, since you guys are just inventing the conversation this is my
> last post in this thread.

Then you're letting yourself off easy.  You should respond to the
comments that James Dow Allen addressed to you, rather than wasting
your time on a so-called invented conversation.

On Sep 8, 2:06=A0am, Seebs <usenet-nos...@seebs.net> wrote:
> On 2010-09-07, James Dow Allen <jdallen2...@yahoo.com> wrote:
>
> > As I stated over and over and OVER,
>
> I think you have GRAVELY overestimated the reading comprehension skills
> of Usenet.

Sigh.  It appears I've overestimated your skills as well.
SAVING THE CALLBACK IN QSORT() WAS JUST A TRIVIAL EXAMPLE
to avoid digressing into a discussion of a reusable hash-table
manager.  The hashtable manager has MANY options.  Do you store
via bits or bytes?  What's your collision/rehash strategy?
We're not trying to avoid one trivial callback, we're avoiding
a largish collection of switches, etc.  Sometimes you need to
waste a bit for a deletion marker, sometimes you don't. Etc. etc.

Writing one hashtable manager is better than writing 3 or 4, right?
Using simple macros makes the code simpler than switches or if/elses,
right?


You quote part of the purposeful discussion:
> > The goal was *reusing source modules* so that, for
> > example, three hash-table managers whose differences are so
> > great that normally three different source modules would be
> > needed can instead share a source module. =A0Code generators
> > have their place, but (unless one wants to apply the term to
> > these "reusable .c files") will be inferior in the cases I envision.

.... But then focus on the trivial example:
> > (Consider the triviality of changing qsort.c to qsort_adaptable.c.)
>
> I'm actually totally surprised that this makes a significant difference,

This has *nothing* to do with my intent for this thread but:
The reason it makes a difference is that qsort() spends a *huge*
majority of its time calling (*cmp)() (which is often a trivial
function) and doing swaps.
Saving function invocation is a big win.  A known-size swap is
faster than a variable-size swap.

> since a lot of qsort()
> implementations are presumably recursive,

I don't have a number to give you offhand, but calls to (*cmp)
sharply outnumber the recursive calls to the sorting function.

> I guess, to me, it doesn't seem like replacing the callback model with
> this #define/inlining stuff model is enough of a conceptual improvement t=
o
> be significant.

I tried to emphasize that it was the READABILITY advantage of using
one (hashtable-manager, for example) function, where otherwise
multiple versions would be needed that was the goal, and that qsort()
(were a speed advanatge happens to obtain) was introduced solely
because it was well-known, simple, and going into detail on a REAL
example where the mehtod isapplicable would be diversive.
Alas, it was to no avail.

Thanks anyway,
James

On Sep 6, 12:48=A0pm, James Dow Allen <jdallen2...@yahoo.com> wrote:
> Jacob's mention of his library reminds me of my own
> suggestion to help with software reusability.
>
> Much software has the form
> =A0 High Level -- application-specific code
> =A0 =A0 Mid Level -- application-specific code
> =A0 =A0 =A0 Low Level -- FREQUENT FUNCTION, use library
>
> But often one encounters
> =A0 High Level -- application-specific code
> =A0 =A0 Mid Level -- FREQUENT FUNCTION
> =A0 =A0 =A0 Low Level -- application-specific code
>
> A familiar example where this form is encountered and
> dealt with is qsort(), with the low-level handled
> simply with a function pointer.
>
> If the qsort() source were recompiled with the
> application-dependent comparison etc. it would speed
> up, perhaps by 25%. =A0The qsort.c source wouldn't
> even change; instead the variation would be provided
> by a very simple application-dependent header included
> by qsort.c.
>
> For example, make this definition:
> =A0 #define COMP(x,y) =A0 =A0 =A0\
> =A0 =A0 =A0(((struct elem *)x)->key - ((struct elem *)y)->key)
> visible to qsort.c, rather than just pass a pointer
> to the function
> =A0 int ecomp(const void *x, const void *y)
> =A0 { return COMP(x,y); }
>
> I mention this simple case to make the idea clear,
> but if all I wanted to do is speed-up qsort() by 25%
> I wouldn't be posting this. =A0Instead I'm thinking
> of cases where the common function CAN'T BE USED
> AT ALL, without this flexibility.
>
> In these interesting cases, the application-dependent
> variations are much too complicated to be represented
> with a few function arguments, but a common source
> code could still be used, with any variations
> coming from #define's in an application-dependent header.
> (I have specific examples in mind, but won't mention
> them. =A0I want to focus on the idea of reusing
> source code in the way I imply, rather than any
> specific example.)
>
> How about it? =A0Anybody do this, or want to do it?
> (There are examples of it *within* a buildable
> library, but I'm talking about library source where
> the user is encouraged to recompile a routine,
> like qsort() but probably more complicated, using
> his own application-specific header.)


qsort is a good example of a function where the indirect function call
can be very expensive, particularly with small elements (say, ints) to
be sorted.

C++'s approach to that is templates, with sort() doing just what you
suggest.

There's also no particular reason a compiler couldn't inline
comparison function to a specialized qqort function as things stand
now.  While qsort is a bit special in that it's a library function, a
compiler that supports link time code generation could quite plausible
specialize and inline that so long as it had the semi-compiled qsort
source available.

On 2010-09-07, James Dow Allen <jdallen2000@yahoo.com> wrote:
> Sigh.  It appears I've overestimated your skills as well.
> SAVING THE CALLBACK IN QSORT() WAS JUST A TRIVIAL EXAMPLE
> to avoid digressing into a discussion of a reusable hash-table
> manager.

Yes.  But it's an *interesting* trivial example, because the
results obtained are so surprising.

> Writing one hashtable manager is better than writing 3 or 4, right?
> Using simple macros makes the code simpler than switches or if/elses,
> right?

Sometimes!  There is a real risk that one of two things will happen:

1.  The macros stop being simple.
2.  The code keeps the macros simple at the expensive of some logic
improvements that would have made the macros less simple.

> This has *nothing* to do with my intent for this thread but:
> The reason it makes a difference is that qsort() spends a *huge*
> majority of its time calling (*cmp)() (which is often a trivial
> function) and doing swaps.
> Saving function invocation is a big win.  A known-size swap is
> faster than a variable-size swap.

Makes sense.

> I tried to emphasize that it was the READABILITY advantage of using
> one (hashtable-manager, for example) function, where otherwise
> multiple versions would be needed that was the goal, and that qsort()
> (were a speed advanatge happens to obtain) was introduced solely
> because it was well-known, simple, and going into detail on a REAL
> example where the mehtod isapplicable would be diversive.

Hmm.  I think the issue is, without that example to look at, it's hard for
me to get a feel for what kind of improvements in code readability
you're thinking about.  Any time you start a discussion with C programmers
with the claim "if we used macros, this would be easier to read", you are
necessarily fighting an uphill battle... :)

Can you give a simple example of, say, two functions which are largely
similar, and how simple macros could make it into one function?
I think the basic idea of having #defines lead to changes in code behavior
is a pretty well-accepted one up to a very limited point; consider assert.

What this suggests to me, though, is possibly a variant usage.  Imagine
a source file to the effect of:

	static inline int cmp(blah *a, blah *b) { /* code goes here */ }
	static inline int swap(blah *a, blah *b) { /* code goes here */ }
	#define qsort qsort_blah
	#define qsort_type blah
	#include <qsort_code.c>

and a header:
	#define qsort qsort_blah
	#define qsort_type blah
	#include <qsort_decl.h>

If this .c module were a separate translation unit, a reasonable compiler
could do the same sorts of optimizations (?) that it would with the macros,
but you'd be avoiding the "it's a macro so it has to be simple and not
re-evaluate arguments" problems.  And then it would provide both a declaration
and a definition of qsort_blah(), which would be a nice and efficient thing
that happened to function much like a qsort.

Is that the kind of thing you're getting at?  I'm afraid I haven't ever
really looked at anything using a hashtable manager in C enough to have much
of a sense for what they look like or where you'd want to insert stuff
in them.

-s
-- 
Copyright 2010, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.

On 9/6/2010 11:05 PM, James Dow Allen wrote:
>
> I almost prefaced my message wtih a disclaimer
> that SPEED WAS **NOT** MY CONCERN, but felt that a
> simple speed-up case led to a clear example.
> It seemed unnecessary -- I mention the point when
> I mention speed.
>
> But the only one to make a joke about the speed-up
> was also the only one who grasped that speed
> performance was not my primary concern!
>
> On Sep 7, 4:50 am, Eric Sosman<esos...@ieee-dot-org.invalid>  wrote:
>> On 9/6/2010 1:48 PM, James Dow Allen wrote:
>>> If the qsort() source were recompiled with the
>>> application-dependent comparison etc. it would speed
>>> up, perhaps by 25%.
>>
>>       Aside: Did you know that 84.6% of all stated percentages
>> are made up out of thin air?
>
> Aside:  Did you suspect that, although any speedup was peripheral
> to my main point, I actually did the implied experiment,
> using glibc's qsort source, with constanted num, size,
> compare?  The element was
>      struct { int a, key, c, d; }
> Speedup was 25%.
>
>>       A concrete example might be helpful here, despite
>> the misgivings you state below.  In particular, I'd like
>> to understand the "CAN'T BE USED AT ALL" part.
>
> One example is hash-table management.  If space-efficiency
> is important, low-level details essential to the table
> handling will vary, while higher-level functionality
> (collision handling, resizing) may be invariant.
> If this isn't clear, note that a space-efficient table
> may pack key AND payload into 2 or 3 bytes, while
> off-the-shelf hashtables often dictate 12 bytes PLUS key.

     Can't comment, as there's a great lack of specificity
about the designs of these competing hash tables.  Separate
chaining, coalesced chaining, open-addressed, ...  The phrase
"hash table" covers a *wide* variety of data structures with
disparate characteristics.

     Besides, the possible space efficiency seems insufficient
to justify "CAN'T BE USED AT ALL;" it's entirely akin to the
time savings you already don't care about.

>>       As to why they don't get more air time -- well, I'm sure
>> there are lots of reasons.  Lack of direct support from the tools
>> that go along with the language has to be one of them: Lots of
>> debuggers, for example, have trouble stepping from line to line
>> through a function generated by a one-line macro invocation.
>> Mistakes by the client/user may well elicit compiler diagnostics
>> that are confusing at best, misleading at worst -- after the
>> #include or whatever you get a cascade of syntax errors and no
>> further clue.  Testing becomes more laborious, because the innards
>> of the "module" are exposed to the surrounding code rather than
>> isolated from it, meaning that there are vastly more client/module
>> interactions to worry about.
>
> I'm assuming the user is an expert programmer.

     s/expert/infallible/, or so it seems.  Speaking for myself,
I have a hard time imagining the mind behind that level of
perfection -- except to think that such a mind wouldn't bother
with crutches like pre-written libraries, but would write all he
needed anew each time, omitting the generalities and such that
are inapplicable to the immediate case at hand.  See also

	http://www.pbm.com/~lindahl/mel.html

> Please note that there are two quite distinct approaches:
>
> (1) common source is in header, often in the form of
> #define'd code fragments, and invoked by application
> via macros.
> (2) common source is in .c file, application-specific
> stuff is presented to .c via user-specific .h defines.
> The .c is compiled (with its user-specific header) and
> then behaves just as an ordinary .c/.o.
>
> I'm thinking of (2) specifically, but Eric's comments
> apply mostly to (1).

     Sorry; I fail to see any difference between the two "quite
distinct" approaches.  Both employ the preprocessor to make
case-specific alterations to a batch of source code; it's just
a matter of the packaging, not of the essence.

     James, I'm not trying to make fun of you.  The technique of
using the preprocessor to specialize general code to a particular
use is fairly well-known -- yet the plain fact is that it's not
widely and routinely used.  Considering the efficiencies it may
offer, one wonders why not?  And my answers (or speculations) are
about the added difficulties the approach brings, and about the
choices experienced developers make.  Occasionally, very occasionally,
the advantages are appealing enough that someone chooses to go this
route.  Mostly, though, they don't -- So you're left with a choice
between "They're all dimwits" and "They've considered other factors."
It's possible that the former is the case, but "Everyone's out of
step except Johnny" is a difficult position to sustain ...

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

On 9/7/2010 3:25 AM, James Dow Allen wrote:
> On Sep 7, 1:17 pm, Nick<3-nos...@temporary-address.org.uk>  wrote:
>> You'll end up with sub-directories and fancy make files
>
>    sallysort.o:  sallysort.c
>         rm qspecif.h
>         ln sallysort.h qspecif.h
>         cc -O -c -o sallysort.o qvariant.c
> Much simpler than many makefiles.

     Simple, maybe, but correct?  I don't see how it could be --
but it's possible I'm blinded by the simplicity.  It seems to me
that sallysort.o should have dependencies on qvariant.c and on
sallysort.h, but I don't see those expressed anywhere.

     Even if cleaned up, such a "for the nonce" change to the file
system would be utter poison for parallel builds.  Since we're
supposing a large project (who would go to this much trouble for
a small one?), I think we've also got to suppose long build times
and an incentive to parallelize.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

On 09/ 7/10 11:46 PM, Tom St Denis wrote:
> On Sep 7, 4:22 am, Richard<rgrd...@gmail.com>  wrote:
>>
>> I can see you've been left to run around establishing your "reg"
>> credentials for a little too long...
>
> I've been an on-and-off poster for a long time.
>
> What I don't get about you trolls is why you think there is a
> hierarchy here.  There isn't.  I consider a few people here more
> knowledgeable about the ISO C spec than myself but it's not like I pay
> homage to them or something, or seek their approval or whatever.

That's the difference between reality and the fantasy world they inhabit.

<snip>

> You trolls really, really, really need to get a life.  Look at what
> you're doing.  You're trolling "computers languages C" ... can you get
> any nerdier and less useful than that?  For all that is decent in this
> world, seriously, go outside.

Well said.

-- 
Ian Collins

On 09/ 8/10 09:58 AM, James Dow Allen wrote:
>
> I tried to emphasize that it was the READABILITY advantage of using
> one (hashtable-manager, for example) function, where otherwise
> multiple versions would be needed that was the goal, and that qsort()
> (were a speed advanatge happens to obtain) was introduced solely
> because it was well-known, simple, and going into detail on a REAL
> example where the mehtod isapplicable would be diversive.

That (readability) may be one of the reasons the whole thing falls down. 
  whenever I have seen this done using macros, readability suffers. 
Pity the poor maintenance programmer.

-- 
Ian Collins

On 09/ 8/10 07:06 AM, Seebs wrote:
>
> I guess, to me, it doesn't seem like replacing the callback model with
> this #define/inlining stuff model is enough of a conceptual improvement to
> be significant -- it doesn't strike me as making things much easier to
> understand.  But if it's making a big speed difference, maybe that IS
> worth looking at.  But it surprises me that it'd matter much!  It would
> be interesting to come up with some reasonable test cases to experiment
> with and see where the efficiency is coming from -- whether it's the
> inlining or the argument lists or what.

It's not easy to knock up a quick example in C, but it is in C++, where 
the standard sort is a function template.  Comparing the sort of 
10000000 random doubles, qsort is at least as fast as std::sort with no 
optimisation, but takes twice as long with optimisation on.  The big 
difference is inlining the comparison function.  I'll post the test case 
if granted immunity from flames for posting C++!

-- 
Ian Collins

James Dow Allen <jdallen2000@yahoo.com> writes:

> Much software has the form
>   High Level -- application-specific code
>     Mid Level -- application-specific code
>       Low Level -- FREQUENT FUNCTION, use library
>
> But often one encounters
>   High Level -- application-specific code
>     Mid Level -- FREQUENT FUNCTION
>       Low Level -- application-specific code
>
> A familiar example where this form is encountered and
> dealt with is qsort(), with the low-level handled
> simply with a function pointer.

When I run into the latter situation in a performance-critical
area, I try to think of ways that I can invert the dependency,
flipping it around so that it becomes the former situation.  One
way to do this is to make the application-specific client code do
more work.  This does have the cost of making the client write
more code (but not always much more) and making the client more
tightly bound to the implementation,

One example is the hash table library that I use in PSPP,
available here:
        http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/hmap.h
        http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/hmap.c

Most generic hash table library, in my experience, require the
client to provide at least a hashing function and a comparison
function.  My library does not use any function pointers.
Instead, the client provides a hash value at the time of
insertion, as an argument call to the insertion function, and the
library saves the hash value as part of the hash table node.
Instead of providing a conventional search function, the library
provides only a macro that iterates through hash table nodes that
have a given hash value, which is a suitable building block from
which the client can build a "search" function.

The resulting library is slightly harder to use in some ways.  On
the other hand, I find that callback functions are often quite
awkward to use--for example, they force auxiliary data to be
inconveniently bundled up--so sometimes it is in fact easier to
use.  Its operation is also, in my opinion, more transparent.

I've often idly thought about how the same idea could be applied
to sorting or balanced binary search trees, but it seems to be a
little trickier in those cases.
-- 
Ben Pfaff 
http://benpfaff.org

On Sep 8, 6:27=A0am, Ian Collins <ian-n...@hotmail.com> wrote:
>
> It's not easy to knock up a quick example in C, but it is in C++, where
> the standard sort is a function template. =A0Comparing the sort of
> 10000000 random doubles, qsort is at least as fast as std::sort with no
> optimisation, but takes twice as long with optimisation on. =A0The big
> difference is inlining the comparison function. =A0I'll post the test cas=
e
> if granted immunity from flames for posting C++!
>
Lots of languages provide sorts.

Most of them are very easy to use for sorting lists of integers, which
of course is what the examples in the documentation provide. The
problem is that you seldom need to sort integers, you want to sort
records on a field.
Then you end up messing about with copy constructors and overloaded
"<" operators. I've found very few languages as easy to use as C's
qsort().

Speed yes, is a factor, particuarly for sorting. But most software
projects that fail do so because the interactions between the
different modules become too complicated, not because the processor
isn't fast enough.

On 09/ 8/10 09:29 PM, Malcolm McLean wrote:
> On Sep 8, 6:27 am, Ian Collins<ian-n...@hotmail.com>  wrote:
>>
>> It's not easy to knock up a quick example in C, but it is in C++, where
>> the standard sort is a function template.  Comparing the sort of
>> 10000000 random doubles, qsort is at least as fast as std::sort with no
>> optimisation, but takes twice as long with optimisation on.  The big
>> difference is inlining the comparison function.  I'll post the test case
>> if granted immunity from flames for posting C++!
>>
> Lots of languages provide sorts.

But only two of them allow one to compare the performance of inlined and 
not inlined function calls.

> Most of them are very easy to use for sorting lists of integers, which
> of course is what the examples in the documentation provide. The
> problem is that you seldom need to sort integers, you want to sort
> records on a field.
> Then you end up messing about with copy constructors and overloaded
> "<" operators. I've found very few languages as easy to use as C's
> qsort().

For most practical uses, C++'s std::sort is no more complex to use than 
qsort(), it requires the same inputs (the range and the comparison 
function).  You can even use the same comparison function (less the 
casing from void*). There's no messing about with anything.

> Speed yes, is a factor, particuarly for sorting. But most software
> projects that fail do so because the interactions between the
> different modules become too complicated, not because the processor
> isn't fast enough.

Which is a language independent problem.

-- 
Ian Collins

On Sep 7, 5:58=A0pm, James Dow Allen <jdallen2...@yahoo.com> wrote:
> On Sep 8, 2:06=A0am, Seebs <usenet-nos...@seebs.net> wrote:
>
> > On 2010-09-07, James Dow Allen <jdallen2...@yahoo.com> wrote:
>
> > > As I stated over and over and OVER,
>
> > I think you have GRAVELY overestimated the reading comprehension skills
> > of Usenet.
>
> Sigh. =A0It appears I've overestimated your skills as well.
> SAVING THE CALLBACK IN QSORT() WAS JUST A TRIVIAL EXAMPLE
> to avoid digressing into a discussion of a reusable hash-table
> manager.

It seems that in lieu of the confusion (including my own) on what
exact concept you're trying to get across, perhaps you could construct
an example (in code) that explicitly demonstrates the differences.  To
simplify the implementation, instead of a sophisticated qsort, you
could create a bubblesort interface a la

\code
void bubblesort ( void * base,
                  size_t num,
                  size_t size,
                  int ( * comparator ) ( const void *, const void
* ) );
\endcode

and demonstrate your version with the macro technique.  Most macro
techniques are harder to understand implementation-wise because you
need to carry more context like remembering or looking up exactly what
the macros do.

> =A0The hashtable manager has MANY options. =A0Do you store
> via bits or bytes? =A0What's your collision/rehash strategy?
> We're not trying to avoid one trivial callback, we're avoiding
> a largish collection of switches, etc. =A0Sometimes you need to
> waste a bit for a deletion marker, sometimes you don't. Etc. etc.
>
> Writing one hashtable manager is better than writing 3 or 4, right?
> Using simple macros makes the code simpler than switches or if/elses,
> right?
>
> You quote part of the purposeful discussion:
>
> > > The goal was *reusing source modules* so that, for
> > > example, three hash-table managers whose differences are so
> > > great that normally three different source modules would be
> > > needed can instead share a source module. =A0Code generators
> > > have their place, but (unless one wants to apply the term to
> > > these "reusable .c files") will be inferior in the cases I envision.
>
> ... But then focus on the trivial example:
>
> > > (Consider the triviality of changing qsort.c to qsort_adaptable.c.)
>
> > I'm actually totally surprised that this makes a significant difference=
,
>
> This has *nothing* to do with my intent for this thread but:
> The reason it makes a difference is that qsort() spends a *huge*
> majority of its time calling (*cmp)() (which is often a trivial
> function) and doing swaps.
> Saving function invocation is a big win. =A0A known-size swap is
> faster than a variable-size swap.
>
> > since a lot of qsort()
> > implementations are presumably recursive,
>
> I don't have a number to give you offhand, but calls to (*cmp)
> sharply outnumber the recursive calls to the sorting function.
>
> > I guess, to me, it doesn't seem like replacing the callback model with
> > this #define/inlining stuff model is enough of a conceptual improvement=
 to
> > be significant.
>
> I tried to emphasize that it was the READABILITY advantage of using
> one (hashtable-manager, for example) function, where otherwise
> multiple versions would be needed that was the goal, and that qsort()
> (were a speed advanatge happens to obtain) was introduced solely
> because it was well-known, simple, and going into detail on a REAL
> example where the mehtod isapplicable would be diversive.
> Alas, it was to no avail.

How can you expect people to understand a hash table technique if they
aren't understanding what your trivial example is meant to get
across.  Plus we don't have access to your hash table source, so we
can't put the code in front of our faces (like Pfaff provided for his
example).  We can't all be mind-readers.  You say that performance is
not the point, but the focus keeps drifting to performance reasons for
doing these things.  Put up a complete example (like bubblesort) that
demonstrates your interpretation of improved readability and more of
us may get what you're trying to say.

> Thanks anyway,
> James

Best regards,
John D.

robertwessel2@yahoo.com <robertwessel2@yahoo.com> wrote:
> 
> There's also no particular reason a compiler couldn't inline
> comparison function to a specialized qqort function as things stand
> now.  While qsort is a bit special in that it's a library function, a
> compiler that supports link time code generation could quite plausible
> specialize and inline that so long as it had the semi-compiled qsort
> source available.

There's no reason an implementation can't inline the comparison function
to qsort itself, even without link-time code generation.  All that's
necessary is to define qsort as a macro that expands to an invocation of
an inline version of qsort:

	#define qsort(_b, _n, _s, _c) _inline_qsort((_b), (_n), (_s), (_c))

	static inline void _inline_qsort(void *_b, size_t _n, size_t _s,
	                  int (*_c)(const void *, const void *))
	{
	...
	}
-- 
Larry Jones

I sure wish I could get my hands on some REAL dynamite. -- Calvin

On Sep 8, 8:24=A0am, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
> >> =A0 =A0 =A0 A concrete example might be helpful here, despite
> >> the misgivings you state below. =A0In particular, I'd like
> >> to understand the "CAN'T BE USED AT ALL" part.

I'll enclose a brief excerpt from a specific header for
the "Source Reusable" Hash-table handler.  The key point is
that the table element structure itself is variable; in the
example application key and data are PACKED together into
a single short.  You can't expect to handle all the
variations of the element type with callbacks or switches.

> =A0 =A0 =A0Besides, the possible space efficiency seems insufficient
> to justify "CAN'T BE USED AT ALL;" it's entirely akin to the
> time savings you already don't care about.
>
> =A0 =A0 =A0... The technique of
> using the preprocessor to specialize general code to a particular
> use is fairly well-known -- yet the plain fact is that it's not
> widely and routinely used. =A0Considering the efficiencies it may
> offer, one wonders why not?

I'll try to address these questions, then
go away quietly!

I agree that seeking a mere 10% improvement in
speed or space is often pointless perfectionism.
But in many hash-table applications one seeks a
space savings which is *MUCH* larger than that.

Some "off-the-shelf" hash-tables use 12 bytes
per entry PLUS the key; call it 16 bytes total.
If instead you want 2 bytes per entry, the
off-the-shelf table will waste 87% of its
storage.

Buying eight times as much storage isn't really
the answer:  If you head 8x storage, you might
want 8x the table size, not the old table
with 87% of space wasted!

Hash tables with 4 (or even 2) bytes per entry
are hardly unusual.  Nodes in typical Connect-4
game-playing software (A topic on which I'm less
than totally ignorant:
   http://www.amazon.com/Complete-Book-CONNECT-History-Strategy/dp/14027562=
16
) are 4 bytes.  I've
seen a Rubik's-cube solver with 2-byte nodes,
and used 2-byte nodes myself on similar problems.

In fact, it was such a 2-byte per node hashtable
that led to my original "reusable source" in the
first place.  Here's part of the application-specific
header:
   typedef unsigned short Te_ktype;
   typedef struct {
        Te_ktype        te_key;
   } Tab_entry;

   #define EPEND         0x4000
   #define OPEND         0x8000
   #define KEY(tekey)    ((tekey) & ~(EPEND | OPEND))
   #define KEYEQ(a, b)   (!(KEY(a ^ b)))
   #define HASHER(s)     ((s) + ((s) >> 1) - ((s) >> 3))
   #define EMPTY         (0)
   #define MTSLOT(s)     ((s) =3D=3D EMPTY)
   #define MTSET(s)      ((s) =3D EMPTY)

Note that the data type of a table element is application
dependent.  To imagine a giant switch statement, or
invocation of a callback, on any table-element operation
would be absurd!

Some may ask:  Why didn't you just "roll your own"
hash-table manager?  I *DID* roll my own; but I rolled
in such a fashion that I wouldn't have to KEEP re-rolling
it for every major change!
(I *did* change the .c, refining the definition
of the .h -> .c interface whenever that seemed best.)

I don't claim the method is a panacea.  I adopted
a wholly different approach in an image-processing
library, with a high-level routine invoking four
processing routines whose nature varied by link.
(And now, I've switched to different hash-table
methods which bypass the concept!)

But the method seems useful.  It's hardly original;
in glibc-2.7 it's used to provide single .c modules
to support several similar functions, e.g.
strtod & friends, wcstol & friends.

Evidently I articulated the idea poorly, and apologize
for that.  Kudos to Eric and Ben, who understand me
anyway and made intelligent responses.  (A big
raspberry to the "Saint" who was completely baffled
but tried to show off anyway.)

James Dow Allen

James Dow Allen <jdallen2000@yahoo.com> writes:
<snip>
> I agree that seeking a mere 10% improvement in
> speed or space is often pointless perfectionism.
> But in many hash-table applications one seeks a
> space savings which is *MUCH* larger than that.
>
> Some "off-the-shelf" hash-tables use 12 bytes
> per entry PLUS the key; call it 16 bytes total.
> If instead you want 2 bytes per entry, the
> off-the-shelf table will waste 87% of its
> storage.
>
> Buying eight times as much storage isn't really
> the answer:  If you head 8x storage, you might
> want 8x the table size, not the old table
> with 87% of space wasted!

> [...]  Here's part of the application-specific
> header:
>    typedef unsigned short Te_ktype;
>    typedef struct {
>         Te_ktype        te_key;
>    } Tab_entry;
>
>    #define EPEND         0x4000
>    #define OPEND         0x8000
>    #define KEY(tekey)    ((tekey) & ~(EPEND | OPEND))
>    #define KEYEQ(a, b)   (!(KEY(a ^ b)))
>    #define HASHER(s)     ((s) + ((s) >> 1) - ((s) >> 3))
>    #define EMPTY         (0)
>    #define MTSLOT(s)     ((s) == EMPTY)
>    #define MTSET(s)      ((s) = EMPTY)
>
> Note that the data type of a table element is application
> dependent.  To imagine a giant switch statement, or
> invocation of a callback, on any table-element operation
> would be absurd!

I need some help with this bit.  What's absurd about a callback?

You've said time and time again that this is not about speed; rather it
is a more general design issue.  But from a design point of view I'd be
happy to have four function pointers stored in the hash table, and once
you have that you only need to tell the table how big the elements are,
and not their actual type.  It can then be a conventional compiled
module.

[I say four because it looks like key equality, hashing and testing and
setting empty are the ones that aren't helpers for the others.  If it's
only a few more, I don't think it alters the argument that much.]

You say this is part, so maybe some other part is where the absurdity
of a callback becomes clear.  Cutting down code can be like that -- you
can simplify to the point of missing a part of what you are trying to
illustrate.

By the way, I don't think the technique is daft, and I've used it myself.
I would try to avoid it on some rather ill-defined grounds of good taste
but it's certainly workable.  Nowadays I'd be tempted to use inline
functions in the way that I think Seebs illustrated, but it would still
feel to me like a design of last resort.

<snip>
-- 
Ben.

On Sep 9, 12:48=A0am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> James Dow Allen <jdallen2...@yahoo.com> writes:
>
> > Note that the data type of a table element is application
> > dependent. =A0To imagine a giant switch statement, or
> > invocation of a callback, on any table-element operation
> > would be absurd!
>
> I need some help with this bit. =A0What's absurd about a callback?

The hash-table handler iterates through elements of an (explicit or
implicit) collision list (in which the iteration stride, sizeof
Element,
is *variable*); each element encountered needs to be classified as
a Match or Other(*).  The test for Match (which also must include
classification of Other) *could* be done by callback, but note
that if quotienting is in use, the callback would need to pass state
info just so the application could do the match.  Possible to
do, but if I try to envision it, it seems horrid.  Admittedly, this
might be partly a matter of taste....  (* - Other can include Empty,
Deleted, Mismatch-Hard, Mismatch-Soft; this last case is useful
in caching applications where some low-value elements are eligible
for overwriting.)

My code looks *very* ordinary and easy to read, except that, e.g.
     if (KEYEQ(a, b))  /* macro */
might occur where
     if (keyeq(a, b))
would be "ordinary".  I personally would find the version full
of callback()'s tedious to look at and annoying.  I'd "roll my own"
rather than using it.

James

On Tue, 7 Sep 2010 11:46:47 +0000 (UTC), gazelle@shell.xmission.com
(Kenny McCormack) wrote:

>In article <16bfb267-4beb-4519-bfc9-e37635fd3467@m15g2000yqm.googlegroups.com>,
>Tom St Denis  <tom@iahu.ca> wrote:

>>> >usually when a newb comes into a group [any group] and says things
>>> >like "why not we do everything while standing on our heads?" it's
>>> >because they don't know what they're talking about.

>>> Yup. �James Dow Allen is a newb here. �Never seen him post before, no
>>> siree! �He's got some nerve comin' in here and stirin' things up!
>>>
>>> Thanks for proving my point.

>>If you had actually read what I wrote, I said we [most regulars]
>>**DO** read what they write.  We just don't have to agree with it
>>because you say so.

>There is no "we".
>There is no committee.
>There is no organization.
>There is no central authority.
>There is no funding body.

I don't seek social structure in ngs.  Some people do though, and they
want to belong.  Thus form cliques.

Ng topicality need not be defined by a dominant clique.  Minorities can
use it as they please, clique objections notwithstanding.



-- 
Web mail, POP3, and SMTP
http://www.beewyz.com/freeaccounts.php
 

John Kelly <jak@isp2dial.com> writes:

> On Tue, 7 Sep 2010 11:46:47 +0000 (UTC), gazelle@shell.xmission.com
> (Kenny McCormack) wrote:
>
>>In article <16bfb267-4beb-4519-bfc9-e37635fd3467@m15g2000yqm.googlegroups.com>,
>>Tom St Denis  <tom@iahu.ca> wrote:
>
>>>> >usually when a newb comes into a group [any group] and says things
>>>> >like "why not we do everything while standing on our heads?" it's
>>>> >because they don't know what they're talking about.
>
>>>> Yup.  James Dow Allen is a newb here.  Never seen him post before, no
>>>> siree!  He's got some nerve comin' in here and stirin' things up!
>>>>
>>>> Thanks for proving my point.
>
>>>If you had actually read what I wrote, I said we [most regulars]
>>>**DO** read what they write.  We just don't have to agree with it
>>>because you say so.
>
>>There is no "we".
>>There is no committee.
>>There is no organization.
>>There is no central authority.
>>There is no funding body.
>
> I don't seek social structure in ngs.  Some people do though, and they
> want to belong.  Thus form cliques.
>
> Ng topicality need not be defined by a dominant clique.  Minorities can
> use it as they please, clique objections notwithstanding.

I am sure your approval will be met with relief by all concerned.

-- 
"Avoid hyperbole at all costs, its the most destructive argument on
the planet" - Mark McIntyre in comp.lang.c

On Sep 8, 12:55=A0pm, Ian Collins <ian-n...@hotmail.com> wrote:
> On 09/ 8/10 09:29 PM, Malcolm McLean wrote:
>
> For most practical uses, C++'s std::sort is no more complex to use than
> qsort(), it requires the same inputs (the range and the comparison
> function). =A0You can even use the same comparison function (less the
> casing from void*). There's no messing about with anything.
>
When you "know the trick" maybe.

Here's an example documentation page

http://www.sgi.com/tech/stl/sort.html

For those who can't be bothered to follow the link, here's the example
of how to use the function.

int A[] =3D {1, 4, 2, 8, 5, 7};
const int N =3D sizeof(A) / sizeof(int);
sort(A, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The output is " 1 2 4 5 7 8".


Can you honestly tell me that, from this documententation, you can
work out how to sort a list of integers by abolute value (for
example)?

> > Speed yes, is a factor, particuarly for sorting. But most software
> > projects that fail do so because the interactions between the
> > different modules become too complicated, not because the processor
> > isn't fast enough.
>
> Which is a language independent problem.
>
The problem occurs in all languages, but is more severe in some than
in others.

On 09/10/10 09:48 PM, Malcolm McLean wrote:
> On Sep 8, 12:55 pm, Ian Collins<ian-n...@hotmail.com>  wrote:
>> On 09/ 8/10 09:29 PM, Malcolm McLean wrote:
>>
>> For most practical uses, C++'s std::sort is no more complex to use than
>> qsort(), it requires the same inputs (the range and the comparison
>> function).  You can even use the same comparison function (less the
>> casing from void*). There's no messing about with anything.
>>
> When you "know the trick" maybe.

So you advocate using qsort() without reading the documentation?

> Here's an example documentation page
>
> http://www.sgi.com/tech/stl/sort.html
>
> For those who can't be bothered to follow the link, here's the example
> of how to use the function.
>
> int A[] = {1, 4, 2, 8, 5, 7};
> const int N = sizeof(A) / sizeof(int);
> sort(A, A + N);
> copy(A, A + N, ostream_iterator<int>(cout, " "));
> // The output is " 1 2 4 5 7 8".
>
> Can you honestly tell me that, from this documententation, you can
> work out how to sort a list of integers by abolute value (for
> example)?

 From the documentation, or the snippet you quote?

If you read the documentation, you can see sort can take a third 
parameter: the ordering function.  Take the function you would pass to 
qsort(), simplify it to return a boolean result and use it.

int absCompare( const void* a, const void* b )
{
   int i = abs(*(int*)a);
   int j = abs(*(int*)b);

   if (i > j)
     return 1;
   if (i < j)
     return -1;
   return 0;
}

reduces to

bool absComp( int i, int j )
{
   return abs(i) < abs(j);
}

and

qsort( A, N, sizeof(*A), absCompare);

reduces to

std::sort( A, A + N, absComp);

So both the comparison function and the call are simplified.

-- 
Ian Collins

On 2010-09-10, Malcolm McLean <malcolm.mclean5@btinternet.com> wrote:
> int A[] = {1, 4, 2, 8, 5, 7};
> const int N = sizeof(A) / sizeof(int);
> sort(A, A + N);
> copy(A, A + N, ostream_iterator<int>(cout, " "));
> // The output is " 1 2 4 5 7 8".

Nit: the output is "1 2 4 5 7 8 ".

On Sep 7, 8:06=A0pm, Seebs <usenet-nos...@seebs.net> wrote:
>
> I'm actually totally surprised that this makes a significant difference,
> because I wouldn't have expected it to be even measurable, since the
> callback idiom is so common. =A0I've done a ton of things that use a
> function pointer for their inner loop processing, and it never occurred
> to me to try to figure out a way to inline them.
>
> That actually leads to an interesting question, to me, which is where
> the inefficiency is. =A0Is it in the indirection through a function point=
er?
> The argument passing? =A0The lack of optimization because the comparison
> argument can't be inlined? =A0In particular, I'm wondering how much of it
> comes down to the extra argument to qsort(), since a lot of qsort()
> implementations are presumably recursive, meaning every layer of the
> call tree has a function pointer argument. =A0If you could strip that awa=
y,
> I wonder whether it would noticably improve performance.
>
> I guess, to me, it doesn't seem like replacing the callback model with
> this #define/inlining stuff model is enough of a conceptual improvement t=
o
> be significant -- it doesn't strike me as making things much easier to
> understand. =A0But if it's making a big speed difference, maybe that IS
> worth looking at. =A0But it surprises me that it'd matter much! =A0It wou=
ld
> be interesting to come up with some reasonable test cases to experiment
> with and see where the efficiency is coming from -- whether it's the
> inlining or the argument lists or what.
>

What you're all missing it that when the compiler sees "qsort" it
doesn't *have to* arrange a call to object code in a library.
It can sort the data however it likes. That includes a technique
as crude as textual insertion of COMP or whatever into some hidden
qsort source code.

The mystery is why implementations generally don't treat
"library functions" as built-ins when it would be advantageous to
do so. A good opportunity arises when a malloc() and its corresponding
free() lie within the same function; calls to the heap manager can be
replaced with allocation on the stack.

Must be the weight of C history.

Regards,
Chris Noonan

On 9/10/2010 6:58 AM, Chris Noonan wrote:
>
> What you're all missing it that when the compiler sees "qsort" it
> doesn't *have to* arrange a call to object code in a library.
> It can sort the data however it likes. That includes a technique
> as crude as textual insertion of COMP or whatever into some hidden
> qsort source code.

     Yes, this could be done.  Given qsort's reliance on a pointer
to a comparison function, though, it might be quite difficult for
the compiler to figure out what qsort should call internally and
to in-line that as well.  Since a single call to qsort probably
produces O(N logN) calls to the comparator, the big gains come
from in-lining that latter, not the former.  Still, in-lining the
qsort "engine" itself, even if the comparison remains external,
would probably speed things up noticeably by simplifying the
item-exchange operations.

> The mystery is why implementations generally don't treat
> "library functions" as built-ins when it would be advantageous to
> do so. A good opportunity arises when a malloc() and its corresponding
> free() lie within the same function; calls to the heap manager can be
> replaced with allocation on the stack.

     Since the stack often has far less space available than the heap,
this could fail rather badly for large allocations.

> Must be the weight of C history.

     Our Foolish Forebears, right?

     But why stop with the library functions?  Why not in-line all
functions, library-resident and user-written, into one enormous blob
of straight-line code?  Every "call" to printf() would just plop the
entire printf() source right down at the call point, every call to
topFunctionInMyHugeTree() would do similarly (and recursively, for all
the functions it calls in turn), and the result would be a program with
no call/return overhead whatsoever!  I can't see any drawbacks to the
scheme; can you?

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

On 10 sep, 12:29, Ian Collins <ian-n...@hotmail.com> wrote:

>
> int absCompare( const void* a, const void* b )
> {
> =A0 =A0int i =3D abs(*(int*)a);
> =A0 =A0int j =3D abs(*(int*)b);
>
> =A0 =A0if (i > j)
> =A0 =A0 =A0return 1;
> =A0 =A0if (i < j)
> =A0 =A0 =A0return -1;
> =A0 =A0return 0;
>
> }
>
> reduces to
>
> bool absComp( int i, int j )
> {
> =A0 =A0return abs(i) < abs(j);
>
> }
>

abs(i) < abs(j) returns 0 or 1

What about -1 ?

Chris Noonan <usenet@leapheap.com> wrote:
> 
> The mystery is why implementations generally don't treat
> "library functions" as built-ins when it would be advantageous to
> do so.

Because it's excruciatingly difficult to know exactly when it would be
advantageous to do so for most library functions, and it would likely
never be advantageous for many.  The no-brainers like memcpy and strcmp
already are implemented as built-ins in many implementations.
-- 
Larry Jones

Even my FRIENDS don't do what I want. -- Calvin

On Sep 10, 12:27=A0pm, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
> On 9/10/2010 6:58 AM, Chris Noonan wrote:
>
> > The mystery is why implementations generally don't treat
> > "library functions" as built-ins when it would be advantageous to
> > do so. A good opportunity arises when a malloc() and its corresponding
> > free() lie within the same function; calls to the heap manager can be
> > replaced with allocation on the stack.
>
> =A0 =A0 =A0Since the stack often has far less space available than the he=
ap,
> this could fail rather badly for large allocations.

I wasn't proposing an unbreakable rule. I envisaged an optimising
compiler making sensible decisions. If size is a problem on a
particular architecture, the compiler may be able to determine
statically that the requested size is bounded above. Otherwise it can
emit code to branch on the size. For malloc the gains are worthwhile,
they go beyond inlining. As well as replacing a call to an intricate
function with as few as two opcodes, you are reducing (in a small way)
heap fragmentation and possibly avoiding a bus-locking instruction.


> > Must be the weight of C history.
>
> =A0 =A0 =A0Our Foolish Forebears, right?

Indeed. C was designed as a hacking language. In the early days,
replacing a library function with one of your own because the library
was buggy or you had written a better one was routine. Of course in
an engineering context, discovering that isdigit() excludes '8' or
that "while" means "if" is the last thing you want. Hence starting
with C89, it is forbidden to spoof standard library functions. I
have always assumed that one motive for the change was to make it
easier for compilers to optimise around library functions - to treat
them as built-ins if necessary.


> =A0 =A0 =A0But why stop with the library functions? =A0Why not in-line al=
l
> functions, library-resident and user-written, into one enormous blob
> of straight-line code? =A0Every "call" to printf() would just plop the
> entire printf() source right down at the call point, every call to
> topFunctionInMyHugeTree() would do similarly (and recursively, for all
> the functions it calls in turn), and the result would be a program with
> no call/return overhead whatsoever! =A0I can't see any drawbacks to the
> scheme; can you?

You overlooked a few words in my post:
"...when it would be advantageous to do so."

Regards,
Chris Noonan

On 2010-09-10, lawrence.jones@siemens.com <lawrence.jones@siemens.com> wrote:
> Because it's excruciatingly difficult to know exactly when it would be
> advantageous to do so for most library functions, and it would likely
> never be advantageous for many.  The no-brainers like memcpy and strcmp
> already are implemented as built-ins in many implementations.

This isn't directly relevant, because it's really fairly system-specific,
but we once encountered a delightful bug caused by a compiler being used
in freestanding mode.

Long story short:  In some cases, when given predictable-enough string
arguments, gcc will turn strcmp(foo, "bar") into memcmp(foo, "bar", 4),
and the like.  Or memchr("foo", x) into memchr("foo", x, 3).  Or, and
this is the kicker, strcpy(foo, "bar") into memcpy(foo, "bar", 4).

Someone wrote something "clever", roughly to the effect of:

	strcat(strcpy(foo, "start: "), end);

gcc did its magic.

Unfortunately, it was working in a freestanding environment, where the
str* and mem* functions had been provided by the code it was working on,
and someone else who was *also* being excessively clever had realized that
you could save an ENTIRE INSTRUCTION from the execution of memcpy by
always returning 0 instead of returning the "unused" return value.

Clever programmers, causing things to blow up without warning since the
60s.

-s
-- 
Copyright 2010, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.

On 09/10/10 11:52 PM, David RF wrote:
> On 10 sep, 12:29, Ian Collins<ian-n...@hotmail.com>  wrote:
>
>>
>> int absCompare( const void* a, const void* b )
>> {
>>     int i = abs(*(int*)a);
>>     int j = abs(*(int*)b);
>>
>>     if (i>  j)
>>       return 1;
>>     if (i<  j)
>>       return -1;
>>     return 0;
>>
>> }
>>
>> reduces to
>>
>> bool absComp( int i, int j )
>> {
>>     return abs(i)<  abs(j);
>>
>> }
>>
>
> abs(i)<  abs(j) returns 0 or 1
>
> What about -1 ?

C++ sort only requires "does i come before j" which is why it can be 
used with any type with a less then operator.  That's why I said the 
sentence you snipped; Take the function you would pass to qsort(), 
simplify it to return a boolean result and use it.

-- 
Ian Collins

On 10 sep, 22:14, Ian Collins <ian-n...@hotmail.com> wrote:

> C++ sort only requires "does i come before j" which is why it can be
> used with any type with a less then operator. =A0That's why I said the
> sentence you snipped; Take the function you would pass to qsort(),
> simplify it to return a boolean result and use it.

Ok, got it

"Seebs" <usenet-nospam@seebs.net> wrote in message 
news:slrni8kopi.2rn.usenet-nospam@guild.seebs.net...
> On 2010-09-10, lawrence.jones@siemens.com <lawrence.jones@siemens.com> 
> wrote:
>> Because it's excruciatingly difficult to know exactly when it would be
>> advantageous to do so for most library functions, and it would likely
>> never be advantageous for many.  The no-brainers like memcpy and strcmp
>> already are implemented as built-ins in many implementations.
>
> This isn't directly relevant, because it's really fairly system-specific,
> but we once encountered a delightful bug caused by a compiler being used
> in freestanding mode.
>
> Long story short:  In some cases, when given predictable-enough string
> arguments, gcc will turn strcmp(foo, "bar") into memcmp(foo, "bar", 4),
> and the like.  Or memchr("foo", x) into memchr("foo", x, 3).  Or, and
> this is the kicker, strcpy(foo, "bar") into memcpy(foo, "bar", 4).
>
> Someone wrote something "clever", roughly to the effect of:
>
> strcat(strcpy(foo, "start: "), end);
>
> gcc did its magic.
>
> Unfortunately, it was working in a freestanding environment, where the
> str* and mem* functions had been provided by the code it was working on,
> and someone else who was *also* being excessively clever had realized that
> you could save an ENTIRE INSTRUCTION from the execution of memcpy by
> always returning 0 instead of returning the "unused" return value.
>
> Clever programmers, causing things to blow up without warning since the
> 60s.
>

yep.


my compiler handles some cases as special builtins as well.

my compiler had typically expanded fixed-size memcpy into a range of 
register-based operations (including SSE).

so, for example:
memcpy(src, dst, 20);

could become, essentailly (src/dst are placeholders):
movdqu xmm0, [src]
movdqu [dst], xmm0
mov eax, [src+16]
mov [dst+16], eax

then another compiler translates this sort of thing to, essentially:
lea esi, [src]
lea edi, [dst]
mov ecx, 20
rep movsb

with essentially *no* real performance cost vs the prior...

I later realized a trick when writing an x86 interpreter:
one doesn't actually have to execute this instruction verbatim, as since all 
properties are known, it is possible to short-cut the logic in many cases 
and move the bytes in whatever way is most convinient.


in many cases, micro-optimization is a trap...
be careful or be snared.

On Sep 10, 2:27=A0pm, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
>=A0Every "call" to printf() would just plop the
> entire printf() source right down at the call point
>
When we write

printf("Hello world, my name is %s\n', fred);

which is not untypical, we are only using a tiny subset of printf()'s
fucntionality. Inelligent and aggressive optiminsation of the
constants could certainly save a great deal of space and time.

On 9/10/2010 12:55 PM, Chris Noonan wrote:
> On Sep 10, 12:27 pm, Eric Sosman<esos...@ieee-dot-org.invalid>  wrote:
>> On 9/10/2010 6:58 AM, Chris Noonan wrote:
>>
>>> The mystery is why implementations generally don't treat
>>> "library functions" as built-ins when it would be advantageous to
>>> do so. A good opportunity arises when a malloc() and its corresponding
>>> free() lie within the same function; calls to the heap manager can be
>>> replaced with allocation on the stack.
>>
>>       Since the stack often has far less space available than the heap,
>> this could fail rather badly for large allocations.
>
> I wasn't proposing an unbreakable rule. I envisaged an optimising
> compiler making sensible decisions. If size is a problem on a
> particular architecture, the compiler may be able to determine
> statically that the requested size is bounded above. Otherwise it can
> emit code to branch on the size. For malloc the gains are worthwhile,
> they go beyond inlining. As well as replacing a call to an intricate
> function with as few as two opcodes, you are reducing (in a small way)
> heap fragmentation and possibly avoiding a bus-locking instruction.

     A compiler that could make the decision reliably would need an
awful lot of smarts.  Consider that the function f() containing the
malloc(100) call might be at the bottom of a l-o-n-g call chain of
other functions that have chewed up unknown amounts of stack space;
f() might even be directly or indirectly recursive.  I suspect that a
practical compiler would only be able to apply this transformation
safely for static functions in the same translation unit as main(),
which might somewhat restrict the benefits ...

     Also, I don't find the benefits all that convincing.  If you've
got to make a run-time decision about whether the malloc(size) call
plucks from the heap or from the stack, then you've got to make some
provision for the corresponding free(): it might be an ordinary free(),
or it might be a pop-and-forget, depending on the choice made at the
malloc() point, which needs to be remembered somewhere, and ...  The
additional machinery to support the "optimization" is not free.

     Finally, if what you really want is an automatically-managed
block-scoped allocation, you've already got it: The variable-length
array is just what you asked for.  Personally, I think the VLA is a
snare of Satan -- but you Devil-worshipers mayn't mind that ;-)

-- 
Eric Sosman
esosman@ieee-dot-org.invalid