神祕指針相關的多線程放緩

背景：所以我工作的光線跟蹤。對於我的建築空間分區方案，我最初有一些像這樣的代碼：神祕指針相關的多線程放緩

if (msize <= 2) { // create a leaf node 
    Model **models = new Model*[msize]; 
    for (uint i=0; i<msize; ++i) 
     models[i] = &mlist[i]; 
    *arrayPtr = Node(models, msize); // class Node contains a copy of models 
    ... increment arrayPtr ... 
    return; 
}

基本上，這個空間後，構建分區樹，射線遍歷尋找模型的樹，這些模型都存儲在一個大陣列中。葉節點包含指向模型的指針陣列的指針。

然後我意識到，嘿，我沒有理由增加額外的間接級別;如果我正確安排我的模型，我可以讓葉節點直接指向大型模型。大陣列中彼此相鄰的模型都屬於給定的葉節點，因此葉子將包含指向模型的指針。所以我做了這個，並測試了其他一切保持不變的情況。

現在人們會認爲這顯然會加快程序。嗯，它加快了單線程版本（減少了大約10％），但是它減慢了多線程版本的速度（減少了大約15％！如果你正在進行繁重的優化，這是非常重要的）。如何解決這個問題 - 我認爲間接是不好的，我認爲減少內存使用是好的，尤其是多線程..沒有寫入任何葉節點或模型，所有的寫作是完成一個單獨的數據結構。

任何關於如何分析問題的指針/建議都會很棒。

一些雜項統計信息：cachegrind告訴我，雙重間接方法的指令引用/緩存未命中少，但更多的數據引用/緩存未命中。兩者的差別並不大。

編輯：按照要求，我所關注的數據結構：

class Node { 
    ushort type; 
    union { 
     ushort axisID; 
     ushort childrenSize; 
    }; 
    union { 
     Model **models; 
     Node *rightChild; 
    }; 
    float leftPlane, rightPlane; 
    ... public methods and stuff ... 
}

我基本上改變Model **models到Model *models，然後我得到的速度下降。類Model本身包含一個指向兩個抽象類的指針，Shape和Material。這裏提到的所有類都是塊分配的，除了Material之外，因爲目前我只使用一個類。

來源

2009-11-06 int3

你可以發佈你正在比較的兩個版本的數據結構嗎？ – 2009-11-06 19:41:58

別名問題，也許？當我在C/C++中看到一個聯合時，這幾乎總是我的第一個想法。分析器說哪個特定功能變慢？你看過反彙編，看看有沒有差異嗎？ – jalf 2009-11-06 20:19:36

你如何在線程之間共享數據？ – Malkocoglu 2009-11-06 20:30:58

我的第一個猜測是你碰到了false-sharing。如果您有多個線程同時修改同一緩存行中的內存，則硬件將花費大量時間在處理器之間傳遞緩存行的所有權。

來源

2009-11-06 18:49:07

但我的節點和模型都是塊分配......嗯..在這種情況下如何發生虛假共享？ – int3 2009-11-06 18:54:48

據我瞭解，任何線程都不會修改有問題的數據，這將排除錯誤的共享。儘管這是我的第一個想法。 – jalf 2009-11-06 20:31:52

在同一個總線週期中讀取同一個緩存行的爭用情況如何？我認爲L1緩存是單端口的。 – 2009-11-09 19:50:45

我會尋找的最大的事情是一些不正確的初始化，要麼重複數據要麼有不正確的共享數據。代碼中不明顯，但從**到*時顯然是錯誤的。

來源

2009-11-09 07:16:55

另一個問題是減速是來自增加的間接性還是改變了你如何分配struct Model。因爲您現在將結構分配爲連續的內存區域，所以相鄰結構可能共享相同的緩存行。如果你的線程正在同時訪問相鄰的結構體，那麼它將競爭訪問。在等待另一個讀取訪問時，一個讀取訪問將停止一個公共汽車循環。

什麼是sizeof(class Model)？您可以嘗試使用虛擬變量進行擴展，直到類爲緩存行的大小。

另一種可能性是您已更改您正在訪問的成員變量的對齊方式。如果您的sizeof(class Model)不是您機器字數的倍數（例如，8字節），那麼這些對象的數組將會有一些成員與字大小對齊，有些則不是。由於讀取單元從對齊的存儲器位置讀取機器字，並將這兩個讀取中的編址值合成，所以未對準會在存儲器總線上引起雙重讀取。

來源

2009-11-09 19:58:42

神祕指針相關的多線程放緩

回答

相關問題