Author Topic: Optimization Techniques  (Read 3714 times)

Offline TechSY730

  • Core Member Mark V
  • *****
  • Posts: 4,550
Optimization Techniques
« on: December 23, 2010, 06:29:37 PM »
What sort of intermediate to advanced optimization techniques do you use? Such as

Loop unrolling
Loop merging
Lazy initialization
Precomputing of constant values
Keeping lists sorted to reduce look-up times (assuming inserts are much rarer than look-ups)
Avoiding making copies made by passing by value
Sharing of internal data structures of two similar immutable objects
Tail-recursion
Rearranging code and variables to improve cache hits and pipe-lining
Rearranging branches to improve branch prediction
Replacing a set of operations with their MMX or SSE counterparts
Hand tuning assembly of critical loops
(Okay, maybe those last four were a little too low-level  ;D)
Or any other optimizations I didn't mention?
« Last Edit: December 23, 2010, 06:50:39 PM by techsy730 »

Offline x4000

  • Chris Park, Arcen Games Founder and Lead Designer
  • Administrator
  • Zenith Council Member Mark III
  • *****
  • Posts: 30,700
Re: Optimization Techniques
« Reply #1 on: December 23, 2010, 06:34:41 PM »
Yes, lots of that sort of thing, plus various optimizations that are .NETE/mono specific.  Avoiding foreach statements is a huuge one.

Very low on time these days, can't really chat about this at the moment, sorry.  Just very slammed trying to get things done for the holidays and actually being able to take time off.
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline TechSY730

  • Core Member Mark V
  • *****
  • Posts: 4,550
Re: Optimization Techniques
« Reply #2 on: December 23, 2010, 06:35:57 PM »
No problem, you can elaborate in more detail once things get a little less hectic if you want to.

Offline x4000

  • Chris Park, Arcen Games Founder and Lead Designer
  • Administrator
  • Zenith Council Member Mark III
  • *****
  • Posts: 30,700
Re: Optimization Techniques
« Reply #3 on: December 23, 2010, 06:38:39 PM »
Note that a lot of those things don't work when you're in JIT languages.  There's a whole other art to doing stuff in specific higher-level languages, and most of those vary by langauge.  A lot of them are so ingrained in my habits (and Keith's as well, I think) that we don't really think of them.  But your list has a mix of general logical refinements (which of course we use), and hardware-specific lower-level-C++ type stuff that doesn't make any sense in C#.
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline TechSY730

  • Core Member Mark V
  • *****
  • Posts: 4,550
Re: Optimization Techniques
« Reply #4 on: December 23, 2010, 06:40:28 PM »
True, hence my "joke" optimizations of low level concepts. When you get more time to answer; are there any convoluted, strange but efficient algorithms you are using?

Offline x4000

  • Chris Park, Arcen Games Founder and Lead Designer
  • Administrator
  • Zenith Council Member Mark III
  • *****
  • Posts: 30,700
Re: Optimization Techniques
« Reply #5 on: December 23, 2010, 06:42:28 PM »
Not really, I prize readability over those sorts of optimizations, as that leads to fewer bugs.  If it can't be done both efficiently and clearly, to me it ought not to be done.  There are much lower-hanging fruits in terms of performance than that.  Call stack branching and paths is extremely low on the list, actually.
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline SalientBlue

  • Newbie Mark II
  • *
  • Posts: 13
Re: Optimization Techniques
« Reply #6 on: January 23, 2011, 05:47:53 PM »
Avoiding foreach statements is a huuge one.

What's inefficient about foreach statements?  Is it only a C# thing, or is it a problem with foreach's in general?

Offline ShadowOTE

  • Hero Member
  • *****
  • Posts: 517
Re: Optimization Techniques
« Reply #7 on: January 23, 2011, 07:34:55 PM »
Foreach isn't as efficient as for statements - off the top of my head I can't recall why, aside from the fact that you have to do some work at run time to figure out what's going on (could be wrong there - I'll link to some more detailed information in a bit). In some cases it doesnt matter much, but when you try using it for anything substantial you get a big boost from using a less generic loop - the cited example tends to involve strings, from what I recall.

Edit - so, after a bit of digging to refresh my memory, here's what I've got: a foreach (usually) sits on top of a collection, whereas a for loop does not. When you go to compile, the for loop is more efficient because there are fewer compares going on in the assembly (http://www.codeproject.com/KB/cs/foreach.aspx).

The string examples I referred to above were from MSDN about a decade ago, so I'm not sure if they still hold true in .NET 4.0 (I suspect many of the early reasons resulting from poor compiler optimization have since been fixed - http://blogs.msdn.com/b/kevin_ransom/archive/2004/04/19/116072.aspx), but the page is still posted and plenty of code is still in early versions of .NET, so it's not a bad bit of advice (http://msdn.microsoft.com/en-us/library/ms973839.aspx#dotnetperftips_topic2).

In newer versions of .NET the verdict seems mixed (there's some great discussion on stackoverflow http://stackoverflow.com/questions/365615/in-net-which-loop-runs-faster-for-or-foreach) but basically if you want to hit everything in a collection, especially when you aren't sure what type of collection, a foreach has near negligible differences from a for loop. However, when you try using it on an indexed array or certain other situations you take a big performance hit. It also has certain limitations in what you can do, which a for loop doesn't - I think (but am not certain) that you can't modify the contents of the collection in such a way as to alter the array bounds or order (it would throw an exception for resizing/reordering your collection while iterating on it... which is a problem).

If you want to see some benchmarks, http://msmvps.com/blogs/jon_skeet/archive/2009/01/29/for-vs-foreach-on-arrays-and-lists.aspx has a brief test - but limited, in that it only tests an int array against a List<int> to see what happens, which is pretty limited compared to the full spectrum of possibilities out there. That said, it's not a bad test, and it does a pretty good job illustrating the point.

By no means is the above definitive, but it appears to be a good summary of the current consensus. Basically, foreach is generic, and you're going to pay a price for that in terms of optimization on less common circumstances, so in most cases there are better ways to loop or iterate through a list/array/whatever of objects.
« Last Edit: January 23, 2011, 07:58:42 PM by ShadowOTE »

Offline x4000

  • Chris Park, Arcen Games Founder and Lead Designer
  • Administrator
  • Zenith Council Member Mark III
  • *****
  • Posts: 30,700
Re: Optimization Techniques
« Reply #8 on: January 23, 2011, 08:23:38 PM »
Avoiding foreach statements is a huuge one.

What's inefficient about foreach statements?  Is it only a C# thing, or is it a problem with foreach's in general?

Well, in all .NET and Mono language implementations it is probably a problem.  I would be surprised if it is not also a problem in many other languages, but I don't know for certain.  ShadowOTE is mostly correct on why it's less efficient, but that's not the whole story.  Foreach is only supported on types of IEnumerable, and those types have a GetEnumerator method that returns an IEnumerator object.  That object is then responsible for looping over an ordered list of items.  This is very handy for, say, Dictionaries, where foreach becomes the only way to loop over all the entries (for is not possible unless you have a separate array of all the keys... which would be pointless).

In .NET there is indeed a lot of debate over for and foreach, and actually some folks talk about compiler optimizations and how thus foreach is actually faster in some cases.  For that reason, in AI War 3.x and before, I used foreach extensively.  In AI War 4.0, we moved to Unity 3D, which uses Mono instead of .NET.  The compiler optimization is not present there.  The end result is that a lot of transient memory winds up being used for the IEnumerators when you have many, many foreachs (or a single foreach called many times -- in AI War we could have literally tens of thousands of foreach calls per second, if not hundreds of thousands), and so the end result was wasting multiple megabytes of memory per second in Mono.  This in turn is handled by the garbage collector, but it makes the garbage collector run more frequently.

AI War is an extreme example because of the massive number of operations it has to perform of this support compared to most games -- possibly more than any other game around, I'm really not sure.  Even a game like Dwarf Fortress that is larger and more complex than AI War has a lot of its complexity more compartmentalized from what I can tell, whereas the sheer scale of battlefields, etc, in AI War makes for the massive computational sinkhole of both collision and especially targeting.  The reason I bring this up is that in most programs, the efficiency gains from using for instead of foreach, even in Mono, would likely be minuscule.
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline TechSY730

  • Core Member Mark V
  • *****
  • Posts: 4,550
Re: Optimization Techniques
« Reply #9 on: January 23, 2011, 08:33:14 PM »
Plus there is what the foreach stands for: a linear stepping through a collection. While a O(n) loop is not all that bad, frequently you can do better via some clever tricks (like keeping a list sorted to give O(log(n)) search times). This is not always possible, some tasks you have to have at least O(n) time, but sometimes just spamming foreachs may "cheat" you out of more scalable algorithms.

Plus, as mentioned earlier, there is the fact the version of Mono that Unity compiles against is pretty stupid. Smart compilers will see a foreach over an array backed data structure, and if the IEnumerator that is given by that structure is the standard, normal, simple kind, the compiler may figure out to implement that foreach as a regular for loop over the backing array. From what you are saying, this version of Mono is not smart enough to figure that out. Thus, there will be overhead.

Offline SalientBlue

  • Newbie Mark II
  • *
  • Posts: 13
Re: Optimization Techniques
« Reply #10 on: January 24, 2011, 01:03:31 PM »
Ah, I see.  Thanks for the in depth replies, guys.