为何Kotlin协程并行计算加速比超出逻辑处理器数量？

问题背景 #

我正在研究Kotlin协程，采用Nilakantha级数进行性能测试，对比串行与并行计算π的效率。测试环境为Intel Core i3-1115G4（2物理核心、4逻辑核心），使用JDK 8。

测试代码 #

import kotlinx.coroutines.*
import kotlin.system.measureTimeMillis
import kotlin.Long.Companion.MAX_VALUE

const val MEASURE_COUNT = 10
const val ITERATIONS = 1_000_000_000

fun main() {

    val sequentialTime = measureTimeMultiple(ITERATIONS, ::calculatePiNilakanthaSequential, "calculatePiNilakanthaSequential")
    val parallelTime = measureTimeMultiple(ITERATIONS, ::calculatePiNilakanthaParallel, "calculatePiNilakanthaParallel")

    println("Parallelization Speedup: ${sequentialTime.toDouble() / parallelTime}")
}

fun calculatePiNilakanthaSequential(iterations: Int): Double {
    var pi = 3.0
    var sign = 1.0

    for (n in 1..iterations) {
        val numerator = 4.0 * sign
        val denominator = (2.0 * n) * (2.0 * n + 1) * (2.0 * n + 2)
        pi += numerator / denominator
        sign *= -1.0
    }

    return pi
}

fun calculatePiNilakanthaParallel(iterations: Int): Double {
    val cores = Runtime.getRuntime().availableProcessors()
    val chunkSize = iterations / cores

    val results = runBlocking {
        (0 until cores).map { core ->
            async(Dispatchers.Default) {
                val start = core * chunkSize + 1
                val end = if (core == cores - 1) iterations else (core + 1) * chunkSize
                var partialPi = 0.0
                var sign = if (start % 2 == 0) -1.0 else 1.0

                for (n in start..end) {
                    val numerator = 4.0 * sign
                    val denominator = (2.0 * n) * (2.0 * n + 1) * (2.0 * n + 2)
                    partialPi += numerator / denominator
                    sign *= -1.0
                }
                partialPi
            }
        }.awaitAll()
    }

    return 3.0 + results.sum()
}

fun measureTimeMultiple(iterations: Int, function: (Int) -> Any, functionName: String): Long {
    var minTime = MAX_VALUE

    for (i in 1..MEASURE_COUNT) {
        val time = measureTimeMillis {
            function(iterations)
        }
        if (time < minTime) minTime = time
    }

    println("$functionName() took minimum $minTime ms")
    return minTime
}

测试输出 #

calculatePiNilakanthaSequential() took minimum 4499 ms
calculatePiNilakanthaParallel() took minimum 1003 ms
Parallelization Speedup: 4.485543369890329

疑问 #

根据阿姆达尔定律，并行加速比理论上不应超过逻辑核心数（4），但实际测试中加速比超过4倍，且多次运行结果一致。已验证单协程未提升性能，推测可能与任务划分、CPU流水线或缓存相关，但无法确定具体原因。

原因分析 #

1. 串行版本的缓存竞争开销 #

串行计算中，pi是热点共享变量，每次循环都要对其进行读写操作。现代CPU缓存架构下，频繁的写操作会触发缓存一致性协议（如MESI）的同步开销，甚至出现缓存颠簸，大幅拖慢执行速度。

并行版本中，每个协程独立计算partialPi，仅在最后做一次汇总。这种无共享的任务划分避免了缓存竞争，每个核心的私有缓存可以高效存储各自的计算数据，缓存命中率显著提升，整体效率得到放大。

2. 超线程与指令级并行的充分利用 #

你的处理器支持超线程（2物理核心扩展为4逻辑核心），超线程核心可在物理核心流水线空闲时（如等待浮点运算结果）调度另一线程的指令。并行版本的纯计算密集型任务无数据依赖，每个协程的浮点运算能充分利用物理核心的流水线资源，超线程的利用率远高于单线程的串行版本。

串行代码的单线程无法充分利用超线程带来的指令级并行能力，部分流水线资源处于空闲状态，单位时间内的指令吞吐量远低于并行版本。

3. JIT编译器优化的差异 #

JVM的JIT编译器对串行和并行代码的优化程度存在差异：

• 串行代码中，pi的频繁更新限制了循环展开、SIMD向量化等激进优化，因为编译器需要保证变量的可见性和运算顺序。
• 并行代码中，每个协程的局部计算逻辑独立，JIT可以更自由地进行循环展开、向量化等优化，进一步提升单核心的计算效率。

4. 阿姆达尔定律的适用边界 #

阿姆达尔定律假设串行部分占比固定，但本次测试中：

• 并行版本的串行开销仅为协程创建、任务划分和结果汇总，占比极低（相对于10亿次循环）。
• 串行版本的实际有效计算占比因缓存竞争等因素被“稀释”，理论上的串行瓶颈被放大，而并行版本规避了这一瓶颈，最终加速比突破逻辑核心数限制。

内容的提问来源于stack exchange，提问作者k1ng0fTerab1th1a