Unity3D Entity Systems: Zero-copy data storage revisited

Recap: previous posts on Unity3D and designing an efficient Entity Systems add-on library, using structs to store data in C#.

But …

C# doesn’t allow you to efficiently use structs nor objects

C# objects are a little inefficient in memory usage and iteration speed (when you compare to raw underlying data). That’s fine for many people, especially corporate programmers who never encounter performance issues. But it’s not fine for us.

But it’s cool; C# has structs that offer almost exactly the same behaviour as C structs: highly efficient memory and iteration.

But … but there are only four ways you can write code that uses (reads from, writes to) C# structs, and they all suck donkey.

C# sucks 1: Forget OOP, forget methods/procedures/functions

Pretend you got in a time machine and are living in 1965, before programmers started using “procedures”; write your app as ONE HUGE FILE WITH ONLY ONE METHOD. WHY AM I SHOUTING? WELL BACK THEN THEY DIDN’T HAVE LOWER CASE LETTERS ON THEIR KEYBOARDS EITHER, AND I’M BEING AUTHENTIC.

C# sucks 2: go ‘unsafe’

C# does not allow you to return a pointer-to-a-struct. This fundamentally undermines the concept of a struct. It’s particularly bad considering C# has an unhealthy obsession with copying things around in memory all the time, especially when it has no need to and is (literally) wasting CPU cycles at a very low level (significant impact on performance in large data applications – e.g. games).

But … well, I told a lie. C# does allow precisely that: except people at Microsoft decided normal people can’t cope with pointers as a concept (a lot of truth in that) and/or that making pointers “safe” would reduce the performance of them in extreme situations (a lot of truth there, too), and so … anything in C# that even thinks about a pointer won’t compile unless you convert your entire app into a “C# unsafe codebase”.

I normally am more than happy with C#’s ‘unsafe’ concept; it’s a nice idea. e.g. it’s a great way for me to see at a glance whether my team mates have gone and put some potentially ruinous code in our codebase and hence I have to be as cautious as a C programmer. I’m only unhappy at the moment because C# has less than universal support for executing unsafe-compiled code at runtime.

Unity can’t/won’t build in “unsafe”-mode: the Webplayer is incapable of running code compiled in this mode, so Unity (rightly so) disables it globally. You can re-enable it, but your game will crash on start on some platforms.

Other languages (*ahem*Java*ahem*) allow for both “competely unsafe” pointers and “protected against damaging Java, but up to you to protect your own code from itself” pointers in parallel. It would be nice if C# did too. There’s a lot of places where C# takes this “Well! if THAT’S what you want, you can HAVE IT! THERE! DO YOU LIKE THAT?? DO YOU!??” all-or-nothing binary option for the programmer. It would be nice if it recognized that real-world programming is a much more nuanced process.

C# sucks 3: destroy OOP: pass internal data structures back to callers

One of the tenets of OOP, one of its greatest benefits, is data-hiding: classes can (and nearly always do) take any internal state and mechanics that are NOT part of their contract with the outside world, and prevent the outside world from seeing them. Code is easier to write (classes have fewer things for you to read and think about when trying to use them), and maintenance and debugging is MUCH easier (there’s less to worry about; many little silos that can be independently tested and debugged).

Well, a workaround to C#’s little problem with structs is this:

1. When you want to read “struct for entity #1234”, you call “.GetStruct( 1234 )”
2. The callee does NOT return you that struct (C# won’t let it do this via pointer, unless you go unsafe)
3. Instead, it returns you the ENTIRE ARRAY that the struct lives in
4. …and the integer index into that array where your struct lives
5. …because C# DOES ALLOW you to return pointers-to-arrays that contain structs (just not directly to structs themselves. Ironic, that)
6. Caller now has to be intelligent enough to:
   1. Combine array + index to find what it wanted in the first place
   2. VERY EXPLICITLY IGNORE everything else in that array; one slip of the index, and all hell will break loose

Congratulations! You just hard-coded every piece of game-logic in your app to the specific set of arrays that you use to store the back-end data.

What’s that, Little Johnny? … You came up with a new data structure that’s 10x as efficient, and want to replace it? … Uh … forget it. You’d have to rewrite 90% of your codebase.

C# sucks 4: There’s a delegate, that delegates delegation. Delegatedly

All the above suck. There’s one more way out, one that doesn’t involve dropping good OOP principles (not exclusive to OOP – so good that they’re used all over the place, pre-date OOP by a decade or more). But … it’s tortuous. It’s so complex to use you’ll want to shoot yourself rather than write any more game code. Which removes one of the main benefits of Entity Systems in the first place (you get to keep “performance” but you lose “easy writing of new code / changing old code”).

C# won’t let you “return” a pointer to a struct – but it will let you “pass” a pointer to a struct as a parameter to a method. WTF? What the ACTUAL ****? Yep! No messing; it really does do this.

So…

1. Callee defines a C# delegate (google them if you haven’t used them; it’s a fancy/clean way of allowing pointer-to-function)
2. Caller says “Get( Component blah, EntityID blahblah, delegate DoThisToTheThingI’mGetting() )”
3. Callee gets the component, as expected, and then manually runs “DoThisToTheThing…()” on the object
4. Callee hopes nothing goes wrong, because it’s going to be a PITA to inform Caller of that fact in a sensible and efficient manner
5. Caller gets messy
6. Debugging makes you weep
7. Junior Programmers on your team look at what you’ve done and cry
   • WHY? WHY ARE YOU DOING THIS TO ME? I WAS AN INNOCENT!

Plz Fix C# nowz, KTHNXBYE

There’s a simple solution, and it’s proposed for the next official version of C#:

Make C# allow you to “return ref (struct)”

There’s plenty of people who hate the idea on principle (the principle being, apparently “I have no idea what this is for, but I don’t like structs, they’re something to do with C? I think? And I never use them – so you shouldn’t either!”. Yeah. Me, bitter? Noooooo…), so support for this going in isn’t universal.

I don’t blame those people: they’re happy living in their professional environment where they never have to marry high-performance code with mass-market deployment. But that doesn’t mean we should accept their stance. I encourage you to reach out to them and help them see the value of this minor tweak to the language, and do what you can to get it approved and added.

NB: I say “minor tweak” quite carefully; Eric Lippert (formerly of the C# language design team, IIRC?) has publically stated that the feature already exists in the runtime, but C# compiler is not allowed to use it, and that he’s personally tested and proved that it works fine to enable this in C# – the runtime works without needing changes. Technically (I’m no expert here, but it seems legit) it appears to be legal to go and hack your C# compiler to support the feature, compile some code, and then use it at runtime alongside “ordinary” C# code.

So, yeah – we should support this.

Also, future teachers will thank us for making the language just that little bit more consistent with itself (you can ref into a method, you should be able to ref out).

Moving on: let’s start copying memory!

Now that I’ve ranted and obsessed and spent more time than anyone should worrying about avoiding copying memory … I’m going to advocate copying memory!

Muahahahaha!

There’s an enormous difference though between what C# imposed and what we actually want to do deliberately: we’re only interested in batch copying. i.e.:

1. Copies are created infrequently (at most: once per frame. Ideally: only a few times per second)
2. We copy large blocks at once, not individual items
3. There are genuine benefits to having a copy rather than the original (i.e. this will NOT be appropriate for all algorithms; but it is for most that we care about)

A unity example: The Unity Editor OnGUI Refresh is 100 times per second

That’s a long subtitle; many many MANY Unity developers are blithely unaware of this fact. It’s right there in the Unity docs! (it didn’t used to be, but is now, so you no longer have any excuse). Unity’s Editor refreshes the screen at 100 FPS. Thats a heck of a lot of pointless wasted work if nothing’s changing – and even if it is, there’s very very little in an Editor GUI that needs updating so fast.

(There’s very little that needs updating more than once per second; even the smoothest of editor features will usually be fine at 10-30 FPS)

Editor GUI is often doing much harder work than the final game – it has to work with not-yet-optimized code and dynamically changing data that will be fixed, static, and made much more efficient by compiler/build process before it goes into the game. So … we’d really like to keep it nippy.

What we don’t want to do is this:

• 100 times / second:
  1. Fetch all entities
  2. Fetch their “name” component
  3. Construct strings for all of them to display
  4. Redraw window segments and background colours for each item

Now, all Unity devs should (these days) be well-educated in being conservative about OnGUI implementations – don’t recreate stuff that isn’t changing frame to frame (e.g. background texture references). But how do you avoid re-doing it when the set of data you’re rendering could change at any moment?

Enter … the COPIED list of entities (not pointer-to-…).

What would you actually want?

Something like this:

1. OnGUI:
   1. For each: cached entity-name / entity ID pair:
      1. Draw the name + entity ID to screen
      2. Allow mouse to click on any row
      3. Clicked row triggers an Editor event “Entity with ID = BLAH was selected”
   2. Refresh():
      1. Whenver called, this re-populates the cache of “entity name + entity ID”
   3. Only two arrays are stored at class level:
      1. int[] entityIDs
      2. EntityName[] entityNames

…although clicking a specific row will trigger the Entity Inspector window to load up the complete data on that entity, the main GUI doesn’t need that info.

i.e. the amount of data being duplicated in RAM is going to be tiny, even on a huge game with a vast number of entities.

If we get to – say – 100,000 live entities then the RAM numbers will no longer be “tiny”. For most platforms, they’ll still be small enough that we probably don’t care in this particular case – but more likely at that point we’d be using filters to reduce the number accessed at once.

e.g. in the GUI we’d only display “1000 most-recently changed” or “1000 entities at a time” – no GUI will meangingfully display 100,000 rows on screen at once anyway.

Copying in C#

This, at least, is easy. C# today (2015) is extremely efficient at direct array-to-array copy (as you’d hope!).

So fast that even if you try to get “clever” and go re-implement array-copying in “unsafe” mode, using raw pointers … you won’t make it much/any faster. You might even slow it down.

Allocation, Shmallocation

Naively, we’d do each copy by allocating a new array of appropiate size and copying into it.

“But allocations are slow!”

Yeah, yeah – not when you’re doing 1 of them per frame they’re not. They’re only slow when you’re re-allocating once for every entity in the game. We’re allocating once, in total. So we don’t care.

But potentially you might care, in which case you’d want to make the “copied array” store into an array of memory shared between the caller (game logic) and the callee (the entity/component store). That’s fine. Standard practice: optionally the caller passes-in a pre-allocated array, and takes responsibility for ensuring it’s “big enough” for the data that will go into it (and for not trying to read/write to it on another thread until after the callee has finished copying into it!).

Any colour you want, so long as it’s black

When do you want the copy, and when do you want the zero-allocation original?

Who gets to decide?

In the long-run, I want it to be non-optional: everyone gets a copy. But that will require some re-architecting of my thinking on standard algorithms I’m used to using (and re-thinking some libraries I already re-use). So, in the short term, I’m going for “caller gets to decide”.

[csharp]
public enum EntityListType
{
REFERENCE, CLONE
}

/** Returns a C# structure you can "foreach()" over.
Defaults to a zero-copy reference, but optionally will
clone it for you.

The foreach() structure can be re-iterated over multiple
times (as expected by C# spec). The cloned one can be
iterated as many times as you want – it’s your private
copy. The (default) referenced one you do need to be
careful about multi-threading, since other callers
may be reading/writing to the same areas of memory.
*/
public ArrayEnumerable<T> all<T>( EntityListType listType = EntityListType.REFERENCE );
[/csharp]

TL;DR

C# needs “return ref” added to the language; .NET already supports it explicitly; rant rant structs pointers unsafe-mode rant; sometimes, copying is a good idea.

Support me on Patreon, writing about Entity Systems and sharing tech demos and code examples