Optimization Pattern

Informally, the logical extension of DesignPatterns to the process of optimization. Hopefully useful when doing ExtremeProgrammingForGames.

An OptimizationPattern, like a DesignPattern, is a specific family of solutions for a specific family of problems. General advice about optimization is not an OptimizationPattern. Please take the time to understand this distinction before contributing to these pages ... thanks!

OptimizationPatterns belong to families. These families break down as follows:

  1. Patterns which affect the code's behavior and therefore its specification
  2. Patterns which affect the code's algorithmic structure
  3. Patterns which affect the code's implementation and layout

The first category includes such patterns as:

For a good discussion of some ideas in this direction, see GrokTaskFirst. These patterns are dangerous, as they require a change in specification. In ExtremeProgrammingForGames, the programmer is forbidden to change the specification without permission from the client/user.

The second and third are "true" optimizations, since they do not affect the code's behavior. Some possible OptimizationPatterns are:

And some good "rules of thumb" for optimization, which are not patterns in and of themselves, are found below:

Anyone care to expand on these and/or add to the list?

How can we publish such patterns? The "problem" statement is generally "the program is too slow" so that seems redundant. [No. I changed my mind. The problem statement is "the program is too slow, because ..." which is discovered in profiling.]

Also (see WriteItOutLonghand) the study of OptimizationPatterns might lead to better optimizing compilers, which would be a GoodThing ... since we do not want to compromise code cleanliness with our manual optimizations.

I'll contribute more when I can; pressures of work forbid today, and I am getting married next week ... see you guys in August ;) -- EddieEdwards

Congratulations!

You should ProfileFirst, to understand where the performance bottlenecks are, before applying any of the other patterns.

The program could also be bloated in physical footprint or runtime storage.

Do you mean, optimization is not simply about time; or do you mean OptimizeLater? -- EddieEdwards

I mean optimization is not about time. It's often a SpeedVersusMemory? trade off. For embedded systems, memory is often the winner. For example, PocketSmalltalk scans the ROM for string constants in order to save memory, albeit slower. For Web applications, disk footprint (actually, bandwidth) is an important consideration, which is why Web designers lower the quality of their images so they compress better.

Theoretically, optimization is achieving the maximal value given an evaluation function. But that's boring to talk about! -- SunirShah

ROFL! Technically you're absolutely correct, but it is pretty boring to talk about ;) But you are right to point out that my implicit assumption is optimizing with time as the major variable ... that's my games heritage. -- EddieEdwards

What form of optimization is this:

The situation was a COBOL class, where given a database of records we had to perform some basic operations on all records, with a small tweak of needing to run an additional operation if the date was July-1.

Most people wrote something like this: 

loop over record set
  do normal operation
  if current date = july 1
do extra operation
  end if
end loop
while some people did this: 

loop over record set
  do normal operation
end loop


if current date = july 1
  loop over record set
do extra operation
  end loop
end if
but I wrote this: 

if current date = july 1
  loop over record set
do normal operation
do extra operation
  end loop
else
  loop over record set
do normal operation
  end loop
end if
For some reason this was remarkable enough that I was called out to the front of the class to explain what I did. I thought it was damned obvious. (By the way, the code itself was almost certainly exactly that number of lines as above making it even more obvious.)

What form of optimization? Probably a premature one breaking the OnceAndOnlyOnce rule.

Is there any other kind?

How does this break OnceAndOnlyOnce? It seems to me that it preserves OnceAndOnlyOnce, by only performing the loop one time, either with or without the "special operation" depending on the date. -- MikeSmith

Seriously though .. it looks like WriteItOutLonghand.

It breaks OnceAndOnlyOnce because you specify the behaviors "loop over record set" and "do normal operation" in two places. OAOO applies to writing (and maintaining) the code, not executing the code. But I thought one of the givens of these optimization pages was that performance has been measured and optimization is required. In this case, the violation of OAOO is necessary to meet the requirements (acceptable performance). If the rest of the code is well-factored, it shouldn't impact maintenance too much. -- JonathanTang

But the break of OnceAndOnlyOnce isn't the fault of the optimization. Consider: 

if current date = "july 1"
operation = normalOperation + extraOperation  //humor me :)
else
operation = normalOperation


loop over record set
operation
Would seem to be OAOO.

CategoryOptimization

EditText of this page (last edited September 23, 2004) or FindPage with title or text search