八叉樹實現的速度問題

Question

現在我試圖加速我的Force-Directed圖形實現。到目前爲止，我已經實現了使用八叉樹來減少計算次數的Barnes-Hut算法。我已經多次測試過，並且與力相關的計算次數確實大幅減少。下面是沒有Barns-Hut（藍線）和（紅線）的節點數的計算圖： 即使現在它應該快得多，事實是，在速度（時間）的問題上，升級只有百分之幾。

我想這可能是造成這種情況的一個部分，就是樹的創建和樹中的元素放置。由於元素不斷移動，我需要在每個循環中重新創建樹，直到達到一些停止條件。但是如果我會花很多時間來創建樹，那麼我會在那裏花費大量時間來增加強制計算。至少這是我的想法。這是我如何在我的主文件循環添加元素：

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; 
     } 
    } 
} 

我在做什麼這裏是經過我在圖中的所有元素，並將它們添加到樹的根部。另外，我正在擴展代表下一個循環的八叉樹邊界的方框，因此所有節點都將適合內部。如下所示

字段以八叉樹更新重要：

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

，並負責更新代碼的一部分：

#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; 
} 

因爲我使用的指針圍繞樹移動元素我不認爲對象創建/銷燬是一個問題。一個地方，我想可能對速度的影響是這一個：

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

雖然我不知道我該怎麼ommit /加快速度。有人有什麼建議可以在這裏做什麼？

編輯：

我已經做了一些餐巾數學，我想還有一個地方可能會造成重大的速度下降。 Boundries在Update方法如下檢查就像是做了很多，我的計算是，由於這種增加的複雜性是在最壞的情況下：

number_of_elements * number_of_childern * number_of_faces * MAX_LEVELS

這在我的情況下，等於到number_of_elements * 240。

有人可以確認我的想法是否合理嗎？

Answer 1

如果我理解正確，你在每一個八叉樹節點存儲一個指針向量？

std::vector<Element*> objects; 

...

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

當我從這段代碼的理解，對八叉樹大廈，你父節點pop_back元素的指針從父向量，並開始推回至適當的元素傳遞給孩子。如果是這種情況，我可以立即說這是一個甚至沒有測量的主要瓶頸，因爲我之前已經處理了這種八叉樹實現，並將它們的建築改進了10倍以上，並且通過簡單地使用單鏈表，在這種特殊情況下，與一堆小型的vectors（每個節點一個）相比，這大大減少了涉及的堆分配/釋放以及甚至改善了空間局部性。我並不是說這是唯一的瓶頸，但它絕對是一個重要的瓶頸。

所以，如果是這樣的話，這是我的建議：

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; 
}; 

這其實只是一個初步的第一傳，但應該有很大的幫助。然後，當您將一個元素從父項轉移到子項時，不會推回並彈出，也不會有堆分配。你所做的只是操縱指針。若要從父傳遞一個元素的孩子：

// 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; 

正如你可以從上面看到，與聯表示，我們需要做的是操縱3個指針轉移從一個節點到另一個節點 - 無堆分配，無需增加大小，檢查容量等。此外，您可以減少將元素存儲到每個節點一個指針和每個元素一個指針的開銷。每個節點的一個向量在內存使用上往往會相當具有爆炸性，因爲即使只是默認構造，vector往往可以採用32+字節，因爲許多實現會在必須存儲數據指針，大小和容量之前預先分配一些內存。

還有很多需要改進的空間，但如果您使用高效的分配器（自由列表或順序分配器，例如）分配OctreeElement *或將它們存儲在穩定的數據結構中，不會使指針失效，但會提供一些連續性，如std::deque。如果你願意做更多的工作，使用std::vector來存儲所有元素（整個樹的所有元素，而不是每個節點一個向量），並使用索引將元素鏈接在一起，而不是指針。如果使用索引而不是指針指向鏈接列表，則可以連續存儲所有節點，而不必使用內存分配器，只需使用一個大的舊vector來存儲所有內容並將鏈接的內存需求減半（假設64位指針和如果您可以使用索引，那麼32位索引就足夠了）。

如果使用32位的索引，你也可能並不需要所有32位，在這一點上，你可以使用，比如說，31位和掖是leaf布爾其中加入了很多的節點的大小（周圍的4個字節與填充和指針的對準要求假設64位爲布爾型字段）插入所述第一元件或只設置第一個子索引-1以指示葉，像這樣：

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; 
}; 

這是所有仍然非常簡陋，有一種我不能在一個答案中真正覆蓋的改善空間，但只是做這些事情應該已經有很大幫助，從避免單獨的每個節點的是您最大的改進。

爲減少堆分配和參考

的改進局部性鏈表這是我覺得像很多C++開發人員，我在過去要麼忘記或工作也許從來沒有學過，但聯繫列表不必總是轉化爲增加的堆分配和緩存未命中，特別是當每個節點不需要單獨的堆分配時。如果比較的重點是少量載體，那麼鏈接列表實際上會減少緩存未命中並減少堆分配。拿這個簡單的例子：

而且我們說的實際電網有10000個細胞。在這種情況下，每個單元存儲32位索引並使用存儲在一個大陣列中的32位索引將元素鏈接在一起（或者一個大的vector）將會便宜得多，並且需要更少的內存分配（以及作爲通常少得多的內存）比存儲10,000個向量。向量是存儲不重要數據量的優秀結構，但它不是您想要用於存儲少量可變大小列表的東西。單鏈表可能已經有了很大的改進，並且它們非常適合以恆定時間和廉價的方式將元素從一個列表轉移到另一個列表，因爲只需要操縱3個指針（或3個索引）而不需要任何額外的分支。

因此，鏈接列表還有很多用處。當您真正以減少而不是增加堆分配的方式使用它們時，它們特別有用。