對大量使用 immutable data structure 的語言，其 VM 和 GC 會有何特點？

01-12

如果可以的話，還請分析一下使用了 immutable.js 後的 javascript 。

Haskell 不僅使用 immutable data structure，還是 lazy 的。laziness 的實現通常會基於 thunk [1]，而 thunk 其實是依賴 mutation 的，因為你最終得把求值的結果寫進這個 thunk，GHC 所基於的 STG [2] 也不例外。

GHC 在 thunk 上有一個特別的優化。在一個 multi-threaded 的環境下，當一個 thunk 被 force 的時候，我們可能通常會覺得這個 thunk 會被更新兩次，第一次把 thunk 標記為正在被 evaluate，防止其他 thread 來 evaluate 它，第二次將結果寫進這個 thunk。但是要完全避免其他 thread 重複 evaluate 的話需要 CAS，特別慢 [3]，因為 thunk 幾乎無處不在。好在 Haskell 是 pure 的，一個 thunk 無論 evaluate 多少次都不會影響正確性，於是 GHC 選擇不做 CAS，極少數情況下（這樣的 race condition 只發生在 1 個 instruction 的時間內）其他 thread 有可能會做重複的工作，不過由於大部分 thunk 都非常簡單，重複的工作做了也就做了。

對於少部分耗時超長的 thunk，如果不幸被重複 evaluate 了，GHC 也有一個奇妙的方式來降低損失：thread 在 GC 的時候，我們原本就會掃描其 stack 來獲取 GC root set。與此同時，我們還可以在這個階段分辨出 stack 上的哪些 thunk 是被標記為正在被 evaluate 的，但是並不是由當前 thread 標記的。如果有的話，這個 thunk 上面的整個 stack 都可以被清空，因為這都是無用功，而整個 thread 的狀態也會被修改成正在等待這個 thunk 的結果。

在一個 generational GC 里，如果老一代的 immutable heap object 指向了新一代的 heap object，那麼後者也可以被移動到老一代里。這樣一來，remembered set 的大小就可以降低，新一代的空間也會更加充裕。這實際上也是大家最通常想到的 immutability 對於 GC 的好處，Simon 在 GHC 中也是這麼做的 [4]。只不過 GHC 里還是有一部分的 mutation，把實現複雜化了，比如 thunk 在 force 了之後才會變成 immutable 的。另一個有趣的優化是 [5]，GHC 的 GC 在遇到有 heap object 指向 immutable thunk 的時候，會直接把這個 heap object 指向 thunk 的內容，從而消除整個 indirection。

有空回頭再來寫..

[1] Simon Peyton Jones: book

[2] Commentary/Compiler/GeneratedCode - GHC

[3] http://research.microsoft.com/en-us/um/people/simonpj/papers/parallel/multiproc.pdf

[4] http://simonmar.github.io/bib/papers/parallel-gc.pdf

[5] https://www.microsoft.com/en-us/research/wp-content/uploads/1993/01/gen-gc-for-haskell.pdf

對於傳統的函數式語言來說，會因為不可變數據產生大量垃圾和頻繁的gc動作。另外一方面，現在流行的分代式gc可以得到優化機會

具體說，對於可變的數據對象，分代式gc每次對副堆進行gc的時候，首先要確定副堆里有哪些對象是被主堆所引用，這意味著：要麼掃描整個主堆——這是不應該的；要麼記錄下每次主堆可變對象的引用操作，把對副堆的引用記錄下來。主流方案是使用一個叫做remembered set的數據結構來記錄這些引用

當可變的小對象被頻繁修改的時候，這種記錄的開銷非常大，超過了直接在副堆里構建一個新對象的開銷。所以只有偶爾修改的時候可變數據結構才有優勢，否則還不如使用不可變對象

總結：gc開銷更大，但同時也給了用戶一個優化的機會