解析 ‘Branch Prediction’ 友好型代码：为什么在 Go 中处理排序后的数组比乱序快得多？ - 智猿学院-前后端，数据库，人工智能，云计算等领域前沿技术讲座

各位同仁，各位对性能优化和底层机制充满好奇的朋友们，下午好！

今天，我们将一起深入探讨一个在高性能计算领域看似玄妙，实则根植于硬件本质的现象：为什么在 Go 语言中，处理一个已排序的数组通常比处理一个乱序的数组要快得多？这并非 Go 语言的魔法，也不是编译器凭空创造的奇迹，而是现代 CPU 架构中两大核心优化技术——分支预测 (Branch Prediction) 和 缓存机制 (Cache Memory Hierarchy)——共同作用的结果。

我们将从硬件层面出发，逐步揭示这些“幕后英雄”的工作原理，然后结合 Go 语言的特性和代码实践，理解如何编写能够充分利用这些硬件优势的“分支预测友好型”代码。

I. 硬件的奥秘：CPU 流水线与分支预测

要理解为什么排序后的数组处理更快，我们首先需要理解现代 CPU 是如何工作的。

1. CPU 流水线：效率的基石

想象一下汽车装配线。一辆汽车在不同的工位（发动机、车身、喷漆、内饰）并行组装。当一辆车在喷漆工位时，另一辆车可能正在安装发动机，第三辆车可能正在焊接车身。这就是指令流水线 (Instruction Pipeline) 的核心思想。

CPU 将一条指令的执行分解为多个阶段（例如：取指、译码、执行、访存、写回）。通过流水线，CPU 可以在同一时刻处理多条不同的指令的不同阶段，从而大大提高吞吐量，而不是等待一条指令完全执行完毕再开始下一条。

指令流水线示意图：

阶段 / 时间片	T1	T2	T3	T4	T5
取指 (IF)	Inst A	Inst B	Inst C	Inst D	Inst E
译码 (ID)		Inst A	Inst B	Inst C	Inst D
执行 (EX)			Inst A	Inst B	Inst C
访存 (MEM)				Inst A	Inst B
写回 (WB)					Inst A

在这个例子中，虽然每条指令仍然需要5个时间片才能完成，但在第5个时间片，CPU 已经完成了 Inst A，并且正在处理 Inst B、C、D、E 的不同阶段。理想情况下，一个5级流水线可以在每个时间片完成一条指令的执行。

2. 分支指令：流水线的“破坏者”

流水线的效率建立在一个关键假设之上：指令是顺序执行的。然而，现实并非如此。我们编写的代码中充斥着各种分支指令 (Branch Instructions)，例如 if/else 语句、for 循环、while 循环、函数调用等。这些指令会改变程序的控制流，导致 CPU 不确定下一条要执行的指令在哪。

当 CPU 遇到一个分支指令时，它有两个可能的路径：要么继续执行分支后的指令（不跳转），要么跳转到另一个地址执行指令。如果 CPU 不知道哪个路径会被采取，它就必须暂停流水线，等待分支条件的结果确定，然后才能继续。这种暂停被称为流水线气泡 (Pipeline Bubble) 或流水线停顿 (Pipeline Stall)，会严重降低 CPU 的性能。

3. 分支预测：CPU 的“第六感”

为了避免流水线停顿，现代 CPU 引入了分支预测器 (Branch Predictor Unit – BPU)。顾名思义，它的任务是在分支指令的条件结果出来之前，猜测哪个分支会被采取，并根据猜测提前取指并填充流水线。

分支预测器通常基于历史行为进行预测。它会维护一个分支历史缓冲区 (Branch History Buffer)，记录过去某个分支是跳转了还是没有跳转。例如：

简单的1位预测器： 记住上次这个分支的结果。如果上次跳转了，就预测这次也会跳转；反之亦然。
2位预测器 (Saturating Counter)： 使用一个2位计数器。00 代表“强不跳转”，01 代表“弱不跳转”，10 代表“弱跳转”，11 代表“强跳转”。每次预测正确或错误都会调整计数器，提供更强的鲁棒性，减少偶尔的预测失误对整体预测准确率的影响。

分支预测的流程：

CPU 遇到分支指令。
分支预测器根据历史数据猜测分支走向。
CPU 根据预测结果，提前取指并填充流水线。
当分支条件实际结果出来时，与预测结果进行比较：
- 预测正确 (Prediction Hit)： 皆大欢喜！流水线继续全速运行，没有性能损失。
- 预测错误 (Prediction Miss)： 灾难降临！CPU 必须清空（flush）已经填充的、基于错误预测的指令，然后重新从正确的分支路径取指，并重新填充流水线。这个过程会消耗大量的 CPU 周期（通常是10-20个或更多周期），严重影响性能。

4. 为什么排序数组是分支预测友好的？

现在我们回到排序数组的问题。考虑一个简单的 if 条件判断：

if value < threshold {
    // do something
}

对于已排序的数组 (例如升序)：
- 在数组的前半部分，value 很可能一直小于 threshold，导致 if 条件连续为真（或者连续为假）。
- 一旦 value 达到或超过 threshold，它在数组的剩余部分很可能一直大于 threshold，导致 if 条件连续为假（或者连续为真）。
- 这种连续性意味着分支的行为是高度可预测的。分支预测器能够轻松地识别这种模式（例如，连续100次跳转，然后连续200次不跳转），并做出几乎100%准确的预测。
对于乱序的数组：
- value 与 threshold 的关系是随机波动的。有时小于，有时大于。
- 分支条件的结果是高度不可预测的。分支预测器很难识别出任何稳定的模式，从而导致大量的预测错误。每次预测错误，都会导致昂贵的流水线停顿。

代码示例：Go 中分支预测的影响

让我们通过一个 Go 语言的例子来直观感受分支预测带来的性能差异。我们将创建一个大数组，填充随机数，然后对其进行排序和反向排序。接着，我们编写一个函数，对这些数组进行简单的条件判断求和，并使用 Go 的 testing 包进行基准测试。

package main

import (
    "fmt"
    "math/rand"
    "sort"
    "testing"
    "time"
)

const (
    arraySize = 100_000_000 // 1亿个整数
    threshold = 50_000_000  // 阈值
)

// generateInts 生成指定大小的整数数组
func generateInts(size int, order string) []int {
    arr := make([]int, size)
    r := rand.New(rand.NewSource(time.Now().UnixNano())) // 使用新的随机源

    for i := 0; i < size; i++ {
        arr[i] = r.Intn(size) // 填充 0 到 size-1 的随机数
    }

    switch order {
    case "sorted":
        sort.Ints(arr)
    case "reverse":
        sort.Sort(sort.Reverse(sort.IntSlice(arr)))
    case "random":
        // 已经是随机的，无需额外处理
    case "half_sorted": // 一半排序，一半随机，模拟部分可预测性
        sort.Ints(arr[:size/2])
        // arr[size/2:] 保持随机
    case "alternating": // 交替排序，模拟可预测但频繁切换
        for i := 0; i < size; i++ {
            if i%2 == 0 {
                arr[i] = i
            } else {
                arr[i] = size - i
            }
        }
    }
    return arr
}

// sumIfCondition 对数组进行条件求和
func sumIfCondition(arr []int, threshold int) int {
    sum := 0
    for _, v := range arr {
        if v < threshold { // 这里的条件判断是分支预测的关键
            sum += v
        }
    }
    return sum
}

// Benchmark 函数用于基准测试
func BenchmarkSumIfCondition(b *testing.B) {
    fmt.Println("n--- Benchmarking sumIfCondition ---")

    // 准备不同类型的数组
    sortedArr := generateInts(arraySize, "sorted")
    reverseArr := generateInts(arraySize, "reverse")
    randomArr := generateInts(arraySize, "random")
    halfSortedArr := generateInts(arraySize, "half_sorted") // 前半部分有序，后半部分随机
    alternatingArr := generateInts(arraySize, "alternating") // 具有规则但频繁切换

    // 确保所有数组的第一个 sumIfCondition 调用不计入基准测试，作为预热
    _ = sumIfCondition(sortedArr, threshold)
    _ = sumIfCondition(reverseArr, threshold)
    _ = sumIfCondition(randomArr, threshold)
    _ = sumIfCondition(halfSortedArr, threshold)
    _ = sumIfCondition(alternatingArr, threshold)

    b.Run("SortedArray", func(b *testing.B) {
        b.ReportAllocs()
        for i := 0; i < b.N; i++ {
            _ = sumIfCondition(sortedArr, threshold)
        }
    })

    b.Run("ReverseSortedArray", func(b *testing.B) {
        b.ReportAllocs()
        for i := 0; i < b.N; i++ {
            _ = sumIfCondition(reverseArr, threshold)
        }
    })

    b.Run("RandomArray", func(b *testing.B) {
        b.ReportAllocs()
        for i := 0; i < b.N; i++ {
            _ = sumIfCondition(randomArr, threshold)
        }
    })

    b.Run("HalfSortedArray", func(b *testing.B) {
        b.ReportAllocs()
        for i := 0; i < b.N; i++ {
            _ = sumIfCondition(halfSortedArr, threshold)
        }
    })

    b.Run("AlternatingArray", func(b *testing.B) {
        b.ReportAllocs()
        for i := 0; i < b.N; i++ {
            _ = sumIfCondition(alternatingArr, threshold)
        }
    })
}

// main 函数只是一个占位符，实际运行基准测试需要 go test -bench=. -benchmem
func main() {
    fmt.Println("Run `go test -bench=. -benchmem` to execute benchmarks.")
}

运行基准测试： go test -bench=. -benchmem

典型输出（因机器和Go版本而异，这里是模拟结果，但性能趋势一致）：

--- Benchmarking sumIfCondition ---
goos: darwin
goarch: arm64
pkg: example/branch_prediction
cpu: Apple M1 Pro

BenchmarkSumIfCondition/SortedArray-10                     8     137456384 ns/op           0 B/op          0 allocs/op
BenchmarkSumIfCondition/ReverseSortedArray-10              8     137688229 ns/op           0 B/op          0 allocs/op
BenchmarkSumIfCondition/RandomArray-10                     1    1132644267 ns/op           0 B/op          0 allocs/op
BenchmarkSumIfCondition/HalfSortedArray-10                 2     623123456 ns/op           0 B/op          0 allocs/op
BenchmarkSumIfCondition/AlternatingArray-10                2     598765432 ns/op           0 B/op          0 allocs/op
PASS
ok      example/branch_prediction   7.345s

结果分析：

SortedArray 和 ReverseSortedArray 的性能几乎相同，且远超其他情况。这是因为在这两种情况下，v < threshold 这个条件判断的分支行为高度可预测。对于升序数组，一开始可能都是 true，然后突然变成 false；对于降序数组，则相反。这两种模式对分支预测器来说都非常容易学习。
RandomArray 的性能最差，比排序数组慢了大约一个数量级（~8-10倍）。这是分支预测器在此场景下失效的直接体现。每次迭代，条件的结果都是随机的，导致大量的预测错误和流水线清空。
HalfSortedArray 和 AlternatingArray 的性能介于排序和完全随机之间。
- HalfSortedArray 在前半部分因为有序性有不错的预测，后半部分随机性导致预测失败。
- AlternatingArray 虽然有规律（1, N-1, 2, N-2…），但这种频繁切换的规律对于简单的分支预测器来说，可能比完全连续的模式更难高效预测，因为每次都要切换状态，虽然可以学习，但代价可能比纯粹的连续模式高。

这个实验清晰地展示了分支预测对程序性能的巨大影响。

II. 内存的艺术：缓存层次与局部性原理

除了分支预测，另一个对性能影响巨大的因素是内存访问速度。现代 CPU 的运行速度远超主内存 (RAM) 的访问速度。为了弥补这个巨大的速度鸿沟，CPU 引入了多级缓存。

1. 缓存层次结构

CPU 内部或紧邻 CPU 存在多级高速缓存 (Cache)，它们离 CPU 越近，容量越小，速度越快，价格也越昂贵。

典型的缓存层次结构：

缓存级别	容量 (典型)	速度 (典型)	访问延迟 (典型)	存储介质	与 CPU 距离
L1 缓存	几十 KB (指令和数据分离)	纳秒级 (0.5 – 1 ns)	3-5 CPU 周期	SRAM	片上
L2 缓存	几百 KB 到几 MB	几纳秒 (3 – 10 ns)	10-20 CPU 周期	SRAM	片上
L3 缓存	几 MB 到几十 MB	几十纳秒 (10 – 50 ns)	30-50 CPU 周期	SRAM	片上/近核
主内存 (RAM)	几 GB 到几百 GB	几十到几百纳秒 (50-200 ns)	100-300 CPU 周期	DRAM	片外
固态硬盘 (SSD)	几百 GB 到几 TB	几微秒 (10,000 ns)	几万 CPU 周期	NAND	外部

当 CPU 需要访问数据时，它会首先在 L1 缓存中查找。如果找到（缓存命中 – Cache Hit），数据会以极快的速度返回。如果 L1 没有，它会去 L2 查找，依此类推，直到主内存。如果数据在任何一级缓存中都没有找到，最终必须从慢速的主内存中加载，这会带来巨大的性能惩罚。

2. 缓存行 (Cache Line)

缓存并非以单个字节为单位进行存储，而是以固定大小的块进行存储，这些块被称为缓存行 (Cache Line)。典型的缓存行大小是 64 字节。

当 CPU 从主内存中加载数据到缓存时，它不会只加载一个请求的字节，而是会加载包含该字节的整个缓存行。这样做的目的是利用空间局部性 (Spatial Locality)。

3. 局部性原理 (Principle of Locality)

局部性原理是缓存设计的基础，它有两种主要形式：

空间局部性 (Spatial Locality)： 如果一个程序访问了某个内存地址，那么它很可能在不久的将来访问附近的内存地址。例如，遍历数组时，会依次访问数组中的相邻元素。
时间局部性 (Temporal Locality)： 如果一个程序访问了某个内存地址，那么它很可能在不久的将来再次访问同一个内存地址。例如，循环中对某个变量的反复读写。

4. 为什么排序数组是缓存友好的？

对于已排序的数组：
- 数组元素在内存中是连续存放的。当我们顺序遍历一个排序数组时，如果访问了 arr[i]，那么很大概率接下来会访问 arr[i+1]、arr[i+2] 等。
- 由于缓存行机制，当 arr[i] 被加载到缓存时，arr[i+1]、arr[i+2] 等相邻元素也会被一同加载到同一个缓存行中。
- 这意味着后续对相邻元素的访问会直接在 L1 缓存中命中，从而避免了昂贵的主内存访问，极大地提高了数据访问效率。这种模式完美地利用了空间局部性。
对于乱序的数组：
- 虽然乱序数组的元素在内存中也是连续存放的，但如果我们的处理逻辑不是简单的顺序遍历，而是基于元素值或索引的复杂跳转（例如，在某些非缓存友好的排序算法中，或者处理链表等非连续数据结构），那么相邻元素的访问可能不是必然的。
- 但对于我们上面的例子 sumIfCondition，它仍然是顺序遍历。那么，乱序数组的缓存性能会差吗？
- 答案是： 对于这种纯粹的顺序遍历，乱序数组和排序数组在缓存命中率上差异不大。因为无论数据内容如何，只要是顺序访问内存中连续存放的元素，缓存行都能很好地发挥作用。
- 然而，当处理逻辑变得更复杂时，排序数组的优势会更明显。 例如，如果我们需要进行二分查找，或者涉及跳跃式访问（如跳表、树结构），排序数组能够保证我们访问的区域是局部化的，从而减少缓存失效。更重要的是，分支预测和缓存是协同工作的。一个分支预测失败可能导致流水线停顿，而在停顿期间，CPU 无法有效地进行数据预取，也可能间接影响缓存的利用率。

所以，对于 sumIfCondition 这样的简单顺序遍历，性能差异主要源于分支预测，而非缓存。但请记住，在更复杂的场景下，缓存和分支预测的协同效应会更加显著。

III. Go 语言的视角：如何驾驭硬件特性

Go 语言以其简洁、高效和并发特性而闻名。它的设计哲学使得开发者能够相对容易地编写出能够有效利用底层硬件性能的代码。

1. Go 的数据结构与内存布局

数组 (Arrays) 和切片 (Slices)：
在 Go 中，数组是值类型，长度固定，其元素在内存中是连续存放的。切片是基于数组的抽象，它包含一个指向底层数组的指针、长度和容量。切片的操作（如遍历、切片操作）都是在连续的内存区域上进行的。这种连续的内存布局是利用缓存局部性的理想选择。
```
var arr [10]int // 数组，10个int连续存放
slice := make([]int, 100) // 切片，底层是一个100个int的数组，连续存放
```
结构体 (Structs)：
Go 结构体的字段在内存中也是连续存放的（尽管为了对齐可能会有填充字节）。这意味着访问结构体的不同字段也具有很好的空间局部性。
```
type Point struct {
    X, Y int
}
points := make([]Point, 100) // Point 结构体数组，每个Point的X, Y都是连续的
```

2. Go 的 `for` 循环与指令流水线

Go 的 for ... range 循环或传统的 for i := 0; i < N; i++ 循环，在编译后会生成非常高效的机器码，通常是对底层数组指针的顺序递增访问。这种简单的顺序访问模式对于 CPU 的指令流水线和分支预测器来说是极其友好的。

循环条件 i < N 在大部分情况下是可预测的，直到循环结束。
数组元素的顺序访问完美地利用了缓存的空间局部性。

3. Go 的标准库与性能优化

Go 的标准库，特别是 sort 包，在设计时也考虑了性能。

sort.Ints()、sort.Strings() 等函数，是基于优化的算法（通常是混合排序，如 Go 的 TimSort 变体）实现的，这些算法本身在处理数据时也尽量考虑了缓存和分支预测的效率。
虽然排序本身会有性能开销，但如果数据需要被多次处理或查询，那么一次性的排序开销往往是值得的。

IV. 深入剖析：编译器优化与数据对齐

除了 CPU 硬件层面的优化，Go 编译器 (gc) 和 LLVM 等后端编译器也会在软件层面进行优化，进一步提升代码性能。

1. 编译器优化：循环展开与向量化

循环展开 (Loop Unrolling)：
编译器有时会将小循环中的几次迭代合并到循环体内部，减少循环控制（如判断和分支）的次数。例如：
```
// 原始循环
for i := 0; i < 100; i++ {
    arr[i] = i
}

// 编译器可能展开为 (伪代码)
for i := 0; i < 100; i += 4 {
    arr[i] = i
    arr[i+1] = i+1
    arr[i+2] = i+2
    arr[i+3] = i+3
}
```
循环展开减少了分支指令的执行频率，从而提高了分支预测的准确性。
自动向量化 (Auto-Vectorization)：
现代 CPU 包含 SIMD (Single Instruction, Multiple Data) 指令集（如 Intel 的 SSE/AVX，ARM 的 NEON）。这些指令允许 CPU 一次性处理多个数据元素（例如，同时对四个整数执行加法）。编译器能够识别出适合向量化的代码模式（例如，对数组进行连续的操作），并将其转换为 SIMD 指令。
- 排序数组对向量化的帮助： 对于排序数组，因为数据访问模式高度规律且条件分支可预测，编译器更容易进行向量化。例如，当 if v < threshold 的条件在一段连续的元素上结果都是一致时，编译器可以一次性处理多个 v，而无需频繁地检查条件。对于乱序数组，由于频繁的条件切换，向量化往往更难实现或效率更低。

2. 数据对齐 (Data Alignment)

虽然对于 int 这种基本类型数组，Go 会自动处理好对齐，但理解数据对齐仍然很重要。
CPU 通常以字 (Word) 或双字 (Double Word) 为单位从内存读取数据。如果数据没有对齐到这些边界，CPU 可能需要进行多次内存访问或额外的操作来获取完整的数据，从而降低性能。Go 编译器会确保基本类型和结构体字段的正确对齐，以优化内存访问效率。

V. 实践指南：何时以及如何编写分支预测友好型代码

理解了底层原理后，我们如何将这些知识应用到实际的 Go 编程中呢？

1. 优先考虑数据布局和顺序

数组/切片优于链表： 如果你的数据需要频繁遍历，且顺序不重要或可以预处理成顺序，那么数组或切片几乎总是优于链表。链表的元素在内存中不连续，会严重破坏缓存局部性。
结构体数组优于指针数组： []MyStruct 通常比 []*MyStruct 性能更好，因为结构体本身连续存储，而指针数组的每个元素指向的数据可能分散在堆上。
保持数据有序： 如果你的业务逻辑需要对数据进行多次查找、过滤或聚合，并且排序成本可以分摊，那么提前对数据进行排序是一个非常值得的投资。例如，你可能需要对用户列表按 ID 排序，以便后续快速查找或范围查询。

2. 利用算法的优势

二分查找 (Binary Search)：
这是最典型的利用排序数据和分支预测优势的算法。每次比较都将搜索范围减半，其分支路径（向左还是向右）高度可预测。
归并排序等分治算法：
虽然排序本身涉及分支，但像归并排序这种算法，在处理子数组时，由于其局部性，也能较好地利用缓存。
避免不必要的随机访问：
在处理大型数据集时，尽量设计算法，使其能够顺序访问数据，或者至少以局部化的方式访问数据。

3. 编写分支预测友好的条件判断

利用数据特性： 如果你知道数据在某个范围内是连续的，利用这个特性简化条件判断。
重排条件： 有时，改变 if 语句中条件的顺序可能会有所帮助。将最可能为真或最可能为假（即最容易预测）的条件放在前面。
避免在循环中进行高度随机的条件判断： 如果可以，尝试将随机性强的判断移出热点循环，或者用查表法等方式替代。
使用无分支代码 (Branchless Code)：
在某些特定情况下，可以通过数学或位运算来替代 if 语句，完全消除分支。例如，min(a, b) 可以写成 a - ((a - b) & ((a - b) >> 31)) (对于32位有符号整数，负数右移高位补1)。但这通常会降低代码可读性，只有在极端性能敏感的场景下才考虑。

4. 持续性能测量和分析

使用 go test -bench： 这是 Go 语言进行基准测试的官方工具，可以准确地测量代码的执行时间、内存分配等。
使用 go tool pprof： 当发现性能瓶颈时，pprof 是你的好朋友。它可以分析 CPU 使用、内存分配、goroutine 阻塞等，帮助你定位问题的根源。
理解 gopls 或 IDE 的优化建议： 有些工具会提供关于代码优化的建议，例如可以优化的循环、可以减少的内存分配等。

VI. 案例分析：二分查找的极致性能

二分查找是分支预测和缓存局部性协同作用的典范。它要求输入数据必须是排序的。

二分查找的优势：

分支预测： 每次比较 mid 值，分支判断 (小于、等于、大于) 都是高度可预测的。例如，在查找一个不存在的较大值时，分支会连续向右跳转；查找较小值则连续向左。
缓存局部性： 每次迭代都将搜索范围减半。这意味着在大部分时间里，你都在一个相对较小的、连续的内存区域内操作。当这个区域被加载到 L1/L2 缓存后，后续的访问都会是缓存命中，极大地减少了内存延迟。

代码示例：Go 中二分查找与线性查找的对比

package main

import (
    "fmt"
    "math/rand"
    "sort"
    "testing"
    "time"
)

const (
    searchArraySize = 10_000_000 // 1千万个整数
    searchTarget    = 7_894_567  // 要查找的目标值
)

// generateSortedInts 生成一个已排序的整数数组
func generateSortedInts(size int) []int {
    arr := make([]int, size)
    r := rand.New(rand.NewSource(time.Now().UnixNano()))
    for i := 0; i < size; i++ {
        arr[i] = r.Intn(size * 2) // 生成0到2*size-1的随机数
    }
    sort.Ints(arr) // 排序
    return arr
}

// linearSearch 线性查找
func linearSearch(arr []int, target int) int {
    for i, v := range arr {
        if v == target {
            return i
        }
    }
    return -1
}

// binarySearch 二分查找
func binarySearch(arr []int, target int) int {
    low := 0
    high := len(arr) - 1

    for low <= high {
        mid := low + (high-low)/2 // 避免溢出
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target { // 分支判断，高度可预测
            low = mid + 1
        } else { // arr[mid] > target
            high = mid - 1
        }
    }
    return -1
}

// Benchmark 函数用于基准测试
func BenchmarkSearch(b *testing.B) {
    fmt.Println("n--- Benchmarking Search Algorithms ---")

    sortedArr := generateSortedInts(searchArraySize)
    // 确保要查找的目标值在数组中，以避免查找整个数组的极端情况
    // 实际基准测试时，应该测试命中和未命中的情况
    // 这里我们假设 target 存在
    // 也可以在生成时，确保 target 存在于数组中
    foundIndex := binarySearch(sortedArr, searchTarget)
    if foundIndex == -1 {
        // 如果目标不存在，可以考虑插入，或者修改 searchTarget
        // 为了测试目的，我们确保它存在
        sortedArr[rand.Intn(searchArraySize)] = searchTarget
        sort.Ints(sortedArr) // 重新排序以保持有序性
    }

    // 预热
    _ = linearSearch(sortedArr, searchTarget)
    _ = binarySearch(sortedArr, searchTarget)

    b.Run("LinearSearch_SortedArray", func(b *testing.B) {
        b.ReportAllocs()
        for i := 0; i < b.N; i++ {
            _ = linearSearch(sortedArr, searchTarget)
        }
    })

    b.Run("BinarySearch_SortedArray", func(b *testing.B) {
        b.ReportAllocs()
        for i := 0; i < b.N; i++ {
            _ = binarySearch(sortedArr, searchTarget)
        }
    })
}

func main() {
    fmt.Println("Run `go test -bench=. -benchmem` to execute benchmarks.")
}