J
Jirka Klaue
Carsten Hansen wrote:
....
I see. Seems to be pretty efficient now, too.
Jirka
....
I see. Seems to be pretty efficient now, too.
Jirka
P
Peter Nilsson
Martin Ambuhl said:
Inline functions yes; but functions, in C, not always.
My problem was not realising that the OP cross posted. My Bad.
I was reading it in clc and concentrated on "Can someone please share
a #define macro or something..." in the OP's post.
[I really don't know why people using C++ also ask C groups for
solutions when the answers are highly likely to involve different
paradigms and/or language constructs.]
Anyway, my mistake...
FWIW, C99 has its own version of inline functions too.
R
Ron Natalie
Peter Nilsson said:
The typical min is inlined to something like
a < b ? a : b
There's always two comparisons. Tests show no speed difference
between the two on my machine.
A
Arthur J. O'Dwyer
Are you using functions, or macros? I'm sure that Peter
was referring to the use of macros, in C -- *not* C++, for
the benefit of those reading in c.l.c++.
So we have, without the usual parentheses since they'd just
clutter the example:
#define min(a,b) ((a < b)? a: b)
#define min3_inefficient(a,b,c) min(a, min(b, c))
#define min3_better(a,b,c) (a < b)? min(a, c): min(b, c)
min3_inefficient(X, Y, Z) becomes
min(X, ((Y < Z)? Y: Z))
((X < ((Y < Z)? Y: Z))? X: ((Y < Z)? Y: Z)))
min3_better(X, Y, Z) becomes
((X < Y)? ((X < Z)? X: Z): (Y < Z)? Y: Z)
In this case, even though both expansions contain the same
number of < and ? characters, the "inefficient" version has
poorer control flow -- three conditionals are evaluated
fully 2/3 of the time, whereas with the "better" version
only two conditionals are ever executed.
<C++ only>
With C++ template functions, of course, it doesn't matter
so much. But if you're interested in efficiency, why are
you using functions? ;-)
</C++>
-Arthur
B
Ben Pfaff
Irrwahn Grausewitz said:
So any proposed solutions should work in both C and C++.
I
Irrwahn Grausewitz
Ben Pfaff said:
And one who is cross-posting complaints about off-topicality of
cross-posted replies to cross-posted questions should make clear
what the word "here" is referring to in this context.
R
Ron Natalie
Arthur J. O'Dwyer said:
I used inline functions. It's even worse if he used macros as
the expressions passed are possibly evaluated more than once.
It's beyond me what you mean by that. Both times execute
the comparison twice, as a result the select. You can make
up your own idea of the cost of the flow between the two, but
as I said, it;s negligable. Both functions on the Sun compiler
take the same amount of time.
Templates have no bearing on this situation at all. You could
as easily code this as functions taking doubles without templates
and the answer would be the same.
G
Glen Herrmannsfeldt
(snip)
Good compilers do common subexpression elimination, and hopefully will
notice that (Y<Z) occurs twice.
In any hand optimization problem, the question is always what will the
compiler find at want won't it find.
-- glen
Good compilers do common subexpression elimination, and hopefully will
notice that (Y<Z) occurs twice.
In any hand optimization problem, the question is always what will the
compiler find at want won't it find.
-- glen
A
Arthur J. O'Dwyer
True; however, he did mention the *usual* definition of 'min',
which IME is more often than not as a macro.
Brain fart?
Unsnipped from my previous post:
min3_inefficient(X, Y, Z) becomes
min(X, ((Y < Z)? Y: Z))
((X < ((Y < Z)? Y: Z))? X: ((Y < Z)? Y: Z)))
min3_better(X, Y, Z) becomes
((X < Y)? ((X < Z)? X: Z): (Y < Z)? Y: Z)
Suppose X is the least of the three... then
min3_inefficient compares Y to Z
then compares X to min(Y,Z)
min3_better compares X to Y
then compares X to Z
Suppose Y is the least of the three... then
min3_inefficient compares Y to Z
then compares X to Y
then compares Y to Z
min3_better compares X to Y
then compares Y to Z
Suppose Z is the least of the three... then
min3_inefficient compares Y to Z
then compares X to Z
then compares Y to Z
min3_better compares X to Y
then compares min(X,Y) to Z
See? min3_better makes exactly 2 comparisons in each case,
while min3_inefficient makes 3 comparisons fully 2/3 of the
time, as I said. Thus min3_inefficient *is* less efficient,
because it computes useless comparisons.
Try running them more than once.
(But before doing that, take a look at the generated machine
code. I would not be surprised if the GCC folks have optimized
this particular computation, so the Sun folks might have too.)
....except in the case where you wanted to compare pointers.
Or C++ std::strings. Or 'long longs'. Or practically anything
that wasn't a double.
(Which, incidentally, is why the most common implementation of
'min' is as a macro -- because C macros can do things that C
functions can't.)
-Arthur
R
Ron Natalie
Arthur J. O'Dwyer said:
Maybe it is in C, but it certainly IS NOT in C++.
It is for the ugly macros, as I was saying, for inline functions it does
not need to generate a bogus third test.
P
pete
Ron said:
The following macro is a paradigm in C:
#define max(a, b) ((a) > (b) ? (a) : (b))
P
pete
Arthur said:
It's illogical to remove required parentheses
and then insert extra one's that you like.
Minimally but correctly parenthesized:
#define min(a, b) ((b) > (a) ? a : (b))
A
Arthur J. O'Dwyer
[Removed c.l.c++ cross-post]
Well, the usual parentheses would just have cluttered the
example. (Remember, I was trying to display the control
flow succinctly, not show how nicely I could mimic the
preprocessor by hand!) I had originally removed the outer
parentheses as well, but then realized that that would
have produced an incorrect expansion. So I had to keep
them.
Your version is indeed the correct way to parenthesize
the macro in the general case, although I'd throw an
extra pair of parentheses around the second 'a', too,
just for paranoia's sake.
-Arthur
Well, the usual parentheses would just have cluttered the
example. (Remember, I was trying to display the control
flow succinctly, not show how nicely I could mimic the
preprocessor by hand!) I had originally removed the outer
parentheses as well, but then realized that that would
have produced an incorrect expansion. So I had to keep
them.
Your version is indeed the correct way to parenthesize
the macro in the general case, although I'd throw an
extra pair of parentheses around the second 'a', too,
just for paranoia's sake.
-Arthur
B
bd
Jirka said:
No, it's not. Taking the minimum of N values takes time proportional to
O(N). Sorting them takes O(Nlog(N)). Try:
#include <stdlib.h>
float fmin(size_t n, float *values) {
float min = values[0];
size_t i;
for(i = 1; i < n; i++){
if(values < min)
min = values;
}
return min
}
J
Jirka Klaue
bd said:
It's not what? Not scalable? Sure it is.
Jirka