Game Engine Architecture

228 5. Engine Support Systems

tion. If an algorithm executes a subalgorithm n times, and the subalgorithm is

O(log n), then the resulting algorithm would be O(n log n).

To select an appropriate container class, we should look at the opera-

tions that we expect to be most common, then select the container whose per-

formance characteristics for those operations are most favorable. The most

common orders you’ll encounter are listed here from fastest to slowest: O(1),

O(log n), O(n), O(n log n), O(n^2 ), O(nk) for k > 2.

We should also take the memory layout and usage characteristics

of our containers into account. For example, an array (e.g., int a[5] or

std::vector) stores its elements contiguously in memory and requires no

overhead storage for anything other than the elements themselves. (Note that

a dynamic array does require a small fi xed overhead.) On the other hand, a

linked list (e.g., std::list) wraps each element in a “link” data structure

that contains a pointer to the next element and possibly also a pointer to the

previous element, for a total of up to eight bytes of overhead per element. Also,

the elements in a linked list need not be contiguous in memory and oft en

aren’t. A contiguous block of memory is usually much more cache-friendly

than a set of disparate memory blocks. Hence, for high-speed algorithms, ar-

rays are usually bett er than linked lists in terms of cache performance (unless

the nodes of the linked list are themselves allocated from a small, contiguous

memory block of memory, which is rare but not entirely unheard of). But a

linked list is bett er for situations in which speed of inserting and removing

elements is of prime importance.

5.3.4. Building Custom Container Classes

Many game engines provide their own custom implementations of the com-

mon container data structures. This practice is especially prevalent in console

game engines and games targeted at mobile phone and PDA platforms. The

reasons for building these classes yourself include:

• Total control. You control the data structure’s memory requirements, the
  algorithms used, when and how memory is allocated, etc.


• Opportunities for optimization. You can optimize your data structures
  and algorithms to take advantage of hardware features specifi c to the
  console(s) you are targeting; or fi ne-tune them for a particular applica-
  tion within your engine.


• Customizability. You can provide custom algorithms not prevalent in
  third-party libraries like STL (for example, searching for the n most-
  relevant elements in a container, instead of just the single most-rele-
  vant).