6

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?

Sean Werkema
  • 5,810
  • 2
  • 38
  • 42
  • 1
    How much speed are you willing to give up? That's why `unsafe` code exists; to trade safety for speed. – Robert Harvey May 27 '22 at 13:47
  • @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#? – Sean Werkema May 27 '22 at 13:52
  • 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. – Hans Passant May 27 '22 at 13:54
  • @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 :-) – Sean Werkema May 27 '22 at 13:57
  • [`Memory` is essentially a `Span` without the `ref`](https://learn.microsoft.com/en-us/dotnet/api/system.memory-1?view=net-6.0). – Robert Harvey May 27 '22 at 14:26
  • @RobertHarvey There are a lot of reasons why `Memory` doesn't work. It's not compatible with the return types of `stackalloc`, so to get a `Memory`, 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` instances in an inner loop. I looked at using `Memory`, but it's not really a viable alternative. – Sean Werkema May 27 '22 at 14:35
  • 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? – Matt Thomas Jun 28 '22 at 16:44
  • @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 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. – Sean Werkema Jun 28 '22 at 18:45

1 Answers1

1

Try Span2D<T>:

Span2D<byte> span2d = (stackalloc byte[height * width]).AsSpan2D(height, width);
David Xuang
  • 11
  • 1
  • 1
    Abstracts a block in memory to be available as _rows_, but doesn't help in using double indirection. – Oliver Jun 06 '23 at 11:29