Is random access always slower? It depends on the scale. Cache lines act to even out small-scale randomness. For instance, if you have a small struct and access its members out of order, you may not notice a difference in performance. If the struct fits in a cache line and is aligned, then the order won’t matter at all because accessing one member has the same cost as any other. As the scale of randomness varies, for instance with larger structs, then the effects are more pronounced.

How Random Is Random?

We have implemented a test to explore randomness confined to a stride size. This source for this test is available in the Performance Test Harness: “memory/traverse/linearLT512byteRandomStatic.” The results are shown in Figure 6.3.

Figure 6.3. Randomness in fine granularity (from 0 to 512 bytes granularity) yields the best performance when randomness strides are very small.

Each data point represents traversal through four megabytes, with the stride of random access getting larger at every point. This performance test is similar to stepping through an array of structures and accessing each current structure’s member in a random order.

So far, we have only discussed automatic hardware pre-fetching’s impact on accessing a single stream of memory. Most CPUs can actually support multiple streams. The number of effective streams is difficult to generalize. It depends on the number of active processes, the specific chip, operating system behavior, and so forth.

The Intel documentation suggests that the number of concurrent streams in Intel processors differs from processor to processor but is in the range from 8 to 16 (Intel, 2008). The best practice is to measure it—which we’ve done—and design your application to rely on a minimum of memory access. Figure 6.4 shows our results.

Figure 6.4. The number of arrays we are reading concurrently changes our performance. On this Intel Xeon, there is a significant penalty reading above eight streams. We traversed slightly less than 4MB, because parsing exactly 4MB causes a different cache penalty. The source for this chart is available in the perf Test Harness test “memory/stream/memorystream.”

So what is the conclusion? In the quad-core 3Ghz Intel Xeon used in the test, hardware pre-fetching will suffice when you have fewer than eight memory arrays streaming per processor. The more streams you use, after eight, the worse your performance will be. (Again, this number can and will differ from processor to processor, so you will want to do your own tests on your target hardware.)

An important side note: We chose arrays slightly smaller than 4MB for several reasons. One, it is slightly smaller than an OS memory page. This is important because many hardware pre-fetch implementations do not allow more than a single stream per page (Intel, 2008). Unfortunately, iterating at a stride of exactly 4K causes problems with the cache on our test systems. This issue is discussed more in the “Fix Critical Stride Issues” section of this chapter.

Layout of memory is crucial, and one way to maximize linear access through memory is to choose the appropriate data structure. There are two major possibilities for laying out memory.

Typically, we create array of structures (AOS). They take the following form:

struct aos
{
     float m_Float1;
     float m_Float2;
     float m_Float3;
     float m_Float4;
};

aos myArray[256];

AOS is used in a lot of scenarios. Most APIs organize their data this way. OpenGL is notable in supporting both AOS and SOA.

The other, somewhat less popular format, is a structure of arrays (SOA):

struct soa
{

     float m_Float1[256];
     float m_Float2[256];
     float m_Float3[256];
     float m_Float4[256];
};

soa myArray;

The difference is subtle. They both hold the same amount of data, and they are functionally equivalent. Why choose one structure over the other?

In Figure 6.5, you can see the effect of each structure in memory. Interleaved memory, like the AOS, would be appropriate if you were planning to iterate through every member and every iteration. But what if you were only going to iterate through one member at a time?

Figure 6.5. The position of members for an array of structures as opposed to a structure of arrays.

By using the array of structures and iterating through only one member, you are much closer to periodic access. If you use the structure of arrays and iterate through one member, your access pattern is more similar to linear than periodic.

Understanding the difference between AOS and SOA is helpful when writing multi-threaded code as well. We will discuss this in Chapter 13, “Concurrency.”

When using an AOS, you can still make some accommodations for better cache usage. When you strip mine, you split iteration of single members (periodic access) into cache-friendly chunks. This technique increases both temporal coherence and spatial locality.

Consider the following code:

for( int i=0;i<numStructs:i++ )
{
      m_Vertex[i].pos = processPos(&m_Vertex[i].pos);
}

for( int i=0;i<numStructs:i++ )
{
      m_Vertex[i].normal = processNormal(&m_Vertex[i].normal);
}

As the first loop iterates, the automatic hardware pre-fetch will fetch data in anticipation of its use; if the loop is large enough, later parts of the loop may evict values fetched earlier. If the evictions occur, the second loop will not benefit from the first loop’s use of the cache.

A solution is to perform both loops together using blocks of access and performing memory loads on both members. This is called strip mining.

for( int j=0;j<numStructs;j+=blocksize)
{
      for( int i=j;i< blocksize;i++ )
      {
            m_Vertex[i].pos = processPos(&m_Vertex[i].pos);
      }
      for( int i=j;i<blocksize;i++ )
      {
            m_Vertex[i].normal = processNormal(&m_Vertex[i].normal);
      }
}

Much better. Now the first loop is warming the cache for the second loop and an increase in overall performance occurs. The optimal block size can differ from processor to processor because cache size is not standard.

When you step into a function, instructions push the parameters onto the stack; any variable whose scope exists within the function will be placed on the stack as well. As you load, store, and calculate values within the function, they are likely to remain in the cache because the stack maintains proximity. When a function returns, you are simply moving down the stack.

The stack has the advantage of maintaining spatial locality and temporal coherence. It is always in use, so it tends to stay in cache. Data is grouped well, since all the data used by a function is adjacent.

Of course, stack space is finite. Especially when working with recursive code, minimizing stack usage is important because it will give you better performance.

Global memory is memory that is allocated as part of your program image. Static and global variables are stored here, the only difference being the scope. Global memory is not freed until your program closes, which is a great way to eliminate memory fragmentation—a common cause of cache misses due to a lack of locality.

Typically, the linker allocates global memory based on the order that the linker receives object files. Therefore, items that are frequently accessed together may benefit from being in the same linkage unit (i.e., same .cpp or .c file for C/C++ developers) in order to preserve locality. It can also be possible to specify explicitly where in the image globals are allocated. Check with your specific compiler to see how it handles global variables. Things like profile-guided optimization could affect variable order, too.

One important caveat about sharing global variables occurs when you are accessing variables with multiple threads. Variables that are co-located in memory may suffer performance due to a synchronizing performance problem called false sharing. For more on false sharing, see Chapter 13.

Memory created or freed dynamically uses the heap. For C++ developers, this typically involves a call to new or delete. C developers will be familiar with malloc and free. Heap memory is subject to fragmentation over time, based on the allocation pattern, although memory managers work hard to minimize this, which is in itself a possible source of performance loss.

Allocating and freeing memory has a high cost relative to heap or global memory. Memory managers can be very complex. Although the average case can be cheap, sometimes the memory manager will have to request memory from the operating system, reclaim memory from a free pool, or perform other bookkeeping optimizations. These can sometimes be quite costly.

However, when you need dynamic memory, that’s a cost you have to pay, but there are many tactics that can help reduce the costs of dynamic memory.

Your authors once sat in on a lecture given by a recent graduate where he discussed topics about the game industry that surprised him in his first days on the job.

On one of his first days writing code, he decided to dynamically allocate memory using the new operator. To his surprise, the keyword caused a compile error. Surprised by his results, he sheepishly asked his boss.

“How do I allocate dynamic memory?”

“You don’t,” replied his boss.

The company’s policy was to remove the new operator and only statically allocate. For devices with limited resources, this can be very effective. But it is quite limiting. Most modern games require dynamic memory management in order to move memory usage from system to system as gameplay changes.

Is there any performance difference between accessing statically allocated memory versus dynamically allocated memory?

Figure 6.6 shows the differences between traversing static allocation and the three access patterns. Notice that dynamically and statically allocated memory achieve very similar performances. Heap Untouched includes data that is slower due to lazy allocation. To ensure that dynamic memory achieves the same performance as global, iterate through the array immediately after allocating the array.

Figure 6.6. The performance of memory types, global and heap, is nearly identical when comparing data memory that has been traversed at least once (Heap Touched). Data that hasn’t been fetched at least once is slower.

Consider a particle system. The particles are modeled using many small structs in some sort of list structure. This data is traversed at least once a frame, maybe more if separate passes for position update and rendering happen.

In the case of a particle system, dynamically allocating particles from the heap can lead to several problems. First, since the structures are small, they may cause fragmentation. The second and much bigger problem is that since they are being allocated dynamically, they can lead to a random access pattern.

If you keep the structs in an array, so that they are always in linear order, you can gain two benefits. First, memory allocation activity is reduced. You always order the array so that “active” particles are at the front. When a particle is freed, you place it at the end of the array and swap the last “active” particle with the now-dead particle in the array. This divides the array into two regions—active particles up front and dead particles at the end.

When you allocate a new particle, you just “reactivate” the first dead particle. You only grow the array when adding more particles. For a continuous particle effect, like spray from a waterfall, this will result in the array growing and staying steady in size. No more allocations and linear access will lead to overall fast performance.

The array approach works less well when the working set varies wildly. For instance, an explosion effect might grow to a high number of particles and then ramp back down. The array approach can be wasteful because most of the time it will be allocating more memory or holding onto more memory than is needed. If you keep a lot of memory in systems that use this approach, you can end up wasting it.

Reduce, reuse, recycle! Pooling is designed to maximize efficiency when you are dealing with lots of similar objects. The idea is simple: Maintain a large pool of memory that holds many copies of the same thing. With our particle example, you would allocate, say, a thousand particles up front in a contiguous array. Instead of dynamically allocating particles, you get a free instance from the pool. When you are done with the particle, you return it to the pool.

This is helpful for several reasons. Since all particles are in the same area of memory, the working set will tend to be more coherent (although rarely fully linear). Memory fragmentation will not occur, because the particles aren’t being allocated in the same memory space as objects of other sizes.

Most significantly, pooling can be very helpful when the allocation costs are high. Particles are usually lightweight; however, you may find that other items are more complex. If setup costs are high, then pooling objects and not fully destructing them between uses can save a lot of time.

POS—plain old structures—are structures with no constructor or destructor.

Suppose that you allocate an array of a million points to store mesh data in. The point class has a constructor, which sets its position to some safe value, like (0,0,0). You immediately overwrite these values with data from a file.

The performance problem here is that when the array is allocated, the constructor will be called on each instance. So before you can load data from the file, you have to wait for a million points to get values set on them so they can be immediately overwritten with real data.

If you can avoid these destructor/constructor calls, you can save a lot of time.

Carefully defining the scope in which memory is needed can lead to opportunities for optimization. Many times, code needs to allocate temporary storage. The lifespan of the storage may be just for the duration of a function call or a single frame of rendering.

Often, this temporary data is simple data that does not need to be destructed. For instance, points or primitive types, or pointers that only point to other data in the temporary pool, are all things that can be torn down without destructors being called.

Many games implement pools for the lifetime of the current level. Everything related to the level is allocated from this pool, and when the level needs to be unloaded, the pool is simply discarded, all at once.

Another useful trick is a frame allocator, so named because it gives out memory that is only valid for a single frame (or less). This is a stack from which memory can be allocated on demand. At the start of a function, the position in the stack is noted. Code is executed, and memory is allocated from the frame allocator contiguously. Before the function returns, the stack pointer is reset to where it was at the beginning of the function. At the end of each frame, the stack position is reset to zero.

The allocator is nice because it gives very fast allocations and even faster deallocation. It can be compatible with types that have constructors, but destructors won’t be run.

Alignment can be an issue with this (and other) custom allocation schemes. For more information on memory alignment see Chapter 4’s discussion on “Alignment and Fetching.”

Pointer aliasing occurs when two pointers reference the same address. This is a perfectly acceptable practice, but if the compiler can’t rule out the possibility for two pointers to “alias” to the same location, it has to be conservative with its optimizations, typically reloading data from memory more than is needed.

The following test uses two pointer references to the same address.

void func( int a[], int *p )
{

      for( int i=0; i<ARRAY_SIZE; i++ )
      {

            a[i] = *p + 5;
      }
}

If the compiler can’t rule out aliasing, then it has to implement this function by loading *p from memory every time through the loop.

If aliasing is not a risk, then the loop can be optimized. In fact, Visual Studio 2008 implements it with a rep stos instruction, the same as a memset call.

When tested on our standard machine, the unaliased version of the function was roughly 30% faster than the aliased version.

How does the compiler determine when it has to worry about aliasing? Ultimately, it can only make a best guess, and it has to guess conservatively to ensure that the program will work. Some compilers provide keywords for indicating assumptions about aliasing, either that two pointers are not aliased or that they are. For instance, in GCC, you can use _restrict_ to indicate this, while Visual Studio uses _restrict.

If you aren’t sure, check the assembly. It will be obvious if the compiler is being careful about aliasing because there will be a lot of extra load and store operations.

Your compiler by default will align structures to their natural alignment by padding with extra bytes. A structure’s natural alignment is the alignment of the largest member. For the following structure, which has a double, the natural alignment is eight bytes, which is the size of an IEEE double-precision float.

struct eightByteAligned
{
     float m_Float;
     double m_Double;
};

Members within a struct are also aligned to their natural alignments. For instance, in eightByteAligned, m_Float will be aligned to an eight-byte boundary because it is at the start of eightByteAligned. There will be four bytes of padding and then m_Double. As a result, eightByteAligned will be 16 bytes long despite only containing 12 bytes of data. Figure 6.7 illustrates some different layout possibilities.

Figure 6.7. Example of possible alignment of a float and double with four bytes’ padding (top) and without padding (bottom). Your compiler may have its own approach to this situation.

You can use various compiler options to change alignment and packing rules. Sometimes, you may want to pack a structure for minimum space usage, while at other times for best alignment.

Unfortunately, the compiler has less control over alignment at runtime. For example:

//function prototype
char* getData();
int* array = (int*)getData();

If the function getData() returns a char array, it will be one-byte aligned (meaning any address), therefore, the array has a one–in-four chance that it will be four-byte aligned. If the char happens to be on a four-byte multiple, all is well. Figure 6.8 demonstrates the performance difference this can cause.

Figure 6.8. Performing addition on 4MB of integer operations shows a slight performance difference between aligned and one-byte offset unaligned data.

If it is not, then depending on platform, OS, and compiler, there will either be a loss in performance or an error. If you have to cast data a certain way for things to work, that’s fine, but be aware that it’s not optimal.

Most CPU caches are set-associative. (A set-associative cache can choose to map a given address to one of N locations.) A set-associative array can have problems when accessing data at certain strides. Similar to how some engine speeds can cause parts of your car to vibrate, these critical strides impact performance by causing the cache to act against itself.

The worst-case critical stride is equal to (number of sets) × (size of cache line).

Consider an Intel Core 2 Duo with an L2 cache size of 2MB. The Core 2 Duo uses cache lines of 64 bytes and is eight-way set-associative.

Therefore, we have 2,048KB/64 bytes = 32,768 cache lines of L2 cache.

These 32,768 lines are organized into eight ways, which gives us 32,768 lines/8 ways = 4,096 total sets.

If you were to have a large array of data, and iterate over 64-byte items at a stride of sets × cache line size = 4,096 × 64 bytes = 262,144 bytes, you would only be using eight L2 cache lines for your traversal. Instead of being able to access 2MB of data before blowing the cache and having to fetch from main memory, you would only be able to access 8 × 64 = 512 bytes!

Now, a 262KB stride is a pretty specific scenario, but critical strides can affect you in more pedestrian situations as well.

Consider a one-channel texture that is 4096px on a side with 1 byte-per-channel. In other words, pixels equal bytes. If you were to traverse the first column of this texture, you would load a byte every 4,096 bytes. The first byte of each column won’t share the same set, but the first pixel of every 64^th row will.

To see this more clearly, consider the math involved in deriving a set from an address.

For simplicity’s sake, let’s assume our texture begins at address 0 × 0000. Since addresses are typically represented in hex, we will do the same. Remember 64 bytes in decimal is 0 × 40 in hex and the number of sets for this example 4,096 in decimal is 0 × 1000.

To derive the set, use the following formula:

For address zero, it is obviously set zero, but let’s try a more challenging address. Consider the address 0 × 40000.

Where does the critical stride come in? The address 0 × 40000 is the first pixel of the 64^th row of the texture, and shares the same set as address zero. This is an example of critical stride. By fetching the first text in row 0 and then the first texel in row 64, you have used two out the eight ways for set zero. If you were to continue with this stride, addressing 0 × 80000, 0 × 120000, and so on, you would quickly use all eight sets. On the ninth iteration with that stride, a cache line eviction must occur.

Because of how the cache is implemented, this is the worst case. Instead of having 2MB of cache available, you’re down to 512 bytes. This leaves pre-fetching with very little room to compensate for slow memory. Similar issues occur with other large power-of-two strides, such as 512, 1,024, and 2,048. Figure 6.9 shows the performance of critical stride scenarios.

Figure 6.9. Average load time equals total time/number of loads. The source code for this test is available in the Performance Test Harness: “memory/criticalStride.” These values will vary significantly, depending on the amount of data traversed and the architecture of your cache.

The best solution for this kind of problem is to pad your data to avoid larger power of two strides. If you know you are only reading memory once, as occurs when streaming music, you can use advanced SSE instructions.