Geschwindigkeitsprobleme der Octree-Implementierung

Question

Seit einigen Tagen versuche ich, meine Force-Directed-Graph-Implementierung zu beschleunigen. Bisher habe ich den Barnes-Hut-Algorithmus implementiert, der Octree verwendet, um die Anzahl der Berechnungen zu reduzieren. Ich habe es mehrfach getestet und die Anzahl der kraftbezogenen Berechnungen ist tatsächlich drastisch verringert. Unten ist das Diagramm der Berechnungen zur Anzahl der Knoten ohne Barns-Hut (blaue Linie) und mit (rote Linie): Auch wenn es jetzt viel schneller sein sollte, ist die Wahrheit, dass in Bezug auf die Geschwindigkeit (Zeit) Das Upgrade ist nur wenige Prozent.

Ein Teil, der vermutlich verursacht wird, ist dies Baumbildung und Elemente in der Baumplatzierung. Da sich Elemente ständig bewegen, muss ich jede Schleife neu erstellen, bis eine Stoppbedingung erreicht ist. Aber wenn ich viel Zeit damit verbringen werde, einen Baum zu schaffen, werde ich dort Zeit verlieren. Das ist zumindest mein Denken. Dies ist, wie ich Elemente in meinem Haupt-Datei Schleife fügt hinzu:

void AddTreeElements(Octree* tree, glm::vec3* boundries, Graph& graph) 
{ 
    for(auto& node:graph.NodeVector()) 
    { 
     node.parent_group = nullptr; 
     if(node.pos[0] < boundries[1][0] && node.pos[0] > boundries[0][0] && 
       node.pos[1] > boundries[4][1] && node.pos[1] < boundries[1][1] && 
       node.pos[2] < boundries[0][2] && node.pos[2] > boundries[3][2]) 
     { 
      tree->AddObject(&node.second); 
      continue; 
     } 

     if(node.pos[0] < boundries[0][0]) 
     { 
      boundries[0][0] = node.pos[0]-1.0f; 
      boundries[3][0] = node.pos[0]-1.0f; 
      boundries[4][0] = node.pos[0]-1.0f; 
      boundries[7][0] = node.pos[0]-1.0f; 
     } 
     else if(node.pos[0] > boundries[1][0]) 
     { 
      boundries[1][0] = node.pos[0]+1.0f; 
      boundries[2][0] = node.pos[0]+1.0f; 
      boundries[5][0] = node.pos[0]+1.0f; 
      boundries[6][0] = node.pos[0]+1.0f; 
     } 

     if(node.pos[1] < boundries[4][1]) 
     { 
      boundries[4][1] = node.pos[1]-1.0f; 
      boundries[5][1] = node.pos[1]-1.0f; 
      boundries[6][1] = node.pos[1]-1.0f; 
      boundries[7][1] = node.pos[1]-1.0f; 
     } 
     else if(node.pos[1] > boundries[0][1]) 
     { 
      boundries[0][1] = node.pos[1]+1.0f; 
      boundries[1][1] = node.pos[1]+1.0f; 
      boundries[2][1] = node.pos[1]+1.0f; 
      boundries[3][1] = node.pos[1]+1.0f; 
     } 

     if(node.pos[2] < boundries[3][2]) 
     { 
      boundries[2][2] = node.pos[2]-1.0f; 
      boundries[3][2] = node.pos[2]-1.0f; 
      boundries[6][2] = node.pos[2]-1.0f; 
      boundries[7][2] = node.pos[2]-1.0f; 
     } 
     else if(node.pos[2] > boundries[0][2]) 
     { 
      boundries[0][2] = node.pos[2]+1.0f; 
      boundries[1][2] = node.pos[2]+1.0f; 
      boundries[4][2] = node.pos[2]+1.0f; 
      boundries[5][2] = node.pos[2]+1.0f; 
     } 
    } 
} 

Was ich hier tue gehen durch alle meine Elemente in Graph ist und fügen Sie sie in Baumwurzel. Außerdem erweitere ich meine Box, die meine Octree-Grenzen für die nächste Schleife darstellt, so dass alle Knoten hineinpassen.

Felder sind wichtig Struktur Update OCTREE wie folgt:

Octree* trees[2][2][2]; 
glm::vec3 vBoundriesBox[8]; 
bool leaf; 
float combined_weight = 0; 
std::vector<Element*> objects; 

und Teil des Codes verantwortlich für Update: nicht

#define MAX_LEVELS 5 

void Octree::AddObject(Element* object) 
{ 
    this->objects.push_back(object); 
} 

void Octree::Update() 
{ 
    if(this->objects.size()<=1 || level > MAX_LEVELS) 
    { 
     for(Element* Element:this->objects) 
     { 
      Element->parent_group = this; 
     } 
     return; 
    } 

    if(leaf) 
    { 
     GenerateChildren(); 
     leaf = false; 
    } 

    while (!this->objects.empty()) 
    { 
     Element* obj = this->objects.back(); 
     this->objects.pop_back(); 
     if(contains(trees[0][0][0],obj)) 
     { 
      trees[0][0][0]->AddObject(obj); 
      trees[0][0][0]->combined_weight += obj->weight; 
     } else if(contains(trees[0][0][1],obj)) 
     { 
      trees[0][0][1]->AddObject(obj); 
      trees[0][0][1]->combined_weight += obj->weight; 
     } else if(contains(trees[0][1][0],obj)) 
     { 
      trees[0][1][0]->AddObject(obj); 
      trees[0][1][0]->combined_weight += obj->weight; 
     } else if(contains(trees[0][1][1],obj)) 
     { 
      trees[0][1][1]->AddObject(obj); 
      trees[0][1][1]->combined_weight += obj->weight; 
     } else if(contains(trees[1][0][0],obj)) 
     { 
      trees[1][0][0]->AddObject(obj); 
      trees[1][0][0]->combined_weight += obj->weight; 
     } else if(contains(trees[1][0][1],obj)) 
     { 
      trees[1][0][1]->AddObject(obj); 
      trees[1][0][1]->combined_weight += obj->weight; 
     } else if(contains(trees[1][1][0],obj)) 
     { 
      trees[1][1][0]->AddObject(obj); 
      trees[1][1][0]->combined_weight += obj->weight; 
     } else if(contains(trees[1][1][1],obj)) 
     { 
      trees[1][1][1]->AddObject(obj); 
      trees[1][1][1]->combined_weight += obj->weight; 
     } 
    } 

    for(int i=0;i<2;i++) 
    { 
     for(int j=0;j<2;j++) 
     { 
      for(int k=0;k<2;k++) 
      { 
       trees[i][j][k]->Update(); 
      } 
     } 
    } 
} 

bool Octree::contains(Octree* child, Element* object) 
{ 
    if(object->pos[0] >= child->vBoundriesBox[0][0] && object->pos[0] <= child->vBoundriesBox[1][0] && 
     object->pos[1] >= child->vBoundriesBox[4][1] && object->pos[1] <= child->vBoundriesBox[0][1] && 
     object->pos[2] >= child->vBoundriesBox[3][2] && object->pos[2] <= child->vBoundriesBox[0][2]) 
     return true; 
    return false; 
} 

Weil ich Zeiger verwende ich um Baumelemente zu bewegen, tun denke, dass die Erstellung/Zerstörung von Objekten hier ein Problem darstellt. Der einzige Ort, wo ich Einfluss auf die Geschwindigkeit haben annehmen könnte, ist diese:

Element* obj = this->objects.back(); 
this->objects.pop_back(); 
if(contains(trees[0][0][0],obj)) 

Obwohl ich nicht sicher bin, wie ich ommit kann/Geschwindigkeit es auf. Hat jemand Vorschläge, was hier gemacht werden kann?

EDIT:

ich einige Serviette Mathe getan habe, und ich nehme an, sich ein weiterer Platz ist die Hauptgeschwindigkeitsabnahme verursacht werden könnte. Boundries in Update Methode Überprüfung sieht aus wie eine Menge zu tun und was ich berechnet, dass die zusätzliche Komplexität zu dieser wegen in schlimmsten Fall ist:

number_of_elements * number_of_childern * number_of_faces * MAX_LEVELS

was in meinem Fall ist gleich zu Anzahl_der_ Elemente * 240.

Kann jemand bitte bestätigen, wenn meine Idee vernünftig ist?

Answer 1

Wenn ich richtig verstanden habe, speichern Sie einen Vektor von Zeigern in jedem einzelnen Octree-Knoten?

std::vector<Element*> objects; 

...

void Octree::AddObject(Element* object) 
{ 
    this->objects.push_back(object); 
} 

Als ich von diesem Code zu verstehen, für OCTREE Gebäude, Ihre Elternknoten pop_back Element Zeiger von einem übergeordneten Vektor und beginnen wieder zu übertragen, die entsprechenden Elemente an die Kinder drängen .

Wenn das der Fall ist, kann ich sofort sagen, dass dies ein großer Engpass ohne Messen ist, da ich schon früher mit solchen Octree-Implementierungen gearbeitet habe und deren Cache um mehr als das Zehnfache verbessert habe Einfach verknüpfte Liste, die in diesem speziellen Fall die beteiligten Heapzuweisungen/Deallocations signifikant reduziert und sogar die räumliche Lokalität im Vergleich zu einer Bootsladung von winzigen vectors (eine pro Knoten) verbessert. Ich sage nicht, dass es der einzige Engpass ist, aber es ist definitiv ein bedeutender.

Also, wenn das der Fall ist, ist es das, was ich vorschlagen:

struct OctreeElement 
{ 
    // Points to next sibling. 
    OctreeElement* next; 

    // Points to the element data (point, triangle, whatever). 
    Element* element; 
}; 

struct OctreeNode 
{ 
    OctreeNode* children[8]; 
    glm::vec3 vBoundriesBox[8]; 

    // Points to the first element in this node 
    // or null if there are none. 
    OctreeElement* first_element; 

    float combined_weight; 
    bool leaf; 
}; 

Dies ist eigentlich nur ein erster rudimentär Pass sollte aber viel helfen. Wenn Sie dann ein Element von einem übergeordneten Element in ein untergeordnetes Element übertragen, gibt es kein Zurück- und Zurückspringen und keine Heapzuweisungen. Sie manipulieren nur Zeiger. Um ein Element von Eltern auf das Kind zu übertragen:

// Pop off element from parent. 
OctreeElement* elt = parent->first_element; 
parent->first_element = elt->next; 

// Push it to the nth child. 
elt->next = children[n]; 
children[n]->first_element = elt; 

Wie Sie aus den oben genannten, mit der verknüpften Darstellung sehen können, alles, was wir tun müssen, um 3-Zeiger manipulieren von einem Knoten zu einem anderen zu übertragen - keine Heapzuweisungen Es ist nicht erforderlich, die Größe zu erhöhen, die Kapazität zu überprüfen usw. Außerdem reduzieren Sie den Aufwand für das Speichern der Elemente auf einen Zeiger pro Knoten und einen Zeiger pro Element. Ein Vektor pro Knoten neigt dazu, bei der Speicherbenutzung ziemlich explosiv zu sein, da Vektor oft sagen kann, mehr als 32 Bytes, selbst wenn er nur standardmäßig erstellt wird, da viele Implementierungen etwas Speicher zusätzlich zum Speichern des Datenzeigers, der Größe und der Kapazität vorbelegen.

Es gibt noch viel Raum für Verbesserungen, aber dieser erste Durchlauf sollte viel helfen, vor allem wenn Sie das OctreeElement * mit einem effizienten Allokator (freie Liste oder sequenzieller Allokator) zuweisen oder in einer stabilen Datenstruktur speichern Zeiger werden nicht ungültig, aber bietet einige Kontiguität, wie std::deque. Wenn Sie bereit sind, etwas mehr Arbeit zu verrichten, verwenden Sie std::vector, um alle Elemente (alle Elemente für den gesamten Baum, nicht einen Vektor pro Knoten) zu speichern und verknüpfen Sie die Elemente mithilfe von Indizes in diesem Vektor statt mit Zeigern. Wenn Sie Indizes anstelle von Zeigern für die verknüpfte Liste verwenden, können Sie alle Knoten zusammenhängend speichern, ohne Speicherzuweiser zu beschäftigen, indem Sie nur einen großen alten vector verwenden, um alles zu speichern sowie die Speicheranforderungen für die Verknüpfungen zu halbieren (unter der Annahme von 64-Bit-Zeigern und die 32-Bit-Indizes sind stattdessen ausreichend, wenn Sie Indizes verwenden könnten).

Wenn Sie 32-Bit-Indizes verwenden, benötigen Sie möglicherweise auch nicht alle 32-Bits. An diesem Punkt können Sie beispielsweise 31-Bits verwenden und den Booleschen Wert leaf übernehmen, was der Größe des Knotens viel hinzufügt (etwa 4 Bytes mit Polsterung und den Ausrichtungsanforderungen der Zeiger 64-Bit für dieses Boolesche Feld) in das erste Element unter der Annahme, oder nur den ersten Kind Index -1 gesetzt Blätter, um anzuzeigen, etwa so:

struct OctreeElement 
{ 
    // Points to the element data (point, triangle, whatever). 
    int32_t element; 

    // Points to next sibling. 
    int32_t next; 
}; 

struct OctreeNode 
{ 
    // This can be further reduced down to two 
    // vectors: a box center and half-size. A 
    // little bit of arithmetic can still improve 
    // efficiency of traversal and building if 
    // the result is fewer cache misses and less 
    // memory use. 
    glm::vec3 vBoundriesBox[8]; 

    // Points to the first child. We don't need 
    // to store 8 indices for the children if we 
    // can assume that all 8 children are stored 
    // contiguously in an array/vector. If the 
    // node is a leaf, this stores -1. 
    int32_t children; 

    // Points to the first element in this node 
    // or -1 if there are none. 
    int32_t first_element; 

    float combined_weight; 
}; 

struct Octree 
{ 
    // Stores all the elements for the entire tree. 
    vector<OctreeElement> elements; 

    // Stores all the nodes for the entire tree. The 
    // first node is the root. 
    vector<OctreeNode> nodes; 
}; 

Dies ist alles noch sehr rudimentär und es gibt so viel Raum für Verbesserungen, die ich in einer Antwort nicht wirklich abdecken kann, aber nur diese wenigen Dinge zu tun sollte schon viel helfen, beginnend mit der Vermeidung einer separaten vector pro Knoten als Ihre größte Verbesserung.

verketteten Listen für Reduced Heapzuweisungen und verbesserte Lokalität Referenz

Dieses etwas, das ich wie eine Menge von C fühlen ++ Entwickler mit denen ich in der Vergangenheit gearbeitet habe, haben entweder vergessen oder vielleicht nie gelernt, sondern verknüpft Listen müssen nicht immer zu erhöhten Heapzuweisungen und Cache-Misses führen, insbesondere wenn für jeden Knoten keine separate Heap-Zuweisung erforderlich ist.Wenn der Punkt des Vergleichs eine Bootsladung von Teeny-Vektoren ist, dann werden verkettete Listen tatsächlich Cache-Misses reduzieren und Heap-Zuordnungen reduzieren. Nehmen Sie dieses einfaches Beispiel:

Und sagen wir mal, die eigentliche Gitter 10.000 Zellen hatte. In diesem Fall wird das Speichern eines 32-Bit-Index pro Zelle und das Verknüpfen von Elementen unter Verwendung von 32-Bit-Indizes, die in einem großen Array (oder einem großen vector) gespeichert sind, viel billiger und erfordern viel weniger Speicherzuweisungen als typischerweise viel weniger Speicher) als das Speichern von 10.000 Vektoren. Vector ist eine ausgezeichnete Struktur zum Speichern nicht-trivialer Datenmengen, aber es ist nicht etwas, das Sie zum Speichern einer Bootsladung von Teeny-Listen variabler Größe verwenden möchten. Einzeln verknüpfte Listen können bereits eine wesentliche Verbesserung darstellen und eignen sich sehr gut, um Elemente in konstanter Zeit und spottbillig von einer Liste in eine andere zu übertragen, da nur 3 Zeiger (oder 3 Indizes) ohne zusätzliche Verzweigung manipuliert werden müssen .

So gibt es noch viel Verwendung für verknüpfte Listen. Sie sind besonders nützlich, wenn Sie sie tatsächlich so verwenden, dass die Heapzuweisungen reduziert und nicht erhöht werden.