RE: optimizing constant ifs out of loop?

RE: optimizing constant ifs out of loop?

[lrtaylor]

-----Original Message-----
From: Eljay Love-Jensen [mailto:eljay@adobe.com] 
> IF you have NOT profiled the code, then optimizing for performance (in
> lieu of the norm:  readability) is like taking potshots in the dark.

> "Premature optimization is the root of all evil."
> ~ Tony Hoare (often misattributed to Donald Knuth, who was quoting
Tony 
> Hoare)

I kind of get tired of hearing this quote, because it's only partly
true, and it leads people to often write very inefficient code, because
they assume (and I've seen people teach) that they can simply write it
so that it's pretty, and then they can profile the code afterward and
make it run fast.  That's not always true (and it's often very untrue).
While you shouldn't just blindly try to optimize all of your code from
the outset, since you'll often spend more time than is necessary on
sections of the code that have little to no impact, neither should you
not take performance into account while designing and building systems,
especially where performance is a major factor in the success of a
system.  If you fail to do so, you may end up having to rewrite major
portions of the system when you find out that you can't simply optimize
your current code enough.

The key and problem to the statement above is the word "premature".
True, you shouldn't optimize before you need to.  However, the problem
is that people seem to think that this means that you shouldn't optimize
much, if at all, until you've discovered that your system runs too slow,
and that is just plain wrong (and often much too late).  Optimization
(or planning/designing for optimum/sufficient performance) for
performance critical systems (such as mathematical systems, certain
distributed systems, etc.) should start happening from the outset in the
analysis and design phases.  Even waiting until the coding stage can
often be too late, because your design may be fundamentally flawed - at
least for the performance characteristics that you are trying to
achieve.  The key is really just to learn how to analyze and measure
your architecture or design so that you only try to optimize the areas
or designs that you know will likely keep your from reaching your
performance objectives.  Profiling can be part of that, but it shouldn't
necessarily be the crux of it, and it should happen well before the end
of your project!

Now, don't get me wrong, I'm not saying that he shouldn't profile his
code and see where the bottleneck is or that's not what people should do
when they discover that it's not fast enough.  The point is just that
it's not right to state in a blanket manner that you should only
optimize once you've found a problem.

For an excellent discussion on this topic, take a look at Performance
Solutions by Smith, et al.  They cover it pretty well and give you some
of the tools you need to help you determine whether your design is
likely to meet your criteria as well as several performance principles,
practices, patterns and anti-patterns that can be used as you design
your system for performance.

Cheers,
Lyle

RE: optimizing constant ifs out of loop?

[Eljay Love-Jensen]

Hi Lyle,

The quote is in reference to micro-optimizations in the programming phase of development.

The quote is not in the context of  encouraging a disregard for good architecture, design and programming practices.

Even the best micro-optimization cannot make up for a poor architecture or design.

My rule of thumb for the programming process:
1. make it work
2. make it work well (i.e., error situations addressed)
3. make it fast

This can be an iterative process (as opposed to strictly linear).  But trying to make a routine fast before that routine is empirically known to be an issue is a bad habit to get into.

Maintainability (99% of the code) is often far more important than micro-optimizations (1% of the code).  And a micro-optimization for one platform (CPU + OS + Compiler) may be a micro-pessimization on another platform.

Sincerely,
--Eljay

RE: optimizing constant ifs out of loop?

[lrtaylor]

-----Original Message-----
From: Eljay Love-Jensen [mailto:eljay@adobe.com] 
 
>Hi Lyle,

Hey,

> The quote is in reference to micro-optimizations in the programming
> phase  of development.

> The quote is not in the context of encouraging a disregard for good
> architecture, design and programming practices.

That may be how it was meant, but I think a lot of people don't limit
its application to that (hence my minor rant), including professors I
had at the university and people I've worked with.  What I've seen more
often than not is more the attitude "make it work; then make it work
fast", but without any other consideration for performance during the
"make it work" phase, since they think they can make it work fast
afterward.  At that point, they often end up rewriting portions of the
code to fix design issues that inherently limit performance and that
could have been foreseen had then been thinking about performance during
the design phase.

I guess we just need to be sure not to take the quote out of context...

Cheers,
Lyle

Re: optimizing constant ifs out of loop?

[Eljay Love-Jensen]

Hi David,

Sometimes, you have to take the bull by the horns and lead it to the water.

IF you have profiled your code, and know that this tight loop is a bottleneck, then you can-and-should reorganize the code so that it is more palatable to the compiler to produce more efficient code.

If that means that you have to have a whole slew of nested for-loops (via macro?), then so be it.  Comment your code heavily so as to explain why you've implemented something in a more obtuse fashion.

If that means you have to implement the routine in lovingly hand crafted assembly... then there you go.

IF you have NOT profiled the code, then optimizing for performance (in lieu of the norm:  readability) is like taking potshots in the dark.

Other ways that you could improve readability while concurrently (perhaps) improve performance is to move each of the loops into a separate function.  That way, the branching logic is segregated from the looping algorithm.  Which reduces the cyclical complexity -- something that degrades readability / maintainability.

"Premature optimization is the root of all evil."
~ Tony Hoare (often misattributed to Donald Knuth, who was quoting Tony Hoare)

Sincerely,
--Eljay

optimizing constant ifs out of loop?

[David Roundy]

Hello.  I have a question about how (and whether) I might be able to
convince g++ to move an if outside of some loops.  The code I'm working on
is a numerical code with a very tight inner loop that I'm trying to
simultaneously clean up and optimise.  Previously I had a number of copies
of the loop (which is actually several nested loops to loop over several
dimensions) for special cases.  I'd like to have only one copy of the loop,
which would be a lot cleaner.

The code is (simplified a bit):

const bool have_plus = ...;
const bool have_minus = ...;
const bool have_pml_plus = ...;
const bool have_pml_minus = ...;
LOOP_OVER_OWNED(v, ind) { // Macro for three four loops
  ...pre
  if (have_minus) {
    if (have_pml_minus) {
      ...a
    } else {
      ...b
    }
  }
  if (have_plus) {
    if (have_pml_plus) {
      ...c
    } else {
      ...d
    }
  }
  ...post
}

*I* know that the compiler can move the ifs out of the loop to give:

if (have_minus && have_plus) {
  if (have_pml_minus && have_pml_plus) {
    LOOP_OVER_OWNED(v, ind) ...pre  ...a  ...c  ...post
  } else if (have_pml_minus) {
    LOOP_OVER_OWNED(v, ind) ...pre  ...a  ...d  ...post
  } ... etc ...

but the compiler doesn't seem to know this.  Unfortunately, the pretty
version of the code takes about twice as long, which is not acceptable.

I'm compiling with -funroll-loops -O3.  Are there any other compiler flags
(or tricks) that I might be able to use to get the compiler to perform this
optimization? btw all the loops involved are simple 0..n-1 style loops with
n being known at runtime when the loop is entered.

Please CC me, as I'm not subscribed.  Thanks!
-- 
David Roundy
http://abridgegame.org/darcs