{"id":320,"date":"2016-09-24T00:00:44","date_gmt":"2016-09-24T00:00:44","guid":{"rendered":"http:\/\/BryanWagstaff.com\/?p=320"},"modified":"2016-10-06T06:14:56","modified_gmt":"2016-10-06T06:14:56","slug":"programming-for-performance","status":"publish","type":"post","link":"https:\/\/bryanwagstaff.com\/index.php\/programming-for-performance\/","title":{"rendered":"Programming for Performance"},"content":{"rendered":"
\n

Working with games\u00a0means programming, but it is also a special kind of programming. \u00a0When working on a game you know will be used for competitive play in\u00a0some ways is like the Formula One race cars; everything you do needs to consider performance. When working on a game you may know that the game is going to do amazing things and must perform well. I’m going to cover a few key items on performance.<\/p>\n

<\/p>\n

Generally you shouldn’t bother.<\/h1>\n

First, there is a famous quote from a pioneer in computer science that applies here:<\/p>\n

Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We\u00a0should<\/em> forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only\u00a0after<\/em> that code has been identified.<\/p><\/blockquote>\n

That was written by Donald Knuth back in 1974<\/a>. While he was applying the rule to one specific area of programming it is sage advice that still applies.<\/p>\n

In his case he was talking about removing some code from outside a loop, which was important with the slow speed of computers at the time. At the time computers speeds were measured in kilohertz, 4-bit processors were\u00a0common, and programmers generally had advanced degrees in mathematics or engineering. \u00a0If you read the code in the article you might think “is that really a big change?” but back then he was reducing a loop from taking about 300 milliseconds per iteration to 200 milliseconds per iteration, so that is indeed a big difference.<\/p>\n

We\u00a0should<\/em> forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.<\/h2>\n

This line became an catchphrase for several decades. It is painful for many people to read, but it is important to understand. \u00a0Generally the code you work with every day is not a performance concern. \u00a0You should be smart about what you write as bad code can ruin performance, but in the general case, if you try to write code that is defect-free and follows typical coding standards the code will run just fine.<\/p>\n

Generally we don’t need to bother. \u00a0Generally we can go on our merry ways, blissfully ignoring anything about performance.<\/p>\n

Some time ago I wrote up an overview of what is happening inside the CPU<\/a>\u00a0which you may want to read if you aren’t familiar with it. Modern processors are amazing. Each processor core (or virtual core for hyper-threaded processors) can decode up to four instructions at once. \u00a0Internally there are registers that can run three or more sub-instructions per cycle. Generally the biggest problem is not the time required to run an individual computation. The most common problem is ensuring there is data to work with.<\/p>\n

And that leads us to the first big feature\u00a0that is part of that all-important 3%.<\/p>\n

Yet we should not pass up our opportunities in that critical 3%.<\/h2>\n

As much as we don’t need to worry about performance, that doesn’t mean we should intentionally make things slow. \u00a0It also isn’t universal. His off-the-cuff number of 3% feels about right to me in practice. \u00a0Usually most of the code isn’t a bottleneck. \u00a0Usually you find just a few elements in the code that are painfully slow, and a few more elements in code that cause performance to drop in unacceptable ways.<\/p>\n

What follows are some simple patterns you can follow to help with those critical parts.<\/p>\n

Keep your CPU Well Fed<\/h1>\n

The first one of those rules is to make sure you take advantage of something modern computer processors do extremely well.<\/p>\n

First, let’s give you a sense of scale. I’m going to talk about things like nanoseconds, but that is often hard to understand. Modern processors are able to compute values really fast. \u00a0There was a teacher years ago who wanted to show people how long a nanosecond is. \u00a0Most people are familiar with light, and are aware of how fast it travels. The teacher wanted to show everyone how short a nanosecond is. \u00a0Imagine a length of about 12 inches long — or about 30 centimeters long. \u00a0For many people that is roughly the length from the elbow to the hand. \u00a0That distance is how far light can travel in one nanosecond.<\/p>\n

A single CPU core generally runs about\u00a0four cycles per nanosecond, and the single core can cover up to\u00a0four instructions per cycle, although often they are limited to two or one; generally the number is closer to 8-10 decoded instructions per nanosecond. \u00a0And most computers have two or four or even more CPU cores inside them, with some server CPUs containing 24 cores. \u00a0On such systems, by the time a single photon of light can travel from your elbow to your wrist such a system could have decoded\u00a0more than 250\u00a0operations. \u00a0Or, if the programs are stalled, they could be sitting around idle waiting for data. \u00a0Waiting around as that same photon travels mile after mile, just waiting, accomplishing no work, with terrible performance.<\/p>\n

The first goal, then, is to make sure the CPU has something to do and doesn’t spend time waiting around for work.<\/p>\n

Everything you do in computer programming requires two things: \u00a0instructions and data. \u00a0Both of these are kept in memory. \u00a0Unfortunately memory is slower than the CPU speed. \u00a0Even though\u00a0computers get faster and faster every year, usually CPU speeds get slightly faster than memory speeds.\u00a0Today that means that even though a single CPU cycle takes about 0.25 nanoseconds, a request to get something from main memory takes about 120 nanoseconds. \u00a0Think about the scale for a moment. \u00a0While it could be doing about 10 things as it travels the length of your forearm, instead it is sitting there idle as light travels the length of a building. If each cpu cycle were one second long, the CPU would be sitting there for six minutes waiting for data instead of working\u00a0on to the next instruction. \u00a0Then the next instruction would be run, it would need data, and again the CPU would stall. \u00a0Without the cache since most instructions require data, the CPU would be waiting around for every instruction rather than doing useful work.<\/p>\n

Starting in the 1980s CPU\u00a0designers incorporated faster memory called caches. \u00a0This high speed memory is expensive, so they’re typically small. \u00a0I’ll go over the different caches and their approximate speeds:<\/p>\n