smuggling data in and out of alarm handlers and the like

[David Mathog]

Every so often I find a need to move data in or out of functions which
are not called directly. For instance, alarm handlers or the compare
function used by qsort. In these cases there is no possibility of
passing the data as a function parameter, so it needs to be "smuggled"
in.

Is there a better way of doing this than the three methods described below?

1. use global variables. This is fine for small monolithic programs
but isn't great in larger programs using lots of code in separate
files and/or shared libraries.

2. create a function like this:

SOME_STRUCT *smuggle_pointe r(SOME_STRUCT *pointer){
static SOME_STRUCT *hold_pointer;
if(pointer)hold _pointer = pointer;
return(hold_poi nter);
}

and load it with data before any possible calls to the
problem functions. The target function contains:

SOME_STRUCT *pointer;
pointer = smuggle_pointer (NULL);

which gives that function access to this data.

3. use setenv/getenv. This is not part of ANSI C, but is
usually available. Only useful for one or two simple
values.
Is there a better way?

Thanks,

David Mathog

[Keith Thompson]

James Kuyper <ja*********@ve rizon.netwrites :

santosh wrote:

>Robert Latest wrote:

>>Paul Hsieh wrote:
But again, we don't care about qsort, since you should never use it
anyways (its always slow, always algorithmically sub-optimal, and
always inflexible -- qsort is just one of many examples of where its
clear that the C-library was designed by amateurs.)
I can't find the passage in the C standard that requires the qsort
function to be implemented in some way or another.

Nevertheless it's interface cannot be changed, which is what, I think,
Paul Hsieh was talking about.

You can't derive the conclusion that qsort() is "... always slow,
always algorithmically sub-optimal, ..." from the interface
specification, or indeed from anything else that the standard says
about qsort().

No you can't (except that using a callback function for each
comparison is bound to impose some overhead). But I don't think Paul
did so. I suspect that he based his conclusion on observations of
actual qsort() implementations .

Whether Paul's conclusion is correct is a different matter.

--
Keith Thompson (The_Other_Keit h) <ks***@mib.or g>
Looking for software development work in the San Diego area.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[CBFalconer]

Paul Hsieh wrote:

>

.... snip ...

>
By this criteria, qsort() is basically broken since the cmp()
function has no simple way to gain access to the contextual state.
Fortunately, its fairly easy and straightforward to write your own
sort. (Probably *more* fortunately, being forced to do so will
make you realize that the sort function should be a macro, not a
function call. This allows your "cmp" to itself be a macro, and
thus eliminate the major cost of qsort(), and you can pass
contextual parameters to macros just as easily as to functions.)

Utter bushwah. Qsort and similar operations are normally
precompiled, and will attempt to call a routine passed in via a
parameter. This cannot be a macro. All you will get is a bunch of
linkage errors or a total blowup, depending on the sophistication
of the linker.

--
Merry Christmas, Happy Hanukah, Happy New Year
Joyeux Noel, Bonne Annee.
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home .att.net>

--
Posted via a free Usenet account from http://www.teranews.com

[Keith Thompson]

CBFalconer <cb********@yah oo.comwrites:

Paul Hsieh wrote:

>>

... snip ...

>>
By this criteria, qsort() is basically broken since the cmp()
function has no simple way to gain access to the contextual state.
Fortunately, its fairly easy and straightforward to write your own
sort. (Probably *more* fortunately, being forced to do so will
make you realize that the sort function should be a macro, not a
function call. This allows your "cmp" to itself be a macro, and
thus eliminate the major cost of qsort(), and you can pass
contextual parameters to macros just as easily as to functions.)

Utter bushwah. Qsort and similar operations are normally
precompiled, and will attempt to call a routine passed in via a
parameter. This cannot be a macro. All you will get is a bunch of
linkage errors or a total blowup, depending on the sophistication
of the linker.

Clearly the cmp operation used by qsort() can't be a macro, since it
has to be passed to qsort() as an argument of a pointer-to-function
type. I don't think Paul was claiming otherwise.

But if you write *your own* sort routine, as Paul suggests, then the
comparison routine can easily be a macro, or even simple inline code.
Such a sort routine would lack qsort()'s flexibility, in that it would
only be able to sort arrays of a single type.

qsort() pays for its flexibility (being able to sort arrays of any
type) with a loss of efficiency (due to the indirect calls to the
comparison routine). Sometimes this cost is worth paying, sometimes
it isn't. (A language with a template facility could give you the
best of both. Even in C, you *might* be able to define the entire
sorting routine as a macro, but it's not something I'd care to try.)

As for letting the comparison function have access to contextual
state, yes, that's a limitation of qsort(), and one that could be
fixed without losing its flexibility. But adding an extra required
parameter to the comparison routine would likely cause another small
loss of performance.

There are open-source C implementations of qsort(). If you need
something that the standard qsort() doesn't provide, you can always
grab one of them and modify it to your taste. Nothing in the C
standard says that qsort() is the only way to sort things.

--
Keith Thompson (The_Other_Keit h) <ks***@mib.or g>
Looking for software development work in the San Diego area.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Paul Hsieh]

On Dec 20, 12:30 pm, Keith Thompson <[e-mail] rote:

CBFalconer <cbfalco...@yah oo.comwrites:

Paul Hsiehwrote:

... snip ...

By this criteria, qsort() is basically broken since the cmp()
function has no simple way to gain access to the contextual state.
Fortunately, its fairly easy and straightforward to write your own
sort. (Probably *more* fortunately, being forced to do so will
make you realize that the sort function should be a macro, not a
function call. This allows your "cmp" to itself be a macro, and
thus eliminate the major cost of qsort(), and you can pass
contextual parameters to macros just as easily as to functions.)

Utter bushwah. Qsort and similar operations are normally
precompiled, and will attempt to call a routine passed in via a
parameter. This cannot be a macro. All you will get is a bunch of
linkage errors or a total blowup, depending on the sophistication
of the linker.

Clearly the cmp operation used by qsort() can't be a macro, since it
has to be passed to qsort() as an argument of a pointer-to-function
type. I don't think Paul was claiming otherwise.

But if you write *your own* sort routine, as Paul suggests, then the
comparison routine can easily be a macro, or even simple inline code.
Such a sort routine would lack qsort()'s flexibility, in that it would
only be able to sort arrays of a single type.

Really?

#define hsortT(type, context, array, length, cmpT) ... \
#define cmpT(type, context, el1, el2) ... \

I *DO* this all the time. The point is that this is the *MOST*
flexible solution. Even if you *wanted* to use function callbacks,
you just fill them into the macros:

#define typeCmp(type, context, el1, el2) cmpPOS (context, el1, el2)

void PaycostofcallOv erheadSort_type (
void * context,
type * array,
size_t len,
int (*cmpPOS) (void * context, type * el1, type * el2))
{
hsortT (type, context, array, len, typeCmp);
}

Of course, there's little point in doing this, but you can't claim its
less flexible than qsort.

qsort() pays for its flexibility (being able to sort arrays of any
type) with a loss of efficiency (due to the indirect calls to the
comparison routine). Sometimes this cost is worth paying, sometimes
it isn't.

Its worth paying if you don't care about performance. The only case
where qsort offers any compensating use is when in a single program
you are sorting very many, widely varied types, and you could care
less about its performance. (Maybe a proof of concept of something
running on an embedded system or something like that.)

[...] (A language with a template facility could give you the
best of both. Even in C, you *might* be able to define the entire
sorting routine as a macro, but it's not something I'd care to try.)

Why not? It really is not that hard. I mean, the only challenge is
writing a sort, which, for real computer programmers ... well it was
supposed to be an exercise in college. If you were asleep during
those classes, you can pull stuff from the web.

As for letting the comparison function have access to contextual
state, yes, that's a limitation of qsort(), and one that could be
fixed without losing its flexibility. But adding an extra required
parameter to the comparison routine would likely cause another small
loss of performance.

Thus maximizing the mediocrity of their solution. Its neither fast,
nor flexible.

There are open-source C implementations of qsort().

Lol! Ever watch the movie Office Space? Where they are looking up
the definition of "money laundering" in the dictionary? That's what
looking up open source for qsort() reminds me of.

[...] If you need
something that the standard qsort() doesn't provide, you can always
grab one of them and modify it to your taste. Nothing in the C
standard says that qsort() is the only way to sort things.

Sorting without a guarantee on the lower bound of performance and
necessarily paying an unnecessary overhead cost -- it makes you wonder
why computer science is even taught in universities at all.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[lawrence.jones]

Keith Thompson <ks***@mib.orgw rote:

>
qsort() pays for its flexibility (being able to sort arrays of any
type) with a loss of efficiency (due to the indirect calls to the
comparison routine).

There's no reason an implementation can't inline qsort() and once you do
that, you can also inline the comparison function.

-Larry Jones

My upbringing is filled with inconsistent messages. -- Calvin

[Keith Thompson]

la************@ siemens.com writes:

Keith Thompson <ks***@mib.orgw rote:

>qsort() pays for its flexibility (being able to sort arrays of any
type) with a loss of efficiency (due to the indirect calls to the
comparison routine).

There's no reason an implementation can't inline qsort() and once you do
that, you can also inline the comparison function.

[I'm piggybacking this followup off my own message, so the Reference
header isn't going to be quite right. Larry's followup appears on the
server where I read news, but not on the one where I post.]

Yes, I believe you're right.

I would think that inlining an indirect call (one made via a function
pointer parameter) would be more difficult than inlining an ordinary
call. Do any implementations actually do this?

Of course, it's still possible to write a qsort() call for which the
comparison function can't be inlined, for example by passing an
expression, rather than just a function name, for the compar
parameter. But a sufficiently clever compiler could certainly handle
that.

--
Keith Thompson (The_Other_Keit h) <ks***@mib.or g>
Looking for software development work in the San Diego area.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[lawrence.jones]

Keith Thompson <ks***@mib.orgw rote:

>
I would think that inlining an indirect call (one made via a function
pointer parameter) would be more difficult than inlining an ordinary
call. Do any implementations actually do this?

In C, function calls are always made via a pointer. And in the case of
qsort(), the argument corresponding to the pointer parameter is nearly
always a function designator (i.e., the name of a function as opposed to
a pointer variable), so it shouldn't be any more difficult to inline
than any other function call. But I don't know of any implementations
that actually inline qsort(), presumably because its performance isn't
critical often enough to be worth while.

-Larry Jones

Mr. Subtlety drives home another point. -- Calvin

[Keith Thompson]

la************@ siemens.com writes:

Keith Thompson <ks***@mib.orgw rote:

>I would think that inlining an indirect call (one made via a function
pointer parameter) would be more difficult than inlining an ordinary
call. Do any implementations actually do this?

In C, function calls are always made via a pointer. And in the case of
qsort(), the argument corresponding to the pointer parameter is nearly
always a function designator (i.e., the name of a function as opposed to
a pointer variable), so it shouldn't be any more difficult to inline
than any other function call. But I don't know of any implementations
that actually inline qsort(), presumably because its performance isn't
critical often enough to be worth while.

[ Again, I'm piggybacking this onto my own article, since Larry's
article isn't on this server. It looks like Larry's articles aren't
showing up on aioe.org. Perhaps homeip.net, like rr.com, is under a
UDP? ]

Yes, but if it's simpler in assembly or machine code to call a
function directly than to call it indirectly via a pointer object or
value, then presumably the fact that ``func(42)'' involves a
conversion of ``func'' to a pointer goes away early in the compilation
process. C function calls are always done via pointers, but the
compiler doesn't have to treat them that way, as long as the same
effect is achieved.

qsort()'s comparison function argument is typically a simple function
designator, but if the qsort() call is inlined, then it's probably
going to look like the designator is converted to a pointer, then
copied to a local object (the parameter object), then used in an
indirect call. Of course any optimizer worth its salt will collapse
that into a simple call, which can then be inlined. So yes, I agree.

Going off on a bit of a tangent, paul Hsieh said elsewhere in this
thread that the overhead imposed by qsort() is acceptable only if you
don't care about performance. I disagree. In my opinion, the
overhead is acceptable if it doesn't significantly affect the
performance of the particular program you're using it in. The saving
in programming effort (avoiding the time needed either to write your
own sorting routine or find one elsewhere), and in risk (getting the
sorting routine wrong), often (but by no means always) can outweigh
the performance penalty.

And if you think that a sorting routine is simple enough that there's
no significant risk of getting it wrong, consider this (Jon Bentley,
"Programmin g Pearls"):

While the first binary search was published in 1946, the first
binary search that works correctly for all values of n did not
appear until 1962.

The most reliable code is the code that isn't there.

--
Keith Thompson (The_Other_Keit h) <ks***@mib.or g>
Looking for software development work in the San Diego area.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Paul Hsieh]

On Dec 22, 1:04 pm, Keith Thompson <[e-mail] rote:

[...]
And if you think that a sorting routine is simple enough that there's
no significant risk of getting it wrong, consider this (Jon Bentley,
"Programmin g Pearls"):

While the first binary search was published in 1946, the first
binary search that works correctly for all values of n did not
appear until 1962.

The most reliable code is the code that isn't there.

So you think compiler vendors implement qsort() without any code?
qsort() also mashes things through void * pointers, which means you
*LOSE* type safety -- so this introduces other risk to the code.

All this is besides the point that you just equated sorting with
binary search.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Keith Thompson]

Paul Hsieh <we******@gmail .comwrites:

On Dec 22, 1:04 pm, Keith Thompson <[e-mail] rote:

>[...]
And if you think that a sorting routine is simple enough that there's
no significant risk of getting it wrong, consider this (Jon Bentley,
"Programmin g Pearls"):

While the first binary search was published in 1946, the first
binary search that works correctly for all values of n did not
appear until 1962.

The most reliable code is the code that isn't there.

So you think compiler vendors implement qsort() without any code?

Of course not -- but it's code that *I* don't have to write. A bug in
a sort routine that I write (and test as much as I have time for) is
more likely than a bug in a vendor's qsort() routine that's been used
by zillions[*] of other programmers. That's not to say that a bug in a
vendor's code is impossible, of course.

I've never heard of a buggy qsort() in a released implementation of
the C standard library. Have you?

qsort() also mashes things through void * pointers, which means you
*LOSE* type safety -- so this introduces other risk to the code.

A valid point. You have to be careful in how you invoke qsort(), and
in how you write the comparison routine. I still think that using
qsort() is less error-prone than writing your own specialized sorting
routine (but sometimes the risk is worth it).

All this is besides the point that you just equated sorting with
binary search.

That was not my intent. I'd say that sorting and binary search are
tasks of comparable complexity. The observation that it took 16 years
to get binary search right was an illustration, not a proof.
[*] 1.21 zillion, on average, according to a recent survey.

--
Keith Thompson (The_Other_Keit h) <ks***@mib.or g>
[...]
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"