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!

OptimizationPattern''''''s 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:

	* DiscardSuperfluousPrecision
	* DoTheSimplestThingThatCouldPossiblyWork

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 OptimizationPattern''''''s are:

	* FunctionalInversion
	* LoopInvariantAnalysis
	* NonuniformCallingConventions (assembly programming only)
	* UseLocalStorage (multiprocessor programming only - e.g. PlayStation2)
	* InterlaceParallelCode (useful on pipelined CPUs)
	* WriteItOutLonghand
		* FunctionInlining
		* UnrollLoops
	* ConvertGathersToScatters (applies to broadcast of data to multiple receivers - be they buffers or network nodes)
	* CacheCalculations
	* DeferDecisionsUntilRuntime
	* CalculateBeforeCompileTime

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

	* GrokTaskFirst
	* GrokTheProblemDomain
	* GrokTheCompiler
	* UseStorageSpacesWisely (In C, C++, Pascal)
	* GrokCaching
	* GrokAliasing
	* GrokBranching
	* GrokLoops

----

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 OptimizationPattern''''''s 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