What is an efficient equivalent in C# for Span<Span<T>>, which does not exist?

Question

I was porting some older high-speed C++ code to C#, and the existing code made use of a pointer-based double-indirection pattern like this (written here in a C# syntax), using the stack as efficient temporary storage:

public struct Source {
    public byte* Start;
    public int Count;
}

public struct SourceSet {
    public Source* Start;
    public int Count;
}

Source* sources = stackalloc Source[n*k];
SourceSet* sourceSets = stackalloc SourceSet[n];

It populates the sources with sets of segments of the data, and populates the sourceSets with how many Sources are in each set.

The code works fine, but ideally, I would like to convert it to no longer use pointers and unsafe — to instead use something memory-safe like this, where each SourceSet would be populated by a .Slice() of the sources:

public struct Source {
    public int Start;
    public int Count;
}

Span<Source> sources = stackalloc Source[n*k];
Span<Span<Source>> sourceSets = stackalloc Span<Source>[n];

But I can't write that, because Span<Span<T>> can't exist in C# — Span<T> is a ref struct and thus can't be used as the type parameter of another Span<T>. And I can't use Memory<Memory<T>> as a replacement, because stackalloc only produces a Span<T> (or a pointer, but the goal is to avoid pointers).

(And yes, I understand that Span<Span<T>> will likely never be added to the language, because it could potentially allow the rules about span lifetimes to be violated.)

So what's a good, efficient equivalent in C# for safe double-pointer indirection on the stack, something like Span<Span<T>>, but that actually exists?

Sandrasandro

How much speed are you willing to give up? That's why unsafe code exists; to trade safety for speed. – Pore

@RobertHarvey The initial setup can be expensive, but the resulting data structures are used millions of times in tight inner loops. It can afford a little bit of loss, which is why byte* Start could be just int Start, but not a lot. But the question is less about my specific case — I can live with unsafe if I have to — than about the general question: What's the best way to do memory-safe double-pointer indirection on the stack in C#? – Sandrasandro

Span is a semantic trick to hide a pointer without having to use the unsafe keyword. The compiler ensures that this pointer can't dangle. It can't do that for pointer-to-pointer. Fear not, just use a pointer when you need one. – Centreboard

@HansPassant Like I said, the code works with pointers as written. But I'd really like to have the safety provided by Span (or equivalent) if I could get it. The introduction of Span in C# showed I could have my cake and eat it too, and now I want more :-) – Sandrasandro

Memory<T> is essentially a Span<T> without the ref. – Pore

@RobertHarvey There are a lot of reasons why Memory<T> doesn't work. It's not compatible with the return types of stackalloc, so to get a Memory<T>, you have to use pointers anyway. It doesn't have an indexer. You have to either Pin it and get a pointer, or convert it to a Span to use it, which have high performance costs if you're iterating over hundreds of Memory<T> instances in an inner loop. I looked at using Memory<T>, but it's not really a viable alternative. – Sandrasandro

I don't have a lot of experience squeezing every last cycle out of the CPU, but putting something on the heap isn't that much of a performance hit, is it? Especially when it'll be in L1 cache because you're accessing it millions of times in tight inner loops. Also C++ compilers are a lot different than what C# does. Do benchmarks on the C# code warrant what you're trying to do, or is it a premature optimization? – Incondite

@MattThomas Those data structures get hit millions of times in an inner loop that has a fixed total execution budget of about half a millisecond. So... yes: The heap would be effectively unusable. There's a reason the original code was C(++), and it's only because now CPUs have gotten so fast and C# has low-level tools like Span<T> that C# was even a viable option. Since writing this, I've left the original C++ in place, because C# simply couldn't handle it. – Sandrasandro

Answer 1

Try Span2D<T>:

Span2D<byte> span2d = (stackalloc byte[height * width]).AsSpan2D(height, width);

Scrummage

Abstracts a block in memory to be available as rows, but doesn't help in using double indirection. – Hendrix