译文 两次拷贝操作的故事

haoheipi · 2021年08月19日 · 214 次阅读
本帖已被设为精华帖!

这是最好的时代,也是最坏的时代。最近,我遇到了一个性能方面的困惑,这让我进入了一场为期数天的探索中。我正在写部分代码来获取一些条目,然后将它们添加到一个固定大小的内存缓冲区中,最后在缓冲区满时将该缓冲区刷回到磁盘中。主代码看起来有点像这样:

type Buffer struct {
    fh  *os.File
    n   uint
    buf [numEntries]Entry
}

func (b *Buffer) Append(ent Entry) error {
    if b.n < numEntries-1 {
        b.buf[b.n] = ent
        b.n++
        return nil
    }
    return b.appendSlow(ent)
}

我们的想法是,当缓冲区中有空间时,我们只需插入条目并增加一个计数器;当缓存区满了时,它将转到那个写入磁盘的较慢方法。非常地简单,对吗?

基准测试

我有一个关于条目大小的问题。我能将它们打包成的最小大小是 28 字节,但对于对齐和其他情况来说,这没有一个 2 的幂次方数合适,所以我想将它与 32 字节进行比较。我决定编写一个基准测试,而不是仅仅依靠我的直觉。基准测试将在每次迭代中追加固定数量的条目 (100,000) ,唯一改变的是条目大小是否为 28 或 32 字节。

即使我不依赖我的直觉,但我发现尝试去预测将会发生什么是非常有用并且有趣的。于是,我心想:

大家都知道,I/O 性能通常比一个低效的小的 CPU 更占主导地位。与 32 字节版本相比,28 字节版本写入的数据更少,对磁盘的刷新也更少。即使在填充内存缓冲区时有点慢 (我对此表示怀疑),也会有更多的写操作来弥补。

也许你想的是类似的事情,也许是完全不同的事情。也许你现在不是来思考的只是想让我继续思考。因此,我运行了以下基准测试:

func BenchmarkBuffer(b *testing.B) {
    fh := tempFile(b)
    defer fh.Close()

    buf := &Buffer{fh: fh}
    now := time.Now()
    ent := Entry{}

    b.ResetTimer()

    for i := 0; i < b.N; i++ {
        fh.Seek(0, io.SeekStart)

        for i := 0; i < 1e5; i++ {
            _ = buf.Append(ent)
        }
        _ = buf.Flush()
    }

    b.ReportMetric(float64(time.Since(now).Nanoseconds())/float64(b.N)/1e5, "ns/key")
    b.ReportMetric(float64(buf.flushes)/float64(b.N), "flushes")
}

困惑

结果如下:

BenchmarkBuffer/28       734286 ns/op      171.0 flushes      7.343 ns/key
BenchmarkBuffer/32       436220 ns/op      196.0 flushes      4.362 ns/key

没错,在基准测试中,写入磁盘数据更多的但还更快,性能相差近 2 倍!

我的探索就这样开始了。以下是我为解答我认为正在发生的事情而进行的漫长而奇怪的探寻所做的努力。剧透警告:我错了很多次,而且错了很长一段时间。

探索开始

CPU 性能剖析

CPU 性能报告是有非常高的参考价值。要从 Go 基准测试中收集它们,你所要做的就是在命令行中指定 -cpuprofile=<some file> ,仅此而已。当然,这是我第一次尝试。

不过,要记住的一件事是,Go 基准测试在默认情况下将尝试运行固定的时间,如果一个基准测试比另一个要花更长的时间来完成它的工作,那么它的迭代次数就会更少。因为我想更直接地比较结果,所以我确保向命令 -benchtime=2000x 传递固定次数的迭代。

让我们来看看这些结果。首先,32 字节版本:

    .          .     24:func (b *Buffer) Append(ent Entry) error {
 30ms       30ms     25:   if b.n < numEntries-1 {
110ms      110ms     26:       b.buf[b.n] = ent
 90ms       90ms     27:       b.n++
    .          .     28:       return nil
    .          .     29:   }
 10ms      520ms     30:   return b.appendSlow(ent)
    .          .     31:}

第一列显示仅在所示函数的上下文中花费的时间,第二列是在该行 (包括它可能调用的任何函数) 上花费的时间。

由此,我们可以看到,与写入内存缓冲区相比,大部分时间都花在了 appendSlow 中刷新磁盘上。

这是 28 字节的版本:

    .          .     24:func (b *Buffer) Append(ent Entry) error {
 20ms       20ms     25:   if b.n < numEntries-1 {
840ms      840ms     26:       b.buf[b.n] = ent
 20ms       20ms     27:       b.n++
    .          .     28:       return nil
    .          .     29:   }
    .      470ms     30:   return b.appendSlow(ent)
    .          .     31:}

与 32 字节版本相比,它花费更少的时间刷新到磁盘。这至少是符合预期的,因为它刷新的次数更少 ( 171 次 vs 196 次)。

但也许内存不对齐的惩罚比我想象的更糟糕。让我们看一下汇编代码,看看它使用了什么指令。

汇编过程

下面是在上面的结果文件中第 26 行出现 840ms 的代码部分:

    .          .     515129: IMULQ $0x1c, CX, CX          (1)
 90ms       90ms     51512d: LEAQ 0xc0(SP)(CX*1), CX      (2)
    .          .     515135: MOVUPS 0x7c(SP), X0          (3)
670ms      670ms     51513a: MOVUPS X0, 0(CX)             (4)
 80ms       80ms     51513d: MOVUPS 0x88(SP), X0          (5)
    .          .     515145: MOVUPS X0, 0xc(CX)           (6)

如果您以前从未读过汇编,这可能会有点令人生畏,所以我已经对行进行了编号,并将提供一个简短的解释。要知道的最重要的寄存器是 CXSPX0 ,语法 0x18(CX) 意味着地址 CX + 0x18 的值。有了这些知识,我们就能理解这些行意思了:

  1. CX 寄存器乘以 0x1c 并将其存储到 CX 中。 0x1c 是十进制值 28 的十六进制编码。

  2. 这是计算我们将存储的条目的地址。它计算 0xc0 + SP + (CX*1) 并将其存储到 CX 中。由此,我们推断 entry 数组的开始位置是 0xc0(SP)

  3. 这将从 0x7c(SP) 开始加载 16 个字节,并将其存储到 X0

  4. 这将存储我们刚刚加载到 0(CX) 中的 16 个字节。

  5. 这将从 0x88(SP) 开始加载 16 个字节并将其存储到 X0 中。

  6. 这将存储我们刚刚加载到 0xc(CX) 中的 16 个字节。

我不知道你怎么想的,但我看不出为什么第 4 行比其他行有这么大的权重。所以,我将它与 32 字节版本进行了比较,看看生成的代码是否不同:

40ms       40ms     515129: SHLQ $0x5, CX
10ms       10ms     51512d: LEAQ 0xc8(SP)(CX*1), CX
   .          .     515135: MOVUPS 0x80(SP), X0
10ms       10ms     51513d: MOVUPS X0, 0(CX)
40ms       40ms     515140: MOVUPS 0x90(SP), X0
10ms       10ms     515148: MOVUPS X0, 0x10(CX)

看起来唯一的区别是 SHLQ vs IMULQ,但几乎没有时间花在这些指令上。前者是对 5 进行 “左移”,实际上是乘以 2 的 5 次方,也就是 32,而后者,正如我们之前看到的,是乘以 28。这可能是性能上的差异吗?

流水线和端口

现代 cpu 是一个复杂的怪兽。也许你有这样的思维模式: CPU 读取指令,然后一次执行一个指令。但那根本不是事实。相反,它们在 流水线 中同时执行多条指令,可能是无序的。且它还有更好的地方: 它们限制了每种指令可以同时运行的数量。这是由具有多个 “端口” 的 CPU 完成的,某些指令需要并可以在这些端口的不同子集上运行。

这和 IMULQ 和 SHLQ 有什么关系呢?好吧,你可能已经注意到,在 IMULQ/SHLQ 之后的 LEAQ 有一个乘法(CX*1)。但是,因为没有无限的端口,所以能够进行乘法运算的端口数量是有限的。

LLVM 项目有很多工具可以帮助您理解计算机的功能,其中一个工具叫做 LLVM-mca。实际上,如果我们通过 llvm-mca 运行 32 字节和 28 字节版本的第一个指令,它会让我们知道在执行它们时将使用哪些端口:

Resource pressure by instruction (32 byte version):
[2]    [3]     [7]    [8]     Instructions:
0.50    -       -     0.50    shlq  $5, %rcx
 -     0.50    0.50    -      leaq  200(%rsp,%rcx), %rcx

Resource pressure by instruction (28 byte version):
[2]    [3]     [7]    [8]    Instructions:
 -     1.00     -      -     imulq  $28, %rcx, %rcx
 -      -      1.00    -     leaq   192(%rsp,%rcx), %rcx

这些数字是每条指令在循环执行时在端口上运行的时间百分比 (这里,编号为 2 、 3 、 7 和 8 )。

也就是说,在 32 字节版本中,SHLQ 有一半时间运行在端口 2 上,另一半时间运行在端口 8 上,LEAQ 有一半时间运行在端口 3 上,另一半时间运行在端口 7 上。这意味着它可以同时有 2 个并行执行。例如,在一次迭代中,它可以使用端口 2 和 3,在下一次迭代中,它可以使用端口 7 和 8,即使端口 2 和 3 仍然在使用。然而,对于 28 字节版本,由于处理器的构建方式,IMULQ 只能在端口 3 上进行,这反过来又限制了最大吞吐量。

有一段时间,我以为这就是问题的原因。事实上,这篇博文的初稿就有这个结论,但我越想越觉得这个解释不太好。

陷阱迷宫

以下是你可能会有的一些想法:

  1. 在最坏的情况下,这只能是 2 倍的速度差。

  2. 循环中没有其他指令吗?不,那这必须使它在实际中远远小于 2 倍。

  3. 32 字节版本在内存部分花费 230ms, 28 字节版本花费 880ms。

  4. 这是比 2 倍大得多。

  5. 不对!

也许最后一个是我的心声。带着这些疑问,我试着弄清楚我该如何测试它是否与 IMULQ 和 SHLQ 有关。现在进入 “perf” 篇。

Perf

perf是一个在 linux 上运行的工具,它允许您执行程序,并暴露 cpu 保存的关于如何执行指令的详细计数器 (以及更多其他细节!)。现在,我不知道是否有一个计数器可以让我看到 “流水线因端口不足或其他原因而停止” 之类的东西,但我知道它有类似于所有事情的计数器。

如果这是一部电影,这部分应该是主角在贫瘠的沙漠中跋涉,烈日炎炎,热量从地面上升,看不到尽头。他们会看到海市蜃楼般的绿洲,然后跳进水里,大口大口地吞下水,突然意识到那是沙子。

快速浏览了一遍,perf 知道如何在我的机器上读取 700 多个不同的计数器,我觉得我已经看过其中大部分了。如果你有兴趣,可以看看 这个大表。我找不到任何计数器能解释速度的巨大差异,我开始绝望了。

二进制数编辑的乐趣和收益

此时,我不知道问题是什么,但它看起来肯定不是我想的端口争用。我认为唯一可能的事情之一就是对齐。cpu 倾向于以 2 的幂次放访问内存,而 28 不是其中之一,所以我想改变基准测试,写入 28 字节的条目,但偏移量为 32 字节。

不幸的是,这并不像我希望的那么容易。被测试的代码与 Go 编译器的内联非常微妙地平衡了。基本上,对 Append 的任何更改都会导致它超过阈值并停止内联,这实际上会改变正在执行的内容。

输入二进制补丁。在我们的例子中,IMULQ 指令编码成与 SHLQ 相同的字节数。事实上,IMULQ 编码为486bc91c, SLHQ 编码为 48c1e105 。因此,只需替换这些字节并运行基准测试即可。我 (仅此一次) 就不告诉你我是如何编辑它的细节了 (好吧,我撒谎了:我经常使用 dd)。结果确实让我大吃一惊:

BenchmarkBuffer/28@32    813529 ns/op      171.0 flushes      8.135 ns/key

我看到了这个结果,感到很挫败。并不是 IMULQ 让基准测试变慢了。这个基准没有 IMULQ。这不是由于不对齐的写入。最慢的指令是用与 32 字节版本相同的对齐方式编写的,正如我们从汇编性能中看到的:

    .          .     515129: SHLQ $0x5, CX
 60ms       60ms     51512d: LEAQ 0xc0(SP)(CX*1), CX
    .          .     515135: MOVUPS 0x7c(SP), X0
850ms      850ms     51513a: MOVUPS X0, 0(CX)
120ms      120ms     51513d: MOVUPS 0x88(SP), X0
    .          .     515145: MOVUPS X0, 0xc(CX)

还有什么可以尝试的呢?

一个小的转变

有时,当我不知道为什么某些代码慢时,我会尝试用不同的方式编写相同的代码。这可能会引起编译器的调整,使它改变是否可以使用哪些优化,从而提供一些关于正在发生的事情的线索。本着这种精神,我把基准测试改成了这样:

func BenchmarkBuffer(b *testing.B) {
    // ... setup code

    for i := 0; i < b.N; i++ {
        fh.Seek(0, io.SeekStart)

        for i := 0; i < 1e5; i++ {
            _ = buf.Append(Entry{})
        }
        _ = buf.Flush()
    }

    // .. teardown code
}

这很难看出区别,但它改为了每次都传递一个新的条目值,而不是手动将 ent 变量传递出循环。我又做了一次基准测试。

BenchmarkBuffer/28       407500 ns/op      171.0 flushes      4.075 ns/key
BenchmarkBuffer/32       446158 ns/op      196.0 flushes      4.462 ns/key

它起作用了吗?这种变化怎么可能导致性能差异呢?它居然比 32 字节版本运行得更快了!像往常一样,该看下汇编了。

 50ms       50ms     515109: IMULQ $0x1c, CX, CX
    .          .     51510d: LEAQ 0xa8(SP)(CX*1), CX
    .          .     515115: MOVUPS X0, 0(CX)
130ms      130ms     515118: MOVUPS X0, 0xc(CX)

它不再从栈中加载值来存储到数组中,而是直接从已经归零的寄存器中存储到数组中。但是我们从前面所做的所有流水线分析中知道额外的负载应该是生效的,并且 32 字节版本证实了这一点。它并没有变得更快,即使它也不再从栈加载。

到底发生了什么?

写重叠

为了解释这个想法,最重要的是要展示整个循环的汇编过程,而不仅仅是将条目写入内存缓冲区的代码。下面是一个经过清理和注释的较慢的 28 字节基准测试的内部循环:

loop:
  INCQ AX                     (1)
  CMPQ $0x186a0, AX
  JGE exit

  MOVUPS 0x60(SP), X0         (2)
  MOVUPS X0, 0x7c(SP)
  MOVUPS 0x6c(SP), X0
  MOVUPS X0, 0x88(SP)

  MOVQ 0xb8(SP), CX           (3)
  CMPQ $0x248, CX
  JAE slow

  IMULQ $0x1c, CX, CX         (4)
  LEAQ 0xc0(SP)(CX*1), CX
  MOVUPS 0x7c(SP), X0         (5)
  MOVUPS X0, 0(CX)
  MOVUPS 0x88(SP), X0
  MOVUPS X0, 0xc(CX)

  INCQ 0xb8(SP)               (6)
  JMP loop

slow:
   // ... slow path goes here ...

exit:
  1. 增加 AX,将它与 100,000 比较,如果它更大则退出。

  2. 从 offset [0x60, 0x7c] 复制栈上的 28 个字节到 offset [0x7c, 0x98]

  3. 加载内存计数器,看看内存缓冲区中是否还有空间。

  4. 计算条目将被写入内存缓冲区的位置。

  5. 在 offset [0x7c, 0x98] 处将栈上的 28 个字节复制到内存缓冲区中。

  6. 增加内存计数器并再次循环。

步骤 4 和步骤 5 是我们到目前为止一直在研究的内容。

似乎第二步看起来愚蠢而多余。确实如此,没有理由将栈上的值复制到栈上的另一个位置,然后从栈上的副本加载到内存缓冲区中。步骤 5 可以只使用偏移量 [0x60, 0x7c] 来代替,而步骤 2 可以被消除。Go 编译器在这里可以做得更好。

但这不应该是它慢的原因,对吧? 32 字节的代码几乎做了同样愚蠢的事情,但它运行得很快,因为流水线或其他神奇的东西。到底发生了什么事?

有一个关键的区别: 28 字节的写重叠。MOVUPS 指令一次写 16 个字节,众所周知,16 + 16 通常大于 28。所以步骤 2 写入字节 [0x7c, 0x8c] 然后写入字节 [0x88, 0x98] 。这意味着 [0x88, 0x8c] 被写入了两次。下面是一个有用的 ASCII 图表:

0x7c             0x8c
├────────────────┤
│  Write 1 (16b) │
└───────────┬────┴──────────┐
            │ Write 2 (16b) │
            ├───────────────┤
            0x88            0x98

存储转发

还记得 cpu 是多么复杂的怪兽吗?它还有更多其他的优化。一些 cpu 做的优化是它们有一个叫做 “写缓冲区” 的东西。你看,内存访问通常是 cpu 所做的最慢的部分。相反,你知道,当指令执行时,实际写入内存前,cpu 首先将写入放进缓冲区。我认为其思想是,在向较慢的内存子系统输出之前,将一组较小的写操作合并为较大的写操作。听起来是不是很熟悉?

现在它有一个写缓冲区来缓冲所有写操作。如果在这些写操作中有一个读操作会发生什么呢?如果在读取数据之前必须等待写操作实际发生,那么它会减慢所有操作的速度,因此,如果可能的话,它会尝试直接从写缓冲区处理读操作,没有人比它更聪明。这种优化称为 存储转发

但是如果这些写重叠呢?事实证明,至少在我的 CPU 上,这抑制了 “存储转发” 的优化。甚至还有一个性能计数器来跟踪这种情况的发生:ld_blocks.store_forward

实际上,关于那个计数器的文档是这样描述:

计算阻止存储转发的次数主要来源于加载操作。最常见的情况是由于内存访问地址 (部分) 与前面未完成的存储重叠而导致负载阻塞。

以下是到目前为止,计数器命中不同基准测试的频率,“慢” 表示该条目在循环外构造,“快” 表示在每次迭代中该条目在循环内构造:

BenchmarkBuffer/28-Slow      7.292 ns/key      1,006,025,599 ld_blocks.store_forward
BenchmarkBuffer/32-Slow      4.394 ns/key          1,973,930 ld_blocks.store_forward
BenchmarkBuffer/28-Fast      4.078 ns/key          4,433,624 ld_blocks.store_forward
BenchmarkBuffer/32-Fast      4.369 ns/key          1,974,915 ld_blocks.store_forward

是的,十亿通常比一百万大。开香槟庆祝吧。

结论

在这之后,我有一些想法。

基准测试是困难的。人们经常这么说,但也许唯一比基准测试更难的事情是充分传达基准测试有多困难。比如,这更接近于微观基准测试,而不是宏观基准测试,但仍然包括执行数以百万计的操作,包括磁盘刷新,并实际测量了实际效果。但与此同时,这在实践中几乎不会成为问题。它需要编译器将一个常量值溢出到栈中,而这个常量值与随后的读入非常接近,这是没有必要的。创建条目所做的任何实际工作都会导致这种效果消失。

随着我对 cpu 工作方式了解的越来越多,一个反复出现的主题是,你越接近 cpu 工作的 “核心”,它就越容易泄漏,也就越充满边缘情况和危险。例如,如果有部分重叠的写,存储转发将会不工作。另一个原因是缓存不是 完全关联的,所以你只能根据它们的内存地址缓存这么多东西。比如,即使你有 1000 个可用的插槽,如果你所有的内存访问都是某个因子的倍数,他们可能无法使用这些插槽。这篇博文有很好的讨论。我猜测,也许这是因为在更严格的物理约束下,解决这些边缘情况的 “空间” 更小了。

在此之前,我从未能够在实际的非人为设置中具体观察到端口耗尽问题导致的 CPU 减慢。我听过这样的说法,你可以想象每一条 CPU 指令占用 0 个周期,除了那些与内存有关的指令。作为初步估计,这似乎是正确的。

我已经把完整的代码示例放在 a gist中,供您查看/下载/运行/校验。

通常情况下,探索比结果更重要,我认为在这里也是如此。如果你能走到这一步,谢谢你陪我一路走来,希望你喜欢。下次再见。

更多原创文章干货分享,请关注公众号
  • 加微信实战群请加微信(注明:实战群):gocnio
astaxie 将本帖设为了精华贴 08月19日 03:18
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册