在Ruby中，`arr << x`比`arr += [x]`更快。

Question

直观来说，后者应该比前者更快。然而，当我看到基准测试结果时，我感到非常惊讶:

  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

我们还进行了交叉基准测试，在我们两台机器上运行，他的基准测试显示 += 比<<明显慢，而我的则相反。

原因是什么？

更新：我的Ruby版本是Ruby 2.2.3p173（2015年08月18日修订版51636）[x86_64-darwin14]; 我同事的版本是2.2.2（不知道完整的细节，明天会更新帖子）。

更新2：ruby 2.2.2p95 (2015-04-13 revision 50295) [x86_64-darwin12.0] 是我队友的Ruby版本。

- DNNX

---

我看到这两个代码之间有差异，不知道是否正在dup和to_a之间进行基准测试？ - Wand Maker

这种差异如何解释为什么在一种情况下<<更快，但在另一种情况下却不是？ - DNNX

你有两个不同的测试，结果不同。为了找出差异的原因，请尽量减小差异。正如Wand所指出的那样，一个差异是dup与to_a。另一个差异是使用局部变量与实例变量。还有一个差异是使用相同的变量a与使用不同的变量@a、@b、@c。尝试更改您的测试代码，并使其尽可能接近您朋友的代码。然后，您将能够确定您的测试代码与您朋友的代码之间的差异的原因。 - sawa

@sawa：我没有看到任何责备。他的问题非常合理。 - Karoly Horvath

明天到了吗？因为你承诺要更新这篇文章... - Mogsdad

Answer 1

在我看来，为了简化各个运算符的比较，我们应该删除不必要的代码并保持测试简单。

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#<< 是向数组添加元素的四种方法中最快的，因为它只是向数组添加一个元素。相反，Array#+ 会添加一个元素，但会返回一个新的数组副本，这样就会变得更慢。 （可以使用文档中的“toggle 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 创建的全新副本数组。

- Wand Maker

---

让我感到疑惑的是，“<<”和“push”的结果如此不同。我原以为它们是互相别名的。 - sawa

@sawa push和<<有不同的实现方式 - push支持添加多个元素，而<<只允许添加一个元素。 - Wand Maker

@sawa #push 可以接受任意数量的参数，而 #<< 只能接受一个参数，因此它不能被别名化。 - joanbm

顺便说一句，这样的基准测试并没有太多意义，因为对于一般规则没有推论。它们取决于操作系统/硬件平台和语言实现。在我的Linux x86_64系统上，#<< 一直是最快的，而 #+ 最慢（约15%）,使用CRuby 2.2.3。使用JRuby 9.0.1.0时，最快的是 #[]=，而最慢的是 #+（约23%）。使用 #dup 来创建数组而非文字定义则将 #+ 移到了顶部，尽管它生成了更长的字节码（指令序列），没有明显的优化技巧。这可能是由底层操作系统或硬件缓存流水线引起的。 - joanbm

问题的实质和最吸引人的部分是为什么dup如此极端地反转结果，而不是哪个运算符最快。 - stefkin

变化范围在ips给出的+/-边界内 - 我不确定我会太相信结果。 - Frederick Cheung

Answer 2

我认为这与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 +=和<<实际上都会分配足够大小的新缓冲区并复制所有数据。

在这里我有些模糊：如果<<和+执行相同，则完全可以解释这些问题，但情况并非如此。我的理解是+更简单。无论如何，它只需要分配一个缓冲区，并从两个位置复制一些数据-这很快。

另一方面，<<正在改变数组，因此它正在支付写时复制的开销：与+相比，它正在做额外的工作。例如，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

如果您两次执行数组追加操作，它将再次回到顶部。

- Frederick Cheung

---

a << y; a<< [y] - 必须是一个打字错误。 - DNNX

糟糕，似乎没有改变结果。 - Frederick Cheung