Stupid C# Tricks: Dealing With Non-Generational Garbage Collection

Mostly for Nathan:

Better men than me have already discussed non-generational GC with XNA Xbox, and a few things you can do to deal with it. 

Trying to build upon their work - your best buddy is going to be the CLRProfiler.  Once you figure out how to use it, it's an awesome tool that tells you what's allocating the most garbage, when and where.

Once you've found trouble spots, there's a variety of things you can do.  Using structs instead of classes is often what you want - structs are put on the stack;  and an array of structs is just one object.

If there are moments in your game where pauses make sense, (when the user hits the pause button, for example - or in a turn-based game, the beginning of every turn, maybe?) - that's a good time to force a garbage collection.

Earlier I said we're using fixed pools.  Not anymore.  What we've done is, we've written our own SpecialNew and SpecialDelete functions for some of our problem classes.  Delete doesn't delete;  it just puts the object at the front of a linked list.  Thus, the object never gets collected.  New first checks that linked list to see if an old object is available, clears it out and hands it back, only actually calling the C# new if no object is available.  Voila, no garbage collection, and no fixed-pool restrictions on number of objects allocated.  It seems so simple once you've seen it, I don't know why I didn't think of it;  it was one of our other programmers who showed me the light.

One problem with it (and fixed-pools) is suddenly you lose the advantage of a constructor that is guaranteed to set your object to a known initialized state.  Just like with C++, if you forget to initialize a variable in your SpecialNew...then that object's behavior is undefined.  We get around this with reflection.  We don't actually reflect through every object when it's SpecialNewed to initialize everything...that would probably be too slow - what we do, is in our debug builds, we reflect through the object to make sure it matches a canonical initialized object that was newed the regular way, and fire an assertion if it doesn't.  This has caught a handful of omissions.

One might ask: why use C# to make our game if one of the most useful features of C#, the garbage collection, shouldn't be used on the Xbox?  Well, in C++, if you forget to delete an object when it goes out of scope, you've got a memory leak that will eventually crash your game.  With C# on the Xbox, you do the same thing, you've got a memory "leak" that will eventually cause a garbage collection and make your game drop a frame and maybe have a noticeable hitch.  I'll take the latter.  It allows you to fix on an as-needed basis:  you can play fast-and-loose with the heap for your early product development, and then fix your problem classes as needed.

As for delegates and closures:  I love, love, love delegates and it's the main reason I like working with C#.  If I found out I shouldn't use them on the Xbox I would go into a Black Hole of Despair.  That said, you do have to massage them sometimes.  A closure, obviously, will put an object on the heap every time it's created.  So if you, say, create a closure and pass it to a function for every entity every frame, that's probably going to create too much garbage.  Sigh.  A not-so-obvious case is if you pass a member function to a delegate parameter, that member function gets...wrapped...somehow...(I really need to look deeper into it, there are some websites that discuss it in high detail)...and so it puts garbage on the heap also.  Here you can protect yourself by creating a static delegate variable and assigning the member function to it...that way the wrap only happens once and never gets collected.  Still, I'm happy to play fast-and-loose with delegates and closures and then fix them once I discover the problem cases.

Brief plug - I'll be speaking at the next GameFest about this stuff and more!

Comments

[Nathan McKenzie]

Thanks Jamie - this is tons of really great information.

I've been meaning to take closer looks at C# memory management, but because I've been mostly focusing on the PC, and because my current project doesn't have an incredibly large memory footprint (although it burns up fill rate like there's no tomorrow), I've been kind of leaving it on the back burner.

I have to say - I'm nearing the point where I'd almost advocate writing games that ultimately will be C++ in C# or Java or, well, anything higher level, and then doing a massive (painful) line-by-line translation in the last few months of development... or outsourcing that translation, maybe, or having dedicated optimization engineers who eat that sort of thing up. Maybe my instincts on that are misguided, but I'm finding I'm so vastly much more productive working in C# (and the tools and lack of compile time are so much better) that I have a hard time picturing myself wanting to do any sort of iterative development in C++ again.

Anyway, thanks again.

Do you know if Sony or Nintendo are making any efforts to provide any higher-level language support for their consoles? It seems like this might be an area, much like XBox Live, where Microsoft's extensive and far-reaching background in writing software really helps distinguish them from people mostly focused on hardware.

[Charlie Tangora]

I think the central issue is that there's no language designed from the ground up for game development. C is for systems programming, where speed is more important than everything - including iteration time. C++ is a kludge for people forced to develop applications that have to interface fluently with systems code. Neither one have any benefit for game programmers except that it's easy to optimize C and C++ code.

C#, on the other hand, is an application development language. It's not for people who think of 100 milliseconds as a long time. (Frankly, 14 ms to run GC on 100,000 objects is pretty impressive - especially on a pig like the 360! That's why GC is still a bad idea on consoles.)

Naughty Dog gave it a decent try with their in-house GOAL language - for performance, GOAL had every assembly instruction available as an intrinsic and various cute compiler features like a "this function is not allowed to spill registers" pragma, and for quick iteration it had the ability to dynamically relink code into a running game. Plus it used Lisp syntax, so you could write macros to build your own high-level language features.

On the other hand, GOAL only ever had one programmer working on the compiler and debugger, so lots of programmer time was lost to compiler bugs. And it never had any optimization features beyond register coloring.

[Martin Vilcans]

Thanks for an interesting post! I've never used C# for anything big, but I've worked on a lot of Java projects, and these two languages share a lot of traits. I agree that garbage collection is not the only productivity-increasing feature in these languages. Yes, garbage collection is nice, but once you have worked on a C++ project that used smart pointers from the very beginning, it's not that big a deal.

Nathan: I have thought along the same lines, i.e. to code in a higher language first and then port to C++. It's not very flattering for C++ to think that we'd save time by developing that way. :-)

Charlie: I agree with your point, but I don't think there's a need for a language that is targeted just at games programming. What we need is a language that is higher level than C++, but not quite as high level as C# or Java. So what we're looking for is a language that allows you to handle memory manually, make low-level optimizations etc. and still provide decent abstractions for higher level programming. One such language that seems to fill this middle ground perfectly is D, but that is new and unproved. Perhaps old statically compiled languages such as Ada might fit well, but it's not very mainstream obviously.

The most realistic approach to this problem right now is to combine a very high level language that gives good abstraction with a low level language that gives speed in low-level code. I'd probably chose Python and C++ for this.

[Andy Larder]

'Frankly, 14 ms to run GC on 100,000 objects is pretty impressive - especially on a pig like the 360! That's why GC is still a bad idea on consoles.'

But the real issue with XNA on the 360 is the lack of generational GC.

I have had games code running in the desktop Java VM with 100,000's of live objects, with collections taking place every so often of no longer than 0.1 mS. So long as objects are either extremely short lived, or permanent, there should never be any longer collections. I can live with 0.6% of my frame time going to the GC!

The XNA team have made a great start getting the .NET CLR onto the 360 in the first place, but I really hope they have plans to change the GC to something either generational or incremental.

[Nathan McKenzie]

Martin:

It seems like the longer C# is around, the more it diverges from Java (in, I would say, often good ways). In particular, where as the spec in Java seems largely frozen (much the same way that C++ mostly has been for several years now), C# has been more aggressive about incorporating ideas from languages such as Ruby, Python, Javascript, and so on. I'm not sure what impact that'll ultimately have on the complexity of the language, but so far it's making a lot of my code progressively smaller, cleaner, and co-located, which I like.

I know it's a trivial thing, but as I think Python has proven, syntax matters, particularly for readability. I can't count the number of times I've seen critiques of both C++ and Java where the response has been, "Oh, that's just syntactical sugar. All you have to do to do that is " and then a giant unreadable blob of boilerplate code that involves either verbose template programming or verbose anonymous inner classes that obscures what the code is actually DOING. It reminds me of C programmers who point out that you can get much of the functionality of classes by manually writing your own virtual function tables in structures, coupled with aggressive uses of macros. Ugh.

In many ways it's unfortunate that languages have to advance as clumps of features (which seems to reek of the inheritance versus composition problems in class design, if you'll allow the metaphor). By tying syntax improvements to specific memory management schemes, newer languages provide too many features that a person might have to balk on, even though they'd like all the other improvements the new language provides. That seems like a shame (though it's understandable).

My main concern with C# if, of course, that it's controlled by Microsoft completely... but that's also likely what's allowing it to evolve so quickly. I guess it's tough to say.

Oh - and I have to say, if I never see another custom game scripting language again, it'll be too soon. At this point, I think I've learned about seven different custom game scripting languages. None of them were supported by even one full time programmer. None of them had any meaningful documentation or tool support. None of them had access to good libraries. Occasionally they tried some interesting, game specific things (QuakeC gave free serialization, Unrealscript has special language-level constructs to support client-side prediction of real-time stuff across the client-server boundary), but in general, using them was not a win.

[Martin Vilcans]

Nathan: "In many ways it's unfortunate that languages have to advance as clumps of features (which seems to reek of the inheritance versus composition problems in class design, if you'll allow the metaphor). By tying syntax improvements to specific memory management schemes, newer languages provide too many features that a person might have to balk on, even though they'd like all the other improvements the new language provides."

I'm not sure what you mean with this. Are you referring to the fact that if you want a language with new useful features, you have to use a language with garbage collection? I guess there's a reason for that. For example, to implement useful closures, you'll need garbage collection. So, like it or not, any language with powerful features is likely to have garbage collection. I also have the strong impression that it's less work to implement powerful new features in dynamic languages. There are features in Ruby that would be close to impossible to implement in C# or Java and definitely impossible in C++. The power comes at a price though, which is performance. Ruby is orders of magnitude slower than C++.

[Nathan McKenzie]

Martin:

Yeah, of course Garbage Collection is, in fact, needed for a host of other language changes. I think I was playing a little fast and loose with what I was saying.

What I meant was, for example, if you want C#'s anonymous methods, or if you want C#'s namespacing, then you're going to have to accept C#'s lack of macros. If you want Java's memory management, then you're going to have to accept Java's lack of overloading the addition symbol for strings. And the reason I would consider that unfortunate is that it seems like game development slips through the cracks because of this - we want many of the language improvements from more recent languages, and many of the improvements are just straightforward improvements with no specific trade-offs, but because languages are general all-or-nothing affairs (aside from outlawing techniques internally at a company), one glaring language choice can make all the other improvements off limits (since you can't use the language in question). That's kind of what I was getting at - that, in a sense, many of the language features are by no means tightly coupled, but because compilers work on specific languages, one red flag can jettison all other improvements. Obviously memory-management techniques ARE tightly coupled to certain things, such as closures - but even there, it's certainly not connected to, for example, policies about operator overloading, or the existence of macros or template programming.

That's all I'm saying. Maybe it's an analogue to the infinite debates on the MMO message boards about class based vs skill based game rule systems - we're always having to pick between the fighter and the magic user of programming languages, but we can't easily make a customized magetankhealer.