optimizing an expression

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

Got another idea worth trying:
e_type median3d(e_type a, e_type b, e_type c)
{
e_type *pa = &a;
e_type *pb = &b;
e_type *pc = &c;
const e_type *elist[7] = {pa, pc, pa, pb, pb, pa, pc};
return *elist[(a > b) + ((b > c) << 1) + ((c > a) << 2)];
}

I am benchmarking now.

 

[user923005]

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.

Got another idea worth trying:
e_type          median3d(e_type a, e_type b, e_type c)
{
    e_type         *pa = &a;
    e_type         *pb = &b;
    e_type         *pc = &c;
    const e_type   *elist[7] = {pa, pc, pa, pb, pb, pa, pc};
    return *elist[(a > b) + ((b > c) << 1) + ((c > a) << 2)];

}

I am benchmarking now.

/*
Using pointers offers no improvement.
*/
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;
}
}

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

e_type median3d(e_type a, e_type b, e_type c)
{
e_type *pa = &a;
e_type *pb = &b;
e_type *pc = &c;
const e_type *elist[7] = {pa, pc, pa, pb, pb, pa, pc};
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,
m5;
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);
m5 = median3d(i, j, k);
#ifdef SHOW_RESULTS
printf("median of %d %d %d is %d\n", i, j, k, m3);
#endif
if (m5 != m)
printf("Disagreement (5) of %d verses %d\n", m5,
m);
if (m4 != m)
printf("Disagreement (4) of %d verses %d\n", m4,
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 %,
"median3d","48,112",25.95,
"median3c","47,707",25.73,
"median3b","40,897",22.06,
"main","27,725",14.95,
"median3a","10,774",5.81,
"median3","10,196",5.50,
*/

 

[spinoza1111]

You invented the term signum?  Cool.

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.

What are you, 14 years old? Crack a book.

http://en.wikipedia.org/wiki/Sign_function

 

[spinoza1111]

In <[email protected]>,

spinoza1111wrote:



No. It doesn't "seem" anything. It addresses the problem.


It's amazing that you seem to think signum() is its only name. It's
been called many things in its time. SGN() is a common name, for
example.




It was a comment based on the observation that the majority of
articles posted under the account (e-mail address removed) contain
errors of one kind or another. I don't see what personalities have to

That's false. They merely contain more ideas based on wider knowledge,
and more positive statements as opposed to negatives and as such are
more vulnerable to jealous individuals with time on their hands who
have "edited" a grand total of one unsaleable book from one unethical
publisher.

do with it. But if you want me to stop claiming that most of what you
write is wrong, start writing some right stuff. (Personally, I'm not
holding my breath waiting for that to happen. I've waited nearly a
decade and it hasn't happened yet to any noticeable degree.)

This is indeed the sort of language inadequate individuals learn to
use in banks: it's deliberately abstract in order to be proof against
criticism. The result of this sort of language at Northern Rock and
Lehmann brothers was widespread financial disaster except for the
superrich. You describe yourself as working for "banks and insurance
companies". Did you work for Northern Rock, and how many people did
you trash there? How much software did you write, and how much damage
did it do?

 

[spinoza1111]

Uh...you've written it in one line. The only less would be zero lines...

It's not a correct piece of software. It divides by zero when x is
zero. The signum function is defined as zero when x is zero.

 

[spinoza1111]

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

It's one thing to be falsely, whiningly humble in a monastery, but to
be afraid to use a perfectly sensible construct in a corporation
because one doesn't want to be thought by inadequate people to be
"pretentious" is just absurd. One of the biggest problems with the
above code is the amount of vertical space it takes, which causes
simple functions to be partly hidden on small screens. It also doesn't
allow the puts call to be written once, saving whatever storage it
takes to express the puts call at runtime, whereas this does:

puts(cond?"You suck":"You don't suck");

Nor does it allow a further optimization in C Sharp only:

puts("You " + cond?"":"don't " + "suck")

In C:

puts("You %ssuck", cond?"":"don't ");

 

[Nick Keighley]

No, I didn't say that. I said: "It was a comment based on the
observation that the majority of articles posted under the account
(e-mail address removed) contain errors of one kind or another."

The difference is significant. If your newsreader can't quote
properly, learn to proof-read.

you got me. What *is* the difference? Google's mangled the address. Is
that the difference you are talking about?

 

[Nick Keighley]

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

It will be /obvious/ after a few hours study.

 

[Nick Keighley]

I hope I never have to code to a standard like this.

 One of the biggest problems with the
above code is the amount of vertical space it takes, which causes
simple functions to be partly hidden on small screens. It also doesn't
allow the puts call to be written once, saving whatever storage it
takes to express the puts call at runtime, whereas this does:

I think it's just ugly and unclear

puts(cond?"You suck":"You don't suck");

Nor does it allow a further optimization in C Sharp only:

puts("You " + cond?"":"don't " + "suck")

In C:

puts("You %ssuck", cond?"":"don't ");

printf ("You %ssuck", cond ? "" : "don't ");



<snip>

 

[spinoza1111]

Would you describe:

x = *y;

as buggy code?

Not as such, given that all I know is that x is set to y,
dereferenced. Sure, y might not be dereferenceable and may cause a
segment fault.

But this does NOT excuse coding crap like this:

return x>0 ? 1 : -1;

or this:

if (x>0) return 1; return -1;

[and note that compared to the egregious error in both the above code
snippets, it matters not in the slightest whether the programmer has
used ?:, or if].

This is KNOWN to be probable crap because independent of programming
there exists a signum function, and the code communicates:

(1) An intent to "do" signum
(2) An ignorant or uncaring disregard for the case of x==0

Don't worry about whether your code will seem "pretentious" to some
Troglodyte because he doesn't like ?:. Just get it right.

 

[spinoza1111]

Its fine if you know that y is pointing somewhere valid.



Its fine if you know that x is not zero.  

We don't know that. And even if we do (if some "end user" reassures us
that this is so), that can change without notice, and it doesn't hurt
to implement a more easily documented mathematical function...even if
the end user may not know the "signum" function. This is because end
users and requirements change, faster than mathematical terminology.

It never hurts to get it right, UNLESS the end user requires that the
value be -1 (or 1) for x==0. I got the impression that this was not
the case, that instead nobody even thought about x==0. And, the
original code just crashes on divide by zero in this case.

 

[spinoza1111]

Would you describe:

x = *y;

as buggy code?

In terms of modern OO practice, x = *y is buggy code. This is because
both C Sharp and Java define a subset of all possible programs such
that references are always and everywhere managed, not referencing
storage outside of a known error unless, of course, the runtime
virtual machine is itself buggy; the runtime VM machine will be buggy
with small if nonzero probability p while applications code will be
buggy with a much larger probability P>=10*p.

In terms of modern OO practice, C code is buggy code in all cases. The
probability PP of bugginess of any arbitrary snippet of C code is

=10p where p is the probability of managed C Sharp code.

Furthermore,

return x>0?1:-1;

is a prima facie bug because the closest mathematical function to what
it does is signum, and it gets signum wrong. Neither programmers nor
end users have the right to create new mathematical functions *ex
nihilo*. A competent programmer, when told to "return 1 when x is
greater than zero, and return -1 when x is less than zero", would ask
"what the goddamn hell should I return when x is zero, dorkwad?"

Managers of software used to brag that "every line of code written in
my 'shop' must have a Biznez Case or else because I'm such a studly
dudley practical man, and I don't put up with no monkey business from
a bunch of ****** math majors", or words to that effect.

I would change that. I would say that ideally, every line of code
would have a referent outside of programming, preferably to
mathematics. That's because in an ideal world there would be no
"business", just meeting human needs.

 

[Keith Thompson]

Yes.

Google Groups always mangles e-mail addresses like thot, supposedly
to make it more difficult for spammers to harvest addresses.
(Note that this affected the second quotation of the sentence as
well as the first, because Nick also posts through Google Groups.)
Since there's no real risk of confusion, it was perfectly reasonable
to leave it alone rather than manually correct it.

This is perhaps the most trivial offense Nilges has committed here,
and I'm surprised you bothered to note it.

 

[James Dow Allen]

One man's stylistic fetish is another man's readability-friendly
constraint:

[fragment that uses 3 lines]

into

 [someone else's 3 line fragment]

I don't like the latter

I don't like either of them. I like:

[10 or 11 line fragment]

I was happy to see in this thread that I'm not the only who
finds it virtuous to conserve vertical space. Evidently
Mr. Heathfield is not in our select company!
Richard, are you one of these people with 20-10 vision who
view code in the smallest font available?

First: Switch to TRUE style; you can save 3 lines just
by placing the braces correctly in your fragment. I was
already approaching middle-age when I switched to TRUE,
and even if you don't feel like switching in your
personal code, please watch your C language here: there
are children present!

One "wasted" line in Richard's fragment I *don't*
object to: he replaced

return Complicated; with
newstatus = Complicated;
return newstatus;

This will come in handy when you need to debug.
.... As you will since you're not using True Style.

Hoping I added enough smiley-faces to avoid giving offense,
Yours truly,
James

 

[James Dow Allen]

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

Touche (or rather Touch&eacute; -- I can't do UTC).
I should have arranged the white space better.
The "real" code, I'm not too shy to admit, was actually

return a < b ? b < c ? b : a < c ? c : a : c < b ? b : c < a ? c : a;

But I *had* to edit it somehow for the post since
Groups.DoNoEvil.com was otherwise going to break the line.
(I'm not posting this message from DoNoEvil.)

I would *NOT* jam this logic into a single line if I
thought anyone would ever need to read it, but here,
surely the comment
/* Return the median of 3 numbers */
tells the reader everything he needs to know about
the details, without wasting vertical space!
(And if someone counters with "What if there's a bug?"
my answer will be "Same to you, buddy!")

Staring at these fragments I'm wondering if "if/else"
*might* be more readable than "?/:" after all -- *not*
because ":" is less clear than "else" but because it
uses *less ink* (or less phosphors) and thus doesn't
stand out as well!

Given the interest in rewriting median3(), I'm surprised
no one offered:

double fmedian3(double a, double b, double c)
{
return a + b + c
- fmax(fmax(a, b), c)
- fmin(fmin(a, b), c);
}

Get yourself a new compiler if it can't even
optimize *this* !

By the way, I found the median3() in old source with the command:

cat */*.c | tr ";\n" "\n\r" | grep "?.*?.*?" | tr "\n\r" ";\n"

Another example that turned up with that was
in the code that creates pages for the
Fabulous Pedigree website
http://fabpedigree.com/s098/f811410.htm

fprintf(wpfd, "<hr> &nbsp;%s%s%s:%s \n",
Labb,
Partnerposs ? "poss. " : "",
Abstractroot
? (cnt > 1
? ("\"Partners\"")
: ("\"Partner\""))
: cnt > 1
? (ismale ? "Wives/Partners" : "Husbands/Partners")
: (ismale ? "Wife/Partner" : "Husband/Partner"),
Labe);

James Dow Allen

 

[Stefan Ram]

return a < b ? b < c ? b : a < c ? c : a : c < b ? b : c < a ? c : a;

The following experiment in formatting is following the rule
that each colon has the same indentation as the
corresponding question mark:

return a < b ? b < c ? b
: a < c ? c
: a
: c < b ? b
: c < a ? c
: a;

Thus, for every question mark, the eye can easily find the
following parts:

1st operand: left of the »?«

colon: first colon below the »?«

2nd operand: between the »?« and the »:«

3rd operand: after the »:« until to the point
where the indentation is left of the »?« or the
full expression ends.

 

[bartc]

I understand what that does. However, for those of us who read left
to right, the problem is the ? modifies what the = does, so I have to
mentally backtrack.

As I scan the line, my mind first sees

a = b ...

Thinks: "OK, I'm setting a to the value of b" ...

a = b ?

Thinks: "Oh, no look a, '?'. I'm not setting a to b at all.
b is a condition that controls whether to set a to c or d."

When parsed from left to right (as those of us who use Indo-European
languages do) its a tortuous construction. Yoda-code.

You might have trouble with

a = b + c

then. I tend to enclose these ?: expressions in parenthesis as I haven't a
clue how ?: interacts with other operators:

a = (b ? c : d)

 

[Tim Streater]

That's all well and good but I, and anyone that has spent any time with C
should IMO, read it as "assign to a the result of the logical expression
following" .. or assign to a depending on b. It really is straightforward.

Especially useful in embedded in expressions.

printf("%s\n", (fArrived?"Hello":"Goodbye"));

Clean, obvious, efficient, no cluttering namespace.

A good programmer should never program to the lowest common denominator
and should use the features of the language.

But don't emulate perl programmers, though. Their one goal in life is to
reduce every program to a .

 

[Phil Carmody]

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");
}

Better written as:

puts(condition ? "A message" : "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."

The original ?: example used ?: only for control flow, not for
selection of values. So it doesn't tell me that the author knows
that it has that latter use. The fact they avoided my version
tells me that probably they don't. So we'd both flag the line,
for mostly the same reason, but my terseness pushes me to my
one-liner rather than

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.

Sometimes they make the function easier to understand as they
clearly and cleanly frame off sections which can be considered
separately. That's not clutter at all.

(But tabs? Spaces only, please.)

A coding standard which is 100% strict about how wide a tab is
may also approve or demand the use of tabs.

I don't personally care - I press 'tab' in emacs, and it makes
the code conform to the coding standard in effect at the time.

Phil

 

[Phil Carmody]

printf("I see %u ship%s.\n",nships, nships == 1 ? "" : "s");

printf("I see %u ship%s.\n", nships, "s"+(nships==1));

Phil