局部性和共享訪問對象

分析我的代碼，我看到很多緩存未命中，並想知道是否有辦法改善這種情況。優化並不是真的需要，我更加好奇是否存在這個問題的一般方法（這是一個後續問題）。局部性和共享訪問對象

// class to compute stuff 
class A { 
    double compute(); 
    ... 
    // depends on other objects 
    std::vector<A*> dependencies; 
}

我有一個容器類，它存儲指向所有創建的類A的對象的指針。我不存儲副本，因爲我想共享訪問權限。在我使用shared_ptr之前，但如果沒有容器，單個A沒有意義，原始指針就沒有問題。

class Container { 
    ... 
    void compute_all(); 
    std::vector<A*> objects; 
    ... 
}

矢量objects是插入的方式，全面評估可以通過簡單的迭代和調用A.compute()進行排序，因此所有的依賴關係都解決了。

隨着A類的a_i對象，評估可能是這樣的：

a_1 => a_2 => a_3 --> a_2 --> a_1 => a_4 => ....

其中=>表示在Container迭代和 - >迭代過A::dependencies

此外，創建容器類只有一次，並且compute_all（）被調用很多次，因此在創建後重新整理整個結構是一個選項，並且不會損害效率。

我們的意見/問題：

顯然，遍歷Container::objects是緩存效率，但訪問指針對象絕對不是。
而且，由於A類型的每個對象都必須遍歷A::dependencies，這又會導致緩存未命中。

它是否有助於創建在評估順序所有需要的對象單獨vector<A*>使得A依賴插入的副本？

事情是這樣的：

a_1 => a_2 => a_3 => a_2_c => a_1_c => a_4 -> ....

其中a_i_c來自A_I副本。

感謝您的幫助和抱歉，如果這個問題令人困惑，但我覺得從簡單的例子推斷到大型應用程序很困難。

來源

2011-04-22 bbtrb

檢查這一個標準庫（我認爲提升了一些好的，EASTL圍繞這個概念居中）：HTTP：/ /stackoverflow.com/questions/460666/decreasing-cache-misses-through-good-design – AJG85 2011-04-22 15:36:13

這絕對不是C的問題。 – Puppy 2011-04-22 19:12:26

不幸的是，我不確定我是否正確理解你的問題，但我會盡力回答。

緩存未命中是由於處理器要求數據分散在整個內存中造成的。

增加緩存命中率的一種常見方式就是組織數據，以便順序訪問的所有內容位於內存的相同區域。從你的解釋來看，我認爲這很可能是你的問題。你的A物體分散在各處。

如果您每次只需撥打一個A即可撥打常規電話new，那麼您最終可能會分散您的所有A對象。

您可以爲將要創建很多次，順序訪問對象自定義分配器。這個自定義分配器可以分配大量的對象，並根據請求提交它們。這可能與重新排序數據的含義類似。

它可以採取一些工作但實現這一點，因爲你必須要考慮，如當它運行的對象，它是如何知道哪些對象已經遞出，等會發生什麼情況。

// This example is very simple. Instead of using new to create an Object, 
// the code can just call Allocate() and use the pointer returned. 
// This ensures that all Object instances reside in the same region of memory. 
struct CustomAllocator { 
    CustomAllocator() : nextObject(cache) { } 

    Object* Allocate() { 
     return nextObject++; 
    } 

    Object* nextObject; 
    Object cache[1024]; 
}

另一種方法涉及對連續數據進行處理的緩存操作，但不是按順序執行。我認爲這是你擁有一個單獨的載體的意思。

然而，要明白，你的CPU不只是保持一個內存部分緩存在一個時間是非常重要的。它保存了多段內存緩存。

如果你在另一部分來回跳躍的一個部分，在數據運算操作之間的數據，這很可能不會導致很多緩存命中率;你的CPU可以並且應該保持這兩個部分同時被緩存。

如果你操作之間的50組不同的數據的跳躍，你可能會遇到很多高速緩存未命中。在這種情況下，緩存操作將是有益的。

在你的情況，我不認爲高速緩存操作將會給你帶來多少好處。確保所有的A對象都駐留在同一段內存中，但是，可能會。

要考慮的另一件事是線程，但這可能會變得非常複雜。如果您的線程正在執行很多上下文切換，則可能會遇到很多緩存未命中。

來源

2011-04-22 16:23:58

+1建檔第一:)

邊使用cusomt分配器可以是正確的解決方案，我肯定第一個推薦兩件事情：

參考/指針保持到整個矢量的A而不是A *的載體：

。

class Container { 
    ... 
    void compute_all(); 
    std::vector<A>* objects; 
    ... 
}

使用自定義的分配

$ 0.02

來源

2011-04-22 18:19:44 sehe

局部性和共享訪問對象

回答

相關問題