为什么这两个较小的循环比包含相同指令的单个循环慢得多?

Why are these two smaller loops so much slower than a single loop containing the same instructions?

Ruby v2.3.3p222
MacOS Catalina v10.15.3
Processor: 2.6GHz 6-Core Intel Core i7

我有以下性能基准脚本,旨在测试一个较大循环操作与两个较小循环之间的区别:

require 'benchmark'

N = 10_000_000

def one_loop
  N.times do
    foo = 1+1
    bar = 2+2
  end
end

def two_loops
  N.times do
    foo = 1+1
  end

  N.times do
    bar = 2+2
  end
end


Benchmark.bmbm do |performance|
  performance.report("two smaller loops") { two_loops }
  performance.report("one large loop") { one_loop }
end

我的假设是这两种方法的执行时间大致相同,因为(我认为)它们都执行相同数量的指令:较大的循环执行 2 * 10,000,000 次操作,而每个2 个较小的循环执行 1 * 10,000,000 次操作。

但是,我观察到的情况似乎并非如此。当我 运行 脚本时,我得到以下输出:

Rehearsal -----------------------------------------------------
two smaller loops   0.840000   0.000000   0.840000 (  0.838101)
one large loop      0.500000   0.010000   0.510000 (  0.506283)
-------------------------------------------- total: 1.350000sec

                        user     system      total        real
two smaller loops   0.850000   0.000000   0.850000 (  0.863052)
one large loop      0.500000   0.000000   0.500000 (  0.494525)

这真是令人失望,因为我希望说服我的团队,通过将我们的 1 个大代码循环拆分为几个更简洁的循环,每个循环只做一件事并且做得很好,我们不会看到任何性能下降.

我认为这可能是由于生成报告的顺序所致,但是当我颠倒对 performance.report 的两次调用的顺序时,我得到了同样令人失望的结果:

Rehearsal -----------------------------------------------------
one large loop      0.500000   0.010000   0.510000 (  0.508246)
two smaller loops   0.850000   0.000000   0.850000 (  0.852467)
-------------------------------------------- total: 1.360000sec

                        user     system      total        real
one large loop      0.490000   0.000000   0.490000 (  0.496130)
two smaller loops   0.830000   0.000000   0.830000 (  0.831476)

我错过了什么吗? 2 个较小的循环是否真的比单个较大的循环做更多的工作?还是我以某种方式以误导或不准确的方式构建了我的基准测试脚本?

这是 1000 万次迭代,每次迭代进行两次计算,总共 3000 万次我们称之为操作:

  N.times do
    foo = 1+1
    bar = 2+2
  end

这是 2000 万次迭代,在每次迭代中完成一次计算,总共有 4000 万次我们称之为操作:

  N.times do
    foo = 1+1
  end

  N.times do
    bar = 2+2
  end

30 < 40,因此第一个示例更快。

the larger loop was doing 2 * 10,000,000 operations, while each of the 2 smaller loops was doing 1 * 10,000,000 operations

如果不定义我们为这些“操作”建模的机器模型和成本模型,就谈论“操作”是没有意义的。或者,简单地说:在你清楚自己在数什么之前,数数是没有意义的。

在这种情况下,您正在计算 添加 。你是对的:在你的模型中,它只计算加法,两个版本有相同数量的加法 ].

但是,他们具有相同数量的块激活

记住,Integer#times 大致是这样的:

class Integer
  def times
    return enum_for(__callee__) unless block_given?
    return self unless positive?

    i = -1
    yield i while (i += 1) < self

    self
  end
end

因此,对于循环的每次迭代,都会激活传递给 Integer#times 的块(即 yield)。

如果我们将其添加为“操作”的新 class,我们将得到以下内容:

  • one_loop:20,000,000 次添加和 10,000,000 次区块激活
  • two_loops:20,000,000 次添加和 20,000,000 次区块激活

因此,两种方法的加法次数相同,但 two_loops 的块激活次数是其两倍。

这意味着,我们还必须考虑添加与块激活的相对成本。现在,语义上,加法只是一个普通的方法调用。激活块有点类似于方法调用。

因此,我们会期望添加和块激活具有大致相似的成本,这意味着我们的成本将是:

  • one_loop: 30,000,000“方法调用类似操作”
  • two_loops: 40,000,000 "方法调用类似操作"

换句话说,我们预计 two_loops 会慢 33% 或 one_loop 会快 25%,具体取决于您如何看待它。

然而,我们实际上发现差异要大得多,很明显我们在模型中遗漏了一些东西。

我们缺少的是优化。整数的算术运算非常常见并且非常性能关键,因此所有Ruby 实现竭尽全力使它们更快。事实上,在所有 Ruby 实现中,简单的添加(例如您正在使用的那个)将直接映射到单个 CPU ADD 指令,并且 不会 [=214] =] 根本不会产生方法调用的开销。

块激活在 Ruby 中也非常重要,因此它们也经过了大量优化,但它们基本上只是比相加两个机器字整数复杂几个数量级。

事实上,块激活与机器字整数加法的相对复杂性如此之大,以至于我们实际上可以在我们的模型中完全忽略加法:

  • one_loop:10,000,000 次区块激活
  • two_loops:20,000,000 块激活

这给了我们 2:1 的因数,因此我们预计 two_loops 会慢 100% 或 one_loop 会快 50%。

顺便说一句,我忽略了另一个正在发生的操作:局部变量的定义和初始化。论点类似:那是一个操作,速度快到与块激活相比可以忽略不计。

实际上,到目前为止,我们只讨论了这些操作的相对成本,以及它们如何意味着我们可以忽略添加和局部变量的成本。然而,还有一个更有力的理由来忽略这些:optimizations.

即使是最简单的 Ruby 实现也能够完全优化局部变量:它们只在一个地方定义和初始化,并且永远不会被再次访问。它们只存在于块的范围内,在块的一次激活期间存在,所以即使是一个非常简单的优化器也可以看出它们是完全无用的,所以即使是最简单的优化器也会将代码优化成大致这样的东西:

def one_loop
  N.times do
    1+1
    2+2
  end
end

def two_loops
  N.times do
    1+1
  end

  N.times do
    2+2
  end
end

这意味着我们不仅可以忽略局部变量的成本,因为它与其他成本相比很小,但实际上,局部变量甚至不存在

同样,稍微聪明一点的优化器会认识到 one_loop 中的第一个加法没有副作用,不是 returned,不存储在变量中(或者至少不在一个在任何地方使用的),并且通常不会以任何方式、形状或形式影响计算结果,因此将代码优化为:

def one_loop
  N.times do
    2+2
  end
end

def two_loops
  N.times do
    1+1
  end

  N.times do
    2+2
  end
end

此外,相同的论点实际上适用于剩余的加法。它没有副作用,它所做的只是从块中 returned,但是 Integer#times 忽略 块的 return 值。我没有查看生成的代码,但我强烈怀疑即使是最愚蠢的优化器也可以轻松证明您的块是空操作,因此它将代码优化为大致如下所示:

def one_loop
  N.times do
  end
end

def two_loops
  N.times do
  end

  N.times do
  end
end

这意味着 one_loopN 次块迭代,two_loops2 * N 次迭代,因此应该花费大约两倍的时间。

现在,我们可以在您的基准测试中看到这些数字实际上不是 2:1。它们是 1.75:1 或大致 7:4.

我可以在我的机器上确认这些结果,这里使用没有 JIT 的 YARV 2.7.1,我几乎完全得到 7:4:

                       user     system      total        real
two smaller loops   0.711479   0.000099   0.711578 (  0.711680)
one large loop      0.401808   0.000059   0.401867 (  0.401916)

但是,当我打开 JIT 时,我得到的 2:1 几乎完全符合我们的预期:

                       user     system      total        real
two smaller loops   0.587017   0.000279   0.587296 (  0.587098)
one large loop      0.291713   0.000062   0.291775 (  0.291779)

您还会注意到它通常速度更快。

使用 JRuby 9.2.9.0,我们再次获得稍微更快的执行速度,几乎 2:1:

                       user     system      total        real
two smaller loops   0.740000   0.010000   0.750000 (  0.517670)
one large loop      0.260000   0.000000   0.260000 (  0.263270)

这是使用默认选项的结果,这里是一些更激进的编译器标志的结果:

                       user     system      total        real
two smaller loops   0.370000   0.000000   0.370000 (  0.362050)
one large loop      0.390000   0.010000   0.400000 (  0.213861)

TruffleRuby 20.1.0 再次比 JRuby:

快得多
                       user     system      total        real
two smaller loops   0.009955   0.000039   0.009994 (  0.010035)
one large loop      0.004759   0.000007   0.004766 (  0.004742)

同样,非常接近 2:1。此外,尽管我们只对这两种方法的相对性能感兴趣,但很高兴看到 TruffleRuby 在这个基准测试中比 YARV 快 70-100 倍!

实际上,我有点惊讶 TruffleRuby 无法证明 Integer#times 具有空块主体是空操作。我本来希望它能够像这样优化代码:

def one_loop
end

def two_loops
end

因此两个版本之间完全没有运行时间差。

Am I missing something? Are the 2 smaller loops really doing a much greater amount of work than the single larger loop? Or did I somehow construct my benchmark script in a misleading or inaccurate way?

我会说以上所有内容。

主要问题是您测量几乎与您计算[=214]完全相反 =].你只计算加法而忽略块激活,这没有错,IFF你感兴趣的只是加法的数量,没有别的。

并且您 测量 仅块激活的成本并忽略添加的成本,如果您对此感兴趣,这也完全没问题。

问题是这两者不匹配:你没有测量你正在计算的东西,你也没有计算你正在测量的东西,所以你只是不能画任何从你的实验结果得出的结论对你的假设。

中,你问过:

so does this mean that each iteration of each loop counts as its own operation, in addition to whatever operation(s) happen inside the loop?

我们不能告诉你。 需要定义您感兴趣的操作,以及您想忽略的操作。如果将“操作”定义为 only 表示“加法”,则不会,循环的每次迭代都 not 算作自己的操作,并且您的两个示例都具有完全相同的操作量。

另一个问题是你的假设“加法次数相同,因此执行时间相同”是无效的,因为加法并不是唯一需要时间的操作。并且即使你算上其他种类的操作,那么你的假设仍然假设每个操作花费相同的时间,这也是不正确的。

一般来说,您的基准测试方法还有一些问题,但这并不是您困惑的根源。以下是我发现的一些与您的基准测试有关的问题,尽管我确信还有其他问题:

  • 您的基准测试的编写方式是优化掉您感兴趣的所有操作,只留下您不感兴趣的操作。
  • 即使它们没有被优化掉,与您不关心的操作的执行时间相比,它们的执行时间也可以忽略不计。
  • 您的基准测试不会 运行 长,而且通常不足以给优化器一个机会。例如,编译方法时的默认阈值在 20 到 20000 次调用之间,具体取决于 Ruby 实现、编译器标志等。您的两种方法仅被调用两次,一次在排练期间,一次在真实情况下.您需要确保它们被调用的次数超过 20000 次,以确保 a) 它们完全被编译,并且 b) 有足够的迭代 after 它们被编译了编译之前较慢的迭代不会显着影响结果。

我总是建议想要编写基准测试的人阅读并理解以下邮件列表主题:

JMH vs Caliper: reference thread

特别是从链接消息开始的子线程和后续讨论。

虽然此线程是关于用于基准测试 Java 代码的 特定 基准工具,但线程中讨论的任何内容适用于 all all 现代高性能语言实现的基准测试。

基准测试由将编写基准测试作为全职工作的基准测试工程师编写是有原因的:编写基准测试需要大量知识和专业知识。

你至少需要

  • 对一般计算机组织有深入了解。
  • 深入了解您进行基准测试的所有特定硬件平台。
  • 一般编程语言的深入知识。
  • 深入了解您编写基准代码所用的所有特定编程语言。
  • 深入了解一般语言实现,包括但不限于提前编译器、JIT 编译器、解释器、VM、垃圾收集器、内存分配器、优化器、内联、循环展开、死代码消除、常量折叠、公共子表达式消除、尾调用消除、窥孔优化、编译时评估、多态内联缓存等等。
  • 深入了解您正在使用的特定语言实现运行您的代码。
  • 还有更多,例如操作系统、调度、NUMA、多线程、SMT、CMT、……

当你拥有所有这些时,你会看到一堆你需要知道如何解释的数字,这需要深入的统计知识。

benchmark library in the Ruby stdlib 就是其中许多“罪过”的一个例子。 25 年前它非常好,当时只有一个 Ruby 实现,它只是一个愚蠢的 AST-walking 解释器,没有任何优化,而计算机有一个 CPU 没有乱序执行或投机,仅此而已。但就目前而言,我们有大量积极优化的 Ruby 实现(最突出的是 TruffleRuby)和执行自己优化的复杂 CPUs,它只是没有别再剪了

不幸的是,没有可与现有工具相媲美的基准测试工具,例如在 Java 世界中,但至少有一些替代方案,例如 better-benchmark (no longer maintained), benchmark-ips (by Evan Phoenix, founder of Rubinius), or fruity(Marc-André Lafortune,ruby-核心团队成员)。