optimizing an expression

[Tim Streater]

No, it is not pot and kettle. If you sequence the posts, it is
consistently Richard Heathfield who starts the campaign of personality
destruction. I finish it and will continue to do so because "this
animal is dangerous, it defends itself when attacked."

So you agree you are childish, then, and that you have no place here? As
in:

 

[Mark Bluemel]

We must have wildly different ideas about readability. To me readable
code is code that expresses intent clearly. "Programs are meant to be
read by humans and only incidentally for computers to execute".

Thank you. That's pretty much what I feel. I'd kind of like to see a
book published on "expressive coding".

 

[spinoza1111]

So you agree you are childish, then, and that you have no place here? As
in:

No. This is because people have a right to defend themselves like men,
something which boys will never learn.

 

[Keith Thompson]

Also, the former is undefined if abs(x) can't be represented which is
a practical concern on many machines when x == INT_MIN.

<snip>

Good point. I knew there was *something* else that bothered me
about that, but I couldn't quite put my finger on it.

Another thing: The OP needs to decide exactly what he's trying to
accomplish. He's presented two expressions that aren't actually
equivalent, and asked for a way to do the same thing (which?) more
efficiently.

First, describe the problem correctly and unambiguously. Either
English, pseudoc-code, or straightforward C will do for this.
Second, implement it correctly (if you chose C for step 1, you're
done, but then you can't compare the code against the specification,
since they're the same). Nth, for some larger value of N, optimize
the code (N might well exceed the number of steps worth doing
at all). Xth, for some *very* large X, worry about expressing it
in a single expression. As I mentioned, step X can be necessary
if you're writing ia macro.

 

[spinoza1111]

We must have wildly different ideas about readability. To me readable
code is code that expresses intent clearly. "Programs are meant to be
read by humans and only incidentally for computers to execute".

x -= (x>0)-(x<0);

does not express intent clearly.  One can work out what it does quite
easily, but that's still work. It's all about "how" and not about
"why".

/* ... or a macro, obviously ... */
static inline int signum (int x){
  return (x>0)-(x<0);}

/* ... */
x -= signum(x);

is the best of both worlds.

Good, you're using my word. I like that, not because I'm vain
(although I am) but because somebody other than me has seen that the
OP is probably trying to implement signum, and signum is zero for
zero.

I also realize that I should have used inline int with a strongly
typed parameter as opposed to a macro.

Keep up the good work.

 

[Keith Thompson]

I think we'd all agree that "cutesy" shortcuts to achieve a
false keystroke economy are wrong, but this statement goes much
too far. It seems to assume that "if else" is more readable
than "? :" but that should *not* be the case for a C programmer.

I was referring specifically to cases where a ?: operator appears at
the top level of a statement expression, and the second and third
operands' results are discarded. For example:

condition ? puts("A message") : puts("Another message");

In my opinion, using ?: here is just silly; it's better written as:

if (condition) {
puts("A message");
}
else {
puts("Another message");
}

or whatever brace style you prefer. In cases like this, the use of
the ?: operator tells me "I know what the ?: operator is, and you
should be impressed."

I often string together ?, : and/or && and || into an involved
expression, and add newlines and tabs to make it easy to read.
IMHO the if/else equivalent would be harder to read because of
all the "if/else" clutter.

Can you give an example? If it doesn't meet the criteria I mentioned
above, so that the transformation from ?: to if-else is absolutely
trivial, I probably wouldn't object. I don't find "if" and "else" to
be clutter; they're just part of the code.

(But tabs? Spaces only, please.)

 

[Tim Streater]

I was referring specifically to cases where a ?: operator appears at
the top level of a statement expression, and the second and third
operands' results are discarded. For example:

condition ? puts("A message") : puts("Another message");

In my opinion, using ?: here is just silly; it's better written as:

if (condition) {
puts("A message");
}
else {
puts("Another message");
}

I don't think I agree with this. For such a simple case, something like:

puts condition ? "A message" : "Another message";

is much less clutter and more readable.

 

[Stefan Ram]

You invented the term signum? Cool.

It is the latin word for »sign«.

»The symbol [a], to represent 0, 1, or -1, according to
whether a is 0, positive, or negative, was introduced by
Leopold Kronecker (1823-1891). He wrote:

Bezeichnet man naemlich mit [a] den
Werth Null oder +1 oder -1, je nachdem
die reelle Groesse a selbst gleich Null
oder positiv oder negativ ist ...
[February 14, 1878]«

http://www.luigigobbi.com/EarliestUsesOfSymbolsOfOperation/

Interestingly I learned it from John Nash while we were
briefly contestants on "Play Your Cards Right", in 1971. It
was around this time that I also invented cheez-whiz, price
comparison websites and the leg-before-wicket law.

From life one can learn that ideas are cheap.

The successful people are not the ones with ideas,
but the ones with the ability to turn ideas into
products and to do proper marketing for these product.

These people never or hardly ever use their time
to think about »optimizing an expression«, unless
they have indeed determined that the execution speed
of their product is a hindrance in marketing and
then used a profiler to determine that this expression
indeed is critical for performance.

That is, if we measure »success« by incoming money.

If we measure »success« by the pleasure gained by
optimizing an expression solely for the fun of doing
it, we get yet another story.

 

[Keith Thompson]

I don't think I agree with this. For such a simple case, something like:

puts condition ? "A message" : "Another message";

is much less clutter and more readable.

And a syntax error.

I think you mean:

puts(condition ? "A message" : "Another message");

I suppose there's some benefit in writing the function name only once.
Personally I still prefer the if-else form, but I see the point.

Ok, how about this:

if (x_has_been_set) {
printf("x = %d\n", x);
}
else {
puts("x has not been set");
}

I've seen people who would write that as:

x_has_been_set ? printf("x = %d\n", x) : puts("x has not been set");

which, IMHO, is absurd.

 

[Tim Streater]

And a syntax error.



I think you mean:

puts(condition ? "A message" : "Another message");

Yes, very likely. I haven't written C for 20 years. I write PHP and
JavaScript these days, both of which include this construct.

I suppose there's some benefit in writing the function name only once.
Personally I still prefer the if-else form, but I see the point.

Ok, how about this:

if (x_has_been_set) {
printf("x = %d\n", x);
}
else {
puts("x has not been set");
}

I've seen people who would write that as:

x_has_been_set ? printf("x = %d\n", x) : puts("x has not been set");

which, IMHO, is absurd.

Well - there it is!

 

[James Dow Allen]

I was referring specifically to cases where a ?: operator appears at
the top level of a statement expression, ...

Sorry, I didn't mean to misconstrue what you were saying.

Can you give an example?

OK, but let me confess that I really don't know what
is the *best* way to place white-space in code like this.
(And I normally don't scrunch "a < b" down to "a<b",
but isn't that a good way to make such code slightly
more readable?)

/* Return the median of 3 numbers */
int median3(int a, int b, int c)
{
return a<b ? b<c ? b
: a<c ? c : a
: c<b ? b
: c<a ? c : a;
}

This example may be too tame for much controversy.
I *would* post a more interesting example than this
one, but for that I'd want to be in a coffee-shop
with you all saying "Hello, James!" after I say,
"My name is James, and I write funny-looking C code."

James Dow Allen

 

[user923005]

/* Return the median of 3 numbers */
int median3(int a, int b, int c)
{
      return a<b ? b<c ? b
                : a<c ? c : a
           : c<b ? b
                : c<a ? c : a;
}

I love ASCII art.  What's it supposed to be?

Rven with that relatively simple construct, I have to mentally insert
brackets before I convince myself its correct.  If the expressions get
ever more complicated, I'm ever more glad that I don't have to
maintain that code.

int median3(int a, int b, int c)
{
   if(a < b){
     if(b < c) return b;  /* a b c */
     if(c < a) return a;  /* c a b */
     return c;            /* a c b */
   } else {
     if(a < c) return a;  /* b a c */
     if(c < b) return b;  /* c b a */
     return c;            /* b c a */
   }

}

That, to me, is more clearly correct[0], at the cost of a lot more typing..

[0] which guarantees that I've cocked it up.

I think that if you attach a unit test, then it is easy to be
confident about the alternate form:

typedef int e_type;

e_type median3(e_type a, e_type b, e_type c)
{
return (a < b) ? ((b < c) ? b : ((a < c) ? c : a)) : ((a < c) ?
a : ((b < c) ? c : b));
}

#ifdef UNIT_TEST

int main(void)
{
e_type i,
j,
k,
m;
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
for (k = 0; k < 3; k++) {
m = median3(i, j, k);
printf("median of %d %d %d is %d\n", i, j, k, m);
}
return 0;
}

#endif
/*
median of 0 0 0 is 0
median of 0 0 1 is 0
median of 0 0 2 is 0
median of 0 1 0 is 0
median of 0 1 1 is 1
median of 0 1 2 is 1
median of 0 2 0 is 0
median of 0 2 1 is 1
median of 0 2 2 is 2
median of 1 0 0 is 0
median of 1 0 1 is 1
median of 1 0 2 is 1
median of 1 1 0 is 1
median of 1 1 1 is 1
median of 1 1 2 is 1
median of 1 2 0 is 1
median of 1 2 1 is 1
median of 1 2 2 is 2
median of 2 0 0 is 0
median of 2 0 1 is 1
median of 2 0 2 is 2
median of 2 1 0 is 1
median of 2 1 1 is 1
median of 2 1 2 is 2
median of 2 2 0 is 2
median of 2 2 1 is 2
median of 2 2 2 is 2
*/

 

[user923005]

I love ASCII art.  What's it supposed to be?

Rven with that relatively simple construct, I have to mentally insert
brackets before I convince myself its correct.  If the expressions get
ever more complicated, I'm ever more glad that I don't have to
maintain that code.

int median3(int a, int b, int c)
{
   if(a < b){
     if(b < c) return b;  /* a b c */
     if(c < a) return a;  /* c a b */
     return c;            /* a c b */
   } else {
     if(a < c) return a;  /* b a c */
     if(c < b) return b;  /* c b a */
     return c;            /* b c a */
   }

}

That, to me, is more clearly correct[0], at the cost of a lot more typing.

[0] which guarantees that I've cocked it up.

I think that if you attach a unit test, then it is easy to be
confident about the alternate form:

typedef int     e_type;

e_type          median3(e_type a, e_type b, e_type c)
{
    return (a < b) ? ((b < c) ? b : ((a < c) ? c : a)) : ((a < c) ?
a : ((b < c) ? c : b));

}

#ifdef UNIT_TEST

int             main(void)
{
    e_type          i,
                    j,
                    k,
                    m;
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++)
            for (k = 0; k < 3; k++) {
                m = median3(i, j, k);
                printf("median of %d %d %d is %d\n", i, j, k, m);
            }
    return 0;

}

#endif
/*
median of 0 0 0 is 0
median of 0 0 1 is 0
median of 0 0 2 is 0
median of 0 1 0 is 0
median of 0 1 1 is 1
median of 0 1 2 is 1
median of 0 2 0 is 0
median of 0 2 1 is 1
median of 0 2 2 is 2
median of 1 0 0 is 0
median of 1 0 1 is 1
median of 1 0 2 is 1
median of 1 1 0 is 1
median of 1 1 1 is 1
median of 1 1 2 is 1
median of 1 2 0 is 1
median of 1 2 1 is 1
median of 1 2 2 is 2
median of 2 0 0 is 0
median of 2 0 1 is 1
median of 2 0 2 is 2
median of 2 1 0 is 1
median of 2 1 1 is 1
median of 2 1 2 is 2
median of 2 2 0 is 2
median of 2 2 1 is 2
median of 2 2 2 is 2
*/

Showing both methods:

typedef int e_type;

e_type median3(e_type a, e_type b, e_type c)
{
return (a < b) ? ((b < c) ? b : ((a < c) ? c : a)) : ((a < c) ?
a : ((b < c) ? c : b));
}

int median3a(int a, int b, int c)
{
if (a < b) {
if (b < c)
return b; /* a b c */
if (c < a)
return a; /* c a b */
return c; /* a c b */
} else {
if (a < c)
return a; /* b a c */
if (c < b)
return b; /* c b a */
return c; /* b c a */
}
}


#ifdef UNIT_TEST

int main(void)
{
e_type i,
j,
k,
m,
m2;
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
for (k = 0; k < 3; k++) {
m = median3(i, j, k);
printf("median of %d %d %d is %d\n", i, j, k, m);
m2 = median3a(i, j, k);
printf("median of %d %d %d is %d\n", i, j, k, m2);
if (m2 != m)
printf("Disagreement of %d verses %d\n", m2, m);
}
return 0;
}

#endif
/*
median of 0 0 0 is 0
median of 0 0 0 is 0
median of 0 0 1 is 0
median of 0 0 1 is 0
median of 0 0 2 is 0
median of 0 0 2 is 0
median of 0 1 0 is 0
median of 0 1 0 is 0
median of 0 1 1 is 1
median of 0 1 1 is 1
median of 0 1 2 is 1
median of 0 1 2 is 1
median of 0 2 0 is 0
median of 0 2 0 is 0
median of 0 2 1 is 1
median of 0 2 1 is 1
median of 0 2 2 is 2
median of 0 2 2 is 2
median of 1 0 0 is 0
median of 1 0 0 is 0
median of 1 0 1 is 1
median of 1 0 1 is 1
median of 1 0 2 is 1
median of 1 0 2 is 1
median of 1 1 0 is 1
median of 1 1 0 is 1
median of 1 1 1 is 1
median of 1 1 1 is 1
median of 1 1 2 is 1
median of 1 1 2 is 1
median of 1 2 0 is 1
median of 1 2 0 is 1
median of 1 2 1 is 1
median of 1 2 1 is 1
median of 1 2 2 is 2
median of 1 2 2 is 2
median of 2 0 0 is 0
median of 2 0 0 is 0
median of 2 0 1 is 1
median of 2 0 1 is 1
median of 2 0 2 is 2
median of 2 0 2 is 2
median of 2 1 0 is 1
median of 2 1 0 is 1
median of 2 1 1 is 1
median of 2 1 1 is 1
median of 2 1 2 is 2
median of 2 1 2 is 2
median of 2 2 0 is 2
median of 2 2 0 is 2
median of 2 2 1 is 2
median of 2 2 1 is 2
median of 2 2 2 is 2
median of 2 2 2 is 2
*/

 

[Tim Streater]

[snip]

FWIW, I like SESE as a rule of thumb, especially if there's resource
management to do be done at function exit. Make refactoring much
easier.

int frobnicate()
{
int result;
/* allocate resources */
.
/* manipulate result*/
.
/* cleanup resources */
return result;
}

The C I wrote typically involved a lot of syntax checking of some input
string with a lot of early returns on error. The preceded any attempt to
allocate resources.

If the manipulations are even slightly complicated, that's the way.

But I can't bring myself to recommend:

int frobnicate(int val)
{
int result;
switch(val){
case 0: result = 7;
break;
case 1: result = 17;
break;
case 3: result = 173;
break;
default: result = -9;
}
return result;
}

over

int frobnicate(int val)
{
switch(val){
case 0: return 7;
case 1: return 17;
case 3: return 173;
default: return -9;
}
}

or even

int frobnicate(int val)
{
return val == 0 ? 7
: val == 1 ? 17
: val == 3 ? 173
: -9;
}

Due to the simplicity of the returned expressions, they all work
reasonably well for me. By and large, the people who wrote theose
incredibly stacked "return ?:?:?:" constructs really were fetishist
about SESE, and would tell you the middle option was an appalling
affront to good style.

Well, rude anglo-saxon gestures to them, in that case.

 

[Keith Thompson]

Sorry, I didn't mean to misconstrue what you were saying.


OK, but let me confess that I really don't know what
is the *best* way to place white-space in code like this.
(And I normally don't scrunch "a < b" down to "a<b",
but isn't that a good way to make such code slightly
more readable?)

/* Return the median of 3 numbers */
int median3(int a, int b, int c)
{
return a<b ? b<c ? b
: a<c ? c : a
: c<b ? b
: c<a ? c : a;
}

I'm sure that will look very simple after a few hours of study.

I do sometimes write fairly long *linear* chains of conditional
operators. For example:

printf("x = %d = %s\n",
x,
x == SOME_CONSTANT ? "SOME_CONSTANT" :
x == ANOTHER_CONSTANT ? "ANOTHER_CONSTANT" :
x == YET_ANOTHER_CONSTANT ? "YET_ANOTHER_CONSTANT" :
/* ... */
"???");

(Calling a function that uses a switch statement to return the
value of one of several string literals might make more sense;
I probably had some obscure reason not to do that.)

It might seem like the long chain needs some parentheses, but it
really doesn't, for much the same reason that you can write:

if (foo) {
...
}
else if (bar) {
...
}
else if (baz) {
...
}
else {
...
}

and it's actually clearer than:

if (foo) {
...
}
else {
if (bar) {
...
}
else {
if (baz) {
...
}
else {
...
}
}
}

(<OT>Some languages have an additional "elseif", "elsif", or "elif"

This example may be too tame for much controversy.
I *would* post a more interesting example than this
one, but for that I'd want to be in a coffee-shop
with you all saying "Hello, James!" after I say,
"My name is James, and I write funny-looking C code."

}

 

[Moi]

Here is mine:
***/

#include <stdio.h>

int median3(int a,int b,int c);
int main(void)
{
int a,b,c,m;


for( a=0; a< 3; a++)
for( b=0; b< 3; b++)
for( c=0; c< 3; c++) {
m = median3(a,b,c);
printf("%d %d %d median3=%d\n" , a,b,c,m);
}
return 0;
}

int median3(int a,int b,int c)
{
switch ((a>b)+((b>c)<<1)+((c>a)<<2)) {
case 0: return a;
case 1: return c;
case 2: return a;
case 3: return b;
case 4: return b;
case 5: return a;
case 6: return c;
}
}

/****



AvK

 

[user923005]

Here is mine:
***/

#include <stdio.h>

int median3(int a,int b,int c);
int main(void)
{
int a,b,c,m;

for( a=0; a< 3; a++)
        for( b=0; b< 3; b++)
                for( c=0; c< 3; c++)  {
                m = median3(a,b,c);
                printf("%d %d %d median3=%d\n" , a,b,c,m);
        }
return 0;

}

int median3(int a,int b,int c)
{
switch ((a>b)+((b>c)<<1)+((c>a)<<2)) {
case 0: return a;
case 1: return c;
case 2: return a;
case 3: return b;
case 4: return b;
case 5: return a;
case 6: return c;
        }

}

/****


AvK

/*

Surprising to me, the switch ran 4x slower than the simple if() tests.

It appears that the missed branch predictions are killer.
I guess that profile guided optimization will help your routine
quite a bit if the data has some particular pattern.
*/

typedef int e_type;

e_type median3(e_type a, e_type b, e_type c)
{
return (a < b) ? ((b < c) ? b : ((a < c) ? c : a)) : ((a < c) ?
a : ((b < c) ? c : b));
}

e_type median3a(e_type a, e_type b, e_type c)
{
if (a < b) {
if (b < c)
return b; /* a b c */
if (c < a)
return a; /* c a b */
return c; /* a c b */
} else {
if (a < c)
return a; /* b a c */
if (c < b)
return b; /* c b a */
return c; /* b c a */
}
}

e_type median3b(e_type a, e_type b, e_type c)
{
switch ((a > b) + ((b > c) << 1) + ((c > a) << 2)) {
case 0:
return a;
case 1:
return c;
case 2:
return a;
case 3:
return b;
case 4:
return b;
case 5:
return a;
case 6:
default:
return c;
}
}


#ifdef UNIT_TEST
#include <stdio.h>
int main(void)
{
e_type i,
j,
k,
m,
m2,
m3;
for (i = 0; i < 3000; i++)
for (j = 0; j < 3000; j++)
for (k = 0; k < 3000; k++) {
m = median3(i, j, k);
m2 = median3a(i, j, k);
m3 = median3b(i, j, k);
#ifdef SHOW_RESULTS
printf("median of %d %d %d is %d\n", i, j, k, m3);
#endif
if (m3 != m)
printf("Disagreement of %d verses %d\n", m3, m);
if (m2 != m)
printf("Disagreement of %d verses %d\n", m2, m);
}
return 0;
}

#endif
/*
Profile results were:
Function Name,Exclusive Samples,Exclusive Samples %,
"median3b","48,756",55.35,
"main","16,790",19.06,
"median3a","11,644",13.22,
"median3","10,898",12.37,
*/

 

[Moi]

Surprising to me, the switch ran 4x slower than the simple if() tests.

It appears that the missed branch predictions are killer. I guess that
profile guided optimization will help your routine quite a bit if the
data has some particular pattern. */

Thanks for benchmarking. It was not intended to be a racer...
There are probably too many sequence points and too few common
subexpressions to give the compiler enough freedom to optimise.

There are other cases where this "computed enumeration" method can save
you some headaches. (e.g. 2D range-compare) It is relatively easy to
build and test, even if the conditions get very complex. The cases where
you know beforehand that you won't get it right the first time.


AvK

 

[user923005]

Thanks for benchmarking. It was not intended to be a racer...
There are probably too many sequence points and too few common
subexpressions to give the compiler enough freedom to optimise.

There are other cases where this "computed enumeration" method can save
you some headaches. (e.g. 2D range-compare) It is relatively easy to
build and test, even if the conditions get very complex. The cases where
you know beforehand that you won't get it right the first time.

Gave me an idea:
int median3c(int a, int b, int c)
{
e_type elist[7] = {a,c,a,b,b,a,c};
return elist[(a > b) + ((b > c) << 1) + ((c > a) << 2)];
}

I am benching it now.

I guess that the 7 assignments filling the array will be expensive but
a benchmark may prove revealing.

 

[user923005]

Thanks for benchmarking. It was not intended to be a racer...
There are probably too many sequence points and too few common
subexpressions to give the compiler enough freedom to optimise.

There are other cases where this "computed enumeration" method can save
you some headaches. (e.g. 2D range-compare) It is relatively easy to
build and test, even if the conditions get very complex. The cases where
you know beforehand that you won't get it right the first time.

Gave me an idea:
int             median3c(int a, int b, int c)
{
          e_type elist[7] = {a,c,a,b,b,a,c};
          return elist[(a > b) + ((b > c) << 1) + ((c > a) << 2)];

}

I am benching it now.

I guess that the 7 assignments filling the array will be expensive but
a benchmark may prove revealing.

The array idea was worse.

typedef int e_type;

e_type median3(e_type a, e_type b, e_type c)
{
return (a < b) ? ((b < c) ? b : ((a < c) ? c : a)) : ((a < c) ?
a : ((b < c) ? c : b));
}

e_type median3a(e_type a, e_type b, e_type c)
{
if (a < b) {
if (b < c)
return b; /* a b c */
if (c < a)
return a; /* c a b */
return c; /* a c b */
} else {
if (a < c)
return a; /* b a c */
if (c < b)
return b; /* c b a */
return c; /* b c a */
}
}

e_type median3b(e_type a, e_type b, e_type c)
{
switch ((a > b) + ((b > c) << 1) + ((c > a) << 2)) {
case 0:
return a;
case 1:
return c;
case 2:
return a;
case 3:
return b;
case 4:
return b;
case 5:
return a;
case 6:
default:
return c;
}
}

int median3c(int a, int b, int c)
{
e_type elist[7] = {a, c, a, b, b, a, c};
return elist[(a > b) + ((b > c) << 1) + ((c > a) << 2)];
}


#ifdef UNIT_TEST
#include <stdio.h>
int main(void)
{
e_type i,
j,
k,
m,
m2,
m3,
m4;
for (i = 0; i < 3000; i++)
for (j = 0; j < 3000; j++)
for (k = 0; k < 3000; k++) {
m = median3(i, j, k);
m2 = median3a(i, j, k);
m3 = median3b(i, j, k);
m4 = median3c(i, j, k);
#ifdef SHOW_RESULTS
printf("median of %d %d %d is %d\n", i, j, k, m3);
#endif
if (m4 != m)
printf("Disagreement (4) of %d verses %d\n", m3,
m);
if (m3 != m)
printf("Disagreement (3) of %d verses %d\n", m3,
m);
if (m2 != m)
printf("Disagreement (2) of %d verses %d\n", m2,
m);
}
return 0;
}

#endif
/*
Profile results were:
Function Name,Exclusive Samples,Exclusive Samples %,
"median3c","51,810",38.73,
"median3b","36,892",27.58,
"main","22,829",17.07,
"median3a","11,904",8.90,
"median3","10,320",7.72,
*/