无法重现 cpu 缓存未命中

Question

美好的一天！

我正在阅读这篇精彩的文章：What every programmer should know about memory。现在我正试图弄清楚 CPU 缓存是如何工作的，并重现缓存未命中的实验。目的是在访问数据量增加时重现性能下降（图 3.4）。我写了一个小程序，应该可以重现退化，但它没有。分配超过4Gb的内存后出现性能下降，我不明白为什么。我认为它应该在分配 12 或 100 MB 时出现。也许程序是错误的，我错过了什么？我用

Intel Core i7-2630QM
L1: 256Kb
L2: 1Mb
L3: 6Mb

这是 GO 列表。

main.go

package main

import (
    "fmt"
    "math/rand"
)

const (
    n0 = 1000
    n1 = 100000
)

func readInt64Time(slice []int64, idx int) int64

func main() {
    ss := make([][]int64, n0)
    for i := range ss {
        ss[i] = make([]int64, n1)
        for j := range ss[i] {
            ss[i][j] = int64(i + j)
        }
    }
    var t int64
    for i := 0; i < n0; i++ {
        for j := 0; j < n1; j++ {
            t0 := readInt64Time(ss[i], rand.Intn(n1))
            if t0 <= 0 {
                panic(t0)
            }
            t += t0
        }
    }
    fmt.Println("Avg time:", t/int64(n0*n1))
}

main.s

// func readInt64Time(slice []int64, idx int) int64
TEXT ·readInt64Time(SB),[=13=]-40
    MOVQ    slice+0(FP), R8
    MOVQ    idx+24(FP), R9
    RDTSC
    SHLQ    , DX
    ORQ     DX, AX
    MOVQ    AX, R10
    MOVQ    (R8)(R9*8), R8 // Here I'm reading the memory
    RDTSC
    SHLQ    , DX
    ORQ     DX, AX
    SUBQ    R10, AX
    MOVQ    AX, ret+32(FP)
    RET

Answer 1

对于那些感兴趣的人。我重现了 'cache-miss' 行为。但性能下降并不像文章描述的那样剧烈。这是最终的基准列表：

main.go

package main

import (
    "fmt"
    "math/rand"
    "runtime"
    "runtime/debug"
)

func readInt64Time(slice []int64, idx int) int64

const count = 2 << 25

func measure(np uint) {
    n := 2 << np
    s := make([]int64, n)
    for i := range s {
        s[i] = int64(i)
    }
    t := int64(0)
    n8 := n >> 3
    for i := 0; i < count; i++ {
        // Intex is 64 byte aligned, since cache line is 64 byte
        t0 := readInt64Time(s, rand.Intn(n8)<<3)
        t += t0
    }
    fmt.Printf("Allocated %d Kb. Avg time: %v\n",
        n/128, t/count)
}

func main() {
    debug.SetGCPercent(-1) // To eliminate GC influence
    for i := uint(10); i < 27; i++ {
        measure(i)
        runtime.GC()
    }
}

main_amd64.s

// func readInt64Time(slice []int64, idx int) int64
TEXT ·readInt64Time(SB),[=11=]-40
    MOVQ    slice+0(FP), R8
    MOVQ    idx+24(FP), R9
    RDTSC
    SHLQ    , DX
    ORQ     DX, AX
    MOVQ    AX, R10
    MOVQ    (R8)(R9*8), R11 // Read memory
    MOVQ    [=11=], (R8)(R9*8) // Write memory
    RDTSC
    SHLQ    , DX
    ORQ     DX, AX
    SUBQ    R10, AX
    MOVQ    AX, ret+32(FP)
    RET

我禁用了垃圾收集器以消除其影响并进行了 64B 索引对齐，因为我的处理器有 64B 缓存行。

基准测试结果是：

Allocated 16 Kb. Avg time: 22
Allocated 32 Kb. Avg time: 22
Allocated 64 Kb. Avg time: 22
Allocated 128 Kb. Avg time: 22
Allocated 256 Kb. Avg time: 22
Allocated 512 Kb. Avg time: 23
Allocated 1024 Kb. Avg time: 23
Allocated 2048 Kb. Avg time: 24
Allocated 4096 Kb. Avg time: 25
Allocated 8192 Kb. Avg time: 29
Allocated 16384 Kb. Avg time: 31
Allocated 32768 Kb. Avg time: 33
Allocated 65536 Kb. Avg time: 34
Allocated 131072 Kb. Avg time: 34
Allocated 262144 Kb. Avg time: 35
Allocated 524288 Kb. Avg time: 35
Allocated 1048576 Kb. Avg time: 39

我运行这个长凳很多次，每次运行都给了我相似的结果。如果我从 asm 代码中删除了读写操作，那么我得到了 22 个用于所有分配的周期，所以这个时间差就是内存访问时间。如您所见，第一个时间偏移是 512 Kb 分配大小。只有一个 cpu 周期，但它非常稳定。下一次更改为 2 Mb。在 8 Mb 时有最显着的时间变化，但它仍然是 4 个周期，我们完全没有缓存。

在所有这些测试之后，我发现缓存未命中并没有太大的成本。它仍然很重要，因为时差是 10-15 倍，而不是我们在文章中看到的 50-500 倍。也许今天的内存比 7 年前快得多？看起来很有希望 =) 也许在接下来的 7 年之后，将会出现完全没有 cpu 缓存的架构。我们拭目以待。

编辑：正如@Leeor 所提到的，RDTSC 指令没有序列化行为，并且可能会乱序执行。我改用 RDTSCP 指令：

main_amd64.s

// func readInt64Time(slice []int64, idx int) int64
TEXT ·readInt64Time(SB),[=13=]-40
    MOVQ    slice+0(FP), R8
    MOVQ    idx+24(FP), R9
    BYTE [=13=]x0F; BYTE [=13=]x01; BYTE [=13=]xF9; // RDTSCP
    SHLQ    , DX
    ORQ     DX, AX
    MOVQ    AX, R10
    MOVQ    (R8)(R9*8), R11 // Read memory
    MOVQ    [=13=], (R8)(R9*8) // Write memory
    BYTE [=13=]x0F; BYTE [=13=]x01; BYTE [=13=]xF9; // RDTSCP
    SHLQ    , DX
    ORQ     DX, AX
    SUBQ    R10, AX
    MOVQ    AX, ret+32(FP)
    RET

这里是我得到的变化：

Allocated 16 Kb. Avg time: 27
Allocated 32 Kb. Avg time: 27
Allocated 64 Kb. Avg time: 28
Allocated 128 Kb. Avg time: 29
Allocated 256 Kb. Avg time: 30
Allocated 512 Kb. Avg time: 34
Allocated 1024 Kb. Avg time: 42
Allocated 2048 Kb. Avg time: 55
Allocated 4096 Kb. Avg time: 120
Allocated 8192 Kb. Avg time: 167
Allocated 16384 Kb. Avg time: 173
Allocated 32768 Kb. Avg time: 189
Allocated 65536 Kb. Avg time: 201
Allocated 131072 Kb. Avg time: 215
Allocated 262144 Kb. Avg time: 224
Allocated 524288 Kb. Avg time: 242
Allocated 1048576 Kb. Avg time: 281

现在我看到了 cahce 和 RAM 访问之间的巨大差异。时间实际上比文章中的时间低 2 倍，但它是可以预测的，因为内存频率高出两倍。

Answer 2

这确实不会产生尝试观察，不清楚您的基准究竟做了什么 - 您是否在范围内随机访问？您在测量每次访问的访问延迟吗？

您的基准测试似乎会在每次未摊销的时间测量中产生恒定的开销，因此您基本上是在测量函数调用时间（这是常数）。只有当内存延迟变得足够大以传递该开销时（当您以 4GB 访问 DRAM 时），您才真正开始获得有意义的测量值。

您应该切换到测量整个循环（超过 count 次迭代）和除法的时间。

无法重现 cpu 缓存未命中

Can't reproduce cpu cache-miss

cpu-cache