XNA's use of Collections

Aaron Leiby


XNA uses Collections for a lot of things: ModelMeshCollection, ModelEffectCollection, EffectPassCollection, ModelMeshPartCollection, etc. which results in a lot of foreach iteration in code. I recently discovered the CLR Profiler and started poking around. It appears that using foreach on these Collections results in creation of SZArrayHelper and Enumerator helper objects. Most other systems are doing pretty well to avoid any constant object "leakage", and I'd rather keep it that way if possible (I come from the "No Dynamic Allocations at Runtime" school of console development). I'm still pretty new to C#, so what I'm wondering is if there are there ways to avoid this constant pressure on the GC -beyond hand unrolling the loops (in turn binding code to data), or rolling my own model classes, etc..

Neverwhere


Use a simple for() loop to do the work of your collection set.

Eg:
LinkedList<Type> myLL = new LinkedList<Type>();
// add a bunch of things of Type to the collection...
for(int nLoop = 0; nLoop < myLL.Count; x++)
{
LinkedListNode<Type> cur = myLL[nLoop];
Type curType = cur.Value;
// Manipulate curType here
}



That same code could be turned into a foreach() call ( eg: foreach(Type curType in myLL) ), but as you said this generates some overhead which needs to be managed by the GC. You could also use a while() loop to do the same thing using the ability of the LinkedListNode<> class to traverse the list.

While I am using a LinkedList here, the same general principle works on any of your mentioned collection sets. Anything with the array sub-script overloaded can be done with a for() or while() loop. Try using one of those methods instead.

MattDavey

There's a simpler (and more efficient way) to iterate through a LinkedList object....

LinkedList<Type> _list = new LinkedList<Type>();
//...
LinkedListNode<Type> node = _list.First;
while (node != null)
{
    //do something to node.Value...
    node = node.Next;
}



Or if you're using the standard List<> class...

List<Type _list = new List<Type>();
//...
_list.Foreach(delegate(Type obj)
{
    //do something to obj...
});



Most of the container classes you mention should allow at least one of those approaches. I use both extensively in my project and i was able to completely eliminate Foreach loops - and i saw a pretty big improvement in performance :)

Joel Martinez

for the List<T>, I'd reconsider using a plain jane for(;;) loop ... delegates are much slower to call than just accessing each individual item by the indexer. And it's not like you're getting anything syntactically with the anon delegate ... in fact, it might confuse newcomers even more :-)

Michael Hansen

remember if you use genirc it is type safe and that why it all ways produce a overhead

 

the fastest collections build in net is a hashtable

remove the using system.collections.generic

use onlye system.collections;

and a hasttable useng int as key and your class as value

and do not use any struct use a class instead and keep the amount of classes small

the class that you have as value .......................do not use any interfaces in thies classes

a hashtable is slow to insert a item into but verry fast to pul out from

 

Leaf.

Michael Hansen wrote:

the fastest collections build in net is a hashtable remove the using system.collections.generic use onlye system.collections; and a hasttable useng int as key and your class as value and do not use any struct use a class instead and keep the amount of classes small the class that you have as value .......................do not use any interfaces in thies classes a hashtable is slow to insert a item into but verry fast to pul out from

I'm sorry for the bluntness but this is just rubbish. Instead of paying any attention to that read something a little more authoritative like this explanation of the collection classes in .Net 2.0. Learn a little about how the collection classes work and you will be much better placed to know when to use which collection.

Cheers,
Leaf.

Gunston

Leaf

Thanks for this post. Have been looking for something similar for a while. IMHO, people should generally post links to support their assertions. By definition, there are lots of new game programmers (I'm a long-time corporate software developer but newbie game developer) on this forum and we shouldn't be frustrating them with demonstrable nonsense.

The issues that come up in my day job are very different from those that arise when developing a 60 fps game (even if it's pretty rubbish and only 2D and will never go anywhere!). Lots of people here are learning and many are prepared to spend their own time supporting others which makes for a great forum.

Cheers.

Michael Hansen

i have done some testing on the xbox360 both with generic and non generic

and a array and stack is not a collection

if you use a hashtable on the xbox360 with 4000 bounding boxed it is verry slow to inset a item into , but if you pull out from that table it is the fastest the overhead on a hashtable is 20 bytes in my test and if i use generic no mater what table i use it is 44 bytes even with linkedliist

 

 so if you whant to get tings going fast use unsafe pointer to your hashtable

this can we do on the xbox360

so the memory overhead is a 4 bytes for a pointer

it allso prevent the garbge collector to interfear

and the speed of hashtable you are on the way

 and a little tip of games developerment for scenegraph managerment us a kd-tree

 

Jim Perry

Michael Hansen wrote:

so if you whant to get tings going fast use unsafe pointer to your hashtable this can we do on the xbox360

You can't use unsafe code on the 360 with GSE.

Leaf.

Not that I'm agreeing with the idea of using a pointer to a hashtable but you can use unsafe code on the Xbox 360. Pointers, fixed pointers to managed objects and fixed buffers work but there appears to be a problem with stackalloc - code with stackalloc in causes an exception - not sure if that is a bug or by design. Not that I need to use stackalloc I was just experimenting.

Cheers,
Leaf.

Michael Hansen

i was allso experimenting and tamming the clr for a month or so

i used list<myobject> before but when a have a lot of bounding boxed in the list the framework is relly slow

i allso tryed octtree and protal it is just slow mabye my code is no to pritty

but i was trowing all the code away and come to this solluiction

i have scene management that onlye hold a bounding box

public unsafe class node

{

vector3 min and max , radius, center,rot,pos,scale

matrix world

and a pointer to the meshobject

}

and a simple array<node> myscenenode

and a UNSAFE pointer to the array node class from my scenegraph management

this is verry fast , but remember there is no copy of the class stored in memory so that garbage collector can not collect

normal the cli store a copy of the class in the memory

try do do some test

a you see a huge speed diff

best regards

michael

so the onlye

MVP User

[Please do not mail me a copy of your followup] <= UTF-8 B QWFyb24gTGVpYnk= =@discussions.microsoft.com> spake the secret code <ca093697-3be7-4347-a9f6-b5df4a42aa67@discussions.microsoft.com> thusly: >[...] I'm still pretty new to C#, so what I'm >wondering is if there are there ways to avoid this constant pressure on >the GC -beyond hand unrolling the loops (in turn binding code to data), >or rolling my own model classes, etc.. Computers are fast and cheap. Programmers are slow and expensive. Why are you optimizing for the fast and cheap part Just use the standard collections and the simplest code possible until you've profiled your application and determined that this is actually worth worrying about. This isn't a C=64; don't program it like one. -- "The Direct3D Graphics Pipeline" -- DirectX 9 draft available for download <http://www.xmission.com/~legalize/book/download/index.html> Legalize Adulthood! <http://blogs.xmission.com/legalize/>

MVP User

[Please do not mail me a copy of your followup] <= UTF-8 B TGVhZi4= =@discussions.microsoft.com> spake the secret code <e6b993b6-95db-4638-8faa-366a79d6cca6@discussions.microsoft.com> thusly: >Not that I'm agreeing with the idea of using a pointer to a hashtable >but you can use unsafe code on the Xbox 360. [...] Its my understanding that you CANNOT use unsafe code blocks with XNA Game Studio Express. This is not the same thing as saying you can't do it on the Xbox 360, its just saying you can't do it with XNA GSE. -- "The Direct3D Graphics Pipeline" -- DirectX 9 draft available for download <http://www.xmission.com/~legalize/book/download/index.html> Legalize Adulthood! <http://blogs.xmission.com/legalize/>

Leaf.

NNTP User wrote:

Its my understanding that you CANNOT use unsafe code blocks with XNA Game Studio Express. This is not the same thing as saying you can't do it on the Xbox 360, its just saying you can't do it with XNA GSE.

Is that you Richard I'm guessing from the signature it is. Accessing these forums from NNTP doesn't seem to work too well, the formatting is gone and they are not that easy to read.

Anyway, regarding unsafe code on the Xbox 360 with XNA GSE, just try it, it works. I'm not talking about hacking something onto it, just create an Xbox game project, set it to build with the unsafe option and write some unsafe code. See Shawn's post in this thread for futher confirmation. Note, unsafe code refers to the use of pointers and fixed buffers not P/Invoke or other interop methods.

I found out a little more about stackalloc, it looks like the compact framework doesn't support it but the compiler doesn't spot it - so you end up with a runtime exception instead.

Cheers,
Leaf.

Aaron Leiby

Programmers are slow and expensive.

Actually, I'm pretty fast, and doing this all in my free time. :)

I may not have been clear. I've gotten to a pretty significant milestone, broken out the profiler and identified the parts that needed optimizing. This is currently at the top for memory guzzling. Wasn't sure if this was standard fare, or if it was a big no-no to be using foreach with collections in production realtime programming. For the system's I've written myself on top of XNA, I've been able to mostly stick to static arrays which seem to behave much better. I was just surprised to find iteration incurred allocation.