performance - go 的加速问题

Question

我在 go 中编写了一个非常简单的程序来测试并行程序的性能。我写了一个非常简单的程序，通过除法试验分解一个大的半素数。由于不涉及通信，我预计会有近乎完美的加速。但是，该程序的扩展性似乎很差。

我用 1、2、4 和 8 个进程对程序进行计时，在 8(真正的，不是 HT)核心计算机上运行，​​使用系统 time 命令。我分解的数字是“28808539627864609”。这是我的结果:

cores  time (sec) speedup  1   60.0153      1  2   47.358       1.27  4   34.459       1.75  8   28.686       2.10

How to explain such bad speedups? Is it a bug in my program, or is it a problem with go runtime? How could I get better performances? I'm not talking about the algorithm by itself (I know there are better algorithms to factorize semiprime numbers), but about the way I parallelized it.

Here is the source code of my program:

package main

import (
    "big"
    "flag"
    "fmt"
    "runtime"
)

func factorize(n *big.Int, start int, step int, c chan *big.Int) {

    var m big.Int
    i := big.NewInt(int64(start))
    s := big.NewInt(int64(step))
    z := big.NewInt(0)

    for {
        m.Mod(n, i)
        if m.Cmp(z) == 0{
            c <- i
        }
        i.Add(i, s)
    }
}

func main() {
    var np *int = flag.Int("n", 1, "Number of processes")
    flag.Parse()

    runtime.GOMAXPROCS(*np)

    var n big.Int
    n.SetString(flag.Arg(0), 10) // Uses number given on command line
    c := make(chan *big.Int)
    for i:=0; i<*np; i++ {
        go factorize(&n, 2+i, *np, c)
    }
    fmt.Println(<-c)
}

---

编辑

问题似乎确实与 Mod 函数有关。用 Rem 替换它可以提供更好但仍然不完善的性能和加速。将其替换为 QuoRem 可提供 3 倍的性能提升和完美的加速。结论:似乎内存分配扼杀了 Go 中的并行性能。为什么？您对此有任何引用吗？

Answer 1

Big.Int 方法通常必须分配内存，通常用于保存计算结果。问题是只有一个堆，所有的内存操作都是序列化的。在这个程序中，数字相当小，与重复分配所有微小内存位的不可并行化操作相比，Mod 和 Add 等操作所需的(可并行化)计算时间也很小。

就加速而言，如果没有必要，不要使用 big.Ints 是显而易见的答案。您的示例编号恰好适合 64 位。不过，如果您计划处理非常大的数字，问题就会自行消失。您将花费更多的时间进行计算，而花在堆上的时间将相对少得多。

顺便说一下，你的程序中有一个错误，尽管它与性能无关。当你找到一个因子并在 channel 上返回结果时，你发送一个指向局部变量 i 的指针。这很好，只是你当时没有跳出循环。 goroutine 中的循环继续递增 i，当主 goroutine 开始将指针从 channel 中取出并跟随它时，该值几乎肯定是错误的。