How to store structs of different types without boxing

Question

I'm creating a messaging system for use in an XNA game. My Message types are structs because I want them to behave in a Value Type way.

struct MyMessageType1 : IMessage {}
struct MyMessageType2 : IMessage {}

List<IMessage> messageQueue = new List<IMessage>();

I want to be able to store Messages of different types in my message queue, but I want to do so without any of them being boxed.

If I have the structs implement an interface such as IMessage and I try to store them in a List, they get boxed.

I don't know all the possible message types ahead of time, so I can't just hard code one List for each type.

So the question is how can I store a list of structs of different types without them being boxed?

Answer 1

Basically, you can't nicely;

• treating as object or an interface: boxed
• wrap in a generic type with an abstract base-class: re-inventing a box
• reflection: uses object, boxed
• dynamic: essentially object, boxed

There is the option, however, of encapsulating the object in a bigger struct, i.e.

struct AnyMessage {
    public TypeA A;
    public TypeB B;
    public TypeC C;
}
struct TypeA {...}
struct TypeB {...}
struct TypeC {...}

now, this should work but hsa the downside of being much bigger, obviously. You might be able to work around this using explicit-layout to position them all at byte 0 (making a union), but I suspect this isn't allowed on xbox. But on regular .NET:

[StructLayout(LayoutKind.Explicit)] struct AnyMessage {
    [FieldOffset(0)] public TypeA A;
    [FieldOffset(0)] public TypeB B;
    [FieldOffset(0)] public TypeC C;
}

Answer 2

You could create a queue that stores your structs without boxing, and then processes it using an interface with generic method like this:

interface IMessageProcessor
{
    void Process<T>(T message) where T : struct, IMessage;
}

class MessageQueue
{
    abstract class TypedMessageQueue
    {
        public abstract void ProcessNext(IMessageProcessor messageProcessor);
    }

    class TypedMessageQueue<T> : TypedMessageQueue where T : struct, IMessage
    {
        Queue<T> m_queue = new Queue<T>();

        public void Enqueue(T message)
        {
            m_queue.Enqueue(message);
        }

        public override void ProcessNext(IMessageProcessor messageProcessor)
        {
            messageProcessor.Process(m_queue.Dequeue());
        }
    }

    Queue<Type> m_queueSelectorQueue = new Queue<Type>();
    Dictionary<Type, TypedMessageQueue> m_queues =
        new Dictionary<Type, TypedMessageQueue>();

    public void Enqueue<T>(T message) where T : struct, IMessage
    {
        TypedMessageQueue<T> queue;
        if (!m_queues.ContainsKey(typeof(T)))
        {
            queue = new TypedMessageQueue<T>();
            m_queues[typeof(T)] = queue;
        }
        else
            queue = (TypedMessageQueue<T>)m_queues[typeof(T)];

        queue.Enqueue(message);
        m_queueSelectorQueue.Enqueue(typeof(T));
    }

    public void ProcessNext(IMessageProcessor messageProcessor)
    {
        var type = m_queueSelectorQueue.Dequeue();
        m_queues[type].ProcessNext(messageProcessor);
    }
}

You keep a separate queue for each type of message and using that you can avoid boxing of messages altogether, without any StructLayout trickery and without knowing all possible message types beforehand.

Answer 3

This cannot be done.

Alternative 1

However, you can emulate things, by using two Lists (List<MyMessageType1> and List<MyMessageType2>).

You then concoct one Super Index (possibly, just another array of ints (longs?)) to make it possible to (indirectly) address an item as if it were one list.

You might want to optimize the index (runlength encoding: store just the indexes where the backing array switches: this will also enormously help when iterating a subrange that is known to be contiguous in one of the backing arrays)

Lists use Array storage internally, so - you get no boxing - fast random access - blazing iteration with list.ForEach

Alternative 2

Look at the StructLayout attribute and somehow emulate a Union by doing all the manipulations. If you are really prepared to get your hands dirty, throw in unsafe {} blocks (and compile with /unsafe) ... however, seriously consider P/Invoke a C DLL or use C++/CLI if it matters that much

Alternative 3 (added)

Because I really liked the fact that Marc Gravell pointed out you can use the StructLayout that I mentioned, to pinpoint all three members of a union .NET struct at the same offset; I thought I'd go the extra step and see whether I could make that a hell of a lot more leaky tranparent still. This comes pretty close to being transparent:

using System.Collections.Generic;
using System.Runtime.InteropServices;

namespace LeakyAbstractions
{
    struct TypeA {}
    struct TypeB {}
    struct TypeC {}

    [StructLayout(LayoutKind.Explicit)] internal struct AnyMessage {
        [FieldOffset(0)] public TypeA A;
        [FieldOffset(0)] public TypeB B;
        [FieldOffset(0)] public TypeC C;

        AnyMessage(TypeA a) { A = a; }
        AnyMessage(TypeB b) { B = b; }
        AnyMessage(TypeC c) { C = c; }

        public static implicit operator TypeA(AnyMessage msg) { return msg.A; }
        public static implicit operator TypeB(AnyMessage msg) { return msg.B; }
        public static implicit operator TypeC(AnyMessage msg) { return msg.C; }

        public static implicit operator AnyMessage(TypeA a) { return a; }
        public static implicit operator AnyMessage(TypeB b) { return b; }
        public static implicit operator AnyMessage(TypeC c) { return c; }
    }

    public class X
    {
        public static void Main(string[] s) 
        {
            var anyMessages = new List<AnyMessage> { 
                new TypeA(),
                new TypeB(),
                new TypeC(),
            };

            TypeA a = anyMessages[0];
            TypeB b = anyMessages[1];
            TypeC c = anyMessages[2];

            anyMessages.Add(a);
            anyMessages.Add(b);
            anyMessages.Add(c);
        }
    }
}

I'll leave the problem of discriminating this poor men's variant as an exercise to you. The simplist way would be to add a field to the AnyMessage struct, but depending on the payload, other strategies might be much more (space/time) efficient.

---

My $0.02

Oh, I'd never actually do this, because it seems like overcomplicated. I'm assuming you have a valid reason to optimize this

---

PS. If you are asking this after reading my answer here (yesterday: Should I use a struct or a class to represent a Lat/Lng coordinate?), I'm going to snap-judge this premature optimization

Answer 4

I don't think you can. Generality comes at a cost. My advice is do not do premature optimization if what you are worried about is performance. If Its not and you really need copy by value behavior think about using inmutable types (a la System.String)

Answer 5

It's possible, entirely within managed code, to create a single non-generic type of structure (which I'll call a MagicInvoker) which implements an interface, and holds references to an arbitrary number of other structures implementing that same interface, all without using reflection, boxing, or anything else that would cause GC pressure. Indeed, once arrays have reached their maximum sizes, one can create and delete billions of value-type objects without any more heap allocations.

The biggest caveat with such an approach is that such structures become in many ways like the pointers in "old C". Although the MagicInvokers are themselves a value types, and they refer to value types, their semantics are more like old-style pointers. If one copies a MagicInvoker, it will refer to the same structure as the original. Creating a MagicInvoker and then abandoning it without Dispose will cause a memory leak, and using or attempting to Dispose a copy of a MagicInvoker that has already been disposed will cause Undefined Behavior.

Public Interface IDoSomething
    Sub Dosomething()
End Interface
Structure MagicInvoker
    Implements IDoSomething, IDisposable

    Private holder As InvokerBase
    Private index As Integer
    Sub DoSomething() Implements IDoSomething.Dosomething
        holder.DoDoSomething(index)
    End Sub
    Shared Function Create(Of T As IDoSomething)(ByVal thing As T) As MagicInvoker
        Dim newInvoker As MagicInvoker
        newInvoker.holder = Invoker(Of T).HolderInstance
        newInvoker.index = Invoker(Of T).DoAdd(thing)
        Return newInvoker
    End Function
    Function Clone() As MagicInvoker
        Dim newHolder As New MagicInvoker
        newHolder.holder = Me.holder
        newHolder.index = Me.holder.DoClone(Me.index)
        Return newHolder
    End Function
    Private MustInherit Class InvokerBase
        MustOverride Sub DoDoSomething(ByVal Index As Integer)
        MustOverride Function DoClone(ByVal srcIndex As Integer) As Integer
        MustOverride Sub DoDelete(ByVal srcIndex As Integer)
    End Class
    Private Class Invoker(Of T As IDoSomething)
        Inherits InvokerBase
        Shared myInstances(15) As T, numUsedInstances As Integer
        Shared myDeleted(15) As Integer, numDeleted As Integer

        Public Shared HolderInstance As New Invoker(Of T)
        Overrides Sub DoDoSomething(ByVal index As Integer)
            myInstances(index).Dosomething()
        End Sub
        Private Shared Function GetNewIndex() As Integer
            If numDeleted > 0 Then
                numDeleted -= 1
                Return myDeleted(numDeleted)
            Else
                If numUsedInstances >= myInstances.Length Then
                    ReDim Preserve myInstances(myInstances.Length * 2 - 1)
                End If
                numUsedInstances += 1
                Return numUsedInstances - 1
            End If
        End Function
        Public Shared Function DoAdd(ByVal value As T) As Integer
            Dim newIndex As Integer = GetNewIndex()
            myInstances(newIndex) = value
            Return newIndex
        End Function
        Public Overrides Sub DoDelete(ByVal srcIndex As Integer)
            If numDeleted >= myDeleted.Length Then
                ReDim Preserve myDeleted(myDeleted.Length * 2 - 1)
            End If
            myDeleted(numDeleted) = srcIndex
            numDeleted += 1
        End Sub
        Public Overrides Function DoClone(ByVal srcIndex As Integer) As Integer
            Dim newIndex As Integer = GetNewIndex()
            myInstances(newIndex) = myInstances(srcIndex)
            Return newIndex
        End Function
    End Class

    ' Note: Calling Dispose on a MagicInvoker will cause all copies of it to become invalid; attempting
    '       to use or Dispose one will cause Undefined Behavior.  Conversely, abandoning the last copy of
    '       a MagicInvoker will cause a memory leak.

    Public Sub Dispose() Implements System.IDisposable.Dispose
        If holder IsNot Nothing Then
            holder.DoDelete(index)
            holder = Nothing
        End If
    End Sub
End Structure

A MagicInvoker holds an instance of some class derived from InvokerBase (which will happen to be an Invoker<T> for some T that implements IDoSomething), and an array index. For every type T which is used with MagicInvoker.Create, there will be one instance of class Invoker<T> created; that same instance will be used for all MagicInvokers created from that type.