在C大結構緩存局部性

如果我有一個鏈接結構是這樣的：在C大結構緩存局部性

struct phonebook { 
    char LastName[16]; 
    char FirstName[16]; 
    char Email[16]; 
    char PhoneNumber1[10]; 
    char PhoneNumber2[10]; 
    char Addr1[16]; 
    char Addr2[16]; 
    char City[10]; 
    char Country[12]; 
    char State[2]; 
    struct phonebook *pNext; 
}

，當我想要搜索的人匹配姓氏，
我可以使用

while (pHead != NULL) { 
    if (strcasecmp(lastname, pHead->LastName) == 0) 
      return pHead; 
    pHead = pHead->pNext; 
} 

return NULL;

東西像這樣，但每次我得到一個電話簿節點時，緩存都會加載整個結構並且緩存會丟失很多。
那麼，如何增加緩存命中率呢？
如何在緩存中分組LastName？

沒有熱/冷或中斷鏈表到鏈式散列表中。

來源

2015-10-06 tonyyanxuan

請參閱[這個問題重新AoS與SoA]（http://stackoverflow.com/questions/5323154/which-kind-of-data-organization-using-c-arrays-makes-fastest-code-and-why/5323220＃5323220）。 –

當你說'高速緩存將加載整個結構和高速緩存未命中'，是你的猜測或實際分析的結果？這是不太可能的（儘管不是完全不可能的），電話簿應用程序對性能敏感，明顯受到緩存未命中的影響。 – ach

當您使用O（n）查找算法時，無需擔心緩存性能。這是一個難以解決的問題，因爲從緩存和操作複雜性角度來看，'正確'的答案是使用散列表。 – QuestionC

正如你所指出的，在一般情況下，你鏈表中的每個節點可以指向一個完全不同的地址範圍，導致高速緩存未命中。

如果在構建列表時整個存儲器空間不整齊，即使單個節點不存在（假設您將節點插入到鏈中間的某個頻率），整個存儲器結構的內存空間也可能是連續的。如果你的堆在這一點上是碎片化的，這個列表將會進一步擴展。

如果您正在運行到一個支離破碎的堆，但知道鏈表將大約有多大，你可以在程序開始時預先分配的內存大塊，並根據需要分分配它。這可能會浪費RAM，但會減少緩存缺失，而不是針對已經分散存儲的堆分配節點的情況。

TCMalloc還可以提供改進的緩存命中率，因爲它是非常節省空間的用於小型分配。它還會嘗試在同一個4K內存頁面中保留連續的小分配。

如何提高搜索

如果你的鏈接列表的排序方式，它只是一個標準排序。您可以維護一個單獨的數據結構（例如哈希表），該結構將特定搜索關鍵字（例如LastName + FirstName）映射到鏈接列表中該節點的指針。這在概念上類似於數據庫如何具有表示行的物理排序的聚集索引以及針對不同搜索條件（可通過電子郵件，電話，名稱搜索）的潛在多個非聚集索引。

來源

2015-10-06 17:52:26

預先分配使它們在RAM中更密集。但我仍然需要將其他部分（如FirstName，Addr1，Addr2 ...）加載到緩存中。當我只需要這個結構中的一小部分信息時，錯失率仍然很高。 – tonyyanxuan

作爲一個小改進，你可以看看你的結構是如何被打包的。您的陣列可能使用默認設置在32位或64位邊界上啓動。鑑於您當前的字段大小，打包到字節或字邊界會略微減小每個結構的大小，稍微提高緩存局部性。 –

每當我收到一個電話簿節點時，緩存將加載整個結構並緩存未命中。那麼，我該如何增加緩存命中率呢？如何在緩存中分組LastName？

C要求每個結構對象的成員在內存中連續佈局（但不一定是連續的）。因此，即使在您認爲結構本身可能不連續之前，各種結構的LastName陣列也會散佈在內存中。你不能改變它，因爲它是由C指定的。

你可以，然而，創建索引由較小的結構的動態數組，如

struct pb_index { 
    char LastName[16]; 
    struct phonebook *entry; 
}

的LastName陣列將是動態陣列內更密比phonebook秒的陣列內，所以通過這樣的數組掃描將比使用鏈表掃描更高效地使用緩存。

所有這一切，設置和維護它看起來像一個相當可觀的工作量，可能收益很少。如果你有效率問題，那麼使用提供更高效訪問的數據結構會更好。散列表或搜索樹可能適合。

來源

2015-10-06 18:05:17

我認爲這是一種熱/冷方法？如果我不想要這個結構呢？是否有可能這樣做，使姓氏數組更密集。 – tonyyanxuan

@tonyyanxuan你可以修改你的'phonebook'結構，或者你可以完全使用不同的結構（如我的答案），但是你不能不改變現有的結構來獲得整個數組中更高密度的LastName，或者分配給它的內存的任何部分。正如我所說的，C指定一個結構的所有成員必須作爲一個組在存儲器中進行佈局，因此在相鄰的'struct phonebook'對象的每對'LastName'之間將是'struct phonebook'的所有其他成員，也許還有一些填充。 –

在C大結構緩存局部性

回答

相關問題