111
Harris’s Linked List
在學術論文中Harris Linked List是使用最廣泛的並發數據結構之一。
Harris Linked List是一個基於linked-list的並發有序set（或者是map），可進行無鎖性質的插入，刪除和查找操作。
https://research.microsoft.com/pubs/67089/2001-disc.pdf
這篇文章最早在2001年的DISC會議上發表，作者是Tim Harris，目前在Oracle就職。
https://labs.oracle.com/pls/apex/f?p=labs:bio:0:296
除非你閱讀並發方麵的學術論文，否則你很可能不知道這個數據結構是什麼。主要原因是，雖然它是最快，最簡單的並發list-based-set，但是在我看來，卻是最不切實際的。
鏈表中的每個節點引用一個鍵值，節點的相對位置反映出它們所包含的鍵值在鏈表中的相對順序。在鏈表中，總是有兩個特殊的節點（永遠不會被刪除），一個是列表的開始，head，另一個是列表的表尾，tail。
Harris’s linked list就像一種中國的益智類玩具，即那種你可以玩一會兒，並且湊巧地解決了；但是當你重置它以後，你又需要幾個小時來再次解決它。Harris’s linked list並不隻包含一個技巧，而是有很多種技巧。
Harris’s linked list的技巧之一是設置指向下個節點的指針中的一位（one bit），將它標記為邏輯刪除。這就是問題所在。
自動管理內存的語言（Java, Scala, C#）是不能直接訪問一個指針中的一位的，並且很可能永遠都不行。
一種可能的實現是使用AtomicMarkableReference或者相近的技術，每當執行一次CAS時創建一個新的對象。新對象包含一個下一個節點的引用，和一個bit標誌位，它們都需要被定義為final類型。這樣的對象常量創建行為（譯者注：嚴格地來說這樣翻譯並不對，final類型並不意味著constant variable）意味著在Java中實現這種技術（非常）慢。
在Java中，另一種可能的實現是使用運行時類型信息（RTTI）並創建的一種Harris算法的變體，使用RTTI來確定對象每個節點的類型，如MarkedNode或UnMarkedNode，在運行時，替換對象來表示標記/取消標記。這種技術導致了一個新的問題，因為在現實中，會存在大量的交織的邏輯鏈表，而解釋這樣的鏈表是非常困難的，但它的確比java.util.concurrent中AtomicMarkableReference的處理方式更快。
我們現在有了兩種技術實現，接下來將要討論一下他們的未來發展。
使用非自動管理內存的語言（如C、C++,等等）可以直接訪問指針，但是這裏有一個問題是在自動內存管的語言中不存在的——內存管理。
在Java中，我們不需要擔心內存清理，因為JVM垃圾收集器負責清理未使用的節點，但在C/C++並沒有這樣的特性。我在這裏不是談論ABA的問題，Harris linked-list算法考慮到了這個問題，其解決方案是：一旦一個節點“標記”為刪除，它就永遠不可能變成“未標記”，如果相同鍵值要被插入到鏈表中，那麼必須創建一個新節點。
https://en.wikipedia.org/wiki/ABA_problem
現在有一些語言，比如D，允許在特定的指針上使用GC，但他們不支持在這些指針上的位操作，所以還是有相同的問題。
https://dlang.org/garbage.html
若使用非自動管理內存的語言，能安全實現Harris linked-list的唯一方法是使用lock-free內存管理技術，如”Hazard Pointers”，或 “Pass the Buck”，或”Drop the Anchor”。
https://researchweb.watson.ibm.com/people/m/michael/ieeetpds-2004.pdf
https://secs.ceas.uc.edu/~paw/classes/ece975/sp2010/papers/herlihy-05.pdf
https://www.cs.technion.ac.il/~sakogan/papers/spaa13.pdf
到目前為止的問題是，我還沒有看到任何正確使用Hazard Pointers實現的Harris linked-list。即使有人寫出了一個較好的實現，它也不會太快，因為做一個簡單的遍曆列表需要兩個全局可見的存儲指令和至少每個節點上的屏障釋放….是的，它將是緩慢的。也許“Drop the Anchor”技術將提供足夠的性能，但我還沒有發現任何優秀或差勁的代碼，所以目前的實現都是關於Hazard Pointers的。即便如此，如果有人知道使用Hazard Pointers或其他技術較好地實現了Harris linked-list，我想看看，所以請在評論欄中添加鏈接吧！
總之，如果你想使用自動管理內存的語言實現Harris linked-list，你必須使用怪異的技巧，如AtomicMarkableReference或RTTI，這將極大地影響算法的性能，甚至極大改變算法的工作方式。如果你想使用非自動管理內存的語言實現Harris linked-list，那麼你需要一個內存管理技術，這也將影響性能，並且內存管理技術的實現非常重要，而不是說非常困難。
我看過一些研究論文，使用C/C++實現越過了這個障礙，並且簡單地跳過了內存管理（譯者注：根據本人看過的論文而言，的確是這樣，在很多Memory Management Section，通常隻是提到了上述的Hazard Pointer技術可以實現，然而就簡單跳過）。他們隻是有很多的內存，在內存填滿之前停止他們的微基準測試。這是種欺騙，但我理解他們，因為最終他們試圖將Harris鏈表與其他算法比較，如Sets和Maps的算法，而不是那些使用內存管理技術的算法，然而有時我真的懷疑這些基準測試的真實性和可用性。
不管怎樣，這就是為什麼Harris linked-list不那麼受軟件工程師和研究人員歡迎，以及java.util.concurrent為什麼沒有實現的原因。
最後更新：2017-05-23 17:03:21