List<T> to T[] without copying

Question

I'm have a large list of value types that needs to be given to OpenGL. It would be great if this could happen as quickly as possible. What I'm doing now looks like this:

List<Vertex> VList = new List<Vertex>();
... //Add vertices
Vertex[] VArray;
VList.CopyTo(VArray, VList.Length);
GL.SetData(..., VArray);

This list is easily 10MB big, so copying is slow. Can I do this without copying, like somehow get a pointer to the array used internally by List?

Or do I have to implement my own List class..

EDIT: I forgot to mention that I don't know the number of elements that will be added to the List.

Answer 1

It's not a good way, but you can use CollectionsMarshal.AsSpan (since .net 5). It has access to the internal List array (see source code).

var list = new List<int>();
CollectionsMarshal.AsSpan(list);

https://learn.microsoft.com/en-us/dotnet/api/system.runtime.interopservices.collectionsmarshal.asspan?view=net-6.0

Answer 2

If you need to access internal array repeatedly, it good practice to store accessor as delegate.

In this example, it's delegate to dynamic method. First call may not be fast, but subsequent calls (on List of same type) will be much faster.

public static class ListExtensions
{
    static class ArrayAccessor<T>
    {
        public static Func<List<T>, T[]> Getter;

        static ArrayAccessor()
        {
            var dm = new DynamicMethod("get", MethodAttributes.Static | MethodAttributes.Public, CallingConventions.Standard, typeof(T[]), new Type[] { typeof(List<T>) }, typeof(ArrayAccessor<T>), true);
            var il = dm.GetILGenerator();
            il.Emit(OpCodes.Ldarg_0); // Load List<T> argument
            il.Emit(OpCodes.Ldfld, typeof(List<T>).GetField("_items", BindingFlags.NonPublic | BindingFlags.Instance)); // Replace argument by field
            il.Emit(OpCodes.Ret); // Return field
            Getter = (Func<List<T>, T[]>)dm.CreateDelegate(typeof(Func<List<T>, T[]>));
        }
    }

    public static T[] GetInternalArray<T>(this List<T> list)
    {
        return ArrayAccessor<T>.Getter(list);
    }
}

Make sure to include:

using System.Reflection;
using System.Reflection.Emit;

Answer 3

Since you're using GL I'll assume you know what you're doing and skip all the caveats. Try this, or see https://stackoverflow.com/a/35588774/194921

  [StructLayout(LayoutKind.Explicit)]
  public struct ConvertHelper<TFrom, TTo>
      where TFrom : class
      where TTo : class {
    [FieldOffset( 0)] public long before;
    [FieldOffset( 8)] public TFrom input;
    [FieldOffset(16)] public TTo output;

    static public TTo Convert(TFrom thing) {
      var helper = new ConvertHelper<TFrom, TTo> { input = thing };
      unsafe {
        long* dangerous = &helper.before;
        dangerous[2] = dangerous[1];  // ie, output = input
      }
      var ret = helper.output;
      helper.input = null;
      helper.output = null;
      return ret;
    }
  }

  class PublicList<T> {
    public T[] _items;
  }

  public static T[] GetBackingArray<T>(this List<T> list) {
    return ConvertHelper<List<T>, PublicList<T>>.Convert(list)._items;
  }

Answer 4

I wouldn't recommend what you want to do. Why are you using a List<T> in the first place? If you can tell us precisely what characteristics the data-structure that you want to create should have, and how it should interface with the consuming API, we might be able to give you a proper solution to your problem.

But I will try to answer the question as asked.

Can I do this without copying, like somehow get a pointer to the array used internally by List?

Yes, although you would be relying on an undocumented implementation detail. As of NET 4.0, the backing array field is called _items.

Vertex[] vertices = (Vertex[]) typeof(List<Vertex>)
                   .GetField("_items", BindingFlags.NonPublic | BindingFlags.Instance)
                   .GetValue(VList);

Do note that this array will almost certainly have slack at the end (that's the whole point of List<T>), so array.Length on this array won't be all that useful. The API that consumes the array would need to be notified of the "real" length of the array through other means (by telling it what the list's real Count was).

Answer 5

Rather than use reflection to access the internal array in a List<T>, if you only need the ability to add, then I would actually recommend implementing your own resizable array (gasp!). It's not that hard.

Something like:

class ResizableArray<T>
{
    T[] m_array;
    int m_count;

    public ResizableArray(int? initialCapacity = null)
    {
        m_array = new T[initialCapacity ?? 4]; // or whatever
    }

    internal T[] InternalArray { get { return m_array; } }

    public int Count { get { return m_count; } }

    public void Add(T element)
    {
        if (m_count == m_array.Length)
        {
            Array.Resize(ref m_array, m_array.Length * 2);
        }

        m_array[m_count++] = element;
    }
}

Then you can get at the internal array with InternalArray and know how many items are in the array using Count.

Answer 6

You may want to consider if your approach to this is wrong. If you find yourself using reflection to do this - you've already lost.

I can think of a few ways to approach this though which one is ideal depends a lot on whether this is a multi-threaded piece of code or not.

Let's assume it's not ...

Think about the characteristics of the array. Each time this method is called an N-length array is created. Your goal is to improve performance (which implies you want to minimize allocations and data copies).

Can you hint at compile or runtime what the ideal starting size for the array is? I mean - if 95% of the time the N-length is 100k or less ... start with a 100k item array. Keep using it until you hit a case where the array is too small.

When you hit this case you can decide what you do based on your understanding of the program. Should the array grow 10%? Should it grow to the literal needed length? Can you use what you have and continue the process for the rest of the data?

Over time the ideal size will be found. You can even have your program monitor the final size each time it runs and use that as a hint for allocation the next time it starts (perhaps this array length depends on environmental factors such as resolution, etc).

In other words - what I'm suggesting is that you not use the List-to-Array method and that you pre-allocate an array, keep it around forever, and grow it as needed.

If your program has threading issues you will obviously need to address those.

Answer 7

The IList<T> interface isn't that difficult to do (well, not so long as Reflector is free and functioning, hint hint).

You can create your own implementation and expose the internal array as a public property.

Answer 8

You can do that with reflection:

public static T[] GetUnderlyingArray<T>(this List<T> list)
{
    var field = list.GetType().GetField("_items",
        System.Reflection.BindingFlags.Instance |
        System.Reflection.BindingFlags.NonPublic);
    return (T[])field.GetValue(list);
}

edit: ah someone already said it while I was testing this..

Answer 9

You might be able to get a pointer out of a generic List, but I wouldn't recommend it and it probably wouldn't work the way you'd expect (if at all). Basically it means getting a pointer to an object, not a memory structure like an array.

I think you should go about this the other way around, and if you need speed then work directly on a byte array using structure array pointer in an unsafe context instead.

Background info:
"Even when used with the unsafe keyword, taking the address of a managed object, getting the size of a managed object, or declaring a pointer to a managed type is not allowed." - From C#: convert generic pointer to array

MSDN unsafe