为什么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需要多长时间，fib(x) cilk_for都应该比cilk_spawn做得更好。

我还不明白什么？

Answer 1

根据评论，问题是缺少了一个cilk_sync。我将对此作进一步的阐述，指出如何准确地预测时间的比率。

在具有P硬件线程(通常是i7上的8个线程)的系统上，/cilk_sp结识代码将按以下方式执行：

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

因此，线程将手工执行循环，循环退出到P-1线程仍在进行迭代的点。因此，在只计算(100-P1)迭代后，可以期望循环完成.

因此，对于8个硬件线程，缺少cilk_sync的for /cilk_ should应该占用cilk_for所需时间的93/100，非常接近观察到的5.703/6.151 = 0.927的比率。

相反，在“子窃取”系统(如TBB或PPL task_group )中，循环将竞相完成，生成100个任务，然后继续运行直到调用task_group::wait。在这种情况下，忘记同步会导致更大比例的时间。