c++ - 为什么我的 cilk_spawn 循环比我的 cilk_for 循环做得更好？

Question

我有

cilk_for (int i = 0; i < 100; i++)
   x = fib(35);

以上耗时6.151秒

和

for (int i = 0; i < 100; i++)
   x = cilk_spawn fib(35);

耗时 5.703 秒

fib(x) 是可怕的递归斐波那契数函数。如果我调低 fib 函数 cilk_for 比 cilk_spawn 做得更好，但在我看来，无论执行 fib(x) cilk_for 应该比 cilk_spawn 做得更好。

我不明白什么？

Answer 1

根据评论，问题是缺少 cilk_sync。我将对此进行扩展，以准确指出如何以惊人的准确度预测时间比率。

在具有 P 个硬件线程(在 i7 上通常为 8 个)的系统上，for/cilk_spawn 代码将执行如下:

1. 初始线程将执行 i=0 的迭代，并留下被其他线程窃取的延续。
2. 每个小偷都会偷一个迭代并为下一个迭代留下一个延续。
3. 当每个窃贼完成一次迭代时，它会返回到第 2 步，除非没有更多的迭代可以窃取。

因此，线程将交替执行循环，循环在 P-1 个线程仍在进行迭代的点处退出。因此，预计循环会在仅评估 (100-P-1) 次迭代后完成。

因此，对于 8 个硬件线程，缺少 cilk_sync 的 for/cilk_spawn 应该花费 cilk_for 的大约 93/100 的时间，非常接近观察到的大约 5.703/6.151 = 0.927 的比率。

相比之下，在诸如 TBB 或 PPL task_group 之类的“child steal”系统中，循环将竞相完成，生成 100 个任务，然后继续运行直到调用 task_group::wait。在那种情况下，忘记同步会导致更显着的时间比。