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?

Ashbey

Why exactly do you want them to be structs? And why don't you want them boxed? Do you fear about performance? – Digiacomo

I want them to be structs because I think value type semantics feel more correct for my Message objects. I don't want them boxed because I'm using this in an XNA game and for my messaging stuff I don't want to create any garbage that the garbage collector has to clean up. – Ashbey

“I don't want to create any garbage” Why not? Do you know it causes performance problems for you? – Digiacomo

Garbage creates problems on the Xbox. This messaging system is used many many times per frame and if it creates garbage the GC is going to be going all the time. – Ashbey

Answer 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

Spanish

I was thinking about using Alternative 1, the multiple generic lists solution, but since I don't know all the possible message types at compile time, I'd need to dynamically create these generic lists, which I can do. But now I have to figure out how to store the lists. If I put them in a List<IList> then I'll incur boxing when I try to get a value out of the ILists. If I store them as ILists I couldn't figure out a way to cast it back to its List<MyMessageType1> self at runtime so as not to be hit with any boxing. Is there a way to do that? – Ashbey

@BowserKingKoopa: If your elements will be limited set of types, I'd simply go with List<Ilist>; in no way will that incur boxing while accessing the underlying items provided you cast the List itself as early as possible, not the items. Anything more than this is asking for a valuetype Variant implementation. If that were allowed, no boxing would ever have been invented. – Spanish

I went and implemented some more glue on Marc Gravells PoC; This is almost transparent (see usage in Main) – Spanish

Answer 2

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;
}

Mountainside

Actually, you can use StructLayout and FieldOffset on the Xbox. – Madelle

Answer 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.

Digiacomo

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)

Effable

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.

Granivorous

Thanks for your answer. I did not mention in my question that my goal was performance, so this answer sadly doesn't help me, i shouldve mentioned that at the start. – Romanfleuve

@MHGameWork: The MagicInvoker technique allows excellent performance; did I fail to make that clear? – Granivorous

I am using this in a very hot codepath, so i dont want to use virtual function calls and risk getting cache misses. – Romanfleuve

@MHGameWork: The .NET framework just-in-time compiler will produce separate machine code for every different MagicInvoker<T> class which gets used, thus avoiding the need for virtual function calls at runtime. That's one of the beauties of this approach--it avoids virtual function calls. – Granivorous

Ill have a more in depth-look, its been 15 years since i last used vb.net :) ill have to run a benchmark too be sure – Romanfleuve

Answer 6

here is the way how i solve this problem. no alloc when enqueue,only alloc when concurrentqueue expand size.

public class JobQueue { 
    abstract class Invoker {
        public abstract void Do();
    }
    class Invoker<F>:Invoker where F : IJob {
        static volatile Invoker<F> _ins = null;
        static object syncRoot = new Object();

        public static Invoker<F> ins {
            get {
                if (_ins == null) {
                    lock (syncRoot) {
                        if (_ins == null)
                            _ins = new Invoker<F>();
                    }
                }
                return _ins;
            }
        }
        public int registerIndex { get; private set; } = -1;
        ConcurrentQueue<F> queue;

        Invoker() {
            queue = new ConcurrentQueue<F>();
        }
        public void Register(int index) {
            registerIndex = index;
        }
        public void Enqueue(F t) {
            queue.Enqueue(t);
        }
        public override void Do() {
            if (queue.TryDequeue(out var msg)) {
                msg.DoJob();
            }
        }
    }

    public bool isWork { get; set; } = false;
    ManualResetEvent manualResetEvent = new ManualResetEvent(false);
    Invoker[] invokers = new Invoker[1000];
    int index = 0;
    ConcurrentQueue<int> jobIndexs = new ConcurrentQueue<int>();

    public void Enqueue<T>(T t)where T : IJob {
        var invoker = Invoker<T>.ins;
        lock (invoker) {
            if (invoker.registerIndex == -1) {
                lock (invokers) {
                    invokers[index] = invoker;
                    invoker.Register(index);
                    jobIndexs.Enqueue(index);
                    index++;
                }               
            } else {
                jobIndexs.Enqueue(invoker.registerIndex);
            }
            invoker.Enqueue(t);
        }
        manualResetEvent.Set();
    }
    public void Run() {
        while (true) {
            if(jobIndexs.TryDequeue(out var index)) {
                invokers[index].Do();
            } else {
                manualResetEvent.Reset();
                return;
            }
            //if (!isWork)
            //    return;
            manualResetEvent.WaitOne();
        }
    }
}

Pacifistic

Answer 7

I had a similar problem with storing structs in non-boxing manner and found this post on google, so even if this answer isn't strictly a solution to your problem, I would like to write it here as I believe people looking to solve the same issue I had will probably find it.

I use an in-memory database for storing the state of the whole application and all of the data are structs only but the number of different struct types is not known. The in-memory database should at least support updating, inserting and getting data without boxing as these operations can be done quite often.

If we store everything in its original type, there will be no boxing. So why not create a separate dictionary/list/recycled wrapper object for each struct type? Then of course we have the question how do we store the dictionary? Because we always know the type when calling it, we can just store the dictionary into another dictionary with a type key and cast it to the right type when it needs to accessed. If we want to generically handle the structs through an interface like IIdentifiable or IMessage, we can use the where T: IIdentifier constraint to use IIdentifiable features without boxing. However, if we want to run, let's say a method for every IIdentifiable in the Dictionary, we would need some additional wrappers but I believe that goes out of scope a bit.

My current solution to this is something like this:

        private readonly Dictionary<Type, object> StateDictionary = new Dictionary<Type, object>();


        public Task Upsert<T>(T identifiable)
            where T : struct, IIdentifiable
        {
            if (string.IsNullOrEmpty(identifiable.Id))
                throw new ArgumentNullException($"{typeof(T)} had null id");

            if (!TryGetInnerDictionary<T>(StateDictionary, out var innerDictionary))
            {
                StateDictionary[typeof(T)] = innerDictionary;
            }
            
            innerDictionary[identifiable.Id] = identifiable;

            Debug.Log($"Upsert {typeof(T)} {identifiable.Id}");

            SendChangedEvent(identifiable);

            return Task.CompletedTask;
        }

        private static bool TryGetInnerDictionary<T>(Dictionary<Type, object> outerDictionary,
                                                     out Dictionary<string, T> innerDictionary)
        {
            if (!outerDictionary.TryGetValue(typeof(T), out var objInnerDictionary))
            {
                innerDictionary = new Dictionary<string, T>();
                outerDictionary[typeof(T)] = innerDictionary;

                return false;
            }

            innerDictionary = (Dictionary<string, T>)objInnerDictionary;

            return true;
        }


        public T Get<T>(string id)
            where T : struct, IIdentifiable
        {
            TryGetInnerDictionary<T>(StateDictionary, out var innerDictionary);
            var success = innerDictionary.TryGetValue(id, out var state);

            return success ? (T)state : throw new ArgumentNullException($"Unable to find {typeof(T)} with id {id}");
        }

Trusty