On Programming

A discussion of programming strategies and results

On Game Object Architecture

| Comments

This post will serve as a fact finding mission. In class my professor described two object models for video games: Object-Centric Architecture and Property-Centric Architecture. In class it was suggested that while Property-Centric Architecture is less intuitive to write, it will run faster due to less cache misses by packing all the relevant data into the same block of memory. I decided that there was a third option which I will call Hook-Centric Architecture which I believed would be the fastest through avoiding branches. To run this test I am going to write a small C++ program to perform Explicit Euler Numerical Integration.

Object-Centric Architecture

This is your classic design of objects. All the properties relating to the object are stored in the object itself. Below is the structure I used.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  typedef struct
  {
      double x;
      double y;
      double z;
  } triplet;

  typedef struct
  {
      triplet acceleration;
      triplet velocity;
      triplet position;
      bool in_use;                /**< Only used for Property-Centric */
  } transform;

  typedef struct
  {
      bool has_transform;
      transform* p;
      float mass;
      void* model;                /**< Since this is just a test we can use void* */
      void* texture;
  } object;
You’ll notice that this closely mimics the classic object oriented design which closely mimics real life objects.

Property-Centric Architecture

The idea behind the Property-Centric Architecture is that all the related data is packed together in contiguous memory in order to avoid cache misses. For this test we don’t need to actually create the object structs since I am only performing operating on the transform.

1
2
3
4
5
6
7
  transform* transform_objects;

  void init_property_centric()
  {
      transform_objects = new transform[MAX_NUM_OF_OBJECTS];
      //Perform other initialization
  }
You’ll notice that since this data is allocated in an array it will be in one contiguous block in memory, whereas depending on how I allocate the Object-Centric objects they could be scattered across the full spectrum of memory.

Hook-Centric Architecture

The idea here is that every object would store all the fields it owns just like in Object-Centric Architecture, but now the fields would only be processed by putting function pointers into a long list of functions to get executed at every frame. This way only the objects with the specified property will spend cycles calculating the changes. Allow me to illustrate:

Classic Update

1
2
3
4
5
6
7
  for (object & o : classic_objects) //C++11 range-based for loop
  {
      if (o.has_transform) // BRANCHING!
      {
          update_transform(o);
      }
  }

Hook Update

1
2
3
4
5
  //Passing in a double representing number of milliseconds since last frame
  for (function<void (double)> & f : callbacks)
  {
      f(time);
  }

Explanation

As you can see, the Object-Centric Archtecture introduces branching through its if statement, whereas the Hook-Centric Architecture can blindly chug along processing everything in its path.

Running The Tests

For all three architectures I initialized the transform object using this function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  /** 
   * Initialize the phyics objects with blank data and random acceleration
   * 
   * @param data The transform object to initialize
   */
  inline void init_transform(transform & data)
  {
      data.position.x = 0;
      data.position.y = 0;
      data.position.z = 0;
      data.velocity.x = 0;
      data.velocity.y = 0;
      data.velocity.z = 0;
      data.acceleration.x = ((double)(rand()%100)) / 10.0;
      data.acceleration.y = ((double)(rand()%100)) / 10.0;
      data.acceleration.z = ((double)(rand()%100)) / 10.0;
  }
To perform the integration I used this function:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  /**
   * Perform explicit euler numeric integration
   * 
   * @param data The transform object
   * @param time The amount of time in seconds since last run
   */
  inline void explicit_euler_numeric_integration(transform & data, const double & time)
  {
      data.velocity.x += data.acceleration.x * time;
      data.velocity.y += data.acceleration.y * time;
      data.velocity.z += data.acceleration.z * time;
      data.position.x += data.velocity.x * time;
      data.position.y += data.velocity.y * time;
      data.position.z += data.velocity.z * time;
  }
The tests were run on a Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz with 200000 objects created for each test, and each test went through 10000 integrations. Before performing the test I made sure to disable all CPU freqency scaling since the processor will be running at full blast inside a game anyway.
1
  for i in 0 1 2 3 4 5 6 7; do sudo cpufreq-set -c $i -g performance; done

Results

Times are listed in number of seconds

No Compiler Optimizations

Object-CentricProperty-CentricHook-Centric
4531135
4430135
4531136
4629137
4531135

Compiler Optimizations

Object-CentricProperty-CentricHook-Centric
362928
342929
332928
333026
363028

Analysis

As you can see, the Hook-Centric model without compiler optimizations is just awful, but once you put on compiler optimizations it suddenly becomes the best option. I’ve uploaded the code for these tests to http://static.paphus.com/blog/architecture_test.tar.bz2. I encourage everyone to try it out for themselves. The comment section is open for anyone who can enlighten us further or provide another alternative!

To compile the code install premake and run

1
2
3
4
  premake4 gmake
  make config=debug #no optimizations
  # -or-
  make config=release #compiler optimizations

Comments