在 Ruby、`arr += [x]` 或 `arr << x` 中哪个更快
What is faster in Ruby, `arr += [x]` or `arr << x`
从直觉上看，后者应该比前者快。然而，当我看到基准测试结果时，我感到非常惊讶：
require 'benchmark/ips'
b = (0..20).to_a;
y = 21;
Benchmark.ips do |x|
x.report('<<') { a = b.dup; a << y }
x.report('+=') { a = b.dup; a += [y] }
x.report('push') { a = b.dup; a.push(y) }
x.report('[]=') { a = b.dup; a[a.size]=y }
x.compare!
end
结果是：
Calculating -------------------------------------
<< 24.978k i/100ms
+= 30.389k i/100ms
push 24.858k i/100ms
[]= 22.306k i/100ms
-------------------------------------------------
<< 493.125k (± 3.2%) i/s - 2.473M
+= 599.830k (± 2.3%) i/s - 3.009M
push 476.374k (± 3.3%) i/s - 2.386M
[]= 470.263k (± 3.8%) i/s - 2.364M
Comparison:
+=: 599830.3 i/s
<<: 493125.2 i/s - 1.22x slower
push: 476374.0 i/s - 1.26x slower
[]=: 470262.8 i/s - 1.28x slower
然而，当我的一个同事独立创建了自己的基准时，结果却恰恰相反：
Benchmark.ips do |x|
x.report('push') {@a = (0..20).to_a; @a.push(21)}
x.report('<<') {@b = (0..20).to_a; @b << 21}
x.report('+=') {@c = (0..20).to_a; @c += [21]}
x.compare!
end
结果：
Calculating -------------------------------------
push 17.623k i/100ms
<< 18.926k i/100ms
+= 16.079k i/100ms
-------------------------------------------------
push 281.476k (± 4.2%) i/s - 1.410M
<< 288.341k (± 3.6%) i/s - 1.457M
+= 219.774k (± 8.3%) i/s - 1.093M
Comparison:
<<: 288341.4 i/s
push: 281476.3 i/s - 1.02x slower
+=: 219774.1 i/s - 1.31x slower
我们还交叉 运行 我们的基准测试，在我们的两台机器上，他的基准测试显示 += 明显慢于 <<，而我的则相反。
这是为什么？
UPD：我的 Ruby 版本是 Ruby 2.2.3p173（2015-08-18 修订版 51636）[x86_64-darwin14]；我同事的是2.2.2（不知道完整细节，明天更新post）。
UPD2：ruby 2.2.2p95（2015-04-13 修订版 50295）[x86_64-darwin12.0] 我队友的 Ruby版本。
在我看来，为了简化各种运算符的比较，我们应该删除不必要的代码并保持测试简单。
require 'benchmark/ips'
y = 10
Benchmark.ips do |x|
x.report('<<') { a = [0,1,2,3,4,5,6,7,8,9]; a << y }
x.report('+=') { a = [0,1,2,3,4,5,6,7,8,9]; a += [y] }
x.report('push') { a = [0,1,2,3,4,5,6,7,8,9]; a.push(y) }
x.report('[]=') { a = [0,1,2,3,4,5,6,7,8,9]; a[a.size]=y }
x.compare!
end
上述代码的结果与问题中分享的第二个代码片段一致。
Calculating -------------------------------------
<< 101.735k i/100ms
+= 104.804k i/100ms
push 92.863k i/100ms
[]= 99.604k i/100ms
-------------------------------------------------
<< 2.134M (± 3.3%) i/s - 10.682M
+= 1.786M (±13.2%) i/s - 8.804M
push 1.930M (±16.1%) i/s - 9.472M
[]= 1.948M (± 7.9%) i/s - 9.761M
Comparison:
<<: 2134005.4 i/s
[]=: 1948256.8 i/s - 1.10x slower
push: 1930165.3 i/s - 1.11x slower
+=: 1785808.5 i/s - 1.19x slower
[Finished in 28.3s]
为什么 << 比 += 快？
Array#<< is fastest out of the four ways of appending an element to the array because it does just that - appends an element to the array. On the contrary, Array#+ 附加一个元素，但 returns 数组的新副本 - 创建数组的新副本使其最慢。 （可以使用文档中的 toogle code 选项来了解某些方法完成的额外工作）
基准标记 dup
如果我们使用下面的代码进行基准测试，
require 'benchmark/ips'
y = 10
Benchmark.ips do |x|
x.report('<<') { a = [0,1,2,3,4,5,6,7,8,9].dup; a << y }
x.report('+=') { a = [0,1,2,3,4,5,6,7,8,9].dup; a += [y] }
x.report('push') { a = [0,1,2,3,4,5,6,7,8,9].dup; a.push(y) }
x.report('[]=') { a = [0,1,2,3,4,5,6,7,8,9].dup; a[a.size]=y }
x.compare!
end
我们看到以下结果：
Calculating -------------------------------------
<< 65.225k i/100ms
+= 76.106k i/100ms
push 64.864k i/100ms
[]= 63.582k i/100ms
-------------------------------------------------
<< 1.221M (±14.3%) i/s - 6.001M
+= 1.291M (±13.1%) i/s - 6.393M
push 1.164M (±14.1%) i/s - 5.773M
[]= 1.168M (±14.5%) i/s - 5.722M
Comparison:
+=: 1290970.6 i/s
<<: 1221029.0 i/s - 1.06x slower
[]=: 1168219.3 i/s - 1.11x slower
push: 1163965.9 i/s - 1.11x slower
[Finished in 28.3s]
如果我们仔细观察两个结果，我们会发现只有一处不同。 += 条目已成为第一个，而其余方法的顺序与原始结果相同。
为什么使用 dup 结果会翻转？
这是我的大胆猜测，我猜测 Ruby 解释器优化了代码并且没有创建新数组作为 += 的一部分，因为它知道它正在处理新创建的副本数组的 dup
我认为这取决于 MRI 分配数组的方式（所有这些答案都是 MRI 特定的）。 Ruby 非常努力地提高数组的效率：例如，小数组（<= 3 个元素）直接打包到 RARRAY 结构中。
另一件事是，如果您获取一个数组并开始一次一个地附加值，ruby 不会一次一个地增加缓冲区，而是分块进行：这样效率更高, 以牺牲少量内存为代价。
查看所有这些的一个工具是使用 memsize_of:
ObjectSpace.memspace_of([]) #=> 40 (on 64 bit platforms
ObjectSpace.memspace_of([1,2]) #=> 40 (on 64 bit platforms
ObjectSpace.memsize_of([1,2,3,4]) #=> 72
ObjectSpace.memsize_of([]<<1<<2<<3<<4) #=> 200
在前两种情况下，数组被打包在 RARRAY 结构中，因此内存大小只是任何对象的基本大小（40 字节）。在第三种情况下 ruby 必须为 4 个值（每个 8 个字节）分配一个数组，因此大小为 40 + 32 = 72。在最后一种情况下 ruby 将存储增加到 20 个元素
这与第二种情况有关。基准测试中的块有一个新创建的数组，它仍然有一些空闲容量：
ObjectSpace.memsize_of((0..20).to_a) #=> 336, enough for nearly 40 elements.
<< 可以只将其对象写入适当的槽，而 += 必须分配一个新数组（对象及其缓冲区）并复制所有数据。
如果我这样做
a = [1,2,3,4,5]
b = a.dup
ObjectSpace.memsize_of(b) #=> 40
此处 b 与 a 共享其缓冲区，因此报告为未使用超出基本对象大小的内存。在写入 b 时，ruby 将不得不复制数据（写入时复制）：在第一个基准测试中 BOTH +=和 << 实际上正在分配一个足够大小的新缓冲区并复制所有数据。
这里是我手忙脚乱的地方：如果 << 和 += 执行相同，这将完全解释事情，但事实并非如此。我对事物的理解是 + 更简单。它所要做的就是分配一个缓冲区，并从 2 个位置 memcpy 一些数据——这很快。
另一方面，<< 正在改变数组，因此它支付了写时复制的开销：与 += 相比，它做了额外的工作。例如 ruby 需要跟踪谁在共享缓冲区，以便在没有人共享缓冲区时可以对原始数组进行垃圾回收。
在某种程度上让我相信这种解释是正确的基准如下：
require 'benchmark/ips'
b = (0..20).to_a.dup
y = 21
Benchmark.ips do |x|
x.report('<<') { a = b.dup; a << y }
x.report('+=') { a = b.dup; a += [y] }
x.report('<<2') { a = b.dup; a << y; a<< y}
x.report('+=2') { a = b.dup; a += [y]; a += [y] }
end
这与原来的基准基本相同，但现在附加了 2 个元素。对于 <<，写时复制开销只会在第一次发生。我得到的结果是
<< 1.325M (± 7.6%) i/s - 6.639M
+= 1.742M (± 9.5%) i/s - 8.677M
<<2 1.230M (±10.3%) i/s - 6.079M
+=2 1.140M (±10.8%) i/s - 5.656M
因此，如果您执行两次附加到数组的操作，则会回到顶部。
从直觉上看，后者应该比前者快。然而，当我看到基准测试结果时，我感到非常惊讶：
require 'benchmark/ips'
b = (0..20).to_a;
y = 21;
Benchmark.ips do |x|
x.report('<<') { a = b.dup; a << y }
x.report('+=') { a = b.dup; a += [y] }
x.report('push') { a = b.dup; a.push(y) }
x.report('[]=') { a = b.dup; a[a.size]=y }
x.compare!
end
结果是：
Calculating -------------------------------------
<< 24.978k i/100ms
+= 30.389k i/100ms
push 24.858k i/100ms
[]= 22.306k i/100ms
-------------------------------------------------
<< 493.125k (± 3.2%) i/s - 2.473M
+= 599.830k (± 2.3%) i/s - 3.009M
push 476.374k (± 3.3%) i/s - 2.386M
[]= 470.263k (± 3.8%) i/s - 2.364M
Comparison:
+=: 599830.3 i/s
<<: 493125.2 i/s - 1.22x slower
push: 476374.0 i/s - 1.26x slower
[]=: 470262.8 i/s - 1.28x slower
然而，当我的一个同事独立创建了自己的基准时，结果却恰恰相反：
Benchmark.ips do |x|
x.report('push') {@a = (0..20).to_a; @a.push(21)}
x.report('<<') {@b = (0..20).to_a; @b << 21}
x.report('+=') {@c = (0..20).to_a; @c += [21]}
x.compare!
end
结果：
Calculating -------------------------------------
push 17.623k i/100ms
<< 18.926k i/100ms
+= 16.079k i/100ms
-------------------------------------------------
push 281.476k (± 4.2%) i/s - 1.410M
<< 288.341k (± 3.6%) i/s - 1.457M
+= 219.774k (± 8.3%) i/s - 1.093M
Comparison:
<<: 288341.4 i/s
push: 281476.3 i/s - 1.02x slower
+=: 219774.1 i/s - 1.31x slower
我们还交叉 运行 我们的基准测试，在我们的两台机器上，他的基准测试显示 += 明显慢于 <<，而我的则相反。
这是为什么？
UPD：我的 Ruby 版本是 Ruby 2.2.3p173（2015-08-18 修订版 51636）[x86_64-darwin14]；我同事的是2.2.2（不知道完整细节，明天更新post）。
UPD2：ruby 2.2.2p95（2015-04-13 修订版 50295）[x86_64-darwin12.0] 我队友的 Ruby版本。
在我看来，为了简化各种运算符的比较，我们应该删除不必要的代码并保持测试简单。
require 'benchmark/ips'
y = 10
Benchmark.ips do |x|
x.report('<<') { a = [0,1,2,3,4,5,6,7,8,9]; a << y }
x.report('+=') { a = [0,1,2,3,4,5,6,7,8,9]; a += [y] }
x.report('push') { a = [0,1,2,3,4,5,6,7,8,9]; a.push(y) }
x.report('[]=') { a = [0,1,2,3,4,5,6,7,8,9]; a[a.size]=y }
x.compare!
end
上述代码的结果与问题中分享的第二个代码片段一致。
Calculating -------------------------------------
<< 101.735k i/100ms
+= 104.804k i/100ms
push 92.863k i/100ms
[]= 99.604k i/100ms
-------------------------------------------------
<< 2.134M (± 3.3%) i/s - 10.682M
+= 1.786M (±13.2%) i/s - 8.804M
push 1.930M (±16.1%) i/s - 9.472M
[]= 1.948M (± 7.9%) i/s - 9.761M
Comparison:
<<: 2134005.4 i/s
[]=: 1948256.8 i/s - 1.10x slower
push: 1930165.3 i/s - 1.11x slower
+=: 1785808.5 i/s - 1.19x slower
[Finished in 28.3s]
为什么 << 比 += 快？
Array#<< is fastest out of the four ways of appending an element to the array because it does just that - appends an element to the array. On the contrary, Array#+ 附加一个元素，但 returns 数组的新副本 - 创建数组的新副本使其最慢。 （可以使用文档中的 toogle code 选项来了解某些方法完成的额外工作）
基准标记 dup
如果我们使用下面的代码进行基准测试，
require 'benchmark/ips'
y = 10
Benchmark.ips do |x|
x.report('<<') { a = [0,1,2,3,4,5,6,7,8,9].dup; a << y }
x.report('+=') { a = [0,1,2,3,4,5,6,7,8,9].dup; a += [y] }
x.report('push') { a = [0,1,2,3,4,5,6,7,8,9].dup; a.push(y) }
x.report('[]=') { a = [0,1,2,3,4,5,6,7,8,9].dup; a[a.size]=y }
x.compare!
end
我们看到以下结果：
Calculating -------------------------------------
<< 65.225k i/100ms
+= 76.106k i/100ms
push 64.864k i/100ms
[]= 63.582k i/100ms
-------------------------------------------------
<< 1.221M (±14.3%) i/s - 6.001M
+= 1.291M (±13.1%) i/s - 6.393M
push 1.164M (±14.1%) i/s - 5.773M
[]= 1.168M (±14.5%) i/s - 5.722M
Comparison:
+=: 1290970.6 i/s
<<: 1221029.0 i/s - 1.06x slower
[]=: 1168219.3 i/s - 1.11x slower
push: 1163965.9 i/s - 1.11x slower
[Finished in 28.3s]
如果我们仔细观察两个结果，我们会发现只有一处不同。 += 条目已成为第一个，而其余方法的顺序与原始结果相同。
为什么使用 dup 结果会翻转？
这是我的大胆猜测，我猜测 Ruby 解释器优化了代码并且没有创建新数组作为 += 的一部分，因为它知道它正在处理新创建的副本数组的 dup
我认为这取决于 MRI 分配数组的方式（所有这些答案都是 MRI 特定的）。 Ruby 非常努力地提高数组的效率：例如，小数组（<= 3 个元素）直接打包到 RARRAY 结构中。
另一件事是，如果您获取一个数组并开始一次一个地附加值，ruby 不会一次一个地增加缓冲区，而是分块进行：这样效率更高, 以牺牲少量内存为代价。
查看所有这些的一个工具是使用 memsize_of:
ObjectSpace.memspace_of([]) #=> 40 (on 64 bit platforms
ObjectSpace.memspace_of([1,2]) #=> 40 (on 64 bit platforms
ObjectSpace.memsize_of([1,2,3,4]) #=> 72
ObjectSpace.memsize_of([]<<1<<2<<3<<4) #=> 200
在前两种情况下，数组被打包在 RARRAY 结构中，因此内存大小只是任何对象的基本大小（40 字节）。在第三种情况下 ruby 必须为 4 个值（每个 8 个字节）分配一个数组，因此大小为 40 + 32 = 72。在最后一种情况下 ruby 将存储增加到 20 个元素
这与第二种情况有关。基准测试中的块有一个新创建的数组，它仍然有一些空闲容量：
ObjectSpace.memsize_of((0..20).to_a) #=> 336, enough for nearly 40 elements.
<< 可以只将其对象写入适当的槽，而 += 必须分配一个新数组（对象及其缓冲区）并复制所有数据。
如果我这样做
a = [1,2,3,4,5]
b = a.dup
ObjectSpace.memsize_of(b) #=> 40
此处 b 与 a 共享其缓冲区，因此报告为未使用超出基本对象大小的内存。在写入 b 时，ruby 将不得不复制数据（写入时复制）：在第一个基准测试中 BOTH +=和 << 实际上正在分配一个足够大小的新缓冲区并复制所有数据。
这里是我手忙脚乱的地方：如果 << 和 += 执行相同，这将完全解释事情，但事实并非如此。我对事物的理解是 + 更简单。它所要做的就是分配一个缓冲区，并从 2 个位置 memcpy 一些数据——这很快。
<< 正在改变数组，因此它支付了写时复制的开销：与 += 相比，它做了额外的工作。例如 ruby 需要跟踪谁在共享缓冲区，以便在没有人共享缓冲区时可以对原始数组进行垃圾回收。
在某种程度上让我相信这种解释是正确的基准如下：
require 'benchmark/ips'
b = (0..20).to_a.dup
y = 21
Benchmark.ips do |x|
x.report('<<') { a = b.dup; a << y }
x.report('+=') { a = b.dup; a += [y] }
x.report('<<2') { a = b.dup; a << y; a<< y}
x.report('+=2') { a = b.dup; a += [y]; a += [y] }
end
这与原来的基准基本相同，但现在附加了 2 个元素。对于 <<，写时复制开销只会在第一次发生。我得到的结果是
<< 1.325M (± 7.6%) i/s - 6.639M
+= 1.742M (± 9.5%) i/s - 8.677M
<<2 1.230M (±10.3%) i/s - 6.079M
+=2 1.140M (±10.8%) i/s - 5.656M
因此，如果您执行两次附加到数组的操作，则会回到顶部。