Allow Span<T> and ref struct at stackalloc

[Hessi9]

Version Used:
c# 7.2 or C# 8.0

Steps to Reproduce:
var spans = stackalloc Span< int >[5];

Expected Behavior:
I just thought the idea of Span< T > is to have a stack reference to some memory. I feel it is strange that single Span< T > variables work well, but an set of them fail. The same effect occures when a Span< T > is used as a field inside a ref struct.

Actual Behavior:
Error: Cannot take the address of ... a managed type Span< int >

[Joe4evr]

I feel it is strange that single Span< T > variables work well, but an set of them fail.

You wouldn't be able to stackalloc a set of spans in the first place, because that requires a target type of Span<Span<T>> which is illegal.

[ronnygunawan]

Even if we had ImmutableSpan<Span<T>>, it would be useless though. stackalloc Span<int>[5]; creates 5 empty spans.

[AlgorithmsAreCool]

What about introducing a Span2D<T> type analogous to a 2D array?

[Hessi9]

I know it's unfortunately not a trivial request. The problem is I haven't found any way to reference a set of spans. This currently make it impossible to use spans with any algorithm operating on sets.

[ronnygunawan]

I know it's unfortunately not a trivial request. The problem is I haven't found any way to reference a set of spans. This currently make it impossible to use spans with any algorithm operating on sets.

Here's a simple implementation of Span2D<T>, in case you don't need jagged 2D span

ref struct Span2D<T> {
    public Span2D(T[,] array) {
        Span = new T[array.Length];
        Length0 = array.GetLength(0);
        Length1 = array.GetLength(1);
        int k = 0;
        for (int i = 0; i < Length0; i++) {
            for (int j = 0; j < Length1; j++) {
                Span[k++] = array[i, j];
            }
        }
    }

    public Span<T> Span { get; }
    public ref T this[int index0, int index1] => ref Span[index0 * Length1 + index1];
    public static Span2D<T> Empty => new T[0, 0];
    public int Length0 { get; }
    public int Length1 { get; }
    public bool IsEmpty => Length0 == 0 || Length1 == 0;
    public static implicit operator Span2D<T>(T[,] array) => new Span2D<T>(array);
}

// Usage:
Span2D<double> matrix = new[,] {
    { 1.0, 0.0, 0.0 },
    { 0.5, 1.0, 0.0 },
    { 0.1, 0.2, 1.0 }
};

double matrix22 = matrix[2, 2];

[AlgorithmsAreCool]

I kind like this actually, with a little compiler support it might be workable.

Here is a rectangular 2d span that supports any span based source memory

using System;

namespace Span2D
{
        public enum Span2DLayout : byte
    {
        Auto,
        Packed
    }

    public readonly ref struct Span2D<T> {

        private readonly Span2DLayout Layout;
        private readonly int IndividualSpanLength;
        public readonly int SpanCount;
        
        private readonly Span<T> Source;

        public Span2D(Span<T> source, int individualSpanLength, int spanCount, Span2DLayout layout = Span2DLayout.Auto)
        {
            Layout = layout;
            Source = source;
            IndividualSpanLength = individualSpanLength; //TODO : validate >= 0
            SpanCount = spanCount; //TODO : validate >= 0

            if (Source.Length < Get1DLength(individualSpanLength, spanCount, layout))
                ThrowHelperBufferTooSmall();
        }

        public Span<T> this[int index] => GetSpan(index);

        private Span<T> GetSpan(int index)
        {
            if(index < 0)
                ThrowHelperIndexOutOfRange();

            return Layout switch {
                Span2DLayout.Auto => GetAutoLayoutSpan(index),
                Span2DLayout.Packed => GetPackedLayoutSpan(index),
                _ => ThrowHelperInvalidLayout()
            };
        }

        private Span<T> GetPackedLayoutSpan(int index)
        {
            int offset = IndividualSpanLength * index;
            return Source.Slice(offset, IndividualSpanLength);
        }

        private Span<T> GetAutoLayoutSpan(int index)
        {
            //i imagine here you could make some fancy choices about memory
            //padding and alignment to make access faster if you wanted...
        }

      
        public static int Get1DLength(int individualSpanLength, int spanCount, Span2DLayout layout = Span2DLayout.Auto)
        {
            //lets abstract this to allow for fancy/aligned mem layouts
        }

        private static void ThrowHelperBufferTooSmall() => throw new ArgumentException("Provided buffer is not large enough to contain 2D Span");
        private static Span<T> ThrowHelperInvalidLayout() => throw new ArgumentException("Provided buffer is not large enough to contain 2D Span");
        private static Span<T> ThrowHelperIndexOutOfRange() => throw new IndexOutOfRangeException();        
    }

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");

            //array example

            var arrayLength = Span2D<int>.Get1DLength(32, 1024);//big allocation
            var sourceArray = new int[arrayLength];
            var arraySpan2d = new Span2D<int>(sourceArray.AsSpan(), 32, 1024);
            
            UseSpan2D(arraySpan2d);

            //stackalloc example

            var allocLength = Span2D<int>.Get1DLength(32, 64);//smaller allocation
            var sourceSpan = stackalloc int[allocLength];
            var stackSpan2d = new Span2D<int>(sourceSpan, 32, 64);
            UseSpan2D(stackSpan2d);
        }

        public static void UseSpan2D(Span2D<int> span2d)
        {
            for (int i = 0; i < span2d.SpanCount; i++)
            {
                var subSpan = span2d[i];
                //do things with subSpan...
            }
        }
    }
}

[AlgorithmsAreCool]

Jagged 2d spans can be done also, but some implementation decisions would have to be made about the tradeoff between memory overhead and access time complexity

[AlgorithmsAreCool]

Releated #2513

[Hessi9]

The presented 2D-Spans don't solve the problem. Just a 2D-Indexer will not allow holding references to different memory locations - so no it's not #2513.
Just imagine a simple text sorting allgorithm were text is referenced by spans a.e. sorting string sentences alphabetical on the last word. I think it's currently impossible.
But algorithms that need to point to a part of a bigger data structure are common. The idea of Spans had been to make this possible - but without the ability to create more than one reference it's unuseable for many algorithms.

[AlgorithmsAreCool]

@Hessi9
Ah, i see what you are saying.

There isn't a way to compute the space needed for a ref struct. You can't use Unsafe.SizeOf or sizeof() on a ref struct so you can't safely compute the size of allocate as a Span and then Unsafe.As or anything like that.

The Span2D stuff we were talking about is allocating all the space on the stack, not just the space for the ref structs.

Yeah, this definitely needs compiler support.

[Hessi9]

So what I expect to work would be:

ref struct WorkItem {
  public Span<int> Span;
  ...
}
void MyFunc(int count) {
  var workset = stackalloc WorkItem[count];
  for (int i=0; i<count; i++)
    workset[i].Span = new Span<int>(...);
}

[ronnygunawan]

workset[i].Span = new Span<int>(...);

How do you propose this to be implemented or to behave?

[Hessi9]

I just want to show the basic syntax. The Span would be a reference into a more complex data structur. Without the ability to store references the positions need to be recalculated on every access. Below you find a small example of a surname bubble sort algorithm. Of cause this algorithm is not a usefull implementation, but again it is there to show the concept. The importance of partial data references increase as more complex the data and so the recalculation of the index gets. In my current personal case it is about .5 GB transit timetable data that are of cause stored like all big datasets in some struct[] insted of millions of small c# objects.
And here the sorting sample, first with index recalculation, second with spans:

static void Main(string[] args) {
	var res = SurNameSort(new string[] { "Adam Smith", "Beathe Use", "Lukas Neuman" });
	foreach (var name in res)
		Console.WriteLine(name);
}
struct WorkItem {
	public int index;
	public int SurNameIndex;
}
static string[] SurNameSort(string[] data) {
	Span<WorkItem> items = stackalloc WorkItem[data.Length];
	for (int i=0; i<items.Length; i++) {
		items[i].index = i;
		items[i].SurNameIndex = data[i].LastIndexOf(' ') + 1;
	}
	// bouble sort
	for (int n = items.Length; n > 1; --n)
		for (int i = 0; i < n - 1; ++i)
			if (data[items[i].index].Substring(items[i].SurNameIndex).CompareTo(
				data[items[i + 1].index].Substring(items[i + 1].SurNameIndex)) > 0) {
				var tmp = items[i];
				items[i] = items[i + 1];
				items[i + 1] = tmp;
			}
	// return results
	var res = new string[items.Length];
	for (int i = 0; i < items.Length; i++)
		res[i] = data[items[i].index];
	return res;
}

ref struct WorkItem {
	public int index;
	public ReadOnlySpan<char> SurName;
}
static string[] SurNameSort(string[] data) {
	Span<WorkItem> items = stackalloc WorkItem[data.Length];
	for (int i=0; i<items.Length; i++) {
		items[i].index = i;
		items[i].SurName = data[1].AsSpan(data[i].LastIndexOf(' ') + 1);
	}
	// bouble sort
	for (int n = items.Length; n > 1; --n)
		for (int i = 0; i < n - 1; ++i)
			if (MemoryExtensions.CompareTo(items[i].SurName, items[i + 1].SurName, StringComparison.Ordinal) > 0) {
				var tmp = items[i];
				items[i] = items[i + 1];
				items[i + 1] = tmp;
			}
	// return results
	var res = new string[items.Length];
	for (int i = 0; i < items.Length; i++)
		res[i] = data[items[i].index];
	return res;
}