上代码：

go/slice.go at master · golang/go · GitHubgo/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 上做权衡。

总结来说就是：

  1. 这个世界上没有免费的动态增长内存，各种实现方案都有设计权衡
  2. Go 在 append 和 copy 方面的开销是可预知 + 可控的
  3. 应用上简单的调优有很好的效果
  4. 如果还有 4 的话，不做 profile 就讲性能都是耍流氓