[game_edu] Feedback request on this programming lecture snippit

[Steve Graham]

One more comment about algorithm/data structure choice/macro optimization.

Something I emphasize in classes (and practice) has always been to focus 
on simplicity and getting it correct first. Anyone who's been through 
data structure or an algorithms class *knows* that quicksort is much 
better than a simpler sort such as insertion or selection sort. BUT the 
problem is that it ain't necessarily so.

I've had students do experiments in class to determine *when* quicksort 
became better than the other sorts -- results have varied a lot, but 
typically, it has not been until the size of the list to be sorted has 
gotten into several thousands of elements.

Quicksort is more complex and easier to screw up than are the other 
sorts. So ... if your list of elements is on the order of tens or 
hundreds, then quicksort is likely NOT to be the best choice. The 
additional risk of errors more than offsets the negligible improvement 
in performance.

This is often the case -- that the benefits of a more complex, but 
asymptotically better algorithm don't justify the complexity. This is 
often due to data size -- the data just isn't big enough!

Another factor which is crucial is the nature of the data -- there can 
be big differences in performance of algorithms based on characteristics 
of the data. Is it almost sorted? Is it reverse sorted? is it .... 
Analysis is typically done making assumptions about uniform random 
distributions of data (because it makes the analysis easier or even 
possible, and because we may not have a clue what the data will really 
be like). If you have or can get some idea about the character of the 
data, it is a vital consideration as well.

Yet another crucial factor is the nature of the performance criteria -- 
is there some threshold which must *never* be exceeded? Or perhaps we 
are more concerned with typical performance and rare cases which are 
much worse don't really matter.

Robert Sedgewick has some interesting things to say about empirical 
studies in algorithm performance (e.g., 
http://www.cs.princeton.edu/~rs/talks/ScienceCS10.pdf ). Here is an excerpt:


> Motivating example: max flow Compare performance of Ford-Fulkerson 

> implementations • shortest augmenting path • maximum-capacity 

> augmenting path Graph parameters for example graph • number of 

> vertices V = 177 • number of edges E = 2000 • maximum capacity C = 100 

> How many augmenting paths? worst case upper bound for example actual 

> shortest VE/2 177,000 37 VC 17,000 max capacity 2E lg C 26,575 7

> How many steps to find each path?<  20, on average

> total is a factor of 1 million high for thousand-node graphs!


It is not so much the nature of the language and platform that senior 
software designers know -- it is the nature of the problem and how such 
factors as the algorithm, data structures, language, platform, data, 
context, ... all can affect the best choice. And when in doubt they fall 
back on the KISS principle -- and if performance measurements prove more 
is needed, *then* they make changes as appropriate.

cheers,
skg


On 6/8/2011 11:55 PM, Richard Fleming wrote:

> Some good feedback guys, thanks.

>

> @Steve: I guess in my mind I break down design into various types of optimizations: decisions to optimize code maintenance, decisions to optimize code re-use, and decisions to optimize performance.  I agree that is is worthwhile to mention that 'macro optimization' is more traditionally referred to as System Design or Architecture.

>

> @Ian: Good point, I'll modify it mention that the system or macro level is normally done by senior programmers who really understand the language and platform.  And then mention that if they're trying to go indie (which I encourage them to try) that

>   means typically *they* are the senior programmer ;)

>

> Dragons are awesome and dragons are fun.

> But if you get one angry...

> then you'll be well done.

> ---------------------------------------

> Richard Fleming

> RC 332G, x4838

> Interested in creating computer games?

> Then check out JCCC's Game Development AA Degree!

> http://www.jccc.edu/home/depts.php/1287

> ________________________________________

> From: game_edu-bounces at igda.org [game_edu-bounces at igda.org] On Behalf Of Steve Graham [skudge at gmail.com]

> Sent: Tuesday, June 07, 2011 11:47 PM

> To: IGDA Game Education Listserv

> Subject: Re: [game_edu] Feedback request on this programming lecture snippit

>

> Personally, I don't use "optimization" as a name for what you refer to

> as "macro optimization". I'd call that design or architecture or

> algorithm/data structure selection.

>

> Now, of course, unsuitable design choices may have to be revisited and

> changed for a variety of reasons including poor performance. But at that

> point, I think of it as redesigning (or maybe refactoring or changing

> the algorithm or the data structure) rather than optimizing.

>

>    *If* you categorize your micro and macro activities together as

> optimization, then it's useful to distinguish them. But why lump them

> together in the first place? What benefits are there to thinking about

> it that way?

>

> It's quite foreign to the way I conceptualize the activities, so I'm

> having a hard time seeing the benefits. I draw a distinction between

> routine design activities (which include your macro activities) and

> activities that are only undertaken if they happen to be necessary

> (which include your micro activities).

>

> cheers,

> skg

>

>

>

> On 6/7/2011 3:46 AM, Richard Fleming wrote:

>> Looking for general feedback on this, good/bad/what are you smoking/ect, before I inflict it on my students

>>

>>

>> Macro and Micro Optimization

>>

>> Many times on the net you will find articles and blog posts proclaiming the evils of optimization.  “Don't do it!  Not until you absolutely must!” They all cry.  “Profile and measure before you try!”  is another rally cry.  And this is good advice, but only for certain kinds of optimizations.  The problem is that very few of them make a distinction between kinds of optimization, which is what I will do here.

>>

>> Macro Vs. Micro

>> I sort optimizations into two groups: Micro and Macro.  When you read a blog post on the evils of early optimization, they are talking about Micro optimization.  This is where you take small and isolated sections of code, and change them so they run as fast as possible.  This kind of optimization tends to create code that is very hard to read, complex, and bug prone unless you are very careful.  It can also take a lot of effort and time.  So the net is correct on this issue, avoid it until performance degrades bad enough that you feel you must.  Also, measuring or profiling is critical.  Humans are bad at guessing where performance bottlenecks are.  You can actually make things worse if you 'optimize' a spot that doesn't need it.

>>

>> Macro optimization however is different.  You want to do this from the very start.  Macro optimization is optimization at the architectural level.  Do I use a list or a queue for this data structure?  How about trees, do I need a red-black tree, or perhaps a b-tree?  The point here is to examine what you need to do and come up with an architecture that makes sense will work well.  This involves knowing the language and target platform really well.  A macro optimization that works well for a desktop app might be horrible for a mobile target, and vice versa.

>>

>> Now you might look at this and wonder: Doesn't this sound a lot like micro optimizations?  I mean, it's a lot of effort and time, and didn't you just finish saying humans are bad at guessing performance bottlenecks?  Well, yes and yes, but some things are different here.  First and foremost, you should be doing a technical design doc for your game anyways.  If you just grab a regular design document and start coding, you are begging for trouble.  You really, really need to sit down and do some thinking on how you want to structure the code.  As for performance, we know algorithmic performance.  Called 'Big O Notation', you can tell exactly how an algorithm will perform in different cases.  Lists are constant time for insertions.  The cost of bubble sort increase exponentially with added items.  These costs are known and proven.  Keeping these things in mind will help prevent the need for micro optimization.  Then there are the platform issues that I mentioned.  In C#, you have value types like integers, and then everything else is an Object.  If you pass an integer into a parameter that expects an Object, it 'boxes' the integer by creating a new Object to contain it.  Not that big of a deal (in most cases) on a desktop, but this will cripple you in the Compact Framework if it happens even moderately.

>>

>> So the take-away:  How should you optimize?  Always start with macro optimization.  If your code is an unholy mess of spaghetti logic, no amount of micro optimization can save you.  As you implement the code, continually measure the performance.  Once you notice the performance dropping below acceptable levels, break out the profiling tools and find that one line that is draining all of your performance.

>>

>>

>>

>> Dragons are awesome and dragons are fun.

>> But if you get one angry...

>> then you'll be well done.

>> ---------------------------------------

>> Richard Fleming

>> RC 332G, x4838

>> Interested in creating computer games?

>> Then check out JCCC's Game Development AA Degree!

>> http://www.jccc.edu/home/depts.php/1287

>>

>> The information contained in this e-mail and any attachments thereto ("e-mail") is sent by the Johnson County Community College ("JCCC") and is intended to be confidential and for the use of only the individual or entity named above. The information may be protected by federal and state privacy and disclosures acts or other legal rules. If the reader of this message is not the intended recipient, you are notified that retention, dissemination, distribution or copying of this e-mail is strictly prohibited. If you have received this e-mail in error please immediately notify JCCC by email reply and immediately and permanently delete this e-mail message and any attachments thereto. Thank you.

>> _______________________________________________

>> game_edu mailing list

>> game_edu at igda.org

>> http://seven.pairlist.net/mailman/listinfo/game_edu

>> .

>>

>

> --

> steve graham

> associate professor

> computer game design

> dakota state university

> skg at dsu.edu

> 605-480-6603

>

>

> _______________________________________________

> game_edu mailing list

> game_edu at igda.org

> http://seven.pairlist.net/mailman/listinfo/game_edu

> _______________________________________________

> game_edu mailing list

> game_edu at igda.org

> http://seven.pairlist.net/mailman/listinfo/game_edu

> .

>



-- 
steve graham
associate professor
computer game design
dakota state university
skg at dsu.edu
605-480-6603