Multidimentional fixed sized buffer

[Thaina]

This should be possible

public struct Matrix4x4
{
    public fixed float M[4,4];
}

/////////////

var m = new Matrix4x4();
m.M[0,0];
m.M[3,3]; // float[15] ? It could actually be transpile to (x * 4 + y)

If possible I would like C# to also support multidimensional Span2<T> up to Span4<T> or Span8<T> and so the above struct could be changed to

public struct Matrix4x4
{
    public Span2<float> M = stackalloc float[4,4]; //also allow stackalloc in field?
}

[YairHalberstadt]

How would this work internally?
How would you take a slice of a multidimensional span in an efficient way without copying, and without requiring a pointer to the original span?

[Thaina]

@YairHalberstadt Internally it could be just as I said above, it actually just the same fixed float[4 * 4] aka fixed float[16] and all of [x,y] operation would become [x * 4 + y]

Surely it need more work. It need to cache the length of each dimension somewhere

And about a slice, well this is challenging but still possible. We just need to tell the sub span about the dimension of original span. So that it will shift the row by the size of original span instead of it's row

Suppose

var span = float[4,4];
var subspan = span.Slice(1,1,2,2); // position 1,1 with size 2,2 but it should still know the original row size 4,4 too

subspan[0,0] // 1,1 of original span => (4 * (1 + 0)) + (1 + 0) == 5 of float buffer
subspan[1,0] // 2,1 of original span => (4 * (1 + 1)) + (1 + 0) == 9 of float buffer
subspan[0,1] // 1,2 of original span => (4 * (1 + 0)) + (1 + 1) == 6 of float buffer

[YairHalberstadt]

@Thaina
That methodology for slice requirea a span2 to store:

A pointer to the first item in the underlying array.
The length of the underlying array.
The width of the underlying array.
The X offset of the span.
The y offset of the span.
The width of the span.
The length of the span.

And getting the element at [x, y] requires using all 7 of these bits of information.

This makes the span 32 bytes, which is very large for a struct.

At this point I don't see that you're gaining anything by using a ref struct, and would just define a type Array2Segment which requires no language changes.

public class Array2Segment<T>
{
    T[,] array;
    int offsetX;
    int offsetY;
    int width;
    int height;
    this [int x, int y] => array[x + offsetX, y + offsetY];
}

[Thaina]

@YairHalberstadt The benefit is all would be allocated on stack and don't need to garbage collected. Even it got a bit large it would have no memory footprint

And also I just thought that, maybe we also don't need X and Y offset of the span. The pointer to first element is map to the same offset for each row if we just add by the width of the original span. So we just need

• A pointer to the first item in the underlying array.
• The length of the underlying array.
• The columns of the underlying array.
• The rows of the span.
• The columns of the span.

[YairHalberstadt]

And also I just thought that, maybe we also don't need X and Y offset of the span. The pointer to first element is map to the same offset for each row if we just add by the width of the original span.

I don't see how that would work. Can you share the code please?

[Thaina]

@YairHalberstadt Suppose we have Matrix4x4 at memory 0

If we slice from 1,1 with size 2,2. It just virtually mapped the pointer 6,7,10,11 right?
And the slice[0,0] is span[1,1]. slice[1,0] is span[2,1]
But also if we just get the slice[0,0] (which is pointer 6) and move with the width of original span (which is 4) it go to memory 10. Which I think it is a span[2,1] and also a slice[1,0] is it?

Without keeping the offset of X,Y I think if we know the width of original span, the pointer is the offset by itself. And we only go forward in slice so we don't really need to know how far back the original pointer is

[Thaina]

@YairHalberstadt Actually we don't need a length of original array too. Because when we already sliced the new span we will just need to concern only the size of the slice itself

So it just need

• A pointer to the first item
• The width of the original span
• The columns of the slice
• The rows of the slice

I think this is minimum. And a more complex dimension these numbers would growing by 2 per each dimension

3 dimensions might need

• A pointer to the first item
• The width of the original span
• The height of the original span
• The size of 1st dimension of the slice
• The size of 2nd dimension of the slice
• The size of 3rd dimension of the slice

[YairHalberstadt]

@Thaina
I don't believe that would work, as without knowing the width and height of the original array, you don't know how the items are laid out in memory. Remember, the underlying array stores all the rows as one contiguous 1 dimensional array. So you wouldn't know where the second row of the span starts.

[YairHalberstadt]

Scrap that. You would have to know the width of the original array, not the length.

[Thaina]

@YairHalberstadt Yes we need to know the memory layout

But we don't need to know the full layout
We only need just the width of original array to offset the 2D slice

You don't need to know the height because the height of the new sliced span is the new height limit. And it must be ensure that both height and width plus offset will not larger than the original span since the Slice function

[john-h-k]

a multidimensional Span does not really make sense. A Span simply represents a contigous block of memory, Nothing more

[mburbea]

How's about handling it C style?

public struct Fixed4x4
{
    private fixed float _data[4 * 4];
    public ref float this[int x,int y] => _d[x*4 + y];
}

An example usage might be::

var f = new Fixed4x4{
[0, 0] = 0, [0, 1] = 1, [0, 2] = 2, [0, 3] = 3,
[1, 0] = 4, [1, 1] = 5, [1, 2] = 6, [1, 3] = 7,
[2, 0] = 8, [2, 1] = 9, [2, 2] = 10, [2, 3] = 11,
[3, 0] = 12, [3, 1] = 13, [3, 2] = 14, [3, 3] = 15 
};
Console.WriteLine(f[0,2]); // prints 2.

And if you want to you can convert this into a span.

[Thaina]

@mburbea I forgot to mention that I propose this feature to work inline in the function too. Not just field

void DoSomething(int w,int h)
{
    var M = stackalloc float[w,h];
    M[1,1] = 1;
    M[2,2] = 1;
}

[john-h-k]

No you've brought stackalloc in, that's something else. Multindexing doesn't make sense for pointers really

[mburbea]

@Thaina , you can still use C style access with an extension method.

    static class Ext
    {
        public static ref T Get<T>(this ref Span<T> span, int x, int y, int yDim) where T: struct
        {
            return ref span[(x * yDim) + y];
        }
    }
...
        static void DoSomething(int w,int h)
        {
            Span<float> r = stackalloc float[w * h];
            r.Get(0, 1, h) = 1;
            r.Get(0, 2, h) = 2;
        }

Pretty nice if you forget the math. If extension everything ever happens you might be able to even add an indexer (although you do somehow need to persist the idea of the yDim).

You could also just create a struct like my previous suggestion and just cast the span to the struct.