標籤：

函數式編程所倡導使用的「不可變數據結構」如何保證性能？

01-11

先說答案：

  1. 絕大部分情況下不可變數據結構的性能確實不如原始類型
  2. 主流的實現通過一些優化過的數據結構和演算法來「保證」性能，一般情況下性能可以滿足要求
  3. 在現有演算法上還可以做近一步優化，但是需要要具體情況具體分析

因為最近正在研究相關問題，因此在這裡展開介紹一下。

通常來說不可變數據結構還是構建在傳統數據類型的基礎上的，一般不會更快，但是在演算法的設計上已經做出了很多的努力。此外，當我們談起數據結構的性能的時候，一般也要涉及兩個方面：

  1. 數據結構的時間複雜度，也即是各種操作需要花費多少時間
  2. 數據結構的空間複雜度，由於 Immutable 數據結構的不可變性，在每次操作得到新的對象時儘可能節約空間是很重要的

以最基礎的兩類數據結構 數組 和 字典（哈希表）為例，包括 Scala，Clojure 以及 F 家的 ImmutableJS 基本上都是使用 Vector Trie 和 HAMT 兩種數據結構來實現的。

Vector Trie 用來實現數組，它本質上就是將數組切割成等長的分段，然後用 Trie 樹來索引起來。典型的實現每個節點都有32個單位寬，在這種情況下，Vector Trie 的修改和查詢兩種操作的時間複雜度都為O(log_{32} N)。在某些編程語言的文檔上聲稱 Vector Trie 的時間複雜度跟數組一樣是O(1)，這是因為在我們日常需要處理的數據量下log_{32} N確實跟常數級別非常接近了。跟數組一樣，Vector Trie 在中間插入和刪除的時間複雜度比較高，但是僅考慮在尾部的增刪操作的話，也基本可以認為是O(log_{32} N)的。

在空間複雜度方面，修改操作需要複製 Trie 樹從根到葉子節點的一條路徑，需要額外消耗O(log_{32} N)的空間。

HAMT 用來實現字典（哈希表），它的基本原理和 Vector Trie 很接近，但是增加了節點內部的空間壓縮和樹高的壓縮。眾所周知，哈希表的時間複雜度O(1)指的是均攤時間複雜度，在遇到特定序列導致 Hash 碰撞比較嚴重的情況下性能會急速下降。HAMT 這種數據結構本身設計出來是解決這一問題的，它實際上相當於虛擬了整個 Int 範圍的空間用來儲存元素，不存在數組填滿了之後需要倍增空間重新 Hash 的問題。可以認為 HAMT 增刪改查的時間複雜度上界都是O(log_{32} N)。實際上，HAMT 的主要性能瓶頸在於頻繁的內存分配，這一問題一般通過使用內存池來解決。

空間複雜度方面，HAMT 插入一個元素最多需要消耗 O(log_{32} N) 倍的空間。

（擴展-1）Transient ，儘管 Vector Trie 和 HAMT 本身的性能已經可以應對大多數情況了，但是為了進一步提高性能，一些實現（如 Clojure 和 ImmutableJS）還提供了 Transient 這種方法。其原理是我們暫時把 Vector Trie 和 HAMT 轉變為可變數據結構，允許用戶進行一系列修改之後再重新不可變化。在需要進行連續修改的情況下可以極大地提高性能。實際上根據一些簡單的 Benchmark [2]，在 Java 環境下的 Transient Vector Trie 的追加（push操作）性能甚至比原生數組還要好。

（擴展-2) JVM下的性能優化，因為最流行的一些不可變數據結構是來自運行於 JVM 上的編程語言（如 Scala 和 Clojure），且 JVM 本身並不像 CPP 那樣能提供原始的內存訪問，因此在 Java 實現的此類數據結構可能會有近一步的性能損失。在這方面的演算法提高已經有一些相關研究[3]了。

總結：

數據結構的性能是一個很複雜的問題，除了一般的時間複雜度分析，在優化到極致的情況下甚至還要考慮使用場合、平台相關的特性（比如 CPU 的 Cache 大小，內存的命中和換頁機制）等等。並沒有什麼萬能的解決方案。

然而，不可變數據結構擁有的以下一些特性使得它在某些場合下非常有用：

  1. 相對不錯的性能，從上面的分析可以看出，在一般的應用下，不可變數據結構的性能都不是特別大的問題
  2. 不可變數據結構在並行和並發環境下使用有優勢（鑒於關於不可變數據結構無鎖特性存在一些可能的混淆，因此移除了相關的說明。）
  3. 在一些情況下如 Vector Trie 這樣的數據結構對於 CPU 的 Cache 更加友好，因此會出現使用 Transient 反而性能更高的現象

值得注意的是，這篇答案只涉及到我比較了解的兩種不可變數據結構實現演算法，還有一些其它演算法（如實現 Lazy Sequence 的 Finger Tree）等可能具有不一樣的特性。因此還需要具體情況具體分析。

參考資料

[1] Understanding Clojure"s Persistent Vector, pt. 1

[2] Persistent Vector Performance

[3] https://michael.steindorfer.name/publications/oopsla15.pdf

如果看了上面的介紹還想了解更細緻的內容（包括 Vector Trie 和 HAMT 具體演算法實現），可以看我 Blog 上最近正在施工的系列文章： Functional Go: 持久化數據結構簡介 。:)

當程序本身的性能瓶頸不依賴於數據結構共享就有保證性能的可能。

說個真實的故事。我遇上過我司一位程序員，他做過一個非常有趣的實驗，實驗結果「證明」 Apache Spark 比 Apache Storm 在執行一個 streaming 計數邏輯時慢八千多倍，同時機器開支是 Storm 的十倍以上。當我看到這個結論時的腦袋裡回蕩著這樣一句話：

Σ(っ °Д °;)っ 我們不如去證明全球開源大數據社區全體成員集體精神失常了五年，我覺著還容易些。

我抓了他的代碼仔細讀了一遍，發現他的邏輯是這樣的：他在 Spark application 里維護了一個六小時的時間窗口，然後每兩分鐘窗口前移並將六小時時間窗口的所有數據過一遍，算出多少個 key 和每個 key 出現的次數，每一份數據輸入都作為一個 RDD 保留在系統里。可能很多人都知道 Apache Spark 大量應用了函數式程序設計原則，其基本數據結構 RDD 就是不可變的，也就是說他的邏輯導致 Spark 在內存中維護了一個裸數據接近 40GB 的巨大隊列，每兩分鐘就要遍歷一遍。且不說反覆重複計算的開銷，Spark 做 checkpoint 的時候要把這個隊列全部保存在 HDFS 里，這就得花掉大量的時間，這一筆一筆算起來不慢才有鬼。更何況要求 Spark 在內存中保存 40GB 的裸數據，算上數據副本和 Java 運行時的開銷，弄出個十倍的機器開銷簡直是輕鬆愉快。

那為什麼 Storm 就很快呢？他的 Storm 邏輯直接在內存里維護了一個可寫的 java.util.HashMap 哈希表……當然代價是這種原始的內存表扛不住機器掉線，可靠性堪憂。

我們先別急著笑話他，他這麼做是有原因的。因為一些我至今都不理解的業務需求，他的項目要求他每兩分鐘轉儲六個小時時間窗口內的全部裸數據。後來他也承認，其實他存了個心思用 checkpoint 來承擔這個轉儲工作，因此花了大量時間研究怎麼改造 checkpoint 讓它來快速地存儲裸數據上了，但 RDD 的不可變讓他始終無法解決計算開銷問題。——但熟悉 Spark 的朋友都知道 checkpoint 根本不是起這個作用的，改造 checkpoint 顯然不是一個可行的思路。

那麼解決問題的方法是什麼呢？Redis，我給他開了個 Redis 的隊列和哈希表。計數的部分寫哈希表，轉儲的部分寫隊列。機器用量重新回到了十分之一，兩分鐘處理完畢的性能要求也沒問題。想轉儲？開一個非同步進程遍歷 Redis 隊列就可以了，遍歷 40 GB 數據怎麼也用不了六個小時。

所以啊，讓上帝的歸上帝，凱撒的歸凱撒。

在 Clojure 里，數據是復用的

也就是說假設你產生了一個 map，對這個 map

assoc 之後你會得到 2 個 map。這兩個 map 是相互關聯的，在內存結構上它們會共用相同的部分，形成一個樹形結構。即使是 seq 一類扁平的數據結構也是如此。不會是簡單的複製一個新的數據。所以 Clojure 的實現高度依賴 GC，因為在很多時候循環引用是很常見的事情。

既然你都不可變了，那麼我能不能把某些「創建新對象」給優化成「賦值」呢？

然後函數式語言也有 IORef、STRef、TVar 這種東西啊

既然你都不可變了，那麼我能不能復用以前的數據呢？

純函數式編程顯然是不能的。所謂演算法設計，必須同時機敏地利用

  • 目標問題的特殊屬性
  • 問題背後的數學原理的特殊屬性
  • 執行機的特殊屬性

這3點才能構思出最優的演算法，純函數式編程放棄了執行機「可以反覆擦寫內存」這個巨大的特殊屬性，註定是做不到命令式編程的那樣好的演算法複雜度的

但是，函數式編程大大簡化了編譯器自動生成可並行執行的代碼的難度，這在多核/分散式執行機時代是個很大的優點。但是，由於核數和節點數是常數，因此並行演算法不能改變演算法複雜度。命令式編程願意的話，仍然可以在很多場合做到函數式編程做不到的高效演算法

clojure有持久化數據結構 O(log32N) jcouyang/clojure-flavored-javascript

haskell的 Lenses, Folds and Traversals 貌似是小於O(n)記不得了

要追求O(1)就別函數式了吧

就像有些人指出的，函數式也能做出很多優化，特別是在允許全局代碼可見的前提下，比人工指針做的更好也是可能的。但是我還想指出的是函數式不允許副作用的前提下某些目標註定是很難/不可能達到的，這表面上看是可變不可變的差異，實質上其實是我在其他地方/專欄中指出的是否允許共享的因素。

眾所周知當對數據結構作調整時，往往修改操作作用於很小的一個局部上，那麼如果僅允許值語義的情況下，很小的並發操作也可能導致巨大的複製開銷，就算底層用上何種手筋也最多把開銷轉移到別處而不可能完全抵消。

這個問題很容易理解，函數作用的範圍遠小於傳入參數，那麼不允許共享就必然要多付出代價。

性能不需要保證，因為運行程序的電腦有無限多個core，map一個無限序列的時間複雜的是O(1)

我覺得主要靠摩爾定律。

1. 計算機的每一級抽象都有額外開銷。高級抽象是為了降低宏觀的複雜度，使其維持在合理的範圍內。在保持介面定義的前提下，能做的只能是盡量減少額外的開銷。函數式抽象必然是有額外的開銷的。

2. 計算機就是一個善於複製的機器。

綜上，在滿足業務需求的前提下，用部分性能換取較低的複雜度是有必要的。

最後，脫離業務談性能都是耍流氓！

所以函數式裡面不叫賦值叫綁定，因為綁定即指針咯

很多情況下並不能保證性能。。

既然你都不可變了，那麼我能不能把某些「測試對象內容是否相同」給優化成「指針是否相同」呢？

我最近正在學習使用C++構造函數式數據結構，以便於進一步利用它們來編寫並發程序，我對這方面沒有任何經驗，但Microsoft的magazine上有一篇文章也許能解答您的疑惑，該文章介紹了如何用C++構造高效的，不可變的，共享的的函數式數據結構，文中的鏈接附有代碼。

中文鏈接：C + + 的功能在 c + + 編程風格

英文鏈接：C++ - Functional-Style Programming in C++

共享的不可變，可變的不共享。函數式編程並不要求你完全用不可變數據。scala的標準庫大部分都是命令式的實現，但是因為這些操作對外不可見，所以它兼顧了函數式以及性能。

推薦閱讀：

※每一個 Haskell 中的「範疇論的」概念都可以去 co 嗎？
※Haskell的Lens是一個怎樣的庫？
※如何解釋 Lisp 中 call/cc 的概念？
※如何向一個只有命令式編程背景的人解釋函數式編程中的函數？

TAG:Scala | 函數式編程 | 數據結構 | Haskell |