During the development of FEAR 3, to address these limitations, I implemented a new general-purpose allocator based on dlmalloc called dsmalloc.  Dsmalloc makes two important improvements to dlmalloc.

The first improvement is in how dsmalloc treats segments.  In dsmalloc, segments are always managed as completely distinct regions of memory.  Dsmalloc will never coalesce adjacent segments.  Because of this, dsmalloc tracks segments much more closely than dlmalloc.  By overlaying a second intrusive data structure in the free bits of the boundary tag structure used to track individual allocations, dsmalloc can, in constant time and with no memory overhead, determine with every free operation when a segment is no longer occupied and can be returned to the system.

The second improvement is that dsmalloc recognizes the difference between reserved address space and allocated memory.  Unlike dlmalloc, which uses two callbacks to allocate and free system memory, dsmalloc exposes four callbacks, two to reserve and release segment-sized regions of virtual address space, and two to commit and decommit page-sized subregions of segments.

Just as dsmalloc never leaves any unoccupied segments reserved, it also never leaves any unoccupied pages committed.

typedef void* (*ReserveSegmentFunc)(size_t size);
typedef void (*ReleaseSegmentFunc)(void* ptr, size_t size);
typedef int (*CommitPageFunc)(void* ptr, size_t size);
typedef void (*DecommitPageFunc)(void* ptr, size_t size);

MemorySpace* CreateMemorySpace(
    size_t initialCapacity,
    ReserveSegmentFunc reserveSegmentFunc,
    ReleaseSegmentFunc releaseSegmentFunc,
    CommitPageFunc commitPageFunc,
    DecommitPageFunc decommitPageFunc,
    size_t pageSize,
    size_t segmentGranularity,
    size_t segmentThreshold );

These two extensions are implemented without any additional memory overhead compared to dlmalloc and with very little computational overhead.  The added cost is a few percent in targeted tests, but in a real-world scenario the performance difference between dlmalloc and dsmalloc isn’t even measurable.

The great thing about these two changes to dlmalloc is that they enable a wide range of allocation strategies that otherwise wouldn’t be feasible.

Individual systems within the Despair Engine are free to create separate dsmalloc instances (or regions) for their own use.  Because dsmalloc instances are so aggressive about returning memory to the system, they incur minimal internal fragmentation costs and can coexist gracefully with other system allocators.  Thread-safety is left to the users of dsmalloc, so individual systems can bypass thread synchronization costs entirely or at least use local locks to avoid contention with other allocators.  Using separate dsmalloc instances also provides systems with easier tracking of memory allocations, tighter enforcement of budgets, and, if their allocation patterns exhibit temporal or spatial locality within their own systems, reduced external fragmentation.

For systems that don’t want to bother with using a custom allocator (which, frankly, most don’t), Despair Engine provide a common allocator which services request from the tradition global allocation functions like operator new, malloc, and XMemAlloc.  This common allocator also utilizes dsmalloc instances under the hood.

The common allocator creates one dsmalloc instance for allocations larger than 256 bytes and 20 dsmalloc instances covering allocations at every 8 byte size interval less than 64 bytes and every 16 byte interval between 64 and 256 bytes.  The instance for large allocations uses a 32 megabyte segment size and 64 kilobyte pages whereas the small allocation instances use 64 kilobyte segments.  Using page-sized segments for the small allocation regions is a minor optimization that removes the need for dsmalloc to track address reservation and memory commission separately for these regions.

Bucketing small allocations into so many discreet regions significantly reduces external fragmentation in our games, despite creating a modest increase in internal fragmentation.  Since only allocations within a single region need to be synchronized, it also has a side benefit of greatly reducing contention between allocations from multiple threads.

It is worth noting that since the various small allocation regions are essentially used for fixed-size allocations, they could be more efficiently implemented as dedicated fixed-block allocators.  We have such an implementation in the engine, but dsmalloc (like dlmalloc) already implements an internal small, fixed-block allocation optimization, so in practice it is more convenient to use dsmalloc instances for everything and almost as efficient.

One key benefit of using dsmalloc instances for small allocations instead of a pure fixed-block allocator is that it offers us more flexibility in how the small allocation regions are configured.  At the time I was implementing this in FEAR 3, minimizing fragmentation was our top concern, but in the future we might choose to prioritize thread synchronization efficiency over memory consumption.  Instead of routing allocations to regions based on their size, we could create just a few small allocation regions and cycle between them based on thread contention.  The idea is to allow a thread to try to lock a region for allocation, but rather than waiting if the region is already in use by another thread, simply move on to another region and try again.

Dsmalloc is flexible enough to support both of these strategies efficiently or, in fact, any hybrid combination of the two.

The dsmalloc callbacks are designed to be easily mappable to OS functions such as VirtualAlloc in Windows, but sometimes these functions are too expensive to be used directly.  To improve performance, on some platforms the Despair general allocator utilizes a commit cache.  The commit cache is a simple direct-mapped cache that sits between the dsmalloc commit callback and the OS.  Dsmalloc already optimizes allocation order to maximize cache efficiency, and this benefits the commit cache as well.  A 32 megabyte commit cache is probably overly generous, but it guarantees that OS-level calls don’t show up in our profiles even during content streaming transitions.

Having the cache implemented external to dsmalloc is also useful.  When memory is extremely tight, anything that doesn’t utilize the general allocator could fail even though memory is still available in the commit cache.  In those extreme cases the commit cache can be manually prompted to return pages to the system ensuring that OS-level allocations never fail because the memory they need is held in a cache.

There is one additional complication that plagues the consoles.  On both the Xbox 360 and the Playstation 3, the GPU does not share the CPU’s memory mapping unit.  On the Xbox 360 the GPU requires physically contiguous memory for all resources and on the PS3 the GPU has a separate MMU with only 1 megabyte page granularity.  Since we use dsmalloc with 64 kilobyte pages to minimize fragmentation, this means we’re susceptible to physical memory fragmentation when it comes to resources allocated for the GPU.  On the Xbox 360, unbeknownst to many developers, the OS copes with this automatically.  When a physical allocation request can’t be satisfied due to physical memory fragmentation, the Xbox 360 operating system locks the entire address space and defragments physical memory pages (by memcpy’ing physical pages and remapping virtual addresses) to accommodate the request.

On the PS3 the OS doesn’t provide this service automatically, but the same basic need exists.  64 kilobyte pages must be locked and relocated to generate contiguous 1 megabyte pages appropriate for the GPU.  Thankfully with a little bit of acrobatics it is possible to do just that without violating certification requirements.

Although the operation is every bit as expensive as it sounds, it proved necessary to keep FEAR 3 from crashing.  FEAR 3 ran dangerously close to the limits of memory on the Playstation 3 and survived only by allowing flexible budgets for every kind of memory.  GPU allocations in main memory varied by over 100% between streaming regions so not only did CPU addressable memory need to be defragmented for use by the GPU, GPU addressable memory had to be defragmented continually and returned to the CPU.  The really expensive CPU defragmentation provided a safety net against crashes at all times, but thankfully it was only needed at major chapter transitions where a load screen was expected and a 100 ms hitch was infinitely preferable to an out and out crash.

When I undertook to rewrite the Despair memory allocator near the end of FEAR 3, the overarching goal was to never fail to satisfy an allocation request due to prior memory usage patterns.  If a level fit just barely into memory after a fresh boot, we wanted it to fit equally well in memory after a hundred hours of continuous play.  While I can’t pretend that fragmentation doesn’t exist at all in the system I devised, I can say that it was so dramatically reduced that we were able to establish an upper bound on fragmentation and enforce budgets for our content that were reliable regardless of the order or duration in which the game was played.

The new Despair memory allocator based on dsmalloc ran the same content as the old memory allocator on all platforms with a slightly lower lower bound on memory, a much lower upper bound on memory, and it even managed a slightly lower run-time performance cost.

The “concurrency manager” in Despair Engine consists of worker threads and job queues.  By default there is one pool of worker threads that share a single job queue, referred to as public workers, and some number of additional worker threads, each with its own job queue, referred to as private workers.

The job queues and their worker threads are relatively simple constructs.  Jobs can be added to a queue from any thread and, when jobs are added, they create futures which can be used to wait on the job’s completion.  A job queue doesn’t directly support any concept of dependencies between jobs or affinities to limit which worker threads a job can run on.

Jobs are fetched by worker threads in strictly FIFO order, but with multiple worker threads servicing a single queue, that doesn’t provide many guarantees on the order in which jobs are processed.  For example, jobs A and B, enqueued in that order, may be fetched consecutively by worker threads 1 and 2.  Because these tasks are asynchronous, worker thread 2 might actually manage to start and finish processing job B before worker thread 1 has done any meaningful work on job A.

What this means in practice is that any job added to the public worker queue must be able to be processed on any public worker thread and concurrently with any other job in the queue.  If a job really needs to enforce a dependency with other jobs, it can do so by either waiting on the futures of the jobs it is dependent on or by creating the jobs that are dependent on it at the end of its execution.  Combinations of these techniques can be used to create almost arbitrarily complex job behavior, but such job interactions inhibit maximum parallelism so we try to avoid them in our engine.

Public worker threads are mostly used by data-parallel systems that divide their work into some multiple of the number of public workers, enqueue jobs for each worker, and then, at some later point in the frame, wait on all the jobs’ futures.  Examples of systems like this are animation, cloth simulation, physics, effects, and rendering.  Although all of the users of the public job queue try to provide as much time as possible between adding work to the queue and blocking on its completion, work in the public job queue is considered high-priority and latency intolerant.

Systems that have work that can be processed asynchronously, but doesn’t meet the requirements of the public job queue, create private job queues.  The primary reason for using a private job queue is that the work is long but latency tolerant, and we don’t want it delaying the latency intolerant work in the public job queue.

In Fracture, terrain deformation was processed in a private worker thread, consuming as much as 15 ms a frame but at low priority.

Starting with F.E.A.R. 3, decals have used a private worker thread. The decal thread generates and clips geometry from a queue. Although the queue might hold several hundred milliseconds of work, it will happily take only what time slices it can get from a single thread until it finishes its backlog.

We also use private worker threads for systems that have restrictions on their degree of parallelism or that perform primarily blocking work.  Save data serialization, background resource loading, audio processing, network transport, and, on the PC, communication with the primary Direct3D context fall into this category.

I’ve had occasion over the years to use the Despair concurrency manager for a wide variety of tasks with a wide range of requirements, and I have very few complaints.  I find the system simple and intuitive, and it is usually immediately obvious, given a new task, whether a private or public job queue is appropriate.  I’ve occasionally wished for a richer set of scheduling options within the job queues themselves, but I ultimately believe that complex scheduling requirements are a symptom of bad multithreaded design and that if complex scheduling truly is justified, it is better handled within the jobs themselves.

The one area where scheduling has given me a lot of trouble, however, and where I wish we could offer some improvement, is in the interaction of public and private worker threads. When the platform, code, and content are reasonably stable, it isn’t too difficult to arrange the public and private workers such that they share the available processor resources efficiently.

On the Xbox 360, for example, where there are 6 hardware threads available, we have the main thread with affinity to hardware thread 0, four public worker threads with separate affinity to hardware threads 1, 2, 3, and 5, and most of our private worker threads sharing affinity with hardware thread 4.  This arrangement ensures that the main thread and the public workers are never interrupted by the private worker threads, and it means that the private workers get a roughly equal share of an entire hardware thread.  We know exactly how fast the hardware is and we can predict with a high degree of accuracy how much work each private worker will receive, so we don’t need to worry about oversubscription or underutilization of hardware thread 4.

In cases where the private worker threads aren’t sharing the load in a way we consider optimal, we can tweak either the hardware thread affinity or the software thread priorities to get the behavior we want.  For example, in F.E.A.R. 3 we offloaded some marshaling of data for network transport to a private worker thread.  Jobs for that thread were generated near the end of each frame and they had to be completed near the beginning of the following frame.  If the private workers were left to the OS scheduler, the decal thread might preempt the network thread during that crucial window and cause a stall in the next frame.  Since we knew the network thread never generated more than 5-6 ms of single-threaded work, we could safely boost its thread priority and ensure that it was never preempted by decals.

In another case where we weren’t 100% satisfied with the default scheduling of a private worker, we moved the private worker to share a hardware thread with one of the public workers but also lowered its thread priority.  The luxury of a fixed, single-process platform is that we can hand tune the thread layout and be confident that our results will match those of our customers.

Example hardware thread utilization in F.E.A.R. 3, as captured by PIX on the Xbox 360

In the capture above you can see examples of both the situations I described.  The thin colored lines represent software threads and the thick blocks above them represent individual jobs.  A high priority audio thread, shown in yellow, interrupts a job on hardware thread 4, but that’s okay because the job being interrupted is latency tolerant.  Later in the frame another thread, shown in light blue, schedules nicely with the latency intolerant jobs in the pink public worker on hardware thread 5.

The PC is where things get messy.  On the PC we worry most about two different configurations.  One is the low end, which for us is a dual core CPU, and the other is the high end, which is a hyper-threaded quad core CPU.

Currently, on the PC we allocate MAX(1, num_logical_processors-2) public worker threads.  On a hyper-threaded quad core that means 6 public worker threads and on a dual core that means just 1 public worker thread.  Unlike on the Xbox 360, however, we don’t specify explicit processor affinities for our threads, nor do we adjust thread priorities (except for obvious cases like an audio mixer thread).  We don’t know what other processes might be running concurrently with our game and, with variations in drivers and platform configurations, we don’t even know what other third-party threads might be running in our process. Constraining the Windows scheduler with affinities and thread priorities will likely lead to poor processor utilization or even thread starvation.

That’s the convention wisdom anyway, but it sure doesn’t look pretty in profiles.  From a bird’s eye view the job system appears to work as expected on the PC.  As the number of cores increase, the game gets faster.  Success!  If it weren’t for our internal thread profiler and the Concurrency Visualizer in Visual Studio 2010 we’d probably have been happy with that and moved on.

On high-end PCs things aren’t too bad.  Both our job queue visualization and Visual Studio’s thread visualization sometimes show disappointing utilization of our public workers, but that’s not necessarily a problem.  We know we’re oversubscribed because we have more software threads created by the engine than there are hardware threads and there are at least 3 other third-party threads in our process doing meaningful work not to mention the other processes in the system.  One of the benefits of a thread pool is that the number of participating threads can scale with the environment.  Thankfully the behavior we usually see in these cases is fewer public workers tackling more jobs rather than all public workers starting jobs and then some being preempted, which would block the job queue until they can be rescheduled.

Job visualization from the same portion of two adjacent frames on a dual core PC

The image above is an example from our internal thread profiler.  I had to zoom and crop it a bit to fit on the page, but what you’re seeing is the same portion of two frames on a dual core machine.  The colored blocks represent jobs.  You can see in the first frame a long stretch in which the main thread is processing jobs while the single worker thread is sitting idle.  The next frame shows the intended behavior, with both the main thread and the worker thread processing jobs equally.  We can’t visualize third-party threads or other processes with our internal profiler, so we have to turn to Visual Studio’s profiler to see what’s preempting our worker in that first frame.  In our case it is usually the video driver or audio processor, but really any thread could be at fault.  The more active threads in the system, including our own private workers, the more likely this sort of interference becomes.

The other behavior that is a little disappointing on many-core PCs is the high percentage of cross-core context switches.  The Windows scheduler prioritizes quite a few factors above keeping a thread on its current core, so it isn’t too big a surprise for threads to jump cores in an oversubscribed system.  The cost is some nebulous decrease in CPU cache coherency that is all but impossible to measure.  Short of setting explicit processor affinities for our threads, which hurts overall performance, I haven’t had any luck improving this behavior.  I had hoped to combat this effect with SetThreadIdealProcessor, but I haven’t actually been able to detect any change in scheduling when calling this function so we don’t use it.

On a high-end PC, as Louis C.K. might say, these are first world problems.  With 8 logical processors we can afford to be less than perfect.  From my profiles, even the best PC games are barely utilizing 30% of an 8 processor PC, and we’re comfortably within that range so I’m not complaining.

On dual core machines these issues can’t be ignored.  With only two hardware threads, we’re now massively oversubscribed.  The particularly difficult situation that we have to cope with is when all of our private workers are fully occupied at the same time. As I explained earlier, the decal thread is latency tolerant, but it can buffer far more than a single frame’s worth of work.  This means that, left unchallenged, it alone can consume a full core for a full frame.  Video drivers usually have their own threads which might, under heavy load, consume 25% of a core, audio might want another 20%, and Steam another 20%.  All told we can have two thirds of a core’s worth of work in miscellaneous secondary threads and another full cores’s worth of work in the decal thread.  That’s 1.7 cores worth of work competing on a level playing field with the main job queue on a machine with only 2 cores!

For most of these threads we have a general optimization problem more than a concurrency problem.  We don’t have much flexibility in when or how they run, we just need to lower their cost.  The decal thread, on the other hand, is different.  Its purpose is to periodically consume far more work than would normally be budgeted for a single frame and to amortize the cost of that work over multiple frames.  If it is impacting the execution of other threads then it isn’t doing its job.

My first reaction to this problem was, as usual, to wish for a more sophisticated scheduler in the public job queue.  It seemed as though an easy solution would be to stick decal jobs in the public job queue and to instruct the scheduler to budget some fraction of every second to decal processing while trying to schedule decal jobs only at times when no other jobs are pending.  After some consideration, however, I realized that this was asking too much of the scheduler and, perversely, would still require a lot of work in the decal system itself.  Since the job scheduler isn’t preemptive, even a powerful system of budgets and priorities would rely on the jobs themselves being of sufficiently small granularity.  The decal system would have to break up large jobs to assist the scheduler or, similarly, implement a cooperative yielding strategy that returned control to the scheduler mid-execution.

In addition to assisting the scheduler, the decal system would also have to become aware of how its rate of production was being throttled.  Since decal resources are recycled using a heuristic that is heavily LRU, the decal system must manage the rate of input requests to match the rate of production in order to ensure that decals aren’t being recycled as soon as they are created.

It seems that any additional complexity added to the job scheduler is going to require equal complexity to be added to the decal system in order to take advantage of it.  That’s always a red flag for me in systems design.

I’m still weighing some options for dealing with the decal thread, but my current favorite is to swallow my fears and seek help from the OS thread scheduler.  If we reduce the thread priority of the decal thread under Windows, it will only be given time when the cores would otherwise be idle.  However, since Windows implements thread boosts, even in a completely saturated environment the decal thread won’t starve completely.  Nevertheless, this is a risky strategy because it creates the ability for the decal thread to block other threads through priority inversion. This probably isn’t a scalable long-term solution, but given our current thread layout and hardware targets, it achieves the desired result.

The difficulty of achieving maximum throughput on multicore processors is something that is often talked about in games, but what is less often talked about is how much harder this is on the PC than on the consoles.  Maximizing throughout on high-end PCs is great, but, as I’ve shown, it must be done without sacrificing response time on low-end PCs.  With our current approach I’ve been pretty pleased with our progress in this area, but I’m nevertheless having a hard time envisioning a day when we can fully utilize the resources of an 8 processor machine and still continue to provide a compatible play experience on a lowly dual core.

Hopefully by that time we’ll have broad support for GPGPU tasks as well as the scheduling flexibility to rely on them for more of our latency tolerant work.

Dlmalloc is a general-purpose memory allocator developed by Doug Lea since 1987.  It is highly optimized, easily portable, and elegantly designed.  It functions as a drop-in replacement for malloc and the source has been generously released into the public domain.  The code is also an absolute joy to read, with every line conveying volumes of careful intention—optimizations, bug fixes, and refinements thoughtfully integrated over the years.  With so many positive attributes to recommend it, it is no wonder dlmalloc has become the gold standard for memory allocators and a popular choice for game developers.  It is also really unfortunate, because dlmalloc is a terrible allocator for today’s game consoles.

To understand why this is, you must first have an overview of dlmalloc’s interface and how it works.  Dlmalloc manages a pool of address space composed of one or more discrete regions called segments.  Dlmalloc’s pool can optionally grow or shrink through user-provided callbacks to allocate new segments and free unused ones.  The “grow” callback is triggered when dlmalloc can’t satisfy an allocation request within its currently managed pool of memory and the “shrink” callback is triggered when dlmalloc detects that a segment is no longer occupied by any allocations.  The grow callback is typically implemented with OS-level functions that allocate memory such as VirtualAlloc, mmap, or sbrk.

Dlmalloc is a boundary tag allocator at its heart, so segments are treated like new nodes in an intrusive linked list and are written with small headers or footers.  The important thing to note about this is that dlmalloc requires that all memory it manages be readable and writable.  The grow callback can return virtual memory, but it must already be committed (mapped to physical memory) in order for dlmalloc to function.

Another important characteristic of dlmalloc is that while it can return segments through the use of the shrink callback, it is not very aggressive in doing so.  Segments are stored in a linked list and the only way for dlmalloc to coalesce adjacent segments or find empty segments is to perform a linear traversal of that list.  For some users segments may be very large in size and very small in number so the linear traversal is cheap, but for most users segment management isn’t worth the cost, and dlmalloc’s default configuration is to only consider the most recently allocated segment when looking for segments to merge or release.

This is significant because it means dlmalloc’s callbacks can’t be used to allocate and commit individual pages of virtual memory.  Trying to use dlmalloc with a segment equivalent to a virtual memory page would be prohibitively expensive or pointless depending on the configuration.

So to summarize, dlmalloc has no support for virtual memory.

This may seem like a crippling limitation for such a popular allocator, but in practice it affects very few systems.  In fact, if a system meets any of the following requirements, dlmalloc’s blind spot when it comes to virtual memory is almost completely irrelevant.

Demand Paging

Almost all general-purpose computers these days have an operating system that features demand paging.  With demand paging, the operating system keeps track of which pages of virtual memory are needed by the system and tries to keep only those pages resident in memory.  In other words, dlmalloc doesn’t have to bother with the difficult work of committing and decommitting pages because the OS is already doing a pretty good job of it.

More Physical Memory than Virtual Address Space

In the consumer space, most applications are 32-bit and run on machines with more than 2 gigabytes of memory.  This includes the most recent big-budget PC games like Crysis, Battlefield, Call of Duty, and Batman since they all have minimum system requirements of at least 2 gigabytes of main memory.  If dlmalloc can commit all of the available address space without penalty, it has no reason not to do it.

No Virtual Memory or Predictable Allocation Pattern

Embedded systems are likely to have no virtual memory or to have very predictable allocation patterns that don’t benefit from virtual memory.  The fact that dlmalloc sacrifices virtual memory support and dynamic segment management in favor of speed and simplicity is actually a perk for embedded systems.

Which Brings Us to Modern Consoles

Modern game consoles are unusual in that they don’t match any of the above criteria.  Both the Xbox 360 and the Playstation 3 have rich support for virtual memory, but the operating systems on the two consoles offer limited or no support for demand paging.  The Xbox 360 has 512 megabytes of physical memory to back its virtual address space and the Playstation 3 has 256 megabytes.  Both consoles provide games with significantly more virtual address space than physical memory, so there is a huge potential upside to managing them separately.

Why We Care About Virtual Memory

In the absence of demand paging, virtual memory exists for one purpose only—to reduce the cost of fragmentation. Fragmentation occurs in any allocator that manages variable-sized blocks of memory which can be freed in arbitrary order.  Consider the diagrams below.  The green blocks are allocations in a system with 10 megabytes of memory.  In the first diagram, most of the available memory has been allocated in variable-sized amounts.  In the second diagram, some of those allocations have been freed.  There are more than 4 megabytes of memory available in diagram 2, but even a 2 megabyte allocation will fail because there are no contiguous blocks of memory large enough to place it.  This phenomenon is known as fragmentation.

Fragmentation can be a huge problem with any general-purpose allocator.  The less predictable an application’s allocation patterns and the larger the range of its allocation sizes, the more susceptible it is to allocation failure due to fragmentation.  Most console games are large, complex systems integrating code from multiple sources and trying to satisfy a wide range of allocation patterns.  At the same time, the game industry is very competitive, so console games are expected to take maximum advantage of the console hardware’s capabilities.  You simply can’t do that without tackling the problem of memory fragmentation.

The most surefire way to avoid memory fragmentation is to only manage memory in fixed-size blocks.  If every allocation is the same size, any hole left by one allocation can be filled perfectly by another.  Unfortunately requiring that all memory requests be the same size is unreasonable, and trying to do so naively will only result in even more memory waste.  This is where virtual memory comes in.

Virtual memory subdivides all physical memory into fixed-size blocks, known as pages, and provides a mechanism for contiguous allocations of virtual memory to span multiple nonadjacent pages.  By adding this level of indirection, an application can be given an address the behaves like a block of contiguous memory, but under the hood is made up of separate fixed-size allocations of physical memory.  This completely removes the problem of physical memory fragmentation, though it obviously creates the problem of virtual memory fragmentation.  If virtual memory is limited to the same size as physical memory, you’re no better off than when you started.  However, if virtual memory is allowed to be much larger than physical memory, even though fragmentation still exists, it is much less likely to ever cause an allocation failure.

The reason why virtual memory can be larger than physical memory is that unused pages of virtual memory don’t have to be backed by physical memory.  As the name implies, it is virtual resource.

The next set of diagrams shows the exact same sequence of memory allocations as the earlier diagrams, but this time using a slightly larger pool of virtual memory.  Allocations in virtual memory are still marked in green and free regions are still marked in white, but now the diagram is divided into 1 megabyte pages and any pages which are backed by physical memory are shaded with diagonal lines.  In order for an allocation to succeed, it must fit into a free region of virtual memory that is backed by physical pages, ie. white areas shaded with diagonal lines.

In diagram 3 all 10 megabytes of physical memory are allocated, but there are still more than two megabytes of virtual memory available.  A new 2 megabyte allocation could fit in virtual memory, but it will still fail because it can’t be backed by physical memory.  In diagram 4 some allocations have been freed, and not only is there still 2 megabytes of contiguous virtual memory available, there are two free 1 megabyte physical memory pages available to back it.  Diagram 5 shows the successful addition of a new 2 megabyte allocation, the same allocation that would have failed without virtual memory in diagram 2.  If you count the number of physical pages that are allocated in diagram 5, you’ll see that we haven’t exceeded the system limit of 10 megabytes.

Notice that while we’ve succeeded in allocating an additional 2 megabytes despite fragmentation, we still have more than 2 megabytes of virtual memory left and yet we can’t service another 2 megabyte request.  Virtual memory itself is now too fragmented.  We could increase the amount of virtual memory without penalty to make room for another 2 megabyte allocation, but it doesn’t help because although we have 2 megabytes of physical memory that isn’t being used, we don’t have 2 free physical memory pages to back the new allocation.

For virtual memory to be an effective solution to fragmentation, you need a lot more virtual address space than physical memory and you need as small a page size as possible.  On the Xbox 360 the default page size is 64 kilobytes and the on the Playstation 3 it is 1 megabyte, but both consoles support a range of page sizes.  The best page size on consoles for compromising between performance and fragmentation is 64 KB, which begs the question, “why does the Playstation 3 default to 1 megabyte?”  The answer is simple: the Playstation 3 uses dlmalloc for its general-purpose allocator and since dlmalloc doesn’t take advantage of virtual memory, there is no point in using a smaller page size!

Hopefully by now I’ve convinced you of the value of virtual memory and why dlmalloc isn’t the right choice for console games.  In the future I’ll describe the general-purpose memory allocator I wrote for Despair Engine and how I used it to combat fragmentation.  As a bonus, I’ll explain the larger memory management framework that I built on top of the allocator to reduce thread contention and to ensure that the entirety of memory is available to a heterogeneous set of processors, despite their non-unified views of virtual memory.

Development on CrossStitch 2.0 began with the development of Day 1′s Despair Engine.  This was right at the end of MechAssault 2, when the Xbox 360 was still an Apple G5 and the Cell processor was going to be powering everything from super computers to kitchen appliances in a few years.  It is hard to believe looking back, but at that time we were still debating whether to adopt a high-level shading language for graphics.  There were respected voices on the platform side insisting that the performance advantage of writing shaders in assembly language would justify the additional effort.  Thankfully I sided with the HLSL proponents, but that left me with the difficult decision of what to do about CrossStitch.

CrossStitch was a relatively simple system targeting a single, very constrained platform.  HLSL introduced multiple target profiles, generic shader outputs, and literal constants, not to mention a significantly more complex and powerful language syntax.  Adding to that, Despair Engine was intended to be cross-platform, and we didn’t even have specs on some of the platforms we were promising to support.  Because of this, we considered the possibility of dispensing with dynamic shader linking entirely and adopting a conventional HLSL pipeline, implementing our broad feature set with a mixture of compile-time, static, and dynamic branching.  In the end, however, I had enjoyed so much success with the dynamic shader linking architecture of MechAssault 2, I couldn’t bear to accept either the performance cost of runtime branching or the clunky limitations of precomputing all possible shader permutations.

The decision was made: Despair Engine would feature CrossStitch 2.0.  I don’t recall how long it took me to write the first version of CrossStitch 2.0.  The early days of Despair development are a blur because we were supporting the completion of MechAssault 2 while bootstrapping an entirely new engine on a constantly shifting development platform and work was always proceeding on all fronts.  I know that by December of 2004, however, Despair Engine had a functional implementation of dynamic shader linking in HLSL.

CrossStitch 2.0 is similar in design to its predecessor.  It features a front-end compiler that transforms shader fragments into an intermediate binary, and a back-end linker that transforms a chain of fragments into a full shader program.  The difference, of course, is that now the front-end compiler parses HLSL syntax and the back-end linker generates HLSL programs.  Since CrossStitch 1.0 was mostly limited to vertex shaders with fixed output registers, CrossStitch 2.0 introduced a more flexible model for passing data between pipeline stages.  Variables can define and be mapped to named input and output channels; and each shader chain requires an input signature from the stage preceding it and generates an output signature for the stage following it.

A sampling of early HLSL shader fragments.

CrossStitch’s primary concern is GPU runtime efficiency, so it is nice that shaders are compiled with full knowledge of the data they’ll be receiving either from vertex buffers or interpolators.  If, for example, some meshes include per-vertex color and some don’t, the same series of shader fragments will generate separate programs optimized for each case.  It turns out that this explicit binding of shader programs to attributes and interpolators is a common requirement of graphics hardware, and making the binding explicit in CrossStitch allows for some handy optimizations on fixed consoles.

The early results from CrossStitch 2.0 were extremely positive.  The HLSL syntax was a nice break from assembly, and the dynamic fragment system allowed me to quickly and easily experiment with a wide range of options as our rendering pipeline matured.  Just as had happened with MechAssault 2, the feature set of Despair expanded rapidly to become heavily reliant on the capabilities of CrossStitch.  The relationship proved circular too.  Just as CrossStitch facilitated a growth in Despair’s features, Despair’s features demanded a growth in CrossStitch’s capabilities.

The biggest example of this is Despair’s material editor, Façade.  Façade is a graph-based editor that allows content creators to design extremely complex and flexible materials for every asset.  The materials are presented as a single pipeline flow, taking generic mesh input attributes and transforming them through a series of operations into a common set of material output attributes.  To implement Façade, I both harnessed and extended the power of CrossStitch.  Every core node in a Facade material graph is a shader fragment.  I added reflection support to the CrossStich compiler, so adding a new type of node to Façade is as simple as creating a new shader fragment and annotating its public-facing variables.  Since CrossStitch abstracts away many of the differences between pipeline stages, Façade material graphs don’t differentiate between per-vertex and per-pixel operations.  The flow of data between pipeline stages is managed automatically depending on the requirements of the graph.

Façade Material Editor

It was about 6 months after the introduction of Façade when the first cracks in CrossStitch began to appear.  The problem was shader compilation times.  On MechAssault 2 we measured shader compilation times in microseconds.  Loading a brand new level with no cached shader programs in MechAssault 2 might cause a half-second hitch as a hundred new shaders were compiled.  If a few new shaders were encountered during actual play, a couple of extra milliseconds in a frame didn’t impact the designers’ ability to evaluate their work.  Our initial HLSL shaders were probably a hundred times slower to compile than that on a high-end branch-friendly PC.  By the end of 2005 we had moved to proper Xbox 360 development kits and our artists had mastered designing complex effects in Façade.  Single shaders were now taking as long as several seconds to compile, and virtually every asset represented a half-dozen unique shaders.

The unexpected 4-5 decimal order of magnitude increase in shader compilation times proved disastrous.  CrossStitch was supposed to allow the gameplay programmers, artists, and designers to remain blissfully ignorant of how the graphics feature set was implemented.  Now, all of a sudden, everyone on the team was aware of the cost of shader compilation.  The pause for shader compilation was long enough that it could easily be mistaken for a crash, and, since it was done entirely on the fly, on-screen notification of the event couldn’t be given until after it was complete.  Attempts to make shader compilation asynchronous weren’t very successful because at best objects would pop in seconds after they were supposed to be visible and at worst a subset of the passes in a multipass process would be skipped resulting in unpredictable graphical artifacts.  Making matters worse, the long delays at level load were followed by massive hitches as new shaders were encountered during play.  It seemed like no matter how many times a designer played a level, new combinations of lighting and effects would be encountered and repeated second-long frame rate hitches would make evaluating the gameplay impossible.

Something had to be done and fast.

Simple optimization was never an option, because almost the entire cost of compilation was in the HLSL compiler itself.  Instead I focused my efforts on the CrossStitch shader cache.  The local cache was made smarter and more efficient, and extended so that multiple caches could be processed simultaneously.  That allowed the QA staff to start checking in their shader caches, which meant tested assets came bundled with all their requisite shaders.  Of course content creators frequently work with untested assets, so there was still a lot of unnecessary redundant shader compilation going on.

To further improve things we introduced a network shader cache.  Shaders were still compiled on-target, but when a missing shader was encountered it would be fetched from a network server before being compiled locally.  Clients updated servers with newly compiled shaders, and since Day 1 has multiple offices and supports distributed development, multiple servers had to be smart enough to act as proxies for one another.

With improvements to the shader cache, life with dynamic, on-the-fly shader compilation was tolerable but not great.  The caching system has only had a few bugs in its lifetime, but it is far more complicated than you might expect and only really understood by a couple of people.  Consequently, a sort of mythology has developed around the shader cache.  Just as programmers will suggest a full rebuild to one another as a possible solution to an inexplicable code bug, content creators and testers can be heard asking each other, “have you tried deleting your shader cache?”

At the same time as I was making improvements to the shader cache, I was also working towards the goal of having all shaders needed for an asset compiled at the time the asset was loaded.  I figured compiling shaders at load time would solve the in-game hitching problem and it also seemed like a necessary step towards my eventual goal of moving shader compilation offline.  Unfortunately, doing that without fundamentally changing the nature and usage of CrossStitch was equivalent to solving the halting problem.  CrossStitch exposes literally billions of possible shader programs to the content, taking advantage of the fact that only a small fraction of those will actually be used.  Which fraction, however, is determined by a mind-bending, platform-specific tangle of artist content, lua script, and C++ code.

I remember feeling pretty pleased with myself at the end of MechAssault 2 when I learned that Far Cry required a 430 megabyte shader cache compared to MA2′s svelte 500 kilobyte cache.  That satisfaction evaporated pretty quickly during the man-weeks I spent tracking down unpredicted shader combinations in Fracture.

Even so, by the time we entered full production on Fracture, shader compilation was about as good as it was ever going to get.  A nightly build process loaded every production level and generated a fresh cache.  The build process updated the network shader cache in addition to updating the shader cache distributed with resources, so the team had a nearly perfect cache to start each day with.

As if the time costs of shader compilation weren’t enough, CrossStitch suffered from an even worse problem on the Xbox 360.  Fracture’s terrain system implemented a splatting system that composited multiple Facade materials into a localized über material, and then decomposed the über material into multiple passes according the register, sampler, and instruction limits of the target profile.  The result was some truly insane shader programs.

The procedurally generated material for one pass of a terrain tile in Fracture.

A few Fracture terrain shaders took over 30 seconds to compile and consumed over 160 megabytes of memory in the process.  Since the Xbox 360 development kits have no spare memory, this posed a major problem.  There were times when the content creators would generate a shader that could not be compiled on target without running out of memory and crashing.  It has only happened three times in five years, but we’ve actually had to run the game in a special, minimal memory mode in order to free up enough memory to compile a necessary shader for a particularly complex piece of content.  Once the shader is present in the network cache, the offending content can be checked in and the rest of the team is none the wiser.

Such things are not unusual in game development, but it still kills me to be responsible for such a god-awful hack of a process.

And yet, CrossStitch continues to earn its keep.  Having our own compiler bridging the gap between our shader code and the platform compiler has proved to be a very powerful thing.  When we added support for the Playstation 3, Chris modified the CrossStitch back-end to compensate for little differences in the Cg compiler.  When I began to worry that some of our shaders were interpolator bound on the Xbox 360, the CrossStitch back-end was modified to perform automatic interpolator packing.  When I added support for Direct3D 10 and several texture formats went missing, CrossStitch allowed me to emulate the missing texture formats in late-bound fragments.  There doesn’t seem to be a problem CrossStitch can’t solve, except, of course, for the staggering inefficiency of its on-target, on-the-fly compilation.

For our next project I’m going to remove CrossStitch from Despair.  I’m going to do it with a scalpel if possible, but I’ll do it with a chainsaw if necessary.  I’m nervous about it, because despite my angst and my disillusionment with dynamic shader compilation, Day 1′s artists are almost universally fans of the Despair renderer.  They see Façade and the other elements of Despair graphics as a powerful and flexible package that lets them flex their artistic muscles.  I can’t take that away from them, but I also can’t bear to write another line of code to work around the costs of on-the-fly shader compilation.

It is clear to me now what I didn’t want to accept five years ago.  Everyone who has a say in it sees the evolution of GPU programs paralleling the evolution of CPU programs: code is static and data is dynamic.  CrossStitch has had a good run, but fighting the prevailing trends is never a happy enterprise.  Frameworks like DirectX Effects and CgFx have become far more full-featured and production-ready than I expected, and I’m reasonably confident I can find a way to map the majority of Despair’s graphics features onto them.  Whatever I come up with, it will draw a clear line between the engine and its shaders and ensure that shaders can be compiled wherever and whenever future platforms demand.

CrossStitch has been the foundation of Day 1′s graphics libraries for over seven years now, and for almost half of that time it has been a regular source of frustration and embarrassment for me.  What I’d like to do is vent my frustration and write an article explaining all the ways in which I went wrong with CrossStitch and why, despite my hatred of it, I continue to put up with it.  But before I can do that I need to write this article, a remembrance of where CrossStitch came from and how I once loved it so much.

My first job in the game industry had me implementing the in-game UI for a flight simulator.  When that project was canceled, I switched to an adventure game, for which I handled tools and 3dsmax exporter work and later gameplay and graphical scripting language design.  A couple years later I found myself in charge of the networking code for an action multiplayer title, and shortly after that I inherited the AI and audio code.  Next I came back to scripting languages for a bit and worked with Lua integration, then I spent six months writing a physics engine before becoming the lead on the Xbox port of a PS2 title.  I only had a few people reporting to me as platform lead, so my responsibilities ended up being core systems, memory management, file systems, optimization, and pipeline tools.

When I interviewed at Day 1, one of the senior engineers asked me what I thought my greatest weakness was as a game developer and I answered honestly that although I’d worked in almost every area of game development, I’d had little or no exposure to graphics.  Imagine my surprise when less than a month after he hired me the studio director came to me and asked if I’d be willing to step into the role of graphics engineer.  It turned out that both of Day 1′s previous graphics engineers had left shortly before my arrival, and the company was without anyone to fill the role.  I was excited for the challenge and the opportunity to try something new, so I quickly accepted the position and went to work.

This left me in a very strange position, however.  I was inheriting the graphics code from MechAssault, so I had a fully working, shippable code base to cut my teeth on, but I was also inheriting a code base with no owner in a discipline for which I had little training, little experience, and no available mentor.  The title we were developing was MechAssault 2, and given that it was a second generation sequel to an unexpected hit, there was a lot of pressure to overhaul the code and attempt a major step forward in graphics quality.

The MechAssault 1 graphics engine was first generation Xbox exclusive, which meant fixed-function hardware vertex T&L and fixed-function fragment shading.  As I began to familiarize myself with the code base and the hardware capabilities, I realized that in order to implement the sort of features that I envisioned for MechAssault 2, I’d need to convert the engine over to programmable shading.  The Xbox had phenomenal vertex shading capability and extremely limited fragment shading capability, so I wanted to do a lot of work in the vertex shader and have the flexibility to pass data to the fragment shader in whatever clever arrangement would allow me to use just a couple instructions to apply whatever per-pixel transformations were necessary to get attractive results on screen.

The problem was that shaders are monolithic single-purpose programs and the entire feature set and design of the graphics engine were reliant on the dynamic, mix-and-match capabilities of the fixed-function architecture.  This is where my lack of experience in graphics and my lack of familiarity with the engine became a problem, because although I was feeling held back by it, I didn’t feel comfortable cutting existing features or otherwise compromising the existing code.  I wanted the power of programmable shading, but I needed it in the form of a configurable, fixed-function-like pipeline that would be compatible with the architecture I had inherited.

I pondered this dilemma for a few days and eventually a plan for a new programmable shader pipeline started to emerge.  I asked the studio director if I could experiment with converting the graphics engine from fixed-function to programmable shaders, and he found two weeks in the schedule for me to try.  Our agreement was that in order to claim success at the end of two weeks, I had to have our existing feature set working in programmable shaders and I had to be able to show no decrease in memory or performance.

My plan was to write a compiler and linker for a new type of shader program, called shader fragments.  Instead of an object in the game having to specify its entire shader program in a single step, the code path that led to rendering an object would be able to add any number of shader fragments to a list, called a shader chain, and finally the chain would be linked together into a full shader program in time for the object to draw.

My first task was to define the syntax for shader fragments.  I had very limited time so I started with an easily parsable syntax, XML.  Fragments consisted of any number of named variables, any number of constant parameters, and a single block of shader assembly code.  Named variables were either local or global in scope, and they could specify several options such as default initialization, input source (for reading data from vertex attributes), output name (for passing data to fragment shaders), and read-only or write-only flags.

I wrote a simple C preprocessor, an XML parser, and a compiler to transform my fragments into byte-code.  Compiled fragments were linked directly into the executable along with a header file defining the constant parameter names.  Rendering of every object began with clearing the current shader chain and adding a fragment that defined some common global variables with default values.  For example, diffuse was a global, one-initialized variable available to every shader chain and screen_pos was a global variable mapped to the vertex shader position output.  Once the default variables were defined, a mesh might add a new fragment that defined a global variable, vertex_diffuse, with initialization from a vertex attribute and additional global variables for world-space position and normals.  Depending on the type of mesh, world-space position might be a rigid transformation of the vertex position, a single or multi-bone skinned transformation of the vertex position, or a procedurally generated position from a height field or particle system.

Common variables were defined for all shader chains.

A shader fragment for generating the eye vector.

With world-space position and normals defined, other systems could then add fragments to accumulate per-vertex lighting into the global diffuse variable and to modulate diffuse by material_diffuse or vertex_diffuse.  Systems could also continue to define new variables and outputs, for example per-vertex fog or, in the case of per-pixel lighting, tangent space.  Precedence rules also allowed fragments to remap the inputs or outputs or change the default initialization of variables defined in earlier fragments.

Custom height fog was implemented in shader fragments.

Particles were generated in shader fragments.

The final step in rendering an object was to transform the active shader chain into a shader program.  Shader programs were compiled on the fly whenever a new shader chain was encountered, resulting in a small but noticeable frame rate hitch.  Luckily, the shader programs were cached to disk between runs so the impact of new shader compilations was minimal.  I had promised to add no additional CPU or GPU cost to rendering, so I put a lot of care into the code for adding shader fragments to shader chains and for looking up the corresponding shader programs.

It was a nerve-racking few weeks for me, however, because it wasn’t until I’d implemented the entire system and replaced every fixed-function feature supported by the engine with equivalent shader fragments that I was able to do side-by-side performance comparisons.  Amazingly, the CPU costs ended up being nearly indistinguishable.  Setting state through the fixed-function calls or setting shader constants and shader fragments was so close in performance that victory by even a narrow margin couldn’t be determined.

The results on the GPU were equally interesting.  The vertex shader implementation outperformed the fixed-function equivalent for everything except lighting.  Simple materials with little or no lighting averaged 10 – 20% faster in vertex shader form.  As the number of lights affecting a material increased, however, the margin dropped until the fixed-function implementation took the lead.  Our most complex lighting arrangement, a material with ambient, directional, and 3 point lights, was 25% slower on the GPU when implemented in a vertex shader.  With the mix of materials in our MechAssault levels, the amortized results ended up being about a 5% drop in vertex throughput.  This wasn’t a big concern for me, however, because we weren’t even close to being vertex bound on the Xbox, and there were several changes I wanted to make to the lighting model that weren’t possible in fixed-function but would shave a few instructions off the light shaders.

The studio director was pleased with the results, so I checked in my code and overnight the game went from purely fixed-function graphics to purely programmable shaders.  The shader fragment system, which I named CrossStitch, opened up the engine to a huge variety of GPU-based effects, and the feature set of the engine grew rapidly to become completely dependent on shader fragments.  By the time we shipped MechAssault 2, our rendering was composed of over 100 unique shader fragments.  These fragments represented billions of possible shader program permutations, though thankfully only a little more than 500 were present in our final content.

Here are some examples of features in MechAssault 2 that were made possible by shader fragments:

• a new particle effects system which offloaded some of the simulation costs to the GPU
• procedural vertex animation for waving flags and twisting foliage
• a space-warp effect attached to certain explosions and projectiles that deformed the geometry of nearby objects
• mesh bloating and stretching modifiers for overlay shields and motion blur effects
• GPU-based shadow volume extrusion
• per-vertex and per-pixel lighting with numerous light types and variable numbers of lights
• GPU-based procedural UV generation for projected textures, gobo lights, and decals
• content-dependent mesh compression with GPU-based decompression

A mech explosion deforms nearby objects.

MA2 mixed per-vertex and per-pixel lighting.

By the end of MechAssault 2 I was convinced CrossStitch was the only way to program graphics.  I absolutely loved the dynamic shader assembly model I’d implemented, and I never had a second’s regret over it.  It was fast, memory efficient, and allowed me to think about graphics in the way I found most natural, as a powerful configurable pipeline of discreet transformations.  If only the story could end there.

In the future I’ll have to write a follow up to this article describing how CrossStitch evolved after MechAssault 2.  I’ll have to explain how it grew in sophistication and capability to keep pace with the advances in 3-D hardware, to support high-level language syntax and to abstract away the increasing number of programmable hardware stages.  I’ll have to explain why the path it followed seemed like such a good one, offering the seduction of fabulous visuals at minimal runtime cost.  But most importantly, I’ll have to explain how far along that path I was before I realized it was headed in a direction I didn’t want to be going, a direction completely divergent with the rest of the industry.

The first implementation of global shadows in Fracture was a single, orthographic shadow map fit to the view frustum. This was never intended to be the final solution, but it was quick and easy to implement and it provided a good baseline for measuring the value of other techniques.

Fracture was, at that time, spec’d to have draw distances of about a thousand meters, and we’d only budgeted enough memory and fill rate for a single 1024×1024 shadow map. Fracture was also first person initially, and we wanted convincing self-shadowing on the player’s 3-D hands and weapons. To get the kind of shadow resolution we wanted, we’d have needed a 100k by 100k orthographic shadow map or a 10,000 times increase in our shadow budget.

The perspective shadow map at its best.

After the orthographic shadow map, I implemented a form of perspective shadow mapping. Perspective shadow maps distribute resolution non-uniformly across the view frustum by utilizing a perspective projection to warp the shape of the shadow frustum to better fit the view frustum. My implementation of perspective shadow maps was primarily inspired by light-space perspective shadow maps. On the whole I found the perspective shadow map implementation reasonably straightforward, perfectly stable, and very effective at increasing shadow resolution near the player’s camera. With a single 1024×1024 perspective shadow map, the shadows in the immediate vicinity of the player were, in ideal conditions, high enough resolution to provide tolerable coarse shadows on the player’s weapon.

Unfortunately, not all conditions were ideal and there were problems.

Single-pass perspective shadow maps have limited flexibility in how they can redistribute resolution across the view frustum. When the shadow’s light direction is orthogonal to the view direction, the perspective shadow frustum is an almost perfect fit for the view frustum. However, as the shadow direction becomes more aligned with the view direction, perspective shadow maps lose their effectiveness and end up distributing shadow resolution uniformly, just like orthographic shadow maps. Luckily this isn’t as big a problem as it first sounds.

A barely discernable player shadow at a problematic view angle.

When the player camera is looking directly into the light, there aren’t really any visible shadow boundaries. Every visible surface is completely self shadowed, and that effect is handled redundantly by shading and shadowing. When the player is looking directly away from the light, however, he’s generally looking directly at his own shadow and shadow resolution is very important. Luckily there are two common characteristics of game worlds that held true for the prototype levels of Fracture. First, global shadows usually come from above, and second, the player camera is usually situated near the bottom of the world. Given these two constraints, there was an obvious solution to the problem of poor shadow resolution when looking at the player’s feet. Before fitting the shadow frustum to the view frustum, I first clipped the view frustum to the dynamic bounds of the world. When the camera is aligned with the light direction, the shadow frustum dimensions are constrained by the size of the visible camera’s far plane. With the view frustum starting at the player’s head and clipped by the ground just below his feet, the far plane of the view frustum was never more than fifty square meters and even a uniform distribution of resolution was sufficient to provide high quality shadows.

Despite its problems, the single perspective shadow map implementation persisted in Fracture for over a year of development. Unfortunately for me, during that time shadows in competing games continued to improve, and the artists and designers felt more and more constrained by the limitations of perspective shadow maps. The artists wanted to feature dramatic early morning and late afternoon lighting in levels, and the designers wanted to incorporate more vertical gameplay in which the player rained death from above down on enemies fifty meters below. We also had occasional issues in which an errant particle effect or physics object would penetrate the terrain and begin plummeting into the uncharted abyss below, dragging the world bounds and shadow quality along with it. In all of those cases my perspective shadow map implementation was no better than an orthographic shadow map and the shadows deteriorated to little more than dark smudges under large objects.

Player shadows were much improved with cascaded PSMs

To address the complaints about the single perspective shadow map approach, my coworker Kyle extended the system to use a cascade of three perspective shadow maps. The cascades were constructed so that each map covered a parallel slice of the view frustum, and the depth of each slice was hand-tuned to optimal effect. The first cascade covered only 4 meters, the next one 100 meters, and the final one fit the entire remaining portion of the view frustum which was still over a thousand meters. Each of the three maps was the same dimensions as the original shadow map, so memory and rendering costs tripled. However, the results were inarguably worth it. In all the cases where the quality of the single perspective shadow map suffered, the cascaded approach maintained high-resolution shadows in the immediate vicinity of the player. Shadows in the mid-distance (the second cascade) also received a moderate bump in resolution compared to the single map approach. Unfortunately shadows in the last cascade weren’t noticeably improved. The costs of this system were quite high, but nevertheless the artists and designers were appeased and development rolled on for another six months.

From the wrong camera angle, the sharp drop in cascade resolution decapitated the player shadow.

After six months with cascaded perspective shadow maps, the development team once again began to have second thoughts. The biggest complaint about the cascaded solution was the boundary between cascades. In problem areas the drop in resolution between the first and second cascades was dramatic. If the player managed to position himself so that the cascade boundary lay across his own shadow, the effect was really unsightly. In some cases the drop in resolution between the shadow of the player’s body and the shadow of the player’s head was so great that the player looked decapitated in his shadow.

From my perspective, there were three additional issues with our shadows. With the expansion to three cascaded shadow maps, shadows were now fantastically over budget. Also, in the middle and far distance where shadow resolution still struggled, the constant shimmering and crawling of the shadows as the camera moved really bothered me. Lastly, the irregularly shaped shadow frustum from the perspective shadow maps made it impossible to get good results from a constant shadow bias. Again in areas where shadow resolution struggled, the shadow bias was unpredictable resulting in inconsistent, but almost always excessive, “peter-panning.”

In the fall of 2007 I embarked on a final rewrite of global shadows for Fracture. To improve performance, I replaced the three independent shadow maps in the cascaded solution with three square regions allocated out of a single texture. I then replaced the shader code for sampling the three shadow maps with a new shader that calculated the UVs appropriate to the desired cascade and only performed a single (filtered) sample from the map. What I had learned from our experience with cascaded shadow maps was that fitting the view frustum with multiple shadow frusta is a far more effective way of increasing shadow map resolution than trying to warp a single shadow map.

Since the performance of my new shader scaled very gracefully with the number of shadow maps, I was able to simultaneously increase the effective shadow map resolution and decrease runtime performance and memory costs by increasing the number of cascades to five. The three 1024×1024 shadow maps were replaced with five 640×640 regions in a single map.

More cascades easily compensated for the switch to uniform shadow maps.

As the number of cascades increased, the value of the perspective transformation in the shadow frusta decreased. Meanwhile I was still frustrated with the shimmering and inconsistent shadow bias associated with perspective shadow maps. I finally made the difficult decision to abandon the perspective shadow map and use traditional orthographic projections for the cascades. This created a few new optimization opportunities in the shader, but more importantly it allowed me to make the shadows from static objects completely stable despite a moving camera and dynamic world bounds. I fit the orthographic shadow frusta to the cascading slices of the view frustum, but I required that the shadow frusta be world axis aligned and I quantized their positions so that as a shadow map moved through the world, its pixel centers always landed in the same place. I also had to quantize the shadow frusta’s near and far planes, though in a much coarser fashion, to ensure consistent depth for an object in the shadow map. This was necessary to guarantee 100% stability in the shadow map when using floating point depth formats.

An aligned cascade boundary, highlighted in red, cuts at odd angles across the view frustum.

Interestingly, clearing the shadows of shimmering and crawling created a new problem that I had to deal with. The uniform distribution of resolution within a cascade and the perfectly stable static shadows made the transitions between cascades really obvious. Whereas previously the general instability of the shadows helped hide the cascade boundaries sliding through the world, now there was a very clear resolution boundary. The fact that the cascades were aligned to the world axes and not the view direction contributed to this problem as well. I always sampled shadows from the highest resolution map available, which meant the cascade boundaries shifted depending on the orientation of the camera. When the camera was looking diagonally between two world axes, the cascade boundaries were at corners of the shadow maps rather than straight edges.

I was 50% over our original budget for shadows, but the new approach was half the cost of what we’d been living with for six months so I felt justified in sacrificing a bit more performance. I expanded each cascade slightly to create an overlap, and I extended the shader to blend between two cascades at the boundaries. On platforms with good pixel shader dynamic branching this only increased costs by about 15%. On less capable platforms the dynamic branching was omitted and the cost of applying shadows grew by 40% to twice our original budget. I also introduced a maximum range for the lowest resolution cascade at this point and faded shadows away completely beyond that distance. This fit conveniently within the blending code I’d already added to the shader, and it saved us from wasting shadow resolution on the rarely visible back half of a 1500 meter view frustum. As I recall, Fracture shipped with between a 250 and 350 meter shadow range depending on the level.

I also at this time pursued an avenue that turned out not to be fruitful. Much of the cost of applying the cascaded shadow maps came from the filtering I was doing in the shader. I was using an 8 tap, Poisson disk filter, which I felt was the best compromise between cost and quality. I decided to try out variance shadow maps instead. I have seen benefits from variance shadow maps in some situations, but in the case of global cascaded shadows the technique didn’t pan out. Variance shadow maps are more expensive to create because they generally can’t take advantage of depth-only rendering, and they either suffer from precision artifacts or they require more memory. They also incur a cost in prefiltering. All of these costs are expected to be made up for by significantly more efficient application of the shadow maps. In my case this simply wasn’t true. Even the best global shadow maps have pretty poor pixel coverage, so fully prefiltering the variance shadow maps is wasteful. I tried several approaches to optimize the variance shadow map technique, but in the end the performance was only equal to my non-variance implementation and the artifacts from the variance approach outweighed the improved softness of the shadows.

The last change I made for Fracture’s shadows was to replace the manually specified transition and cascade sizes with ones automatically computed to preserve constant screen-space shadow resolution between cascades. For any given scene I found that hand-tuned values could produce slightly more appealing results, but since we had many varying FOVs and shadow ranges, I didn’t feel justified in forcing the artists to manually specify every value.

One of the fun things about the work I put into the shadows in Fracture is that very few of the techniques I experimented with were mutually exclusive. I was able to, at one point, run through our levels toggling the shadows from perspective to orthographic, variance to non-variance, PCF to Poisson disk, and simultaneously varying the number, size, and resolution of the cascades. I also implemented debug visualization modes to show the outline of shadow texels in the world rather than the shadows themselves. Doing this, the value and cost of the various techniques became rapidly apparent. Perspective shadow maps were great, but I could always get better quality and lower costs by increasing the number of cascades. Prefiltering with variance shadow maps was great, but a fairly expensive filter during sampling was better looking for the same cost. The optimal number and size of cascades actually varied slightly depending on the target platform. Although I said we used five cascades at 640×640, that was only on the Xbox 360. On the PS3 the sweet spot for performance turned out to be distributing slightly more memory across three higher-resolution cascades.

The uniform shadow maps provided plenty of resolution even in worst-case scenarios.

That pretty much covers the implementation of global shadows that Fracture shipped with. It survived about two years with few complaints and reasonable performance. Since Fracture I’ve made a few more improvements, though mostly in the realm of optimizations. The most valuable optimization, and the only one I’ll mention here, was culling the contents of each cascade more aggressively. Although each cascade must be an orthogonal frustum from the perspective of the GPU, a much smaller volume can be defined on the CPU that covers all the shadow casters relevant to a particular map. The volume I use for culling each map is constructed by finding the intersection of the view frustum extruded in the direction of the light and the original orthogonal shadow frustum and then subtracting the volume of all the higher resolution maps. The result isn’t a convex shape, but it can be decomposed into an inclusive and an exclusive convex volume for fast object intersection queries.

In real-world data, more aggressive culling of the cascades reduced the number of objects rendered into the global shadow map by between 30 and 75 percent depending on the orientation of the camera relative to the light. The nice thing about this reduction is that it starts at the object level and consequently translates directly into CPU and GPU savings.

I’m pretty confident now that I won’t be revisiting global shadows again in this hardware generation.  I’m completely satisfied with both the cost and the quality of our current solution, and I don’t feel there is much improvement to be had without introducing a new computation model.  With any luck, the next time I’m thinking about global shadows it will be in the context of compute shaders and perhaps even non-rasterization based techniques.

SymbolSort is a utility for analyzing code bloat in C++ applications.  It works by extracting the symbols from a dump generated by the Microsoft DumpBin utility or by reading a PDB file.  It processes the symbols it extracts and generates lists sorted by a number of different criteria.  You can read more about the motivation behind SymbolSort here.

The lists compiled by SymbolSort are:

Raw Symbols, sorted by size

This list is generated from the complete set of symbols.  No deduplication is performed so this list is intended to highlight individual large symbols.

File contributions, sorted by size

This list is generated by calculating the total size of symbols that contribute to a folder path.  If the input is a COMDAT dump, the source location for symbols is the .obj or .lib file that DumpBin was run on (see usage for details).  It is important to note that for COMDAT dumps individual symbols will appear multiple times coming from different .obj files.  If the input is a PDB file, the source location for symbols is the actual source file in which the symbol is defined.  The source file for data symbols is not always clearly defined within the PDB so in some cases it is a best guess.

File contribution, sorted by path

This is a complete, hierarchical list of the size of symbols in all contributing source files.

Symbol Sections / Types, sorted by total size and by total count

This shows a breakdown of symbols by section or type, depending on the kind of information that can be extracted from the input source.

Merged Duplicate Symbols, sorted by total size and by total count

This list is generated by merging symbols with identical names.  The symbols are not guaranteed to be the same symbol.  In the case of PDB input there will be very few duplicate symbols.  COMDAT input, however, should contain a large number of duplicate symbols.  This list is useful for measuring total compile and link time for a particular symbol.  A relatively small symbol that appears in a very large number of .obj files will have a large total size and appear near the top of this list.

Merged Template Symbols, sorted by total size and by total count

This list is generated by stripping template parameters from symbols and then merging duplicates.  Symbols std::auto_ptr<int> and std::auto_ptr<float> will be transformed into std::auto_ptr<T> in this list and be counted together.

Merged Overloaded Symbols, sorted by total size and by total count

This list is generated by stripping template parameters and function parameters from symbols and then merging duplicates.  Overloaded functions sqrt(float) and sqrt(double) will be transformed into sqrt(…) in this list and be counted together.

Symbol Tags, sorted by total size and by total count

This list represents a tag cloud generated from the symbol names.  The symbols are tokenized and the total size and count is tallied for each token.  I’m not sure what this list is good for, but I’m all about tag clouds so I couldn’t resist including it.

USAGE

SymbolSort [options]

Options:
  -in[:type] filename
      Specify an input file with optional type.  Exe and PDB files are
      identified automatically by extension.  Otherwise type may be:
          comdat - the format produced by DumpBin /headers
          sysv   - the format produced by nm --format=sysv
          bsd    - the format produced by nm --format=bsd --print-size

  -out filename
      Write output to specified file instead of stdout

  -count num_symbols
      Limit the number of symbols displayed to num_symbols

  -exclude substring
      Exclude symbols that contain the specified substring

  -diff:[type] filename
      Use this file as a basis for generating a differences report.
      See -in option for valid types.

  -searchpath path
      Specify the symbol search path when loading an exe

  -path_replace regex_match regex_replace
      Specify a regular expression search/replace for symbol paths.
      Multiple path_replace sequences can be specified for a single
      run.  The match term is escaped but the replace term is not.
      For example: -path_replace d:\\SDK_v1 c:\SDK -path_replace
      d:\\SDK_v2 c:\SDK

  -complete
      Include a complete listing of all symbols sorted by address.

Options specific to Exe and PDB inputs:
  -include_public_symbols
      Include 'public symbols' from PDB inputs.  Many symbols in the
      PDB are listed redundantly as 'public symbols.'  These symbols
      provide a slightly different view of the PDB as they are named
      more descriptively and usually include padding for alignment
      in their sizes.

  -keep_redundant_symbols
      Normally symbols are processed to remove redundancies.  Partially
      overlapped symbols are adjusted so that their sizes aren't over
      reported and completely overlapped symbols are discarded
      completely.  This option preserves all symbols and their reported
      sizes

  -include_sections_as_symbols
      Attempt to extract entire sections and treat them as individual
      symbols.  This can be useful when mapping sections of an
      executable that don't otherwise contain symbols (such as .pdata).

  -include_unmapped_addresses
      Insert fake symbols representing any unmapped addresses in the
      PDB.  This option can highlight sections of the executable that
      aren't directly attributable to symbols.  In the complete view
      this will also highlight space lost due to alignment padding.

SymbolSort supports three types of input files:

COMDAT dump

A COMDAT dump is generated using the DumpBin utility with the /headers option.  DumpBin is included with the Microsoft compiler toolchain. SymbolSort can accept the dump from a single .lib or .obj file, but the best way to use it is to create a complete dump of all the .obj files from an entire application.  The Windows command line utility FOR can be used for this:

for /R "c:\obj_file_location" %n in (*.obj) do "C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\bin\DumpBin.exe" /headers "%n" >> c:\comdat_dump.txt

This will generate a concatenated dump of all the headers in all the .obj files in c:\obj_file_location.  Beware, for large applications this could produce a multi-gigabyte file.

PDB or EXE

SymbolSort supports reading debug symbol information from .exe files and .pdb files.  The .exe file will only be used to find the location of its matching .pdb file, and then the symbols will be extracted from the PDB.  SymbolSort uses msdia100.dll to extract data from the PDB file.  Msdia100.dll is included with the Microsoft compiler toolchain.  In order to use it you will probably have to register the dll.

regsvr32 "C:\Program Files\Common Files\Microsoft Shared\VC\msdia100.dll"

It is important that you register the 64-bit version of msdia100.dll on 64-bit Windows and the 32-bit version on 32-bit Windows.  If you don’t find msdia100.dll in the path listed above, try looking for it in the Visual Studio install directory under “\Microsoft Visual Studio 10.0\DIA SDK\bin\”

NM dump

Similar to the COMDAT dump, SymbolSort can accept symbol dumps from the unix utility nm.  The symbols can be extracted from .obj files or entire .elfs.  SymbolSort supports bsd and sysv format dumps.  Sysv is preferred because it contains more information.  The recommended nm command lines are:

nm --format=sysv --demangle --line-numbers input_file.elf
nm --format=bsd --demangle --line-numbers --print-size input_file.elf

DOWNLOAD

SymbolSort-1.2.zip

BUILDING

The source for SymbolSort is distributed as a single file, SymbolSort.cs.  It can be built as a simple C# command line utility.  In order to get the msdia100 interop to work you must add msdia100.dll as a reference to the C# project.  That is done either by dragging and dropping the dll onto the references folder in the C# project or by right clicking the references folder, selecting “Add Reference” and then browsing for the msdia100 dll.

REVISION HISTORY

1.2    + Upgraded to Visual Studio 2010 / msdia100.dll
       + Added -path_replace option to convert paths stored in PDBs.
       + Added -complete option to dump a full list of all symbols sorted by 
         address.
       + Added several options for controlling what symbols are included in PDB
         dumps since PDBs often list the same address redundantly under
         different labels.
1.1    + Added support for computing differences between multiple input sources
       + Added support for nm output for PS3 / unix platforms.
       + Changed command line parameters.  See usage for details.
       + Added section / type information to output.
1.0    + First release!

FUTURE WORK (to be done by someone else!)

• Add a GUI frontend to allow interactive filtering and sorting.
• Read both the PDB and the COMDAT dump simultaneously and cross-reference the two.  This would enable new kinds of analysis and richer dumps.
• Produce additional merged symbol reports by merging all symbols from the same class or namespace or that match based on some more clever fuzzy comparison.
• Improve relative -> absolute path conversion for nm inputs
• Figure out how to extract string literal information from PDB.

The last item on my list of code bloat causes is redundant template instantiation.  Template functions have a lot in common with inline functions.  Like inline functions, template functions are instantiated into the object file of every translation unit in which they are used.  Also like inline functions, template functions generate weak symbols which are merged silently by the linker.  Redundant template instantiations won’t increase your executable size, but they can contribute significantly to your build times.

Consider a commonly used class like std::string.  The std::string class is actually a template class defined as:

In an engine that uses std::strings, some members like std::string::assign may be referenced in nearly every translation unit.  Even engines that eschew the use of std::string may unknowingly be instantiating a lot of std::string code because it is so pervasive in the standard library.  Looking at a symbol dump from one version of Despair Engine, I see over 1600 instances of dozens of functions from std::string.  That’s right, in every full build we compile most of std::string 1600 times, optimize the code 1600 times, write it into .obj files 1600 times, copy it into .lib files 1600 times, read it into the linker 1600 times, and then throw 1599 identical copies away!  All told I think it is less than 10 megabytes of code and accounts for only a couple percent of our build times, but still, it’s a lot to pay for a wrapper around a char*.

Don’t think that these sorts of problems are confined to the standard library.  Any template class that is widely used can produce a lot of code bloat from redundant instantiations.  The question is, what do you do about it?

One option is to convert template code into non template code.  If you never instantiate basic_string with anything other than a single set of parameters, is it really worth being a template class?  The same question could be asked of a templatized math library.  Does matrix<T> need to be a template class when all you ever use is matrix<float>?

Although removing template code is always an option, it isn’t always a good one.  Template code may be expensive, but it is also really handy.  If you have a templatized math library, chances are that while 99% of the instantiations are matrix<float>, somewhere in your engine or tools you have an instantiation of matrix<double>.  Similarly, amid all those instantiations of basic_string<char>, maybe there’s a basic_string<wchar_t> or two hanging out.

Luckily there is a way to prevent redundant template instantiations without changing the code.  That is through the use of explicit template instantiation declarations.  Explicit instantiation declarations aren’t technically part of the C++ standard, but they’re supported by MSVC and gcc and they’re included in the C++09 draft standard, so they’re a safe bet to use.  What explicit instantiation declarations do is allow you to prevent the compiler from instantiating a particular template in the current translation unit.  They look just like explicit instantiation definitions, but they’re preceded by the extern keyword.  For example, the explicit instantiation declaration of basic_string<char> looks like this:

You can add this declaration to a root header in your application and rebuild, and, unless you’ve missed a translation unit, you’ll encounter linker errors for missing basic_string<char> symbols.  Once you’ve removed all the basic_string<char> instantiations from your engine, the next thing to do is to add one back so the linker has all the code it needs to put together a complete executable.  That’s where explicit instantiation definitions come in.

Explicit instantiation definitions are the counterpart to explicit instantiation declarations.  They tell the compiler to fully instantiate a particular template even if it is otherwise unused in the current translation unit.  Here’s an example of how you can use the two concepts together to prevent redundant instantiations of basic_string.

// in string_instantiation.h
#ifdef DS_EXTERN_TEMPLATE_INSTANTIATION
namespace std
{
    extern template class basic_string<char>;
}
#endif

// in string_instantiation.cpp
#ifdef DS_EXTERN_TEMPLATE_INSTANTIATION
#undef DS_EXTERN_TEMPLATE_INSTANTIATION

#include "string_instantiation.h"

namespace std
{
    template class basic_string<char>
}
#endif // DS_EXTERN_TEMPLATE_INSTANTIATION

The DS_EXTERN_TEMPLATE_INSTANTIATION #define in the above code serves two purposes.  First it allows us to disable explicit template instantiation for compilers that don’t support it, and second it allows us to work around a common bug in compilers that do support it.  Although the standard states that an explicit instantiation definition may follow an explicit instantiation declaration within a translation unit, many compilers don’t like it and won’t allow an explicit instantiation definition to override a preceding explicit instantiation declaration.

There is one dark fact about explicit template instantiation that you should know before applying it in your own codebase.  Although explicit template instantiation effectively turns template code into non template code from the perspective of code bloat, it doesn’t really help much with classes like std::string.  The syntax for out-of-line template class function definitions is so cumbersome that many programmers prefer to implement all their template class members entirely within the class declaration.  That’s what has happened with Microsoft’s STL implementation.  Unfortunately what that does is implicitly make every member function in a template class an inline function.  Of course most of the member functions are so large that they’ll never be inlined, but it doesn’t matter from the perspective of the compiler.

The explicit template declaration of basic_string<char> prevents the compiler from instantiating its members as template functions, but it doesn’t prevent it from instantiating them as inline functions!  The basic_string class goes from a classic example of code bloat due to redundant template instantiation to a classic example of code bloat due to incorrect inlining!  You can’t win!

In your own code, at least, you can fix the incorrect inlining problem right after you fix the redundant instantiation problem.  Just move the template class member functions out of line and they’ll disappear from your symbol dumps.

And that’s everything I know about code bloat in a voluminous 6 part series.  Perhaps what I should be writing about is blog bloat.  All that’s left is to post some code.

Earlier I talked about excessive inlining as a common cause of code bloat.  Excessive inlining is when code that shouldn’t be inlined is.  Today I’m going to look at a related problem, code that is declared as inlined but never will be.

Any function whose address is taken for storage in a function pointer or a virtual function table can never fully be inlined.  Even for a function that can legally be inlined, the compiler has ultimate authority over whether or not it will be.  If a function is large the compiler will generally forgo inlining it because the performance benefits of removing the function call overhead don’t justify the increase in executable size.  That’s all well and good, but it still poses a problem.

C++ compilers work by dividing programs into something called translation units.  A translation unit is a single cpp file and all the headers it includes.  The compiler turns these translation units into object files and ultimately the linker combines the contents of all the object files into an executable.  The important thing to note is that every function visible to the compiler in a translation unit must be compiled as part of that unit.  In the case of a function that is declared inline, the compiler will generate a compiled instantiation of the function in every cpp file that uses it.  The various redundant instantiations are marked as weak symbols so the linker knows that multiple copies are expected and that it can pick any one of them for use in the final executable.

Knowing this, you can see how wasteful functions that are incorrectly marked as inline can be.  Large functions are less likely to be inlined, are more likely to take a long time to compile, and consequently can be murder on your build times.

By this point you should have a pretty good idea of how to detect incorrect inlining.  The same technique I proposed for measuring excessive inlining and the compile-time cost of template overspecialization works equally well for detecting incorrect inlining.  Dump the symbols from all your object files with DumpBin /headers and look for large functions with lots of redundant instantiations.

One of the most interesting (and insidious!) sources of incorrect inlining is code that you don’t write at all.  Consider this apparently harmless class definition:

class DataBox
{
    PhysicsData     m_physics;
    AIData          m_ai;
    GraphicsData    m_graphics;
    AnimationData   m_animation;
    UIData          m_ui;
    ScriptData      m_script;
    NetworkData     m_network;
};

This class is potentially a major contributor to code bloat from incorrect inlining.  If you’re scratching your head and wondering how a class with no functions can contribute to code bloat, take a look at the next listing to see this class the way the compiler sees it.

class DataBox
{
    PhysicsData     m_physics;
    AIData          m_ai;
    GraphicsData    m_graphics;
    AnimationData   m_animation;
    UIData          m_ui;
    ScriptData      m_script;
    NetworkData     m_network;

    // Not legal C++.  This is for illustration purposes only.
    DataBox()
    {
        m_physics.PhysicsData();
        m_ai.AIData();
        m_graphics.GraphicsData();
        m_animation.AnimationData();
        m_ui.UIData();
        m_script.ScriptData();
        m_network.NetworkData();
    }

    ~DataBox()
    {
        m_network.~NetworkData();
        m_script.~ScriptData();
        m_ui.~UIData();
        m_animation.~AnimationData();
        m_graphics.~GraphicsData();
        m_ai.~AIData();
        m_physics.~PhysicsData();
    }
};

In C++ every class has a constructor, a destructor, a copy constructor, and an assignment operator.  If you don’t provide these functions the compiler will, and it must do so inline.  Of course good compilers will only instantiate inline functions when they are actually used, so most classes never have their default copy constructor or assignment operators generated, but unless you’re doing something dangerously clever in your codebase, every class has a destructor instantiated at least once.

If you notice default (also sometimes called automatic) methods showing up in the top slots of your redundant function hotlist, the fix is counterintuitive but also really simple.  Just provide an empty, non-inline implementation in place of the default one.  Providing empty, non-inline implementations of default methods for nontrivial classes can sometimes help your build times in other ways.  If you use a lot of smart pointers in your code, the default destructor of a class holding smart pointers may be the only thing preventing you from replacing the #includes of the headers for the classes stored in smart pointers with forward declarations of those classes.  In other words, inline functions create header dependencies, and inline default methods are no exception.

Speaking of smart pointers, as great as they are, code bloat is one of their unfortunate costs.  As I mentioned above, good compilers only instantiate inline code when it is actually used.  Reference counting smart pointers allow for distributed ownership of objects, which can be a powerful and convenient design freedom.  However, if responsibility for destroying objects is widely distributed through your code, so is responsibility for instantiating object destructors.  An engine with rigorously defined ownership hierarchies will have few inline destructor instantiations whereas an engine with sloppily defined ownership hierarchies will have many.  So if you use smart pointers, use them responsibly!  Pass by reference and reference count only when necessary.  Unnecessary reference counting isn’t just inefficient at run time, it is inefficient at compile time too!

If all this sounds like a major pain in the neck, I suggest you give up now and implement unity builds.  They circumvent all these redundant instantiation issues so they’re fantastic at optimizing build times in codebases with poor structure.  On the other hand, if you’re still enjoying this trek through compile land, join me next time for a discussion of redundant template instantiation.

Static allocations are certainly the simplest and most predictable sources of code bloat.  Static allocations refer to data structures in a program for which storage is allocated for the entire duration of the application’s execution.   In C++ file, class, and local static variables all require static allocations.  Additional examples of static allocations in C++ are global variables, string literals, and virtual function tables.

Static allocations can be very useful in some circumstances, but they can also be very wasteful.  Most of the code in an engine is executed very infrequently, which means most of the static allocations supporting that code are rarely needed.  Unfortunately since static allocations exist for the lifetime of the program, they’re taking up memory whether you’re using them or not.

In addition to possibly wasting memory, static allocations can increase program link and load times.  The memory for most static allocations is reserved directly within the application binary.  Consequently, every megabyte of static allocation is a megabyte that must be written to disk every time you link, copied across the network every time you deploy, and read from disk every time you launch.

The one exception to this is a special kind of static allocation known as bss data.  Static allocations that are known at compile time to be zero-initialized are placed in a special section of the executable called the bss section.  Memory used by objects in the bss section isn’t reserved in the executable, instead it is allocated by the program loader.  Bss data doesn’t significantly impact build times, but it has the same run time memory requirements as other static allocations.

In the list of code bloat causes, static allocations are usually a very distant third, but every engine I’ve investigated for static allocations has yielded a few unpleasant surprises.

Dumpbin isn’t of much help when it comes to tracking static allocations.  Data symbols aren’t packaged as COMDATs, so they don’t show up in the /headers report I’m so fond of.   To gather statistics on the static allocations within your application, you’ll have to crack open the PDB.  Every static and global variable is documented in the program database along with its size and, through some creative cross-referencing, its source file.

Large static objects are easy to find–just sort the data symbols by size and gawk at the top offenders. Don’t stop there though.  If you generate a lot of code with templates or macros, you may have large numbers of relatively small static objects.  To quantify the cost of these objects you’ll need to do some pattern matching on symbol names. You can strip template parameters from symbols so MyClass<int>::s_buffer and MyClass<float>::s_buffer get counted together in the stats, or you can strip away the scope entirely and tally the stats for all statics named s_buffer together.  I find it useful to analyze the results from collapsing symbol names in a variety of different ways.  Which option yields the best results depends on the particular codebase I’m dealing with and the type of code generation it uses.

That covers it for static allocations and for executable size optimizations in general.  I still have a couple topics to go, but from now on they’re relevant to build times alone.  Coming up, incorrect inlining.