C!! — Striped Pointers, Structures-of-Arrays and Arrays-of-Structures in the C bang bang programming language | Accidental Scientist

C!! — Striped Pointers, Structures-of-Arrays and Arrays-of-Structures in the C bang bang programming language

Let’s start this ballgame out with something close to my heart – structures of arrays versus arrays of structures.

It’d be great if there was a good way of implementing these in a nice, succinct, low-cost fashion. Preferably without having to define multiple different structures to do it, or jump through too many crazy hoops.

So what can we come up with?

Defining hot and cold data in structures

Let’s say we have a structure that looks like this:

struct DynamicObject
{
   // Position Data
   vector3 pos;
   vector3 velocity;
  
   // Mesh Data
   Mesh* pMesh;
   Material* pMaterial;

   AIBrain* pBrain;
}

Ignore the vector3 types for now (other than let’s say they’re native to the language; that’s the subject of a future post). Now, when we’re doing an update, we might consider the pos and velocity fields to be hot data, and the others to be cold. So we really want to split this into two structs:

struct DynamicObjectPositionData
{
   vector3 pos;
   vector3 velocity;
}

and… 

struct DynamicObjectMeshData
{
 
   Mesh* pMesh;
   Material* pMaterial;
}

But what we’re doing here, really, is trying to deal with the fact that we have a logical object (the original struct) and a physical layout that makes sense for cache-coherency reasons (the split data layout). Ideally we want to conflate them in some way, so that when we’re thinking about the logical object, we can do that easily, and when we’re thinking about the layout, we can care about that more. Ideally without a lot of typing, and even more, without having to have multiple definitions for the same thing that can get out of sync. (I have other ways of doing this that I’ll get to in a future post when I discuss strict duck-typing contracts – but that’s for the future).

So how do we do that?

Well, one way that comes to mind is by using attribute-syntax like C#. But that quickly gets unwieldy too.

struct DynamicObject
{
   // Position Data

   [group(PositionComponent)]
   vector3 pos;

   [group(PositionComponent)]
   vector3 velocity;
  
   // Mesh Data

   [group(MeshComponent)]
   Mesh* pMesh;

   [group(MeshComponent)]
   Material* pMaterial;

   AIBrain* pBrain;
}

This, with some other syntactic sugar, might give us what we want – a way of saying “Hey, this array of things is only the PositionComponent of DynamicObject”. But I don’t like it. It’s too verbose.

Instead, I’m going to propose the stripe keyword (I could also go with striped). That looks like this:

struct DynamicObject
{
   stripe PositionComponent
   {
      vector3 pos;
      vector3 velocity;
   }

   stripe MeshComponent
   {
      Mesh* pMesh;
      Material* pMaterial;
   }

   AIBrain* pBrain;
}

So now we’ve defined a DynamicObject which has two “stripes”. We can even look at the stripes as defining auxiliary structs (I’m avoiding saying nested) that are tightly related to the original; so saying using stripe DynamicObject::PositionComponent here is equivalent to DynamicObjectPositionData  that we mentioned earlier. (stripe here, in the name reference, is a bit redundant… but it makes it explicit what we’re doing. I’ll explain why in a future post when we come to transformation assignment operators).

If we had a DynamicObject* pObject we could also (unhelpfully, perhaps) refer to it like: pObject->::PositionComponent.pos (which would limit access to the pos and velocity components)… Slightly more usefully, we could define DynamicObject*::PositionComponent pPositionComponent = (DynamicObject*::PositionComponent)pObject, which would give us a pointer to pos, through which we could access pos and velocity.

Accessing Stripes through Striped Pointers

To make accessing that data easier, it’s be great if we had a compound-pointer type that was like an iterator, but referred to all of the different stripes easily. Now, we could code something like this up today in C++ – and we’d end up with something like this (allowing for the stripe auxilliary struct naming convention above for simplicity):

struct StripedDynamicObjectPtr
{
   DynamicObject* pUnstripedMembers; // In this case, pBrain gets put in this bucket…
   DynamicObject::PositionComponent* pPositionComponent;
   DynamicObject::MeshComponent* pMeshComponent;
}

If we’re accessing a structure-of-arrays, then each of these members is a pointer to the head of three different arrays.

What’d be even cooler would be if the compiler could define one of these objects for us, and base it on usage. So if you weren’t accessing the pMeshComponent part at all, it wouldn’t even fill it in. (Difficult to do if it’s passing this compound-pointer type around, but maybe that’s the worst case that it reduces to. Within a function, it could optimize away the other, unused parts).

Let’s make this a little simpler with some syntactic sugar.

stripe DynamicObject* pStripedPointer;

This is semantically equivalent to StripedDynamicObjectPtr. If you want to access the pos field in the PositionComponent part through the pointer, you’d do:

pStripedPointer::PositionComponent->pos;

Even better, because there can be no name collisions within DynamicObject’s members (even if they’re marked as being in a stripe/group), we can simplify further to this:

pStripedPointer->pos;

A case could be made for keeping both forms, as the former is more explicit (and rams home the fact that we’re accessing a specific stripe), but I like the latter as it keeps the typing down.

Borrowing from C++ again, how do you use a pStripedPointer to do something useful and access data?

std::vector< packed DynamicObject::PositionComponent > s_positions;
std::vector< packed DynamicObject::MeshComponent > s_meshes;

void UpdateLocation( float deltaT )
{
   stripe DynamicObject* pObjects =
   {
      PositionComponent = s_positions.data()
   };

   for( int i = 0; i < s_positions.size(); ++i )
   {
      vector3 position = pObjects[i]->pos;
      vector3 velocity = pObjects[i]->velocity * deltaT;
      pObjects[i]->pos = position + velocity;
   }
}

I sneakily slipped another keyword in there – packed – which binds tightly to the type (or scope) it’s to the left of and forces it to pack the data as tightly as possible. So vector3 instead of being x,y,z and an inaccessible ‘w’ float parameter for padding would be packed together as an array of float[3]’s. The compiler should handle the rest. We might need to make sure that the underlying std::vector is at least a multiple of cache-lines in length, but at least it’s doable.

If we have a list type (more in a future post) that understands stripes/groups, we can make this code simpler still:

stripe list<DynamicObject> s_dynamicObjects;

void UpdateLocationv2( float deltaT )
{
   stripe DynamicObject* pObjects = (stripe DynamicObject*) s_dynamicObjects;

   for( int i = 0; i < s_positions.size(); ++i )
      {
         vector3 position = pObjects[i]->pos;
         vector3 velocity = pObjects[i]->velocity * deltaT;
         pObjects[i]->pos = position + velocity;
   }
}

And moving on from that, maybe even simpler still with a bit of foreach syntax…

stripe list<DynamicObject> s_dynamicObjects;

void UpdateLocationv3( float deltaT )
{

   foreach( auto& i : s_dynamicObjects.stripes() )
   {
         vector3 position = i.pos;
         vector3 velocity = i.velocity * deltaT;
         i.pos = position + velocity;
   }
}

Clearing up some details…

The stripe definition inside the struct operates in code-file order, and coalesces. So you might do this (if you really wanted to):

struct DynamicObject
{
   stripe PositionComponent
   {
      vector3 pos;
   }

   stripe MeshComponent
   {
      Mesh* pMesh;

   }

   stripe PositionComponent
   {

      vector3 velocity;
   }

   stripe MeshComponent
   {
      Material* pMaterial;
   }

   AIBrain* pBrain;
}

… and you’d still end up with the same DynamicObjectPositionData and DynamicObjectMeshData equivalent auxiliary structs. It’d just take everything marked PositionComponent and lay them out in the same order in the auxiliary ones. It gets a bit more finicky when you look at the logical struct, as now you’re messing with padding potentially, but if you really care, you can define them together, in order, in a single group.

But what about initializing the data?

Yep, I know what you’re thinking… you’ve still got to fill the data in for each of the struct-of-arrays that you’re filling in here. Well, I want to make that easy too. So in a future post we’ll go over transformation assignment operators which should make filling them out easier when you have to do this kind of scatter/gather operation. Once we’ve got that part done, we’ll also go over the list and striped list types which should wrap all of this up in a pretty bow.

End of Part 1

So far we’ve gone over structure-of-arrays and have something that’s pretty compelling in terms of reduction of code needed to handle it and maintenance on existing code. Please comment and let me know what you think. Right now it’s going to be a bit tricky because I’ve not explained the transformation assignment stuff, duck-typed contracts, mappings, list/striped list, packed, and a whole lot more, but I promise, we’ll get to them in the future.

Edit 1: Modified the pointer syntax to the auxiliary structs from DynamicObject::PositionComponent* to DynamicObject*::PositionComponent to make it less ambiguous to a compiler.

Edit 2: Fixed the bad syntax for the foreach loop

Edit 3: Clarified behavior of stripe in struct definition.

The previous article in this series is here

About Simon Cooke

Simon Cooke is a video game developer, ex-freelance journalist, screenwriter, film-maker and all-round good egg in Seattle, WA. The views posted on this blog are his and his alone, and have no relation to anything he's working on, his employer, or anything else and are not an official statement of any kind.
facebook comments
blog comments

One Response to C!! — Striped Pointers, Structures-of-Arrays and Arrays-of-Structures in the C bang bang programming language

  1. Pingback: C!!–Contracts, Duck-Typing and the Transformation Assignment Operator | Accidental Scientist