I am a second year student of Computer Games Technology. I recently finished my first prototype of my "kind" of own pathfinder (that doesn't use A* instead a geometrical approach/pattern recognition, the pathfinder just needs the knowledge about the terrain that is in his view to make decisions, because I wanted an AI that could actually explore, if the terrain is already known, then it will walk the shortest way easily, because the pathfinder has a memory of nodes).

Anyway my question is more general: How do I start optimizing algorithms/loops/for_each/etc. using Assembly, although general tips are welcome. I am specifically looking for good books, because it is really hard to find good books on this topic. There are some small articles out there like this one, but still isn't enough knowledge to optimize an algorithm/game...

I hope there is a modern good book out there, that I just couldn't find...

  • 1
    \$\begingroup\$ This doesn't answer your question directly, but explorative (so called adaptive) A* has been investigated and has really good performance (meaning you won't need to optimize it using ASM). Have a look at D* Lite. \$\endgroup\$ – Jonathan Dickinson Nov 14 '11 at 13:39

I'll be the one going against the grain here and say, it is never too early to learn about optimizations, especially assembly optimizations and more importantly, debugging in assembly. I believe that you will gain the maximum benefit of it if you are a student (because then you have very little to lose [i.e. time/money wise]) and everything to gain.

If you are in the industry and not tasked with tinkering around in assembly, then don't. Otherwise, if you are a student or have time in general, I would find the time to learn to disassemble programs and see if I can come up with a better solution than the compiler. If I can't, who cares! I just learned how to write as well as compiler and that is a HUGE plus when you are faced with a bug in release code (with no debug symbols) and staring at the disassembly because that's the only thing you can look at.

The answer

This is one of the best resource I have found for learning about optimizations.


The rant

If you read some articles by major developers (for example, reasoning behind the making of EASTL and closer inspection of the code will lead you to comments like did this because GCC is terrible at inlining this if statement which will tell you, what the majority of people tell you trust the compiler is not always right, ESPECIALLY in game development) and then set foot in the industry you will find that optimizations are an everyday thing and knowing what the assembly output means is a big plus. Also, people don't seem to realize (especially on stackoverflow) that profiling games is very hard and not always accurate.

There is a caveat though. You can spend time optimizing something and later on realize that was time wasted. But what did you learn? You learned not to repeat that same mistake in a similar circumstance.

What SO is now taking is in my opinion a religious stance to the statement don't optimize until you profile and don't worry, the compiler knows better than you. It hinders learning. I know experts in the industry who are paid very good money (and I mean VERY good money) to fiddle around in assembly to optimize the game and debug it because the compiler is bad at it or simply cannot help you, because, well, it cannot (GPU related crashes, crashes where data involved is impossible to read in a debugger etc. etc.)!

What if someone who loves doing that, hasn't fully realized it yet, asks the question here and is turned away/off by the many answers compiler knows better than you! and never becomes one of those highly paid programmers?

One final thought. If you start doing this early, you will find that soon you will start writing code that is at worst, has no performance improvements whatsoever because the compiler optimized it the same way or at best, has some performance improvements because now the compiler can optimize it. In either case, it has become habit, and you are no slower at writing code this way than what you did before. A couple of examples are (there are many more):

  1. Pre-incrementing unless you really want post-increment
  2. Writing loops for containers using a constant local size variable rather than calling size() on the container within the loop.

EDIT: Update after 8 more years in the industry. Learn assembly. Learn how optimizers work and the assembly they generate (CompilerExplorer is a great tool for that). I have run across countless crashes in Test builds (optimized builds for internal testing) where you cannot rely on the debugger even with debug symbols. The compiler has optimized out too many things and the assembly is your only source of valuable information to find the bug from the crash dump. Each build takes 30-40min if you're lucky and first in the build queue - so you cannot rely on some traditional techniques to isolate the bug. Multiplayer makes things worse. Knowing assembly and how to read optimized assembly will simply make you better and ultimately more valuable to the team.

| improve this answer | |
  • 1
    \$\begingroup\$ Good point about optimizing compilers. They are great to have, but they are far from perfect, and unlike what some people believe it is usually not hard to find a simple optimization that a compiler did not make. \$\endgroup\$ – aaaaaaaaaaaa Nov 13 '11 at 16:13
  • 3
    \$\begingroup\$ It should be noted that there is a difference between "learning to read assembly" and "learning to optimize with assembly". The two are not the same thing, and your answer doesn't really touch on using assembly to implement optimizations. Reading assembly is a useful skill, as it can help in debugging and spotting places where the compiler isn't doing something right. But that's very different from actually using assembly to write optimized routines, which requires deep knowledge of instruction scheduling for a specific CPU. And it's also something you didn't cover. \$\endgroup\$ – Nicol Bolas Nov 13 '11 at 19:50
  • 1
    \$\begingroup\$ Also, "I just learned how to write as well as compiler" No, you did not. You looked how one specific routine was compiled for one specific CPU. Learning how to implement optimized assembly routines requires more than looking at how the compiler compiled one routine. You have to understand why the compiler chose those opcodes in that order to reproduce that specific C++ code. And that requires intimate knowledge of the CPU, instruction scheduling, and so forth. Generalizing this requires years of experience; you won't get it by just decoding a couple of routines. \$\endgroup\$ – Nicol Bolas Nov 13 '11 at 19:55
  • 7
    \$\begingroup\$ So, -1 for A: not actually answering the question about how to write assembly-optimized routines. B: misrepresenting how easy it is to learn how to beat the compiler at writing assembly-optimized routines. And C: encouraging a programmer to look at assembly-level optimizations before algorithm-level optimizations. Even those highly paid "experts in the industry" would tell you that that's putting the cart before the horse. \$\endgroup\$ – Nicol Bolas Nov 13 '11 at 19:59
  • 2
    \$\begingroup\$ @Samaursa: Nobody said that people shouldn't "understanding disassembly and how to optimize code." This is not a religious debate; it's a matter of simple fact. People have spent man-centuries hand-optimizing some routine only to find out that it means nothing to overall performance. Learning how to optimize algorithms is a highly-valuable skillset. Learning how to read assembly is a semi-valuable skillset. Learning how to write assembly routines is a skillset that is only rarely of use. And these days, the best optimizations come from better cache utilization, not hand assembly. \$\endgroup\$ – Nicol Bolas Nov 14 '11 at 1:46

The first tip you'll get is this - don't.

Modern compilers are actually really really good at optimizing code, and will be much more likely to do a better job of it than any self-rolled assembly language you may write.

The exception would be any specific case where you have determined for certain that the compiler is doing a bad job of optimizing, so that's the second tip. There are no general guidelines here, you need to know your own code, know what it's doing, be able to jump into a disassembly of it, and be able to determine for absolute certain that the compiler is doing a bad job.

Even in this case you still may not want to. You need to be certain that there is not going to be any ongoing maintenance overhead for you. You may wish to come back to this code in 6 months time and modify part of it, or you may find an extremely subtle bug that's going to be more difficult to fix in an assembly language version. Even if you think you've worked all the bugs out, once your program goes to the public bugs you never even thought could happen will become a reality for you. That's quite an eye-opener (and a humbling experience).

And even if you're happy to accept that, you may still find that there is absolutely no measurable performance improvement as your main bottleneck could be somewhere completely different in your program. So that brings me back to number 1 again. Don't.

| improve this answer | |

Usually, solid optimisation doesn't depend on using Assembly, or doing micro-optimisations with code in higher level languages. If you read a lot of research papers (as I do -- or try to!), you'll see that oftentimes the improvements made to algorithms are at a broader conceptual, "qualitative" level, rather than at the more "quantitative" level of micro-optimisation. I would stress that order-of-magnitude gains are more likely to be found by looking at algorithms from this point of view, or from vectorising/parallelising existing solutions.

Having said that, I recently happened upon this, which may be a good route towards learning x86 ASM specifically for game developers.


Two sources off the top of my head:

Additionally, reading research papers is an excellent way to follow the thought processes of the wise as they optimise algorithms for better performance. Most often, gains are seen by:

  • Reducing the use of the most costly operations (div, SQRT, trig ops, and conditionals, primarily);
  • Improving cache performance through use of more efficient data structures, memory alignment, and reduced conditionals;
  • Reducing quality of output in acceptable areas for improved performance;
  • Vectorisation (SIMD);
  • Parallelisation (threading, includes shifting tasks off to the GPU);
  • And of course (increasingly rarely) hand-coded assembly. First inspecting C/C++ assemblies to see where the compiler is making non-optimal choices, of course. You will find more of this in older papers from the 80's and 90's, IME.

Reading research also keeps you at the cutting edge of your field, instead of waiting for that knowledge to filter down into the industry.

| improve this answer | |
  • \$\begingroup\$ you talk about algorithm optimisation but you give no information on it, if we were to follow you advice and look at that instead could you give some direction ? \$\endgroup\$ – Skeith Nov 14 '11 at 13:07
  • \$\begingroup\$ In fact, I do mention it; you need to study algorithms, understanding what it is that computer scientists do to qualitatively improve performance. Immerse yourself in this enough, and in time, you begin to think in similar terms. Incremental efforts here pay off big time, as opposed to spending years (and I recently saw this mentioned on an ASM forum) mastering the ins and outs of (just) eg. x86 architecture. Hunt the big game: learn to whittle problems down to their very core, and then decide what is superfluous in order to optimise. See ref books above. \$\endgroup\$ – Engineer Nov 14 '11 at 13:46
  • \$\begingroup\$ @NickWiggill What's your usual source of research papers? \$\endgroup\$ – kizzx2 Jul 27 '14 at 8:05

I think it might be too early.

Anyway, it is important to understand that the compiler itself does not produce slower code than the assembly equivalent, you don't get any performance simply from writing the same assembly code as the compiler would.

For a start at least concentrate on assembly-free optimizations. Igor Ostrovsky have a few good articles that demonstrate some of the basics: http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/

Do note that branch mispredictions and cache misses are what you should primarily optimize against, even if you have to pay by doing some extra arithmetic operations it is usually worth it to avoid an unpredictable branch or reading randomly from too much memory.

And of course, most importantly, optimize your algorithm first. A slow implementation of a fast algorithm will almost always be faster than a fast implementation of a slow algorithm.

| improve this answer | |

This book is exceptionally good for a text book. But its not specifically geared towards optimization. Assembly Language for x86 Processors, 6th edition

It's more about teaching the fundamentals of assembly, using MASM. Then towards the end of the book it gets into how to inline assembly with c++ and integrate it into bigger programs.

I put this up here because it makes sense to learn the fundamentals of assembly before you learn how to optimize programs with it.

I like this book because Irvine teaches you how to use the tools needed to write masm programs. He specifically goes into how to use the IDE (Visual Studio C++) and the debugger. Each chapter has a few videos dedicated towards solving problems. Some of this information is available freely on the website listed.

| improve this answer | |
  • 1
    \$\begingroup\$ "it makes sense to learn the fundamentals of assembly before you learn how to optimize programs with it" - good advice. \$\endgroup\$ – Maximus Minimus Nov 16 '11 at 12:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.