I'm using XNA and c#, and I want to avoid creating any garbage with my message queue. This might turn out to be something of a challenge. It is highly necessary not to allocate too much at runtime on the 360 - the GC is non generational and every 1mb of data you allocate creates a fully recursive mark and sweep which can take several hundred milliseconds.
So far, I've managed to avoid creating a lot of garbage through a combination of object pooling, static buffers, and single object re-use. According to the clr profiler, I have zero allocations. There may be a few allocations when I port to the 360, but right now I'm still detecting runtime allocations using the CLR profiler.


Here is the problem:

I want to do my message handling in two halves. The method call for processing a message queue is as follows:

void handleMessages(MessageQueue input, MessageQueue output)

The idea being that messages in the input are handled and then messages are added to the output. Then, I can tell each of my component lists in turn to handle the messages and produce output. At the end of the frame, the input is cleared, and the two are swapped, so I always have an empty message queue and the queue from the last update.

this odd combination of requirements turns this into something of a challenge - I can't just brute force allocate a huge number of every possible message type. Is there a way to achieve these two goals, or should I abandon one to achieve the other?

I can't just brute force allocate a huge number of every possible message type.

How come?
If there's not enough unused message objects of a particular type (i.e. can't find one to be re-used), you could create one and also increment a counter. Run the game a few times on different levels and record the values of these counters. Then, use the recorded data to find out exactly what 'huge number' is required for each message type.

In C++ I'd allocate a single large block for messages to be written into (e.g. [font="'Courier New"]std::vector<u8> messageBuffer(size)[/font]) and would figure out a good initial size value via experiment as above.

[quote name='speciesUnknown' timestamp='1313057849' post='4847591']I can't just brute force allocate a huge number of every possible message type.

How come?
If there's not enough unused message objects of a particular type (i.e. can't find one to be re-used), you could create one and also increment a counter. Run the game a few times on different levels and record the values of these counters. Then, use the recorded data to find out exactly what 'huge number' is required for each message type.

In C++ I'd allocate a single large block for messages to be written into (e.g. [font="Courier New"]std::vector<u8> messageBuffer(size)[/font]) and would figure out a good initial size value via experiment as above.
[/quote]

Unfortunately in c# we don't have any support for placement new and the such like, so block allocating a big memory pool is not possible; in c++ i would do that. What I need to find is some alternative to block allocation in c# into which I can feed a big set of messages, which will be value types. Is there some kind of binary serialization method which might help? I could in theory put value types, except objects, into binary serialisation one end and take them out the other, but I doubt the performance of this will be any good.

I believe you missed the meat of Hodgman's suggestion, which doesn't require placement new at all. I shall attempt to elaborate.

Assuming the number of message types is tractable:

• Create an array for each message type
• The size of this array should be equal to the maximum number of messages of that type pumped through the system
• Each entry in the array should have two auxiliary members: isFree and isInPool
• isFree encodes whether or not that entry in the array can be used for a "new" message
• isInPool is a dummy used to mark objects of the message type which are not contained in the "master" array
• At runtime, allocate objects from the array if there is a suitable "isFree" entry
• If no entry isFree, allocate a new object dynamically, and mark it as not isInPool
• Every time you set an entry as not isInPool, increment a counter, e.g. a static variable
• On program exit, dump out the value of these counters for each message type
• Use a simple binary search to run the program a few times and home in on appropriate array sizes for each message type
• Even if your program ships with sizes that are "too small", you can safely fall back on dynamic allocation with only a performance hit
• If you have the memory space and can tune the arrays to not be "too small", you win ;-)

For the record, I've used exactly this strategy in the past, and it works very well, albeit with a bit of an up-front cost in finding good sizes for each array.

As a bonus, you can do all processing on each individual message type independently, which can help a lot with cache locality.

C# allows you to simulate C-style unions, linky, though I don't know if XNA/360 has some limitations regarding this. You could make a struct that has a field for the type of event the struct contains, and then all the possible event types as members with the same FieldOffset. You will naturally lose much of the type safety. Another drawback is that the size of the struct is always the size of biggest event type + size of type field, so this approach doesn't necessarily make much sense if the biggest event type is very large. (But at least the queue would be able to contain same number of events regardless of the type, if that's worth anything.)

For example SDL manages its event structures this way, so while hacky, it's not completely insane approach. It's just not so much a C# solution as it is a C solution.

This changes things.

I had abandoned the idea of getting both my original goals, but this might make it feasible. I can have three arrays for each message buffer frame - one of unions for the value types used by the message, one of object for the reference types used by each message, and one containing a list of structs, each with a type type of message, and the offset and length it uses in each buffer.

This is a somewhat bizarre way of doing things, although tbh game dev in c# has felt a bit strange so far, but it may well work.