ruby 为什么分散在阵列中的成本如此之高?

xqkwcwgp  于 2022-12-26  发布在  Ruby
关注(0)|答案(1)|浏览(108)

我喜欢使用splat来构建数组和散列:

  • 它们是数组和散列常量,所以你不需要进行一些计算就可以知道你得到了什么样的值,语法非常清楚
  • 它们使在单个表达式中构建相当复杂的值变得容易,而不是使用命令式(是的,您可以将tap之类的内容转换为单个赋值语句,但可读性较差)。

然而,飞溅是昂贵的。

require 'benchmark'

$array = (0...100).to_a

n = 100_000
Benchmark.bm do |x|
  x.report('add   ') {n.times{$array + $array + $array}}
  x.report('splat ') {n.times{[*$array, *$array, *$array]}}
end

在机器A(MRI 3.1.3)上,我有:

user     system      total        real
add     0.031583   0.001421   0.033004 (  0.033006)
splat   0.050174   0.001397   0.051571 (  0.051584)

在机器B上(MRI 2.7.4):

user     system      total        real
add     0.278377   0.000000   0.278377 (  0.278316)
splat   0.780735   0.043730   0.824465 (  0.824377)

基于splat的数组构造为什么这么慢?我希望基于splat的构造不会比普通加法慢(毕竟AST甚至可以将一个转换为另一个),而且我实际上希望它更高效(因为该语言可以看到所有内容,所以它可以避免二进制加法创建的中间数组,它还可以预测最终数组的大小并预先预留空间,等等)。
那么,为什么抛出一个方法调用(因此,先验地,解释器不太可能优化)的替代方法比所有内容都诚实地暴露给解释器的方法更快呢?

EDIT:更多备选方案

require 'benchmark'

$array = (0...100).to_a

def add
  $array + $array + $array
end

def append
  res = $array.dup
  res.append(*$array)
  res.append(*$array)
  res
end

def concat2
  res = []
  res.concat($array)
  res.concat($array)
  res.concat($array)
  res
end

def concat3
  [].concat($array, $array, $array)
end

def concat_splat
  [].concat(*[$array, $array, $array])
end

def flatten
  [$array, $array, $array].flatten
end

def flatten_1
  [$array, $array, $array].flatten(1)
end

def splat
  [*$array, *$array, *$array]
end

n = 100_000
Benchmark.bm do |x|
  x.report('add         ') {n.times{add}}
  x.report('append      ') {n.times{append}}
  x.report('concat2     ') {n.times{concat2}}
  x.report('concat3     ') {n.times{concat3}}
  x.report('concat_splat') {n.times{concat_splat}}
  x.report('flatten     ') {n.times{flatten}}
  x.report('flatten(1)  ') {n.times{flatten_1}}
  x.report('splat       ') {n.times{splat}}
end

这是机器A,MRI 3.1.3。

user     system      total        real
add           0.032841   0.001502   0.034343 (  0.034347)
append        0.059024   0.009869   0.068893 (  0.068944)
concat2       0.047542   0.000144   0.047686 (  0.047690)
concat3       0.062913   0.010196   0.073109 (  0.073111)
concat_splat  0.056044   0.000748   0.056792 (  0.056796)
flatten       0.978091   0.005750   0.983841 (  0.983952)
flatten(1)    0.165467   0.000998   0.166465 (  0.166472)
splat         0.049761   0.000131   0.049892 (  0.049896)
fzsnzjdm

fzsnzjdm1#

加法和splat版本发出不同的字节码(为了简洁,省略了一些输出):

puts RubyVM::InstructionSequence.compile(<<~ADDITION).disasm
  src = (0...100).to_a
  res = src + src + src
ADDITION

0000 putobject                              0...100                   (   1)[Li]
0002 opt_send_without_block                 <calldata!mid:to_a, argc:0, ARGS_SIMPLE>
0004 setlocal_WC_0                          src@0
0006 getlocal_WC_0                          src@0                     (   2)[Li]
0008 getlocal_WC_0                          src@0
0010 opt_plus                               <calldata!mid:+, argc:1, ARGS_SIMPLE>
0012 getlocal_WC_0                          src@0
0014 opt_plus                               <calldata!mid:+, argc:1, ARGS_SIMPLE>
0016 dup
0017 setlocal_WC_0                          res@1
0019 leave

对比

puts RubyVM::InstructionSequence.compile(<<~SPLATS).disasm
  src = (0...100).to_a
  res = [*src, *src, *src]
SPLATS

0000 putobject                              0...100                   (   1)[Li]
0002 opt_send_without_block                 <calldata!mid:to_a, argc:0, ARGS_SIMPLE>
0004 setlocal_WC_0                          src@0
0006 getlocal_WC_0                          src@0                     (   2)[Li]
0008 splatarray                             true
0010 getlocal_WC_0                          src@0
0012 concatarray
0013 getlocal_WC_0                          src@0
0015 concatarray
0016 dup
0017 setlocal_WC_0                          res@1
0019 leave

上面的两个片段看起来非常相似,区别是2 ops_plus指令与splatarray + 2 concatarray指令。但在实现方面,差异变得更大。
第一个可以归结为2 rb_ary_plus,简而言之:

  • 为src + src分配内存
  • 复制src + src到一个新的内存位置
  • 为(src + src)+ src分配内存
  • 复制(src + src)+ src到一个新的内存位置

后者内部似乎更为复杂:splatarray归结为rb_ary_dup(所以我们先复制ary),concatarray也在幕后复制一个目标数组,然后归结为rb_ary_splice;后者有点麻烦,但我相信我们可以转到这个分支,在那里我们有效地将数组容量加倍(包括复制第一个数组),然后复制第二个数组。我不能100%确定我是否正确地跟踪了这个执行流,但如果我这样做了,我们将得到:

  • 重复源代码
  • 再次复制asrc(?)
  • 双倍目标容量(包括复制)
  • 将第二个阵列复制到上面分配的空间
  • 重复(源代码+源代码)
  • 双倍(src + src)容量(包括将(src + src)元素复制到新的内存位置)
  • 将第3个阵列拷贝到分配的空间

这些额外的重复可以解释这种差异(更不用说后者的整体复杂性,这意味着检查了更多的条件句等)。

相关问题