为什么这个并发代码比串行代码慢？ （走）

Question

我想尝试使用并发解决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) //generates slice of Linked Lists

    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) //generates slice of Linked Lists

    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

我的并发解决方案是否有问题，或者是否有其他问题，例如开销？

Answer 1

有大量开销：

• 启动一个goroutine
• 通过通道发送值

必须通过并行执行大量工作来证明这种开销是合理的。如果任务能够很好地分割，多个 CPU 可以减少执行任务所需的时间。但完成任务所需时间的减少必须超过通信（通道）和设置（go 例程）开销。

在您的示例中，您没有并行执行大量工作。 Goroutine 所做的一切就是

cur.Next = prev

。如果你有

cur.Next = someHeavyOperation(prev)

，事情就会不同。

该示例的下一个问题是主例程除了等待 goroutine 返回之外什么也不做。实际上，这只会将工作放在另一个例程上（具有上述所有开销），但不会利用主例程的 CPU。这意味着这两个 goroutine 没有并行使用。一次只有一个例程在工作。