C++結構：成員越多，成員訪問時間越慢？

我有一個鏈接的結構列表。比方說，我將x百萬個節點插入鏈表，然後遍歷所有節點以找到給定值。C++結構：成員越多，成員訪問時間越慢？

奇怪的是（至少對我來說），如果我有這樣的結構：

struct node 
    { 
    int a; 
    node *nxt; 
    };

那麼我可以遍歷槽列表並檢查在10倍速度的值進行比較時，我有另一名成員的結構，像這樣：

struct node_complex 
    { 
    int a; 
    string b; 
    node_complex *nxt; 
    };

我也使用C風格的字符串（char數組）試了一下，結果是一樣的：只是因爲我有其他成員（串），全迭代（+值檢查）慢了10倍，即使我甚至沒有碰過那個成員！現在，我不知道結構的內部結構如何工作，但它看起來像一個高昂的代價...

有什麼收穫？

編輯：我是一個初學者，這是我第一次使用指針，因此機會是，這個錯誤是我的一部分。我會盡快發佈代碼（現在不在家）。

更新：我再次檢查了值，我知道看到一個更小的差異：2x而不是10x。肯定更合理。

儘管昨天也是這樣，昨天晚上我太累了，我不能分兩個數字，我只是做了更多的測試，結果令人興奮。

的次爲一相同數量的節點是：

一個int和一個指針來迭代波谷的時間是0.101
一個int和一個字符串：0.196
一個int和2字符串：0.274
一個int和3字符串：0.147（!!!）
對於兩個整數，它是：0.107

看看結構中有多於兩個字符串時會發生什麼！它變得更快！有人將LSD放入我的咖啡？沒有！我不喝咖啡。

這對我的大腦來說太方便了，所以我想我會自己弄清楚，而不是在這裏排除公共資源。（Ad：我不認爲我的分析班是越野車，無論如何，我可以用我自己的眼睛看到時間差異）。

無論如何，謝謝你的幫助。乾杯。

來源

2010-09-24 johnny-john

您確定這是您測量的純迭代時間，不包括列表元素的創建時間嗎？創建一個字符串比創建一個int要昂貴得多。你有嘗試過兩個'int'字段嗎？ – 2010-09-24 10:43:07

請發佈鏈接列表結構的代碼 – 2010-09-24 10:43:32

@PéterTörök：我確定。創建時間不包含在測量中。我還沒有嘗試過兩個int字段，但會。 – 2010-09-24 10:44:31

我必須與內存訪問相關。你提到了一百萬個鏈接元素。在節點中只有一個int和一個指針，它需要8個字節（假設32位指針）。這佔用8 MB內存，大約是緩存內存大小。

當您添加其他成員時，您會增加數據的整體大小。它不再適用於緩存內存。您將恢復到速度較慢的普通內存訪問。

來源

2010-09-24 10:52:32

+1在緩存未命中時比我更好的解釋！ – Klaim 2010-09-24 10:55:32

此外，較大的記錄可能會使用更多的TLB條目，可能會觸發一些TLB抖動。 – ConcernedOfTunbridgeWells 2010-09-24 12:39:59

我認爲總高速緩存大小並不重要，因爲數據已經很分散，幾乎每個節點在第一次訪問時都會出現高速緩存未命中，並且由於它以後不再使用，所以沒有任何區別它稍後會從緩存中被逐出。最有可能的是，緩存未命中正在發生，至少佔部分緩慢，但不是因爲總緩存大小 – jalf 2010-09-24 13:19:02

也許解決方案將是指向您的對象的鏈接列表。它可能會使事情更加複雜（除非你使用智能指針等），但它可能會增加搜索時間可能。

來源

2010-09-24 10:48:32

我根本不是一個空間主義者，但是「緩存未命中」問題在閱讀您的問題時在我的腦海中響起。

當你有一個成員時，因爲它使得結構的大小變得更大，它也可能在通過鏈表時緩存未命中（如果你沒有在一個分組中分配節點，這自然是緩存不友好的在記憶中彼此距離不遠）。

我找不到另一個解釋。

但是，我們沒有提供創建和循環，因此如果您不僅僅是讓代碼不以有效的方式執行列表探索，那麼仍然很難猜測。

來源

2010-09-24 10:49:17 Klaim

這也可能是因爲在迭代過程中，您可能會在的處創建您的結構副本。即：

node* pHead; 
// ... 

for (node* p = pHead; p; p = p->nxt) 
{ 
    node myNode = *p; // here you create a copy! 
    // ... 
}

複製一個簡單的結構非常快。但是您添加的成員是string，這是一個複雜的對象。複製它是一個相對複雜的操作，具有堆訪問權限。

來源

2010-09-24 11:00:13 valdo

哎呀，我想我是那麼做的！將很快發佈代碼。 – 2010-09-24 12:26:13

最有可能的問題是，您的較大結構不再適合單個緩存行。我記得，主流CPU通常使用32字節的緩存行。這意味着數據一次以32個字節的塊形式讀入高速緩存，如果您移過這些32個字節，則需要第二次內存提取。從我的標準庫實現（從VS2010）開始，看看你的結構，它開始於一個int，佔4個字節（通常），然後std::string（我假設，即使命名空間沒有指定）佔用28個字節，總共給我們32個字節。這意味着最初的int和next指針將被放置在不同的緩存行中，使用兩倍的緩存空間，並且如果在迭代期間訪問這兩個成員，則需要兩倍的內存訪問。

如果只有指針被訪問，但這應該沒有什麼區別，因爲只有第二個高速緩存行必須從內存中檢索。

如果你始終可以訪問int和指針，並且需要串較少，重新排序的成員可能會有幫助：

struct node_complex 
{ 
    int a; 
    node_complex *nxt; 
    string b; 
};

在這種情況下，next指針和int都毗鄰各其他人，在同一個緩存行上，所以他們可以讀取而無需額外的內存讀取。但是一旦你需要閱讀string，你就會承擔額外的費用。

當然，您的基準測試代碼還可能包括創建節點，或創建節點的（有意或其他）副本，這顯然也會影響性能。

來源

2010-09-24 13:08:45 jalf

+1覆蓋所有基地 – 2010-09-24 13:51:31

C++結構：成員越多，成員訪問時間越慢？

回答

相關問題