golang的slice動態擴展實現為何不用動態鏈表？

01-01

之前在回答這個問題go語言slice作為函數參數的一個問題？ - 編程語言的時候，了解到了append的實現機制，竟然是簡單的copy數組。。。go從本質上說應該不支持動態數組，僅僅是因為有append而看起來像動態數組，我很疑問為何go當初要這樣設計，當數組很大的時候，copy數組不會很慢嗎？還是我理解的不對？

上代碼：

go/slice.go at master · golang/go · GitHub

go/memmove_amd64.s at master · golang/go · GitHub

假設你有一個循環不斷的 append 一個 slice, append 在現有數組 &< 1024 時 cap 增長是翻倍的，此時總拷貝成本還是 N，再往上的增長率則是 1.25 拷貝總成本還是 O(N) 只是常數大了. 這個寫段小程序就能驗證出來。

拷貝一段連續內存其實非常快。更關鍵在 Go 的對象模型里，對象拷貝 == 內存拷貝，拷貝對象數組 == 拷貝一大坨連續內存，開銷非常可控，就看著memmove的實現就行。如果放到有複製構造函數和拷貝重載的C++, 或者用引用計數導致拷貝後要逐個維護的語言，呵呵。

假如不想發生拷貝，那你就沒有連續內存。此時隨機訪問開銷會是：鏈表 O(N), 2倍增長塊鏈 O(LogN), 二級表一個常數很大的 O(1)。問題不僅是演算法上開銷，還有內存位置分散而對緩存高度不友好，這些問題i在連續內存方案里都是不存在的。除非你的應用是狂 append 然後只順序讀一次，否則優化寫而犧牲讀都完全不 make sense. 而就算你的應用是嚴格順序讀，緩存命中率也通常會讓你的綜合效率比拷貝換連續內存低。

關於數據結構對性能的真實影響，可以參考這個 cppcon 上的講座：https://channel9.msdn.com/Events/CPP/C-PP-Con-2014/Efficiency-with-Algorithms-Performance-with-Data-Structures , 簡單來說，鏈表在現代計算機架構是個非常不經濟的東西，幾乎在任何時候都不要用它。

對小 slice 來說，連續 append 的開銷更多的不是在 memmove, 而是在分配一塊新空間的 memory allocator 和之後的 gc 壓力（這方面對鏈表更是不利）。所以，當你能大致知道所需的最大空間（在大部分時候都是的）時，在 make 的時候預留相應的 cap 就好。如果所需的最大空間很大而每次使用的空間量分布不確定（那就去確定啊），那你就要在浪費內存和耗 CPU 在 allocator + gc 上做權衡。

總結來說就是：

這個世界上沒有免費的動態增長內存，各種實現方案都有設計權衡
Go 在 append 和 copy 方面的開銷是可預知 + 可控的
應用上簡單的調優有很好的效果
如果還有 4 的話，不做 profile 就講性能都是耍流氓

和C++的std::vector是一樣的，大驚小怪……

複製當然有開銷，所以每次擴容都是翻倍以減少複製次數。而且很大的話，可以提前分配（make([]T, 0, cap），可能一次複製都不用。

連續內存好處多多，index簡單，緩存友好，對C的數組還能cast到slice來操作。

用鏈表的話隨機訪問怎麼辦？

你覺得鏈表對內存好嗎？？？？？？？？？

數組鏈表有不同的特點呀，隨機訪問還是數組好

鏈表局部性差，隨機訪問效率低，對於slice這種定位為數組的數據結構來說並不合適。同地位的數據結構可以參考c++ stl的vector。

另外，每次翻倍的數組容量能讓擴容的均攤複雜度降到O(1)。如果非要求隨機插入/刪除的複雜度也一樣優秀，那我只能說...用平衡樹/b樹吧o(╯□╰)o

golang的slice底層封裝了一個c的結構體，分別是void*數據指針，len數組的當前長度，cap數組的容量，可以說和cpp的vector有一定的相似性，但是vector在擴容後會自動倍增cap，golang的slice應該不會。

噹噹前的len大於等於cap的時候，append則會進行一次拷貝，反之則直接添加到末尾，調整len

我的理解是slice和數組，都應該當做c中的數組來看待，不能當做動態可以擴容的數組來看待，假如append很頻繁，可以一次性指定很大的cap，或者是改用list來實現。

總結就是假設對slice有頻繁的append，謹慎使用slice，請使用list