c++ - 为什么我的 cilk_spawn for 循环比我的 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 之类的“儿童窃取”系统中，循环将竞相完成，生成 100 个任务，然后继续执行直到调用 task_group::wait。在这种情况下，忘记同步会导致更显着的时间比率。