Taming the CLR: How to Write Real-Time Managed Code

re: Taming the CLR: How to Write Real-Time Managed Code

Joel Martinez — Wed, 23 Aug 2006 05:16:16 GMT

Awesome article! thanks for posting it :-)

At some point, I'd love to hear some further thoughts on when to use pointers (reference types?), and how you might improve something by using Handles.

CrazyPromoter.com » Blog Archive » Taming the CLR: How to Write Real-Time Managed Code

Wed, 23 Aug 2006 06:26:12 GMT

PingBack from http://crazypromoter.com/?p=565

re: Taming the CLR: How to Write Real-Time Managed Code

Chris Nahr — Wed, 23 Aug 2006 10:26:08 GMT

That was a fascinating article. One question: what about the effects of automatic GCs on frame rate and responsiveness on the 360? Would you recommend calling the GC manually in this environment, to ensure that the display won't stutter and user input won't be delayed? Or does the 360 version of the .NET Framework automatically avoid these issues somehow?

re: Taming the CLR: How to Write Real-Time Managed Code

Chris Nahr — Wed, 23 Aug 2006 10:45:41 GMT

Whoops, another question. The Compact Framework with the GC characteristics you describe is the one being used on the Xbox 360, right? I'm assuming this is the case but your article doesn't actually mention it.

re: Taming the CLR: How to Write Real-Time Managed Code

Ben Hollis — Wed, 23 Aug 2006 11:15:27 GMT

Could you toss out a link or two on handles vs pointers? I'm not sure exactly what you mean in the .NET world. I kinda always thought everything was "references" which were basically pointers.

re: Taming the CLR: How to Write Real-Time Managed Code

Matt — Wed, 23 Aug 2006 13:39:06 GMT

Ben:
Handles is likely being used in here in the generic (small G) sense of the word.

I.E. a number, which when passed to the relevant manager gives you back the thing you are interested in.
E.g. imagine you know there will only ever be X entities in your world and most of the time they will all exist.
You might create a structure like a tree for dpeth ordering.
You could either have a pointer based tree or an array based one.
Obviously the array based tree is better from a GC point of view (less pointers, more locality potential when traversing).

However if you use the array structure but, within your tree nodes you keep a reference to each entity object then you have additional GC cost. The GC must traverse each node to follow all these references.

If intsead your tree nodes contain some integer based lookup to your entities then the nodes contain only integral values, thus the entire tree can be throught of by the GC as nothing but a block of used memory.

If you have lot's of data structures holding information about the arrangement of entities this gain can apply to all of them.

Obviously this has a cost in access time (you must do the lookup by hand which will involve a few additional operations *).
But the GC cost is much lower for this block of memory.

Balancing this cost is where the skill of the coder comes in.

* The handle should be made a well defined struct so as to hide the index mechanism in case you need to change it, but in effect it is likely to be an index into your array of all entities)

re: Taming the CLR: How to Write Real-Time Managed Code

JoelMartinez — Wed, 23 Aug 2006 18:15:33 GMT

Thanks for the clarification Matt ... I wonder if I might be able to get some feedback as to wether this is along the lines of what you're talking about:
http://pastebin.ca/146362

re: Taming the CLR: How to Write Real-Time Managed Code

Frank Hileman — Wed, 23 Aug 2006 18:40:23 GMT

Joel, I think Rico was referring to integers instead of pointers. If your handle is an object containing an integer (as in the example), that defeats the purpose. Here are a couple examples using integers instead of pointers.

/// <summary>
/// Creates a binary tree from a linked list of pooled free nodes, using array
/// indices as node references. Nodes can be removed, but the method was not written.
/// </summary>
class Tree5
{
private const int startSize = 16;
private static Node[] pool = CreateNodes();
private static int nextFree = 0;
private static int root = -1;
private static int count;

private static Node[] CreateNodes()
{
Node[] nodes = new Node[startSize];
InitializeNodes(nodes, 0);
return nodes;
}

private static void InitializeNodes(Node[] nodes, int start)
{
// initialize all but last
InitializeNodes(nodes, start, nodes.Length - 1);
nodes[nodes.Length - 1] = new Node(-1, -1, -1); // marks end of pool
}

private static void InitializeNodes(Node[] nodes, int start, int count)
{
// right node is next free; -1 marks empty reference
for (int i = start; i < count; ++i)
nodes[i] = new Node(-1, -1, i + 1);
}

static public void Insert(int key)
{
if (root == -1)
{
root = NewNode(key);
return;
}
int t = root;
for (;;)
{
Node n = pool[t];
if (n.Key == key)
return;

if (key < n.Key)
{
if (n.Left == -1)
{
pool[t].Left = NewNode(key);
return;
}
t = n.Left;
}
else
{
if (n.Right == -1)
{
pool[t].Right = NewNode(key);
return;
}
t = n.Right;
}
}
}

private static int NewNode(int key)
{
if (nextFree == -1)
IncreaseCapacity();
int t = nextFree;
nextFree = pool[t].Right;
pool[t] = new Node(key, -1, -1);
count++;
return t;
}

private static void IncreaseCapacity()
{
int size = pool.Length;
Node[] nodes = new Node[size * 2];
Array.Copy(pool, nodes, size);
InitializeNodes(nodes, size);
pool = nodes;
nextFree = size;
}

public static void Reset()
{
InitializeNodes(pool, 0, count);
count = 0;
nextFree = 0;
root = -1;
}

private struct Node
{
public int Key;
public int Left;
public int Right;

public Node(int key, int left, int right)
{
Key = key;
Left = left;
Right = right;
}
}
}

/// <summary>
/// Creates a binary tree from an array of pooled free nodes, using array
/// indices as node references. Nodes cannot be removed; the tree can only be reset
/// as a unit. Capacity can be initially set.
/// </summary>
class Tree6
{
private const int startSize = 16;
private static Node[] pool = new Node[startSize];
private static int count = 0;

// NOTE: in this tree, 0 signals a null node reference
public static void SetCapacity(int capacity)
{
pool = new Node[capacity];
count = 0;
}

static public void Insert(int key)
{
if (count == 0)
{
NewNode(key);
return;
}
int t = 0; // root node always 0
for (;;)
{
Node n = pool[t];
if (n.Key == key)
return;

if (key < n.Key)
{
if (n.Left == 0)
{
pool[t].Left = NewNode(key);
return;
}
t = n.Left;
}
else
{
if (n.Right == 0)
{
pool[t].Right = NewNode(key);
return;
}
t = n.Right;
}
}
}

private static int NewNode(int key)
{
if (count == pool.Length)
IncreaseCapacity();
int t = count++;
pool[t] = new Node(key);
return t;
}

private static void IncreaseCapacity()
{
int size = pool.Length;
Node[] nodes = new Node[size * 2];
Array.Copy(pool, nodes, size);
pool = nodes;
}

public static void Reset()
{
count = 0;
}

private struct Node
{
public int Key;
public int Left;
public int Right;

public Node(int key)
{
Key = key;
Left = 0;
Right = 0;
}
}
}

re: Taming the CLR: How to Write Real-Time Managed Code

JoelMartinez — Wed, 23 Aug 2006 18:48:33 GMT

But what of Matt's comment:

"The handle should be made a well defined struct so as to hide the index mechanism in case you need to change it, but in effect it is likely to be an index into your array of all entities)"

Wouldn't a structure of value types be able to partake in the benefits just as if it was a simple integer (as long as it doesn't have any references of course)?

In my example, the handle struct did have a property which returned the referenced Sprite, but it wasn't an actual reference, it simply delegated the call to the SpriteManager.

I have to admit I'm having somewhat of a tough time understanding the why, where, and how to apply this ... would love for others to chime in and add to the discussion :-)

re: Taming the CLR: How to Write Real-Time Managed Code

Frank Hileman — Wed, 23 Aug 2006 19:41:03 GMT

You are correct, sorry I did not notice it was a struct and not a class. Matt is correct, if you are to expose the handle to the public it should be wrapped in a struct.

I find integer index pointer replacement most useful for internal data structures (such as the posted tree classes) where the end user has the same experience, regardless of the internal choice of a pointer or integer to reference something.

For public API's, handles are cumbersome. Nearly always you can find an alternative API that does not need to expose them.

re: Taming the CLR: How to Write Real-Time Managed Code

JoelMartinez — Wed, 23 Aug 2006 20:26:48 GMT

So would you say that the effort to implement something like this is only worth it if said data structures are relatively short lived?

I mean, what if you have a List<> of objects that are long lived ... would it be worthwhile to do this. Or does the fact that the list is referenced/traversed somewhat often make the shorter GC time not worth it?

I suppose thats what Matt was talking about when he said, "Balancing this cost is where the skill of the coder comes in. " :-)

re: Taming the CLR: How to Write Real-Time Managed Code

ricom — Wed, 23 Aug 2006 21:36:44 GMT

Frank and Joel seem to have the right idea when it comes to what I meant about handles. I wouldn't jump there too quickly though -- in a game context it can be excellent if you have some fairly static structures that you set up for say a game level and then just park for a considerable amount of time. Making those cheap to collect is a good deal. Other contexts might also benefit for similar reasons but if you intend to mutate the data very much you've basically replaced managed pointers with self-managed pointers disguised as integers. Not sure that's really wise.

Some hybrid is likely the best choice.

Now on the desktop CLR this is much less interesting because you can just let your objects age into gen2 and they won't need to be walked very much anyway.

On .NET CF you might be more excited about this because everything has to be traced every collect.

Again... do this wisely with data to back you up, not because big-mouth Rico said it might be interesting :)

Wrapping the handles in a struct would be ideal but make sure you aren't killing your code-gen by doing so. If you lost some important inlining you might just have to bite the bullet and do it the hard way.

If .NET CF is in the picture you're talking about a great deal of portability (awesome) but also several JITs to check out (ouch). Simpler might be better.

Lastly, remember I'm not a .NET CF expert, I only proxy for one at game conferences :)

re: Taming the CLR: How to Write Real-Time Managed Code

Andrew — Wed, 23 Aug 2006 23:21:49 GMT

Great summary of how the GC works! I have a few comments though.

Rico wrote:
"People learned best practices for classic memory allocators ... you have to wrap them. And that’s exactly what everyone does."

If you are wrapping a classic memory manager then it's trivial to keep track of which line of code made a particular allocation, which is usually all you need to fix a leak. A wrapper also allows you to keep statistics which can detect leaks automatically in debug builds.

There are also techniques, such as buddy memory allocation, that eliminate external fragmentation without the need for compaction.

Rico wrote:
"Garbage Collected memory model is the centerpiece. Amortized cost of allocations in this model can be excellent!"

What makes realtime software so fun is that it absolutely has to meet it's realtime deadlines 100% of the time. Worst case, not amortized, is the cost of interest.

I've been writing realtime software for 10 years now and I'd rather fix 100 memory leaks than a single missed realtime deadline problem caused by a non-deterministic thread like a GC!

re: Taming the CLR: How to Write Real-Time Managed Code

ricom — Thu, 24 Aug 2006 00:54:56 GMT

All good thoughts from Andrew above.

Controlling heap size and allocation volume are great ways to control maximum collection costs.

A theme of the advice is that collections are induced by allocations, so controlling allocations lets you control frequency and cost of collections while keeping a simpler model.

It isn't falling off a log but it can (and does) work with some care.

Life is never easy in the real(time) world.

Interesting Finds: August 23, 2006

Jason Haley — Thu, 24 Aug 2006 05:38:57 GMT

re: Taming the CLR: How to Write Real-Time Managed Code

Matt — Thu, 24 Aug 2006 15:58:19 GMT

Rico,

Another useful article - thanks for the tips.

We have a large desktop application under development here that's exhibiting an ever-growing Gen 2 heap (occasional GCs of small portions of the heap are occurring, but the trend is otherwise inexorably skywards).

Some people here are arguing that this is not a problem, as the CLR would collect more of the heap if it needed it. The machines running the app are typically very high-spec, with 2GB RAM.

What say you?

Tame the CLR: Expect game-quality real-time performance from managed code

Robert Burke's Weblog — Thu, 24 Aug 2006 19:26:27 GMT

Game development is one of those dark arts where the usual laws of scalability don't always apply.&nbsp;...

re: Taming the CLR: How to Write Real-Time Managed Code

ricom — Thu, 24 Aug 2006 21:19:38 GMT

>>We have a large desktop application under development here that's exhibiting an ever-growing Gen 2 heap (occasional GCs of small portions of the heap are occurring, but the trend is otherwise inexorably skywards).

The long and the short of it is that the GC will tend to collect when it seems worthwhile to do so. So if your death rate in generation 2 is fairly low the CLR will just let it sit because on a percentage basis the amount of waste seems low. Generally we're pretty good about getting this right.

So when are we likely to get this wrong you ask? Look at http://blogs.msdn.com/ricom/archive/2004/11/29/271829.aspx for information on that.

Many applications tend to accumulate state. If that's a normal thing for your algorithms, then it's not a problem. If that's not normal then maybe you are holding on to objects you could release (leaks) or maybe you have episodic deaths (see link above).

A common source of leaks is where some data structures get linked to durable objects like event sources and are not unlinked when they die. The event source lives forever and therefore so do the things that registered to receive the events.

re: Taming the CLR: How to Write Real-Time Managed Code

lb — Fri, 25 Aug 2006 03:13:41 GMT

you're like one of those crazy people you see on the bus who are muttering crazy things to themselves. But in a really good and positive way ;-)

i like it.

re: Taming the CLR: How to Write Real-Time Managed Code

ricom — Fri, 25 Aug 2006 03:49:44 GMT

Err. Thanks. I think :)

Tame that CLR!

Michael Klucher's XNA Blog — Fri, 25 Aug 2006 06:40:16 GMT

It almost seems like it was planned, but at Gamefest Rico Mariani did a talk titled "Taming the CLR:...

Rico Tames the CLR

Scott Holden's Blog — Fri, 25 Aug 2006 10:21:02 GMT

Rico posted an article&nbsp;Taming The CLR: How to Write Real-Time Managed Code&nbsp;with the contents...

Rico: Taming the CLR « Tales from a Trading Desk

Rico: Taming the CLR « Tales from a Trading Desk — Fri, 25 Aug 2006 23:17:14 GMT

PingBack from http://mdavey.wordpress.com/2006/08/25/rico-taming-the-clr/

Rico's Talk from Gamefest

XNA Diaries — Sat, 26 Aug 2006 20:51:19 GMT

While the slides and recordings from Gamefest are not yet available on the&nbsp;conference website, Rico...

Watch these mid-life objects! real-time managed code

Ido Samuelson's blog — Sun, 27 Aug 2006 12:22:31 GMT

This article&nbsp;has some great info regarding real-time and manage code.
&nbsp;

TrackBack — Mon, 28 Aug 2006 19:08:27 GMT

PingBack from http://blog.3deurope.com/index.php/2006/08/28/managed-code-for-games/

Community Convergence

Charlie Calvert's Community Blog — Tue, 05 Sep 2006 03:46:54 GMT

The C# team is happy to welcome you to the new look of the C# Developer Center. This is the home page...

Community Convergence

Charlie Calvert's Community Blog — Tue, 05 Sep 2006 04:01:52 GMT

The C# team is happy to welcome you to the new look of the C# Developer Center. This is the home page...

Community Convergence

Charlie Calvert's Community Blog — Tue, 05 Sep 2006 04:06:19 GMT

The C# team is happy to welcome you to the new look of the C# Developer Center. This is the home page...

Community Convergence

Charlie Calvert's Community Blog — Tue, 05 Sep 2006 04:11:44 GMT

The C# team is happy to welcome you to the new look of the C# Developer Center. This is the home page...

Performance Quiz #11: Ten Questiosn on Value-Based Programming : Solution

Rico Mariani's Performance Tidbits — Fri, 08 Sep 2006 00:52:53 GMT

In my last quiz I asked a few questions about a few hypothetical classes that might appear in a value-right...

Games go Managed with XNA « G Krishnaa

Games go Managed with XNA « G Krishnaa — Wed, 08 Nov 2006 20:51:22 GMT

PingBack from http://gkrishnaa.wordpress.com/2006/08/24/games-go-managed-with-xna/

Managed Code Performance on Xbox 360 for XNA: Part 1 - Intro and CPU

.NET Compact Framework Team — Sat, 23 Dec 2006 00:21:28 GMT

Introduction Now that XNA Game Studio Express 1.0 is out, it’s time to start writing managed code for

Performance Quiz #11: Ten Questions on Value-Based Programming : Solution

Rico Mariani's Performance Tidbits — Wed, 24 Jan 2007 05:22:24 GMT

In my last quiz I asked a few questions about a few hypothetical classes that might appear in a value-rich

presentationpointers.check4cheap.com » Blog Archive

presentationpointers.check4cheap.com » Blog Archive — Thu, 01 Nov 2007 02:40:10 GMT

PingBack from http://presentationpointers.check4cheap.com/?p=149

how is the game clr played

how is the game clr played — Sun, 29 Jun 2008 23:38:36 GMT

PingBack from http://anton.meinvoll.com/howisthegameclrplayed.html

A Tale of Two Memory Managers (long) | keyongtech

A Tale of Two Memory Managers (long) | keyongtech — Sun, 18 Jan 2009 20:41:17 GMT

PingBack from http://www.keyongtech.com/1332952-a-tale-of-two-memory