Zuordnungssquashing durch Rückgabe von ReadOnlySpan über Mitgliedsvariablen über MemoryMarshal ⇐ C#

[Anonymous]

Wir haben etwas, das so aussieht:

Code: Select all

abstract class TreeNode {
internal abstract Branches GetChildren();
}

class Leaf : TreeNode {
internal override Branches GetChildren() => Branches.Empty();
}

class UnaryTreeNode : TreeNode {
TreeNode child;
internal override Branches GetChildren()
{
}
}

class BinaryTreeNode: TreeNode {
TreeNode left;
TreeNode right;
internal override Branches GetChildren()
{
}
}

class VariadicTreeNode : TreeNode {
TreeNode[] nodes;
internal override Branches GetChildren()
{
}
}

Dies sind immer noch Basisklassen; buchstäblich Hunderte von Klassen erben von den hier gezeigten Klassen.
Die offensichtliche einfache Implementierung ist also Branches is IReadOnlyList; Dies führt jedoch zu einer Zuteilungsstrafe. Wir gehen davon aus, dass es auf irgendeine Weise möglich wäre, die Anzahl der Zuordnungen beim Abstieg vom Baum auf 0 zu reduzieren. Ich habe versucht, einen ReadOnlyMemory zurückzugeben, aber das ist nicht einmal durch nicht-öffentliche Reflexion möglich, da der Anker eines ReadOnlyMemory nicht wirklich willkürlich ist.
Ich habe mich umgedreht und einen ReadOnlySpan verfolgt und einen plausiblen Ansatz gefunden: MemoryMarshal.CreateReadOnlySpan. Wenn ich die Kommentare richtig verstehe; Der resultierende Span von MemoryMarshal stellt keinen Verweis auf seinen Container her, sodass die triviale Implementierung nicht funktioniert.
Ich frage mich also: Funktioniert Folgendes:

Code: Select all

ref struct Branches {
internal object Anchor {get;init;}
internal ReadOnlySpan Span {get;init;}
}

abstract class TreeNode {
internal abstract Branches GetChildren();
}

class Leaf : TreeNode {
internal override Branches GetChildren() => default;
}

class UnaryTreeNode : TreeNode {
TreeNode child;
internal override Branches GetChildren()
{
var span = System.Runtime.InteropServices.MemoryMarshal.CreateReadOnlySpan(ref child, 1);
return new Branches { Anchor = this, Span = span };
}
}

class BinaryTreeNode: TreeNode {
TreeNode left;
TreeNode right;
internal override Branches GetChildren()
{
var span = System.Runtime.InteropServices.MemoryMarshal.CreateReadOnlySpan(ref left, 2);
return new Branches { Anchor = this, Span = span };
}
}

class VariadicTreeNode : TreeNode {
TreeNode[] nodes;
internal override Branches GetChildren()
{
return new Branches { Anchor = nodes, Span = nodes };
}
}

Eine einfache Testversion wird zeigen, dass es funktioniert. Allerdings kann ich nicht direkt überprüfen, ob dieser Code vernünftig ist: Was passiert, wenn das Objekt vom Garbage Collector verschoben wird?
Ich habe die Span-Implementierung einem Benchmarking unterzogen; es ist zwischen 10 % und 20 % schneller als die offensichtliche Array-Implementierung.