[game_edu] Feedback request on this programming lecture snippit

[Adam Parker]

Hi all,

Sorry about the late reply, but we've been in an audit...

My senior programming lecturer who's not on this list had this to say, so
I've forwarded it FYI... I won't pretend to understand it much, but hope its
useful!

(Bio note: Rob has many years professional experience as lead coder on the
PS2 and PS3 under his belt)

Cheers,
Adam


---------- Forwarded message ----------
From: Robert Walkley <rwalkley at qantmcollege.edu.au>
Date: Fri, Jun 10, 2011 at 12:46 PM
Subject: Re: [game_edu] Feedback request on this programming lecture snippit
To: Adam Parker <aparker at qantmcollege.edu.au>


(Sorry, I'm writing this quickly and my examples refer to a number of
concepts that people may not understand, but hopefully the points still come
across).

Yes, I agree for the most part with these sentiments. You should always plan
to write your code with algorithmic optimizations in mind. This often (but
not always) plays the most significant part on performance.

*Example:*

I have a list of names. I want to search for a name. The simplest algorithm
is to check every one until you find the appropriate name. This algorithm
for N items is O(N). This might not be a problem for small values of N, but
across 1,000,000 items this is significant and will statistically be N/2
steps.

*Algorithmic Optimization:*

Instead, let's sort all the names alphabetically and apply a binary search.
That is, playing a clever game of higher and lower. In the first step, try
item N/2. Is the current value less, or more than what we're searching for?
By doing this, we've just cut our search space in half, and will continue to
do so at each step.

For any given sorted list, by applying an even binary search, for N items,
we'll find the one we're looking for in O(log N) (base 2, sorry, couldn't
find how to subscript in Gmail). What this means, is for 1,000,000 items,
we'll always find it in less than *20 *steps, (that's because 2^20 is
greater than 1,000,000). By the way, this is why I cringe when people play
guess the number and take next guesses in random steps or steps of one ;).

So, by applying an improved algorithm, we've just reduced the number of
steps from *1,000,000* to *20, *speeding up our algorithm *5,000x* when N is
1,000,000!

*Low level (hardware) optimizations*
*
*
By far, the biggest optimizations you can make are algorithmic
optimizations. After that, there are still significant optimizations that
can be made at a lower level, but they'll generally won't make your code
more than an order of magnitude faster.

*Why you should measure and never guess*

There are times when you prematurely include optimizations, thinking
'logically' they'll deliver faster code. With the way modern processors and
memory work, results can often be counter intuitive. Modern hardware is very
complex, and considerations have to include such things as pipelining,
instruction or data cache coherency and efficiency, memory speeds,
load-hit-store (
http://www.gamasutra.com/view/feature/3687/sponsored_feature_common_.php)
issues,
using slow instructions (ie. just comparing floating point values on the
Xbox 360 costs around 100 cycles!) and more.

For example, say you're iterating over a list of game objects, and you want
to multiply their matrices. You realize that on average, only 30% of these
change at any given frame. So you innocently put in a dirty flag in to say
'don't update', thinking you'll save 70% of the time. So each iteration you
only update if the the flag is set. However, on a modern architecture, you
have probably just *slowed your code down*, because arithmetic is very fast
on a modern processor, but memory access is very slow (ie. ~500 cycles to
read a single variable from main memory on PS3 and 360!). This is because
CPU speeds have improved faster than memory speeds have. You cannot read a
memory location in the same time it takes to execute a single instruction,
and this has been the case for a long time.

The complication is that this can at time feedback into the algorithmic
optimization too. Modern architectures generally deal best with flat memory
structures that are in sequential and visited in linear order. Because of
the way the data caches work, using a linked list, tree or graph can be very
very slow.

*Why you should (generally) optimize soon after your first pass, but NOT
until you've profiled your code.*
*
*
Most of the time, you should obey the 80/20 rule. That is, 80% of your time
is going to be spent in less than 20% of your code. So for run of the mill
game code, you should stop at algorithmic optimization. However, for lower
level systems, you really should ensure it's running suitable performance
before it's presented to, or released to your clients:

   - If you don't optimize early, you can promise you'll implement a certain
   feature in your game to your clients (whether they be artists, designers,
   publisher etc), that may actually not be possible to deliver. It can be
   very embarrassing when you have to go back and tell them that the lofty
   promises you made cannot actually be achieved. ie. You may promise you can
   have 100 characters on-screen, but only be able to actually deliver 20.
   - *You should measure and never guess*. Games consoles come with
   sophisticated tools for profiling, and similar tools are available for most
   platforms.
   - You don't want your game to run slow for a very long period of time
   during production. You should set aside performance budgets that meet your
   overall target frame rate (ie. we'll allow our physics system to take 5ms or
   less).
   - If you go ahead and work on adding features to your game, you'll find
   it very difficult to estimate how much work is still to be done. It's
   possible that it will take several times to optimize the code to get it
   running at the desirable frame rate than it did to implement it in the first
   place.

Also note that during profiling, you can sometimes actually slow your code
down when profiling! The best solution to this is to test your code using
much larger numbers than you intend to deliver. For example, if you're
trying to speed up something that takes 1ms, instead do it 10 times instead.

Remember, "If you can not measure it, you can not improve it." (
http://zapatopi.net/kelvin/quotes/):)

Hope that makes some sense! :)

On Thu, Jun 9, 2011 at 11:55 AM, Adam Parker <aparker at qantmcollege.edu.au>wrote:


> Your thoughts? :^)

>

> ---------- Forwarded message ----------

> From: Richard Fleming <rflemin1 at jccc.edu>

> Date: Tue, Jun 7, 2011 at 6:46 PM

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

> To: "game_edu at igda.org" <game_edu at igda.org>

>

>

> 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

>

>

>

> --

> Adam Parker

> Senior Lecturer, Games Design

> Qantm College

>

> Qantm College Melbourne Campus

> 235 Normanby Rd

> South Melbourne VIC 3205 Australia

>

> +61 (0) 3 8632 3400   | Phone

> +61 (0) 3 8632 3401   | Fax

>

> www.sae.edu  | Web

> www.qantm.com.au  | Web

> www.saeshortcourses.com  | Web

>

> SAE National Provider Code: 0273. SAE CRICOS Provider Codes: NSW 00312F.

> SAE Institute Pty Ltd, ABN: 21 093 057 973

>

> This email (including all attachments) is confidential and may be subject

> to legal privilege and/or copyright. The information contained within this

> email (including all attachments) should only be viewed if you are the

> intended recipient. If you have received this email in error, please notify

> the sender immediately and delete this email from your system along with any

> copies that have been made. Any unauthorised use, which includes saving,

> printing, copying, disseminating or forwarding is prohibited and may result

> in breach of confidentiality, privilege or copyright. If you wish to

> unsubscribe or choose not to receive further commercial electronic messages

> from SAE Institute or any grouped/associated entities please send an email

> this address with the word UNSUBSCRIBE in the subject line.

>

> Please consider the environment before printing this e-mail.

>

>




-- 
Adam Parker
Senior Lecturer, Games Design
Qantm College

Qantm College Melbourne Campus
235 Normanby Rd
South Melbourne VIC 3205 Australia

+61 (0) 3 8632 3400   | Phone
+61 (0) 3 8632 3401   | Fax

www.sae.edu  | Web
www.qantm.com.au  | Web
www.saeshortcourses.com  | Web

SAE National Provider Code: 0273. SAE CRICOS Provider Codes: NSW 00312F. SAE
Institute Pty Ltd, ABN: 21 093 057 973

This email (including all attachments) is confidential and may be subject to
legal privilege and/or copyright. The information contained within this
email (including all attachments) should only be viewed if you are the
intended recipient. If you have received this email in error, please notify
the sender immediately and delete this email from your system along with any
copies that have been made. Any unauthorised use, which includes saving,
printing, copying, disseminating or forwarding is prohibited and may result
in breach of confidentiality, privilege or copyright. If you wish to
unsubscribe or choose not to receive further commercial electronic messages
from SAE Institute or any grouped/associated entities please send an email
this address with the word UNSUBSCRIBE in the subject line.

Please consider the environment before printing this e-mail.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://seven.pairlist.net/pipermail/game_edu/attachments/20110610/6bc6cbb9/attachment.htm>