CODEWITHSUNDEEP
c#.net
Martin Han
Martin Han

Reputation: 113

How to make a tree structure on stack only ( no reference type, nothing on heap) in C#?

For performance perpose I am doing multithreading and data is intended to be saved on stack of each thread.

First of all, I want to save a collection of data as a value type(so it can be saved on stack). However all the commonly used collection types, even array are reference type.

By what I know the only posibility is Span, a struct collection. I have a ref struct, which is made ref struct to be able to contain a span.

public ref struct Level{
    ...
    public Span<something> span;
}

This ref struct is also going to be saved into a collection, in this case, it was going to be a span just declared in the thread method:

private void threadStart() {
    Span<Level> levelSpan = stackalloc Level[100];
    ...
}

Unfortunately, this is not allowed,

CS0306: The type 'Level' may not be used as a type argument

Is there any other posible approach to save a tree structed data on stack?

Upvotes: 1

Views: 178

Answers (2)

Nick Strupat
Nick Strupat

Reputation: 5063

I took this approach. To have an arbitrary tree stored in full, you'd need to build it breadth-first.

readonly unsafe ref struct TreeNode<T>
{
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    private readonly TreeNode<T> * parent;
    public readonly T Value;

    public TreeNode(T value) => Value = value;
    public TreeNode(T value, in TreeNode<T> parent) : this(value)
    {
        fixed (TreeNode<T> * ptr = &parent)
            this.parent = ptr;
    }

    public Boolean HasParent => parent != null;
    public ref TreeNode<T> Parent => ref *parent;
}

If you need to traverse down and across, you can add a node pointer that forms a linked list down, and another one to form one across.

Upvotes: 0

Marc Gravell
Marc Gravell

Reputation: 1063198

Possible? Probably - it would involve some horrible stackallocs etc, and lots of fighting the compiler to convince it that things are safe when they aren't verifiable, coercing pointers to spans (because the compiler won't trust your spans, but as soon as you touch pointers, the compiler gives up and just let's you do whatever you're doing, because it knows it can't help) - but honestly: it isn't a good idea. The heap is very unlikely to be your limiting factor here, and even if it was - there are things you can do with array-pool leases mapped to spans. Alternatively, it is possible (but not trivial) to create something like an arena allocator in .NET, especially when dealing with value-tuples; there is one in Pipelines.Sockets.Unofficial, for example.

Additionally, when talking about scalability, my main thought is "async", which is anathema to retained stack allocations (since the stack-frames unwind for await) - resumable state machines need to use the heap (or at least: not the stack).

Upvotes: 4

Related Questions