Fixnum#to_s性能问题

Question

我有以下算法(它搜索二进制表示也是回文的回文)：

#!/usr/bin/env ruby
class Runner
  attr_accessor :min, :max, :sum

  def initialize(min, max)
    @sum = 0
    @min, @max = min, max
  end

  def run
    current = @min
    while current <= @max
      string = current.to_s
      if string == string.reverse && current.to_s(2) == current.to_s(2).reverse
        @sum += current
      end
      current += 1
    end
    puts @sum
  end
end

t1 = Time.now
Runner.new(*ARGV.first.split(/\.+/).map(&:to_i)).run
puts "Time spent: #{(Time.now - t1).round(2)} s."

我运行它的10..10_000_000范围。我提供的上述版本的结果如下：

Time spent: 2.55 s.

但如果我改变了

    while current <= @max
      string = current.to_s
      if string == string.reverse && current.to_s(2) == current.to_s(2).reverse

至

    while current <= @max
      string = current.to_s
      string_b = current.to_s(2)
      if string == string.reverse && string_b == string_b.reverse

然后我得到

Time spent: 6.25 s.

虽然我预计它会更快(更少的计算量)，但速度会慢两倍。同时，没有参数的#to_s按预期工作，如果我移除变量并执行两次计算：

    while current <= @max
      if current.to_s == current.to_s.reverse && current.to_s(2) == current.to_s(2).reverse

那么它的工作速度就慢了

Time spent: 4.17 s.

查看S无助于理解它，除非问题与条件的else分支有关。但我在参数或NUM2INT上也找不到问题。有人能解释为什么它是这样工作的(我使用MRI 2.1.1p76)吗？

Answer 1

在Ruby中，当您有如下表达式时

a && b

首先计算a，如果为false，则不计算b。

Base10回文很少，因此对于循环中的大部分循环，原始代码只检查string == string.reverse是假的，然后继续循环的下一次迭代。因此，您只执行一次to_s，而对to_s(2)几乎从不执行。

其他一些更改都更频繁地调用to_s，从而完成了更多的工作，因此速度更慢。对我来说不太奇怪。

Answer 2

在您的原始版本中，current.to_s(2)只在string == string.reverse时计算，因为&&短路.相当于：

while current <= @max
  string = current.to_s
  if string == string.reverse
    string_b = current.to_s(2)
    if string_b == string_b.reverse

Answer 3

在分析器中分析这段代码，似乎大部分时间都花在fix_to_s() C调用中。

​

​

跳到fix_to_s()的汇编代码中，我们可以看到，它的大部分时间都花在了单个指令movslq %edx, %rdx上。显然，movslq是将一个长(32位)移动到一个四位(64位)。

​

​

在你的string2回忆录版本中，我们有3027个movslq样本，而在非回忆录版本中，我们只有700个样本！怎么回事？

在回忆录版本中，似乎分配了更多的字符串对象，因此由ruby解释器释放。注意创建和释放字符串对象所花费的时间。

​

​

我使用allocation_stats gem对对象分配进行了一些统计，它们表明在非回忆录版本中分配的字符串确实更少。大约2/3的数量。

test.rb String 20032954

与

test.rb String 30010967

当您显式地设置string2 = current.to_s(2)时，它们必须为您分配内存，因为您可能需要它。但是，在您的代码中，它不一定要执行&&语句的第2部分，所以您可以完全避免这种分配。

显然，增加分配量会以多种方式减慢速度，包括使缓存丢失的可能性更大，垃圾收集更多，以及更多的free()ing和malloc()ing，这解释了为什么分配/时间之间的关系不是线性的。