多線程鏈表遍歷

給定一個（雙重）鏈接的對象列表（C++），我有一個操作，我希望多線程，執行每個對象。每個對象的操作成本並不統一。由於各種原因，鏈表是該組對象的首選存儲。每個對象中的第一個元素是指向下一個對象的指針;第二個元素是列表中的前一個對象。多線程鏈表遍歷

我已經通過構建節點數組並應用OpenMP解決了該問題。這給了體面的表現。然後，我切換到自己的線程例程（基於Windows原語），並通過使用InterlockedIncrement（）（作用於數組中的索引），我可以實現更高的整體CPU利用率和更快的吞吐量。從本質上講，這些線程通過沿着元素「跳躍式」進行工作。

我的下一個優化方法是嘗試消除創建/重用鏈表中的元素數組。但是，我想繼續使用這種「跳躍式」方法，並以某種方式使用一些不存在的例程（可以稱爲「InterlockedCompareDereference」）來自動比較NULL（列表結束）並有條件地取消引用存儲，並返回解除引用的值。

我不認爲InterlockedCompareExchangePointer（）將工作，因爲我不能原子取消引用指針並調用此Interlocked（）方法。我已經做了一些閱讀，其他人則提出了關鍵部分或自旋鎖。關鍵部分在這裏看起來很重。我很想嘗試旋轉鎖，但我想我會先在這裏提出問題，並詢問其他人在做什麼。我不相信InterlockedCompareExchangePointer（）方法本身可以像旋轉鎖一樣使用。那麼還必須考慮獲取/釋放/籬笆語義......

想法？謝謝！

來源

2012-09-25 Rob Bryce

關鍵部分並不是真正的重量。假設他們可以快速獲得鎖，就像旋轉鎖一樣。

問題的解決方案取決於您是否修改列表。如果你沒有修改列表，你所需要做的就是像InterlockedCompareExchange那樣將對象中的一個值初始化爲0.交換值爲1，如果你得到0，那麼你做你的動作，如果你返回1，你跳過。下一次您在列表中進行操作時，您將在2中進行交換並檢查1/2而不是0/1。

如果你正在改變列表，那麼這一切都取決於。如果你只想繼續前進，並且只刪除當前節點，那麼最好的辦法就是在執行比較交換位時進行鎖定的項目中有一個下一個鎖定，當跳過時（獲取它的下一個節點）和刪除時節點。

來源

2012-09-25 21:19:39 CrazyCasta

這對於少量的線程很有效，但是如果你例如考慮1000線程，你最終會得到一個內存障礙的_lot_，因爲「skipjumping」1000個條目是昂貴的（10000個列表項會少一點超過10M內存障礙） –

我沒有修改列表，只是希望有很多線程能夠有效地遍歷列表。 –

我覺得卡斯塔有一些很好的觀點，我會自己動手。這個問題的解決方案將大大減輕每個節點所做的思想轉換，無論它們是否相互依存，以及是否可以在單獨的列表中完成已完成的任務。

如果操作不相互依賴，並且清掃方法有意義，我提出了一箇中介取回系統。它幾乎與工作人員的方法相同。每個線程都交給一個代理管理列表的引用，由於每個線程都需要處理內容，因此它會從代理請求內容，鎖定，獲取下一個節點，提前內部掃描迭代器並釋放鎖定，返回節點到請求線程。這一直持續到列表枚舉完成。對於每個節點可能被不同線程訪問多次的累加器問題，可以使用循環列表或其他此類容器。有才華的經紀人可以按照發送的同一方式管理列表，包括新的插入，刪除等：鎖定，操作，解鎖。很明顯，許多活動都可以根據您在經紀商方面的具體需求量身定製。這些需求可以使精心設計的池管理系統成爲可能，同時在鎖定爭用方面仍然非常有效（即幾乎沒有）。

但是，底線有希望顯而易見。瞭解你的問題集以及你希望每個線程使用當前節點完成的具體細節。

來源

2012-09-25 21:36:37 WhozCraig

基本上，要儘可能快地瀏覽列表，您需要避免幾件事情;

鎖碰撞。即使使用自旋鎖，每次循環迭代都是錯過了完成工作的機會。
內存障礙。每次執行原子操作時，內存障礙都會停止執行。
不必要的工作，例如掃描要做的工作列表。

我必須同意你的看法，並採取自旋鎖的一面。

您將指針指向列表頭部的一個易失性指針。

然後每個線程依次;

注意到自旋鎖
指針保存指針的值在臨時
更新到下一個列表條目
發佈自旋鎖。

它可以開始在臨時指向的條目上工作。

這對使用每條輸入鎖尋找列表具有一些優點;

如果每個項目的工作需要花費很少的時間來完成，那麼在更新指針的持續時間短的情況下，您將幾乎沒有碰撞。
如果沒有碰撞，每個列表項只有2個內存屏障，一個用於鎖定，一個用於解鎖。
不掃描列表以獲取新工作項目，只需從「隊列」中獲取工作。

來源

2012-09-26 15:50:42

使用'CRITICAL_SECTION'時，你不需要'volatile'。鎖定關鍵的調用既是編譯器也是CPU屏障。 –

由於對齊，列表指針的低位包含零。通過使用比較和交換指令將對象標記爲正在處理，您可以通過在其中一個指針中原子級地設置其中一個位來利用該優勢。

每個線程會做：

開始遍歷從其頭部列表。
對於每個列表節點，檢查其下一個指針是否具有較低的位集。
如果該位設置爲goto 7.
比較並交換列表節點的下一個指針與(next | 1)。
如果比較和交換失敗goto 7。
處理對象。
移動到下一個節點，並轉到2.

另一種選擇是把該位標誌到具有在對象本身的未使用的比特的整數，除非列出的節點是基類或成員的對象。

通過這種方式，線程可以從列表中獲取對象，而不會阻止或忙於在wait-free fashion中旋轉。

來源

2012-09-26 16:37:06

多線程鏈表遍歷

回答

相關問題