为什么Go语言中这段并发链表反转代码比串行代码慢？

问题背景 #

我尝试用并发方案解决LeetCode第206题（反转链表），分别写了并发和串行的实现，然后做了基准测试，结果并发版本性能远差于串行版本，想知道是代码问题还是并发开销导致的。

并发实现代码 #

func reverseList(head *ListNode) *ListNode {
    var prev, temp *ListNode
    cur, ch := head, make(chan bool)

    for cur != nil {
        temp = cur.Next
        go func(cur *ListNode, prev *ListNode) {
            cur.Next = prev
            ch <- true
        }(cur, prev)
        <-ch
        cur, prev = temp, cur
    }

    return prev
}

串行实现代码 #

func reverseList(head *ListNode) *ListNode {
    var cur, prev *ListNode = head, nil
    for cur != nil {
        prev, cur, cur.Next = cur, cur.Next, prev
    }

    return prev
}

基准测试代码 #

func BenchmarkReverseLinkedListConcurrent(b *testing.B) {
    slice := generateLinkedListSlice(1000000, b.N) //生成链表切片

    b.ResetTimer()
    var cur, prev, temp *ListNode
    var ch chan bool
    for i := 0; i < b.N; i++ {
        fmt.Println("test")
        cur, ch = slice[i], make(chan bool, 5000)

        for cur != nil {
            temp = cur.Next

            go func(cur *ListNode, prev *ListNode) {
                cur.Next = prev
             ch <- true
            }(cur, prev)

            <-ch

            cur, prev = temp, cur
        }
    }
}

func BenchmarkReverseLinkedListSerial(b *testing.B) {
    slice := generateLinkedListSlice(1000000, b.N) //生成链表切片

    b.ResetTimer()
    var cur, prev *ListNode
    for i := 0; i < b.N; i++ {
        fmt.Println("test")
        cur = slice[i]
        for cur != nil {
            prev, cur, cur.Next = cur, cur.Next, prev
        }
    }
}

基准测试结果 #

goos: windows
goarch: amd64
pkg: benchmark-tests
cpu: AMD Ryzen 5 4500U with Radeon Graphics
BenchmarkReverseLinkedListConcurrent-6               602           1812494 ns/op
BenchmarkReverseLinkedListConcurrent-6               673           1767912 ns/op
BenchmarkReverseLinkedListConcurrent-6               680           1557250 ns/op
BenchmarkReverseLinkedListConcurrent-6               771           1896961 ns/op
BenchmarkReverseLinkedListConcurrent-6               634           1874298 ns/op
BenchmarkReverseLinkedListSerial-6                332670             33707 ns/op
BenchmarkReverseLinkedListSerial-6                308980             34237 ns/op
BenchmarkReverseLinkedListSerial-6                278793              3735 ns/op
BenchmarkReverseLinkedListSerial-6                326935              3989 ns/op
BenchmarkReverseLinkedListSerial-6                279200              4182 ns/op

提问 #

请问是我的并发代码存在问题，还是诸如开销之类的其他原因导致性能差异？

原因分析 #

你的并发实现根本没有真正并发执行，反而因为goroutine创建、调度以及channel通信的额外开销，导致性能暴跌。

1. 伪并发的本质 #

在你的并发代码里，每次创建goroutine后立刻执行<-ch，这意味着主线程必须等待当前goroutine完成cur.Next = prev这个操作后，才能进入下一次循环。整个流程是严格串行的：创建goroutine → 等待它执行完毕 → 再处理下一个节点。没有任何并行执行的机会，反而多了goroutine调度和channel同步的开销。

2. 反转链表的操作不适合单任务并行 #

反转链表本身是强依赖顺序的操作：每个节点的Next必须指向前一个节点，而前一个节点的状态必须是已经处理完成的。这种依赖关系决定了单个链表的反转无法拆分成并行任务，因为每个步骤都依赖上一步的结果。

3. 额外开销的影响 #

• goroutine创建与调度：每个节点都创建一个goroutine，这会带来大量的用户态线程创建和上下文切换开销，而这些开销远大于cur.Next = prev这个简单赋值操作的耗时。
• channel同步：channel的发送和接收操作涉及到内核态的同步机制，每次同步都会带来额外的延迟，叠加起来导致整体性能急剧下降。

4. 基准测试中的额外问题 #

你的基准测试代码里还调用了fmt.Println("test")，这个IO操作的开销非常大，会严重干扰基准测试的结果。而且并发版本中每次循环都创建一个带有缓冲区的channel，这也是额外的内存分配开销。

优化建议 #

如果想通过并发提升反转链表的性能，只有当你需要同时反转多个独立的链表时才有意义：比如把多个链表的反转任务分配给不同的goroutine并行执行，而不是在单个链表的节点处理上做并发。

举个例子，修改并发基准测试，让多个goroutine同时反转不同的链表：

func BenchmarkReverseLinkedListConcurrentBatch(b *testing.B) {
    slice := generateLinkedListSlice(1000, b.N) //每个链表短一点，数量多一点
    b.ResetTimer()

    // 使用WaitGroup等待所有goroutine完成
    var wg sync.WaitGroup
    for i := 0; i < b.N; i++ {
        wg.Add(1)
        go func(idx int) {
            defer wg.Done()
            cur := slice[idx]
            var prev *ListNode
            for cur != nil {
                prev, cur, cur.Next = cur, cur.Next, prev
            }
        }(i)
    }
    wg.Wait()
}

这种场景下，并发才能利用多核CPU的优势，提升整体处理效率。

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