251
15
High‐PerformanceProgramming
withData‐OrientedDesign
Noel Llopis
Snappy Touch
Common programming wisdom used to encourage delaying optimizations until
later in the project, and then optimizing only those parts that were obvious bot-
tlenecks in the profiler. That approach worked well with glaring inefficiencies,
like particularly slow algorithms or code that is called many times per frame. In a
time when CPU clock cycles were a good indication of performance, that was a
good approach to follow. Things have changed a lot in today’s hardware, and we
have all experienced the situation where, after fixing the obvious culprits, no sin-
gle function stands out in the profiler but performance remains subpar. Data-
oriented design helps address this problem by architecting the game with
memory accesses and parallelization from the beginning.
15.1ModernHardware
Modern hardware can be characterized by having multiple execution cores and
deep memory hierarchies. The reason for the complex memory hierarchies is due
to the gap between CPU power and memory access times. Gone are the days
when CPU instructions took about the same time as a main memory access. In-
stead, this gap continues to increase and shows no signs of stopping (see Fig-
ure 15.1).
Different parts of the memory hierarchy have different access times. The
smaller ones closer to the CPU are the fastest ones, whereas main memory can be
really large, but also very slow. Table 15.1 lists some common access times for
different levels of the hierarchy on modern platforms.
252 15.High‐PerformanceProgrammingwithData‐OrientedDesign
Figure 15.1. Relative CPU and memory performance over time.
With these kinds of access times, it’s very likely that the CPU is going to
stall waiting to read data from memory. All of a sudden, performance is not de-
termined so much by how efficient the program executing on the CPU is, but
how efficiently it uses memory.
Barring a radical technology change, this is not a situation that’s about to
change anytime soon. We’ll continue getting more powerful, wider CPUs and
larger memories that are going to make memory access even more problematic in
the future.
Looking at code from a memory access point of view, the worst-case situa-
tion would be a program accessing heterogeneous trees of data scattered all over
memory, executing different code at each node. There we get not just the con-
stant data cache misses but also bad instruction cache utilization because it’s call-
ing different functions. Does that sound like a familiar situation? That’s how
most modern games are architected: large trees of different kinds of objects with
polymorphic behavior.
What’s even worse is that bad memory access patterns will bring a program
down to its metaphorical knees, but that’s not a problem that’s likely to appear
anywhere in the profiler. Instead, it will result in the common situation of every-
thing being slower than we expected, but us not being able to point to a particular
spot. That’s because there isn’t a single place that we can fix. Instead, we need to
change the whole architecture, preferably from the beginning, and use a data-
oriented approach.
1
10
100
1000
10,000
1980 1985 1990 1995 2000 2005
C
P
U
:
2
×
e
v
e
r
y
2
y
e
a
rs
D
R
A
M:
2
×
e
v
e
r
y
6
y
e
a
r
s
Relative performance
Gap
15.2PrinciplesofData‐OrientedDesign 253
Memory Level CPU Cycles
per Access
Register 1
L1 cache 5–8
L2 cache 30–50
Main memory 500+
Table 15.1. Access times for different levels of the memory hierarchy for modern plat-
forms.
15.2PrinciplesofData‐OrientedDesign
Before we can talk about data-oriented design, we need to step back and think
about what a computer program is. One of the most common definitions of a
computer program is “a sequence of instructions to perform a task.” That’s a rea-
sonably good definition, but it concentrates more on the hows rather than on the
whys. What are those instructions for? Why are we writing that program?
A more general definition of a computer program is “something that trans-
forms input data into output data.” At first glance, some people might disagree
with this definition. It might be true for the calculations in a spreadsheet, but is it
really a good description for a game? Definitely. In a game, we have a set of in-
put data: the clock value, the game controller state, network packets, and the state
of the game during the previous frame. The outputs we’re calculating are a new
game state, a set of commands for the graphics processor, sound, network pack-
ets, etc. It’s not very different from a spreadsheet, except that it runs many times
per second, at interactive rates.
The emphasis in Computer Science and Engineering is to concentrate on al-
gorithms and code architecture. In particular, procedural programming focuses
on procedure and function calls as its main element, while object-oriented pro-
gramming deals mostly with objects (which are sets of data and the code that
works on that data).
Data-oriented design turns that around and considers data first: how it is laid
out and how it is read and processed in the program. Then, the code is something
written to transform the input data into the output data, but it itself is not the
focus.
As a consequence of looking at the input data carefully, we can apply another
principle of data-oriented design: where there’s one, there are more. How often
254 15.High‐PerformanceProgrammingwithData‐OrientedDesign
have you had just one player in the game? Or one enemy? One vehicle? One bul-
let? Never! Yet somehow, we insist on treating each object separately, in isola-
tion, as if it were the only one in the world. Data-oriented design encourages
optimizing for the common case of having multiple objects of the same type.
15.3Data‐OrientedDesignBenefits
Data-oriented design has three major performance benefits:
1. Cache utilization. This is the big one that motivated us to look at data in the
first place. Because we can concentrate on data and memory access instead
of the algorithms themselves, we can make sure our programs have as close
to an ideal memory access pattern as possible. That means avoiding hetero-
geneous trees, organizing our data into large sequential blocks of homogene-
ous memory, and processing it by running the same code on all of its
elements. This alone can bring a huge speed-up to our code.
2. Parallelization. When we work from the data point of view, it becomes a lot
easier to divide work up into parts that different cores can process simultane-
ously with minimal synchronization. This is true for almost any kind of par-
allel architecture, whether each core has access to main memory or not.
3. Less code. People are often surprised at this one. As a consequence of look-
ing at the data and only writing code to transform input data into output data,
there is a lot of code that disappears. Code that before was doing boring
bookkeeping, or getter/setters on objects, or even unnecessary abstractions,
all go away. And simplifying code is very much like simplifying an algebraic
equation: once you make a simplification, you often see other ways to simpli-
fy it further and end up with a much smaller equation than you started with.
When a technique promises higher performance, it often comes at a cost in
some other department, usually in terms of readability or ease of maintenance.
Data-oriented design is pretty unique in that it also has major benefits from a de-
velopment perspective:
1. Easier to test. When your code is something that simply transforms input
data into output data, testing it becomes extremely simple. Feed in some test
input data, run the code, and verify the output data is what you expected.
There are no pesky global variables to deal with, calls to other systems, inter-
action with other objects, or mocks to write. It really becomes that simple.
15.4HowtoApplyData‐OrientedDesign 255
2. Easier to understand. Having less code means not just higher performance
but also less code to maintain, understand, and keep straight in our heads. Al-
so, each function in itself is much simpler to understand. We’re never in the
situation of having to chase function call after function call to understand all
the consequences of one function. Everything you want to know about it is
there, without any lower-level systems involved.
To be fair and present all the sides, there are two disadvantages to data-
oriented design:
1. It’s different. So far, data-oriented design isn’t taught in Computer Science
curricula, and most developers aren’t actively using it, so it is foreign to most
team members. It also makes it more difficult to integrate with third-party li-
braries and APIs that are not data-oriented.
2. Harder to see the big picture. Because of the emphasis on data and on small
functions that transform data, it might be harder to see and express the big
picture of the program: When is an operation happening? Why is this data
being transformed? This is something that might be addressed with tools,
language extensions, or even a new programming language in the future. For
now, we’ll have to rely on examining the code and the data carefully.
15.4HowtoApplyData‐OrientedDesign
Let’s get more specific and start applying data-oriented design. Eventually, we’d
like the entire game to be architected this way, but we need to start somewhere.
So pick a subsystem that needs to be optimized: animation, artificial intelligence,
physics, etc.
Next, think about all the data involved in that system. Don’t worry too much
about how it is laid out in memory, just about what’s involved. Apart from the
explicit inputs and outputs, don’t forget about data that the system accesses ex-
plicitly, such as a world navigation graph, or global handle managers.
Once you have identified all the data the system needs, carefully think about
how each type of data is used and sort them into read-only, read-write, or write-
only. Those will become your explicit inputs and outputs. It will also allow you
to make better decisions about how to lay out the data.
Also, at this point, it’s important to think about the amount of data. Does this
system ever process more than one of each type of data? If so, start thinking of it
in terms of arrays of data, preferably as contiguous blocks of the same data type
that can be processed at once.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.