Wednesday, April 20, 2011

Optimization Goals  

In my day job, I've worked with many different teams of programmers. Game engine, game tools, OS, SDK, middleware, test engineers, you name it. Many of the people I work with are the best in the industry, true world-class programmers. And others, well, aren't... and that's okay too. :-)

Personally, I find that I've learned a ton from interacting with all of these different groups.

One of the most important lessons I've learned — and I'm frankly surprised this isn't more widely talked about — is that there are many different and equally valid possible optimization goals in programming.

When I talk to a new team, that's often the first thing I try to find out: what are your primary goals? What are you looking for?

The most common definition of optimization involves improving the runtime speed of the code. For example, game engine programmers are often very focused on this, because they have to cram as much work as they can into one frame — generally either 1/30th of a second (33.3ms) or 1/60th of a second (16.6ms). Naturally, this leads to a lot of counting cycles and downcoding inner loops into assembly.

However, game tool programmers tend to be a little more willing to sacrifice speed in favor of optimizing for other goals: development time, correctness, and ease-of-use. For example, it's often OK to use an unoptimized implementation of some algorithm in a tool, since a high-end PC will run it "fast enough". In other cases a tool might only run infrequently or overnight. Or it might be feasible to simply throw more hardware at the problem.

You also see it among different teams: a studio making a AAA game might be very focused on optimizing runtime speed, while a small indie team might be focused on optimizing for development cost — doing the work as cheaply as possible. These teams will have very different optimization goals, to the point that what the AAA game has downcoded to assembly might be C++ objects and STL in the other.

Then there are the sports games — which live in a fascinating alternate world all their own. These guys have to iterate and ship a new version once a year, every single year! Slipping is simply not an option, so they tend to optimize first for reliability, upgradeability, and ease-of-maintenance.

This got me thinking: what are all the possible optimization goals you might have?

Possible Optimization Goals

Here are some things that you may choose to optimize for in your development. It's impossible to optimize for all of these things simultaneously, but it's common to target more than one.

  • runtime speed - Run as fast as possible on your target system. Most of the optimization literature focuses on this. It involves choosing algorithms carefully, choosing your data layout carefully, looking for early exit opportunities, hand-optimizing inner loops, and so on.

  • development time - Complete the engineering work as quickly as possible. In other words, finish the job in a day or a week, rather than a month. Optimizing for development time may mean that you use the highest-level language available that will do the job, along with whatever third-party frameworks you can pull in to solve the problems you need solved. C#, Python, Ruby, etc.

  • development cost - Complete the engineering work as cheaply as possible. This is closely related to development time, but slightly different! The primary difference is the choice of who is doing the work: it might be cheaper (and a better investment) to have an intern use a task as a learning project and work on it for three months, than to have a senior programmer crank it out in three weeks.

  • correctness - Be absolutely sure there are no mistakes or bugs. Bug-free code is always a goal, of course, but sometimes it's even more important than usual. There are two common situations I can think of where correctness is your primary goal: (1) when creating a reference implementation of an algorithm, for possible later optimization. (2) when you're making important architectural decisions based on the results of some investigation or other; you'll generally double- and triple-check the investigation, if you're smart.

  • ease-of-use - Make sure users can grasp your interface quickly and achieve what they need to do. Funnily enough, this applies to both applications (user interfaces) and to middleware (developer interfaces). In both cases, you need to understand how people will expect to use the product. The fastest or easiest way to do things might not be the most understandable.

  • ease-of-maintenance - Make the code so straightforward a monkey could maintain it. Or you, in a few years. ;-) If you've ever had to go back and bug-fix some code that you (or god help you, someone else) wrote more than five years ago, you'll appreciate the value of this. Code that is well-written, easy to read, well-commented, and shaped well to fit the problem is code that is optimized for ease of maintenance. To some extent, this goal can be a cause of "not-invented-here" syndrome; the preference for in-house code is often born from a perfectly rational and reasonable desire to know how to maintain that code.

  • reliability - Never fail. Keep on going in the face of problems. At runtime, if the program gets unexpected input, don't crash: flag it, log it, and continue on with a sensible fallback behavior. At development time, always have a reference implementation to fall back to if the optimized version isn't working. In the extreme, reliability might require a reduction (hopefully small) in average-case performance just to ensure that the code can reliably handle uncommon edge cases. (LibC's memset and memcpy are examples of that.)

  • upgradeability - Make sure every subsystem can be upgraded. This is most commonly achieved with modularity. Good module separation should mean that individual pieces can be swapped out without too much trouble. If you remove modularity in order to run faster with today's situation, then you may be unable to upgrade to handle tomorrow's situation without a full rewrite.

  • iteration time - Minimize the time difference between when you make a change and when you are able to view and test the result. This covers a lot of ground and may include things like build time reduction, file loading, dynamic loading of updated assets, console boot time, and more. This is surprisingly important: the people who write the best software will almost always tell you that rapid iteration is king.

Did I miss any? What are you optimizing for?

3 comments:

  • Pierre said...

    You only give one "runtime speed" goal. For me, that actually covers a number of goals which may or may not be conflicting:

    setup speed - how fast a new program overlay (be it a process, a submodule, a subscreen, a game level) is ready to go.

    average (or amortized) runtime speed - how fast code runs on average; typically what is meant by "runtime speed"

    worst case runtime speed - very important for video, sound, animation, games to reach real-time constraints.

    maximum memory usage

    memory allocation/deallocation activity

    power consumption

    And there may be others…

    Cocoa, for instance, notoriously celebrates laziness to save on setup speed (which in turns help iteration time, as well) at the expense of worst case runtime speed (when you hit something that needs to be loaded on demand), which makes perfect sense in the context of application development, but makes it unsuitable for sound, where C/C++ with CoreAudio is used instead, with more expensive setup but a smooth run afterwards.

    Average runtime speed may conflict with worst case, for instance GCD uses lock-free algorithms and other tricks to get code running on multiple processors as efficiently (i.e. with as little overhead) as possible, but as a result may not respect real-time constraints, Apple still recommends threads for that purpose. The fastest algorithms are not necessarily the most respectful of priorities (and the converse is true as well). And everyone complains that mutexes are slow, and they do have undesirable overhead in the uncontested case, but the worst case here is when the mutex is already held, and here the mutex runtime speed matters much less; on the other hand, mutexes have other properties which make them indispensable real-time system building blocks.

    Maximum memory usage is obviously necessary to optimize to even get a game to run in production on systems with a memory budget like a console, but it may matter on the desktop as well: if you have a utility application that takes up all the memory it can in the name of caching to optimize average runtime speed, it may cause other applications to page out and make them slow when the user comes back to them, causing the system to be slower overall (and in turn causing the user to trash the utility); on the other hand a fullscreen computer game may not need to care about this as much.

    By allocating memory on a small granularity and releasing it as soon as you can, you may have pretty low maximum memory usage, but on the other hand you induce more memory allocation/deallocation activity, which may in turn impact average runtime speed, or impact you in other ways. On the other hand if you allocate in big batches and hold onto memory, you reduce that activity and typically improve average and worst case runtime speeds, but increase maximum memory usage and possibly setup time.

    The obvious case for a power consumption/average and worst case runtime speed tradeoff is when polling: the faster you poll, the faster you'll react, but the more you drain power. Of course, the solution to solve both is to switch to asynchronous APIs, if they are available.

    And those are only the tradeoffs on top of my head…

    Another case where development time may conflict when development cost is when (typically in order to be first to market) you put a bunch of people on a project to start and complete it fast: it will end up costing more than if only one or two people worked on it (i.e. require more man-months overall) due to the unavoidable communication inefficiencies.

  • scott huminski said...

    покушения на свою оппозицию американскогополицейского государства.

    Свобода музыкальных клипов наступление на правительство США, по крайней,

    http://www.youtube.com/user/scottxmysteryband

    Правительство Соединенных Штатов стала неистовой Споследней записи рок-группы, или бой на пребываниебесплатно

    http://www.purevolume.com/ScottXandtheConstitutionCommandos/albums/Fighting+the+U.S.+Police+State+with+Music


    Конституция команды запросить поддержку от международных организаций в их борьбе против американской террористической государственной полиции. ПравительствоСоединенных Штатов находит политической речью в музыке, как наступление, как террор и взрывы самодельных взрывных устройств. Речь критикует правительство в настоящее время является преступлением в Соединенных Штатах.


    الموسيقار الاميركي روك مواجهة السجن لأغاني تاريخية وسياسية وأشرطة الفيديو والموسيقى.

    سكوت X والمغاوير الدستور يواجهون السجن والاغتيال المحتملة لمعارضتهم للدولة على السياسة الاميركية.

    وأشرطة الفيديو والموسيقى حرية هجومية لحكومة الولايات المتحدة وصلت،

    http://www.youtube.com/user/scottxmysteryband

    أصبحت حكومة الولايات المتحدة غاضبة من أحدث ما تم تسجيله من لموسيقى الروك، أو القتالفي البقاء الحرة



    الأوامر دستور طلب الدعم من المنظمات الدولية في نضالهم ضد الدولة البوليسية الإرهابيةالأمريكية. حكومة الولايات المتحدة ترى أن الخطاب السياسي في الموسيقى كما خليع التفجيرات الإرهابية والعبوات الناسفة. خطاب حاسم من الحكومة الآن جريمة في الولايات المتحدة.

  • Teo T said...

    Hi Drew,

    Great post. I've been reading through your blog, and for an aspiring programmer there's some really useful tips here, that you write in a detailed but concise, easily digestible fashion.

    I was wondering if you would be interested in sharing your blog on Glipho? Glipho is a new social blogging network that aims to promote the writing of its users and help build their audiences. We are trying to establish a creative community at Glipho, and your blog is just what we are looking for.

    As your blog is powered by Blogger, you can simply import all your old posts to Glipho without affecting your existing blog at all. You can use your Glipho account to connect to any other major social network accounts you may own, so you can spread your blog as far as possible. We also use our own social media accounts to promote your content.

    If you're interested check out our website at http://glipho.com and have a look around. Please feel free to ask me any questions, and if you would like to receive an invite to set up an account!

    Have a great day,

    Teo



    Glipho Limited
    14 Suite 3 D
    Docklands Business Centre
    10-16 Tiller Road
    London E14 8PX


    (e): teo@glipho.com
    (w): www.glipho.com