ruby - ruby Set.include 中的性能异常？带有符号(2.2.2 与 2.1.6)

Question

在对一些代码进行基准测试时，在检查通过 include 包含的元素时，使用 set 是否真的比 array 更快？我发现集合中的字符串和符号存在一些性能异常。

首先是我用于基准测试的脚本。它基本上创建一个包含 50 个随机 50 个字符串的数组，获取 20 个样本并检查是否包含所有样本值。相同的数据用于创建一组字符串、一组符号和一组符号。

require 'benchmark/ips'
require 'Set'

collection_size = 50
element_length = 50
sample_size = 20

Benchmark.ips do |x|

  array_of_strings = begin
    (1..collection_size).map {|pos| (0..element_length).map { ('a'..'z').to_a[rand(26)] }.join }
  end
  array_of_symbols = array_of_strings.map(&:to_sym)
  set_of_strings = Set.new(array_of_strings)
  set_of_symbols = Set.new(array_of_symbols)

  sample_of_strings = array_of_strings.sample(sample_size)
  sample_of_symbols = array_of_symbols.sample(sample_size)

  x.report("array_of_strings: #{collection_size} elements with length #{element_length}, sample size #{sample_of_strings.length}") {
    sample_of_strings.each do |s|
      array_of_strings.include? s
    end
  }

  x.report("set_of_strings: #{collection_size} elements with length #{element_length}, sample size #{sample_of_strings.length}") {
    sample_of_strings.each do |s|
      set_of_strings.include? s
    end
  }

  x.report("array_of_symbols: #{collection_size} elements with length #{element_length}, sample size #{sample_of_symbols.length}") {
    sample_of_symbols.each do |s|
      array_of_symbols.include? s
    end
  }

  x.report("set_of_symbols: #{collection_size} elements with length #{element_length}, sample size #{sample_of_symbols.length}") {
    sample_of_symbols.each do |s|
      set_of_symbols.include? s
    end
  }

  x.compare!  
end

测试系统是 2011 Macbook Pro，运行 OSX 10.10.4，两个 ruby​​ 版本均使用 rvm 1.26.11 安装。

使用 ruby​​ 2.2.2 执行此操作时，我得到以下结果:

set_of_strings:      145878.6 i/s
set_of_symbols:      100100.1 i/s - 1.46x slower
array_of_symbols:    81680.0 i/s - 1.79x slower
array_of_strings:    43545.9 i/s - 3.35x slower

不出所料，set 比 array 快，即使没有我预期的那么快。让我感到奇怪的是，包含字符串的集合比包含符号的集合快，而对于数组，符号集合要快得多。我多次重复脚本，比例保持不变。

为了获得更多见解，我使用 ruby​​ 2.1.6 运行了基准测试脚本并获得了这些结果:

set_of_symbols:      202362.3 i/s
set_of_strings:      145844.1 i/s - 1.39x slower
array_of_symbols:    39158.1 i/s - 5.17x slower
array_of_strings:    24687.8 i/s - 8.20x slower

同样，集合比数组快，但数组性能比 ruby​​ 2.2.2 差得多，在这种情况下，与 2.1.6 相比，性能改进似乎非常好。

奇怪的是集合的结果。包含字符串的集合在 ruby​​ 2.2.2 和 2.1.6. 中每秒达到大约相同的指令，这应该是这样的。但是包含符号的集合在 ruby​​ 2.1.6 中快了一倍。比 2.2.2 中的还要多!

我还改变了基准脚本的参数，结果保持不变。字符串集在 2.1.6 和 2.2.2 中达到大致相同的 i/s，而符号集在 2.2.2 中要慢得多。

我现在的问题是

• 谁能解释这种行为？
• 我的基准测试脚本中有什么我忽略的吗？
• 如果其他人可以重现，应该如何向 ruby​​ 开发人员报告？

更新 1:

似乎潜在的问题是 Hash 类本身，它用于在 Set 类中存储值。刚刚用 1 到 1000 的数字作为字符串/符号键创建了一个散列，并使用示例进行了 Hash[k] 访问。

ruby 2.2.2:

h_string: 1000 keys, sample size 200:    29374.4 i/s
h_symbol: 1000 keys, sample size 200:    10604.7 i/s - 2.77x slower

ruby 2.1.6.:

h_symbol: 1000 keys, sample size 200:    31561.9 i/s
h_string: 1000 keys, sample size 200:    25589.7 i/s - 1.23x slower

由于某些原因，在 2.2.2 中使用符号作为哈希键要慢得多，使用的基准测试脚本:

require 'benchmark/ips'

collection_size = 1000
sample_size = 200

Benchmark.ips do |x|

  h_string = Hash.new 
  h_symbol = Hash.new

  (1..collection_size).each {|k| h_string[k.to_s] = 1}
  (1..collection_size).each {|k| h_symbol[k.to_s.to_sym] = 1}

  sample_of_string_keys = h_string.keys.sample(sample_size)
  sample_of_symbol_keys = sample_of_string_keys.map(&:to_sym)

  x.report("h_string: #{collection_size} keys, sample size #{sample_of_string_keys.length}") {
    sample_of_string_keys.each do |s|
      h_string[s]
    end
  }

  x.report("h_symbol: #{collection_size} keys, sample size #{sample_of_symbol_keys.length}") {
    sample_of_symbol_keys.each do |s|
      h_symbol[s]
    end
  }

  x.compare!  
end

更新 2:

我用最新的 ruby 2.3.0dev (2015-07-26 trunk 51391) [x86_64-darwin14] 重复了测试，对于小的 collection_size 和 sample_size，带符号的集合再次快得多与 ruby​​ 2.1.6 在一个层面上

对于更大的数字，例如具有 10000 个值并检查 100 个样本的哈希，ruby 2.1.6 的迭代次数大约是 ruby​​-head 的两倍(几乎是 ruby​​ 2.2.2 的 3 倍)。因此，似乎 ruby​​-head 进行了一些改进，但仍不足以恢复到原来的性能。

更新 3:

感谢 comment作者 @cremno 我用 2.2 分支重新检查了我的初始设置基准，发现 2.2 与 2.1.6 处于同一水平

我现在的结论

• 始终对您的实际代码进行基准测试，并考虑差异是否真的可见。在我的用例中，即使每个 Web 请求进行了大约 50 次这种检查，总体时间差异也只有几分之一毫秒
• ruby 2.3 和希望即将到来的 2.2.3 中的反向移植代码似乎再次通过哈希符号变得更快
• 不要做出“符号总是更快”或“Set.include?总是比 Array.include 快？”
• Symbol Garbage Collection 带有一个很大的 performance penalty ，如果你处理非常大的哈希。

Answer 1

这是 ruby​​ 代码中的一个性能问题，很快就修复了:-)

问题:https://bugs.ruby-lang.org/issues/11396 提交:https://github.com/ruby/ruby/commit/442b77e72166c9c993e3c6663568431123510dec