How to store structs of different types without boxing
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?
Solution 1:
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
Solution 2:
Basically, you can't nicely;
- treating as
objector an interface: boxed - wrap in a generic type with an abstract base-class: re-inventing a box
- reflection: uses
object, boxed -
dynamic: essentiallyobject, 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;
}
Solution 3:
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.
Solution 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)
Solution 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.