SOA (Structs of Arrays)

Goal

The desire is to provide a more data-oriented way to do game object systems without losing language expressivity.

This means retaining the following functionality:

is-a / has-a relationships (code re-use via inheritance and composition) ¹
calling functions with parameter types of the base class (upcasting) ²
organizing functions into known slots on the base class (downcasting) ³
convenience of an implicit this -> in member functions ⁴

While being more “data-oriented”—having a clear idea of how you want things to live in memory, in accordance with the principles and guidance outlined in the following references: ⁵

“Data-Oriented Design”, Noel Llopis, http://gamesfromwithin.com/data-oriented-design
“Chandler Carruth: Efficiency with Algorithms, Performance with Data Structures.” YouTube, uploaded by CppCon, Oct 21, 2014, https://www.youtube.com/watch?v=fHNmRkzxHWs
“Mike Acton: Data Oriented Design in C++.” YouTube, uploaded by CppCon, Mar 24, 2017, https://www.youtube.com/watch?v=rX0ItVEVjHc

Problem

In C++, when expressing an is-a / has-a relationship, the following is a typical simple example for organizing game objects:

struct Entity {
    Vector3 position;
    Quaternion orientation;

    unsigned int flags;

    virtual void update() {}
};

struct Door : public Entity {
    float openness_current;
    float openness_target;

    void update() override;
};

struct Human : public Entity {
    char *name;

    void update() override;
}

But this design conceit has introduced problems that grow worse with scale: ⁶

All classes are different sizes
Entities can’t be allocated contiguously
Cache misses occur

Jai provides the using keyword to allow memory-smart composition. ⁷

And Jai provides the SOA keyword to organize data into CPU-friendlier Structures of Arrays (SOA): ⁸ ⁹ ¹⁰ ¹¹

toggle example

// from: https://youtu.be/ZHqFrNyLlpA?t=1835

print_floats_in_memory :: () {

  Vector3 :: struct {
    x : float = 1;
    y : float = 4;
    z : float = 9;
  }

  print_floats_in_memory :: (data : ^ float, count : int) {
    for 0..count-1 {
      s := " ";
      if it > 9 then s = "";
      printf("  %s[%d] = %f\n", s, it, data[it]);
    }
  }

  N :: 3;

  a : [N] Vector3;
  b : [N] SOA Vector3;

  printf("\n");

  printf("Layout of a:\n");
  print_floats_in_memory(cast(a.data, ^float), N*3);
  printf("\n");

  printf("Layout of b:\n");
  print_floats_in_memory(cast(b.data, ^float), N*3);
  printf("\n");
}

/* results:

Layout of a:
   [0] = 1.000000
   [1] = 4.000000
   [2] = 9.000000
   [3] = 1.000000
   [4] = 4.000000
   [5] = 9.000000
   [6] = 1.000000
   [7] = 4.000000
   [8] = 9.000000

Layout of b:
   [0] = 1.000000
   [1] = 1.000000
   [2] = 1.000000
   [3] = 4.000000
   [4] = 4.000000
   [5] = 4.000000
   [6] = 9.000000
   [7] = 9.000000
   [8] = 9.000000
*/

print_floats_in_memory.jai

toggle example

// from: https://youtu.be/ZHqFrNyLlpA?t=3565

Vector3 :: struct {
  x : float = 1;
  y : float = 4;
  z : float = 9;
}

soa_entity_test :: () {

  Entity :: struct SOA { // <-- SOA on the struct declaration
    position : Vector3;
    id : int;
    flags : u32;
  }

  Door :: struct {
    using entity : ^ Entity;

    openness_current : float = 0;
    openness_target : float = 0;
  }


  MAX_ENTITIES :: 100;
  num_entities : int = 0;

  entities : [MAX_ENTITIES] Entity;

  get_next_entity :: (entities : [] Entity, num_entities : ^ int) -> ^ Entity {
    result := ^entities[*num_entities];
    *num_entities += 1;
    return result;
  }

  door : Door;
  door.entity = get_next_entity(entities, ^num_entities);

  print_position :: (using entity : ^Entity) {
    printf("soa_entity_test: (%f, %f, %f)\n", position.x, position.y, position.z);
  }

  print_position(^door);
}

soa_entity_test.jai

The AOS keyword allows for declaration-specific overrides to retain Array of Structures style packing when the default has been set to Structures of Arrays. ¹²

Expressing some kind of is-a relationship or has-a relationship
“Data-Oriented Demo: SOA, composition.” YouTube, uploaded by Jonathan Blow, Jan 21, 2015, https://youtu.be/ZHqFrNyLlpA?t=655 ⮌
C++ lets you call functions with the parameter types of the base class.
“Data-Oriented Demo: SOA, composition.” YouTube, uploaded by Jonathan Blow, Jan 21, 2015, https://youtu.be/ZHqFrNyLlpA?t=822 ⮌
Virtual functions are about going from the base class up to the derived class.
“Data-Oriented Demo: SOA, composition.” YouTube, uploaded by Jonathan Blow, Jan 21, 2015, https://youtu.be/ZHqFrNyLlpA?t=862 ⮌
Some value [in ..] having an implicit this in member functions and you don’t have to write extra code all the time.
“Data-Oriented Demo: SOA, composition.” YouTube, uploaded by Jonathan Blow, Jan 21, 2015, https://youtu.be/ZHqFrNyLlpA?t=902 ⮌
Here are some references in order of approachability about how to structure your program to behave well with respect to memory.
“Data-Oriented Demo: SOA, composition.” YouTube, uploaded by Jonathan Blow, Jan 21, 2015, https://youtu.be/ZHqFrNyLlpA?t=968 ⮌
This packing together of things in memory is part of what makes your game slow, because it has some consequences.
“Data-Oriented Demo: SOA, composition.” YouTube, uploaded by Jonathan Blow, Jan 21, 2015, https://youtu.be/ZHqFrNyLlpA?t=338 ⮌
See Reference > Keywords > Using ⮌
A language like C++ basically assumes your data is going to be in a thing called Array of Structures (AOS): [..] When you’re trying to put things in memory, they go in an array, and each structure in the array is contiguous, so all the members are laid out in order. But most CPUs don’t really want data that way. Most CPUs want things laid out as Structures of Arrays (SOA).
“Data-Oriented Demo: SOA, composition.” YouTube, uploaded by Jonathan Blow, Jan 21, 2015, https://youtu.be/ZHqFrNyLlpA?t=2870 ⮌
In computing, Array of Structures (AoS), Structure of Arrays (SoA) and Array of Structures of Arrays (AoSoA) refer to contrasting ways to arrange a sequence of records in memory, with regard to interleaving, and are of interest in SIMD and SIMT programming.
https://en.wikipedia.org/wiki/AOS_and_SOA ⮌
If a language is going to be data-oriented, then it should—for example—be easy to put your data in SOA format.
“Data-Oriented Demo: SOA, composition.” YouTube, uploaded by Jonathan Blow, Jan 21, 2015, https://youtu.be/ZHqFrNyLlpA?t=2927 ⮌
The reason that’s faster is because now, in my Entity array, all these flags are going to be next to each other [..] and if you just want to deal with flags, that flags-flags-flags for a long time in memory lets you be very fast.
“Data-Oriented Demo: SOA, composition.” YouTube, uploaded by Jonathan Blow, Jan 21, 2015, https://youtu.be/ZHqFrNyLlpA?t=3515 ⮌
I can make [a struct] that’s SOA by default, but if I want an array of them that’s AOS (for some reason) I can do that.
“Data-Oriented Demo: SOA, composition.” YouTube, uploaded by Jonathan Blow, Jan 21, 2015, https://youtu.be/ZHqFrNyLlpA?t=3679 ⮌

jailang 2019 pixeldroid
https://github.com/pixeldroid/jailang

programming pages theme v0.5.21 (https://github.com/pixeldroid/programming-pages)

s	focus search bar ( enter to select, ▲ / ▼ to change selection)
g e	go to examples
g m	go to modules
g o	go to overview
g r	go to reference
h	toggle this help ( esc also exits)

SOA (Structs of Arrays)

Goal

Problem

Keyboard Shortcuts