Pangram verdict · v3.3
We believe that this text is a mix of AI, AI-assisted, and human-written content.
AI likelihood · overall
MixedArticle text · 1,611 words · 11 segments analyzed
This article was originally published in Polish in issue 4/2013 (11) of Programista magazine. Although high-level languages—scripting, interpreted, or running in a virtual machine—have many advantages and are the best choice for numerous applications, sometimes we need to write code that is as efficient as possible. Choosing a native language such as C++ is not enough. Only some knowledge and familiarity with good practices will let us get the most computing power out of the hardware. Introduction C++ is an unusual language: complex, difficult to master, and controversial in some respects. Yet in many applications, especially where performance matters, such as game programming, it is often the best or even the only choice. This is because it has a unique property that makes it a kind of compromise. It is high-level: it supports object-oriented programming and convenient use or creation of custom types and data structures, such as vectors, strings, and other STL containers. At the same time, it is low-level enough to give us access, in a sense, to the hardware itself, or rather to the operating system: no virtual machine or framework stands in the way. We must manage memory allocation and deallocation ourselves, but that also means there is no garbage collector doing it in its own way at unpredictable moments. Moreover, an enormous number of libraries exist for C++ (and for C, with which it is partly backward compatible), and compilers are available for many platforms. In a sense, one could even say that native code is coming back into favor. Although software is becoming increasingly complex and hardware increasingly fast, we still need efficient code in our programs. Some say that a faster processor or more RAM costs less than a good programmer's time. But what if a program, once written, is to run for many years or be installed on millions of machines?
Performance matters both in computing clusters and data centers, where power and cooling costs can be enormous, and in the smallest devices, such as smartphones and tablets, where we want the longest possible battery life. There are also applications in which code must run at a specified speed without compromise. These include programs that process data in real time, such as games (where a drop in FPS, frames per second, destroys the impression of smooth animation and causes unpleasant stuttering) or real-time processing of media streams at a specified bitrate.
Nor can we always set arbitrarily high hardware requirements. Game consoles, for example, have a fixed processor speed and amount of RAM. Even of a PC we cannot demand the latest components if we are writing a simple casual game rather than a new version of Crysis.
Data-Oriented Design Object-oriented programming seems to be a remedy for the difficulties faced by programmers and teams for whom writing large systems in a structured way—the “old-fashioned” way—would be too hard. In object-oriented programming, code consists of classes, which not only group data (fields) and the procedures that operate on it (methods), but above all serve as abstractions of concepts from the real world or from the problem domain. Classes should also be, at least in theory, as independent and reusable elsewhere as possible. Object-oriented programming can, however, be understood in two ways: conceptually, by thinking about the philosophy behind its elements, or technically, by treating it as a programming-language mechanism used for convenience. It is also worth understanding how it all works “under the hood” and what properties and limitations follow from that. Following only the first approach can take us too far from the level at which a programmer should remain when aiming to write efficient code.
What, then, is the solution? Supporters of an approach called Data-Oriented Design (DOD) suggest a somewhat different way of thinking. The term has become popular in recent years, especially among game programmers.
It means focusing during design and coding on the data that will be stored: its layout in memory and the design of suitable data structures, and only then on the algorithms that will operate on it. This may seem like a return to the old idea of structured programming, but it does not rule out using classes and all the benefits of object-oriented programming. It is more a way of thinking that stays closer to the hardware and uses the language's available mechanisms to create code that is not only “elegant” but also simple and efficient. Look at Figure 1. It symbolically shows how data is laid out in memory. On the left are structures scattered far apart and connected by pointers. This happens when we use many small objects of different classes that refer to one another. Code written this way can be inefficient for two reasons. The first is frequent cache misses when traversing such data because we “jump” through pointers. This is discussed in more detail below. Figure 1. Data-Oriented Design The second reason is the difficulty of parallelizing code that operates on such objects. If all we have are the classes' public methods (often virtual), and our assumption is that we do not know what happens inside them (or inside all their derived classes), then by definition we cannot safely run them on multiple threads. We do not know which other objects they refer to during those operations. Using threads, meanwhile, often requires protecting shared data with mutexes (critical sections), which effectively serialize the code and prevent it from running fully in parallel. The right side of the figure, in turn, shows the idea of a regular data structure (such as an array) that we process by performing successive operations on it: sorting, updating particular fields, deleting elements, or converting every element to another form. If the data is “transparent” and we know exactly what operation we want to perform, and if applying it to each element of the collection is independent of the other elements and the rest of the program, then we can easily parallelize the algorithm, for example by dividing the range of elements among threads. Blindly following object-oriented programming brings other pitfalls too. Some people instinctively wrap every piece of functionality they use, such as a library, in a wrapper of their own that is supposed to simplify its interface or make it (subjectively) more elegant. Such an extra layer, especially when it introduces its own logic or uses virtual methods, adds runtime overhead.
I suggest instead making a habit of asking each time whether, in this particular case, we could simply use certain functions and classes directly, without adding another layer of abstraction. There is a similar tendency to make everything as general and universal as possible.
Defining an interface consisting entirely of virtual methods and promising ourselves that we can replace the implementation with a completely different one without changing the interface is tempting, but do we really need that here and now? Design patterns, too, are sometimes overused as ready-made solutions that replace deeper thought about the code.
In fact, simple solutions are often best. If we try to express as directly as possible what data a program must store and what operations it must perform on that data, the code will be simple, elegant, readable, and efficient at the same time. This contradicts the popular view that optimization means making code complicated and unreadable. Memory and Cache It might seem that each processor instruction reads some data from specified addresses in RAM in one cycle, performs an operation on it (such as addition), and writes the result back to memory. In practice it is not that simple. The complex CISC instructions that make up x86 code are translated into microcode inside the processor and executed in multiple steps that may take more or less time. The operation itself may be simple, but reading or writing data in memory takes additional time. In the past, in the 1980s, processors did indeed access RAM directly and could perform such operations in single cycles. Today, unfortunately, the speed at which a processor can perform computations is increasing much faster than RAM performance. This gap keeps growing, and already the time needed to read a piece of data—even a single byte—from a modern computer's main memory is equivalent to several hundred processor cycles! Remember that bandwidth, the rate of data transfer (measured in bits per second), differs from latency, the time required for requested data to reach its destination (measured in fractions of a second). Computer designers naturally look for solutions to this problem.
This is why cache was created: processor memory that holds recently used data and is faster to access than main RAM. We can speak of an entire memory hierarchy whose successive levels have increasing capacity but decreasing speed.
Consider, for example, a processor running at 3 GHz. Approximately speaking, it can perform 3 billion operations per second, so one simple operation (such as addition) takes about 0.33 ns. If access to a value in the L1 cache takes 1 ns, that delay is equivalent to executing 3 instructions (3 cycles). Table 1 gives estimated figures for the memory hierarchy in such an example computer system. Memory typeAccess timeCapacity Processor registers0.33 ns1 cycle L1 cache1 ns3 cycles32 KB L2 cache4.7 ns14 cycles6 MB RAM83 ns250 cycles8 GB Hard disk15 ms45 million cycles1 TB Internet80 ms240 million cycles Table 1: Memory hierarchy In a typical computer system, we do not control the cache directly. It is managed automatically to speed up access to recently used data. How, then, can we benefit from its speed? We need a basic understanding of how it works. When previously unused data is accessed in RAM, it is read and used for computation, but it also enters the cache.