Anheften von Zeiger-Arrays im Speicher

Question

Ich arbeite derzeit als Hobbyprojekt an einem Raytracer in C#.Ich versuche, eine anständige Rendering-Geschwindigkeit zu erreichen, indem ich einige Tricks aus einer C++-Implementierung umsetze, und bin dabei auf ein Problem gestoßen.

Die Objekte in den Szenen, die der Raytracer rendert, werden in einer KdTree-Struktur gespeichert und die Knoten des Baums werden wiederum in einem Array gespeichert.Die Optimierung, mit der ich Probleme habe, besteht darin, so viele Baumknoten wie möglich in eine Cache-Zeile unterzubringen.Eine Möglichkeit hierfür besteht darin, dass Knoten nur einen Zeiger auf den linken untergeordneten Knoten enthalten.Es ist dann implizit, dass das rechte Kind direkt nach dem linken im Array folgt.

Die Knoten sind Strukturen und werden während der Baumkonstruktion von einer statischen Speichermanagerklasse erfolgreich in das Array eingefügt.Wenn ich anfange, den Baum zu durchqueren, scheint es zunächst ganz gut zu funktionieren.Dann zeigt der linke untergeordnete Zeiger des Wurzelknotens zu einem frühen Zeitpunkt des Renderings (jedes Mal ungefähr an der gleichen Stelle) plötzlich auf einen Nullzeiger.Ich bin zu dem Schluss gekommen, dass der Garbage Collector die Strukturen verschoben hat, da das Array auf dem Heap liegt.

Ich habe mehrere Dinge versucht, um die Adressen im Speicher zu fixieren, aber keines davon scheint für die gesamte Anwendungslebensdauer zu halten, wie ich es brauche.Das Schlüsselwort „fixed“ scheint nur bei einzelnen Methodenaufrufen hilfreich zu sein, und die Deklaration von „fixed“-Arrays kann nur für einfache Typen durchgeführt werden, bei denen es sich nicht um einen Knoten handelt.Gibt es eine gute Möglichkeit, dies zu tun, oder bin ich einfach zu weit auf dem Weg zu Dingen, für die C# nicht gedacht war?

Übrigens ist der Wechsel zu C++ zwar vielleicht die bessere Wahl für ein Hochleistungsprogramm, aber keine Option.

Answer 1

Erstens: Wenn Sie C# normal verwenden, können Sie nicht plötzlich eine Nullreferenz erhalten, weil der Garbage Collector Dinge verschiebt, da der Garbage Collector auch alle Referenzen aktualisiert, sodass Sie sich keine Sorgen darüber machen müssen, dass er Dinge verschiebt.

Sie können Dinge im Speicher anheften, dies kann jedoch mehr Probleme verursachen als lösen.Zum einen verhindert es, dass der Garbage Collector den Speicher ordnungsgemäß komprimiert, und kann auf diese Weise die Leistung beeinträchtigen.

Eine Sache, die ich aus Ihrem Beitrag sagen möchte, ist, dass die Verwendung von Strukturen möglicherweise nicht die Leistung verbessert, die Sie erhoffen.C# kann keine Methodenaufrufe integrieren, die Strukturen beinhalten, und obwohl sie dies in ihrer neuesten Runtime-Beta behoben haben, funktionieren Strukturen häufig nicht so gut.

Persönlich würde ich sagen, dass sich solche C++-Tricks im Allgemeinen nicht so gut auf C# übertragen lassen.Möglicherweise müssen Sie lernen, ein wenig loszulassen;Es kann andere, subtilere Möglichkeiten geben, die Leistung zu verbessern ;)

Answer 2

Was macht Ihr statischer Speichermanager eigentlich?Sofern nicht etwas Unsicheres ausgeführt wird (P/Invoke, unsicherer Code), ist das beobachtete Verhalten ein Fehler in Ihrem Programm und nicht auf das Verhalten der CLR zurückzuführen.

Zweitens: Was meinen Sie mit „Zeiger“ in Bezug auf Verbindungen zwischen Strukturen?Meinen Sie wörtlich einen unsicheren KdTree*-Zeiger?Tu das nicht.Verwenden Sie stattdessen einen Index im Array.Da ich erwarte, dass alle Knoten für einen einzelnen Baum im selben Array gespeichert sind, benötigen Sie keinen separaten Verweis auf das Array.Nur ein einzelner Index reicht aus.

Wenn Sie schließlich unbedingt KdTree*-Zeiger verwenden müssen, sollte Ihr statischer Speichermanager einen großen Block z. B. zuweisen.Marshal.AllocHGlobal oder eine andere nicht verwaltete Speicherquelle;Dieser große Block sollte sowohl als KdTree-Array behandelt werden (d. h.einen KdTree* im C-Stil indizieren) Und Es sollte Knoten aus diesem Array unterbelegen, indem es einen „freien“ Zeiger anstößt.

Wenn Sie jemals die Größe dieses Arrays ändern müssen, müssen Sie natürlich alle Zeiger aktualisieren.

Die grundlegende Lektion hier ist, dass unsichere Zeiger und verwalteter Speicher dies tun nicht Mischen Sie außerhalb von „festen“ Blöcken, die natürlich eine Stack-Frame-Affinität haben (d. h.Wenn die Funktion zurückkehrt, verschwindet das angeheftete Verhalten.Es gibt eine Möglichkeit, beliebige Objekte wie Ihr Array mithilfe von GCHandle.Alloc(yourArray, GCHandleType.Pinned) anzuheften, aber Sie möchten diesen Weg mit ziemlicher Sicherheit nicht einschlagen.

Vernünftigere Antworten erhältst du, wenn du genauer beschreibst, was du tust.

Answer 3

Wenn du Wirklich Wenn Sie dies tun möchten, können Sie die Methode GCHandle.Alloc verwenden, um anzugeben, dass ein Zeiger angeheftet werden soll, ohne dass er am Ende des Bereichs automatisch freigegeben wird, wie bei der Fixed-Anweisung.

Aber wie schon andere gesagt haben, übt dies einen übermäßigen Druck auf den Müllsammler aus.Wie wäre es, wenn Sie einfach eine Struktur erstellen, die ein Paar Ihrer Knoten enthält, und dann ein Array von NodePairs anstelle eines Arrays von Knoten verwalten?

Wenn Sie wirklich einen völlig unverwalteten Zugriff auf einen Teil des Speichers haben möchten, ist es wahrscheinlich besser, den Speicher direkt vom nicht verwalteten Heap zuzuweisen, als einen Teil des verwalteten Heaps dauerhaft zu fixieren (dies verhindert, dass der Heap ordnungsgemäß funktionieren kann). verdichtet sich selbst).Eine schnelle und einfache Möglichkeit, dies zu tun, wäre die Verwendung der Methode Marshal.AllocHGlobal.

Answer 4

Ist es wirklich unerschwinglich, das Paar aus Array-Referenz und Index zu speichern?

Answer 5

Was macht Ihr statischer Speichermanager eigentlich?Sofern nicht etwas Unsicheres ausgeführt wird (P/Invoke, unsicherer Code), ist das beobachtete Verhalten ein Fehler in Ihrem Programm und nicht auf das Verhalten der CLR zurückzuführen.

Ich habe tatsächlich von unsicheren Zeigern gesprochen.Was ich wollte, war so etwas wie Marshal.AllocHGlobal, allerdings mit einer Lebensdauer, die einen einzelnen Methodenaufruf überschreitet.Wenn ich darüber nachdenke, scheint es, dass die Verwendung eines Index einfach die richtige Lösung ist, da ich mich möglicherweise zu sehr damit beschäftigt habe, den C++-Code nachzuahmen.

Eine Sache, die ich aus Ihrem Beitrag sagen möchte, ist, dass die Verwendung von Strukturen möglicherweise nicht die Leistung verbessert, die Sie erhoffen.C# kann keine Methodenaufrufe integrieren, die Strukturen beinhalten, und obwohl sie dies in ihrer neuesten Laufzeit-Beta behoben haben, funktionieren Strukturen häufig nicht so gut.

Ich habe mir das ein wenig angesehen und festgestellt, dass es in .NET 3.5SP1 behoben wurde.Ich gehe davon aus, dass Sie das als Laufzeit-Beta bezeichnet haben.Tatsächlich verstehe ich jetzt, dass diese Änderung zu einer Verdoppelung meiner Rendergeschwindigkeit geführt hat.Jetzt sind Strukturen aggressiv eingebunden, was ihre Leistung auf X86-Systemen erheblich verbessert (X64 hatte im Voraus eine bessere Strukturleistung).