07-23-12 - Structs are not what you want

I was looking at some stupid struct in my code which was something like
struct Stuff
    U16     m_val1;
    U32     m_val2;
    U16     m_val3;
because of the order of variables and the standard packing, it wound up taking 12 bytes instead of 8. In this particular case, the types were actually templates or #defined types so I don't know statically that the ordering is fucked up and causing that problem.

It occured to me that the whole C "struct" thing is really not what we want most of the time. 99% of the time I want to say "put all these values in this thing, and I don't care what order". In particular, Mr. Compiler, you can optimize the order to minimize size, or for speed, or whatever.

Now that's not a big deal with just a simple struct, but more generally it's massive.

What if I could say "bag" is some values with certain types and names. Then when I combine bags, you don't duplicate things that are in both. And you can reinterpret bags to other bags as long as they have the needed values.

bag Particle
    Vec3    m_pos;
    ColorDW m_color;

bag GameObject
    Vec3    m_pos;
    String  m_name;

bag GameObject_AndColor : GameObject
    ColorDW m_color;

now a GameObject_AndColor can be passed to any function that wants a Particle because it provides all the needed fields.
alternatively :

bag GameObjectParticle : GameObject, Particle

only has one m_pos.

Obviously this doesn't work with C functions which are compiled once and get to know the offset to the data in that one compile. You want a compiler that can compile all the logic but leave the variable references unspecified until it is bound to a concrete type.

Now obviously templates sort of address this, but in a much uglier way.

Templates are worse in 2 ways. 1. they don't do any shared compilation, they leave all compilation to the last minute when they know the concrete type they get to work on; conversely bags can do 99% of the compilation up front and just need to specialize the variable addressing per usage. 2. they don't do any static type checking; that is, when you write the template you can't specify in any kind of clean way "you can use this template on anything that provides m_pos and m_color" (C++ concepts were supposed to sort of address this) ; bags provide this very nicely and let you write a template and error-check it before you even apply it to anything.

Obviously templates are more powerful, but not useable in reality because of these problems; they delay compilation too much for widespread use, it makes compilation too slow, and puts the errors in the wrong place (at the use site, not the template itself). Compilation up front is great (I think weakly typed languages are ridiculous disasters).

But in theory bags can do even more. One annoying problem we have at RAD is that factored out functions can be massively slower than macros. There are various reasons for this, but one is that if you have some variables in registers and want to call a function on them, the compiler will almost always do a ton of work to move those variables around that it doesn't need to do (either writing them back to memory or pushing them on the stack, or just moving them to other registers).

With bags in theory you could do something like :

Vec3 pos1;
int i;
ColorDW c;

... some code that sets up pos1 and c ...

bag Particle p = { pos &= pos1, color &= c } ;  

// this is not a copy
// it says that the variables I already have can be treated as a Particle bag


// Particle_Move generates code that acts directly on my local variables "pos1" and "c" , no copying

The win is that Particle_Move basically acts like a macro, but I get the type-safety and separate compilation error check benefits of an inline function.

Similarly, I shouldn't have to write new code every time I have a bunch of data that I want to use as SOA (structure of arrays) instead of AOS (array of structures). eg. if I have

Vec3 positions[100];
ColorDW colors[100];

I should be able to use Particle_ functions on those, because they provide the values needed to make a valid bag.

Being a bit redundant : the classic way that simple C inheritance fails happens a lot with vertex types in graphics. It goes something like this :

struct Vertex_Pos { Vec3 pos; }

// functs that only need a "pos" member act on a Vertex_Pos

struct Vertex_PosNormal : Vertex_Pos { Vec3 normal; }

// functs that need a pos and normal act on Vertex_PosNormal

struct Vertex_PosColor : Vertex_Pos { Color color; }

// functs that need a pos and color act on Vertex_PosColor

struct Vertex_PosNormalColor : ??

// oh crap, which do I do ?

struct Vertex_PosNormalColor : Vertex_PosNormal { Color color; }
struct Vertex_PosNormalColor : Vertex_PosColor { Vec3 normal; }

// either way is busted
// with bags I should be able to just do :

bag Vertex_PosNormalColor { Vec3 pos; Vec3 normal; Color color; }

// (or either of the above inheritance ways)

and then the bag Vertex_PosNormalColor can be used as a Vertex_PosNormal or Vertex_PosColor without even explicitly specifying any inheritance. (an ideal compiler would also let you specify that as a compile-time constraint on the type).

Now obviously inheritance and virtual functions solve a slightly different problem than bags. They let you act on part of a type without knowing the concrete type. Bags have to be used on the concrete type, just like templates. I guess the fundamental problem with structs (and why they're wrong for some uses) is that they are actually solving this slightly different problem.



rogojin said...

I like this idea. Feels inspired by Go's interfaces, except this is compile-time and data-oriented (as opposed to function-oriented).

Brian said...

I guess one tricky thing here is that this would play hell with some compiler optimizations. You couldn't optimize the address computations easily. A bigger problem is that reasoning about aliasing relationships would be all messed up.
But it does sound like a nice programming construct. Probably worth paying the performance penalty.

Anonymous said...

It's a little like ML-style function polymorphism, but different.

Back when I was working on designing a new programming language (which I stopped doing once I figured out how to do C better using stb.h), I had intended to do the duck typing version of this; you could define a function that operated on "x.foo" and "x.bar" even if x could be multiple unrelated types.

Actually, because of the potential performance overhead I had been considering using a different operator from "." to distinguish regular "." (must compile to fast code) and can-be-late-bound "." (which can be slow). It was also possible it could have done template-style instantiation to avoid late-binding.

It also by default would reorder structures for packing, but you could override and force a specific structure layout if needed.

Per Vognsen said...

Prepare to be sick to your stomach. http://www.flipcode.com/archives/Flexible_Vertex_Format_Generator.shtml

Per Vognsen said...
This comment has been removed by the author.
G_glop said...

This feels like an entity component system but more granular, without entities that all live in the same namespace and components disambiguated using types.

One place I'd love to use an extended version of this is temporairly adding auxillary data to all items in a container, instead of manually maintaining multiple parallel containers or making the auxillary data a permanent member of the struct.

old rants