为什么我的cilk_forn的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个）的系统上，/cilk_spown代码将执行如下：

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

因此，线程将手动执行循环，并且循环在p-1线程仍在进行迭代时退出。因此，可以预期循环在仅评估（100-P-1）次迭代之后结束。

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

相比之下，在TBB或PPL task_group等"子窃取"系统中，循环将竞相完成，生成100个任务，然后继续进行，直到调用task_group:：wait。在这种情况下，忘记同步会导致更显著的时间比例。