I think the answer is yes. It is a correct but inefficient implementation.

Yup, I agree that the answer to the question here is "Yes, it is a correct implementation if it chooses to run all function calls identified by cilk_spawn serially in the main thread". Kayvon really put an emphasis in lecture on the abstraction aspect of the cilk_spawn call, which means that we have absolutely no idea about how the calls are parallelized, what order they're executed in, or even if they're parallel at all.

I agree with everyone else's answers. One thing that I thought about is how the abstraction can have an impact on the severity of the performance impact from dependencies between threads. For example, if one parallel abstraction runs parallel code with a "child first" strategy like cilk, but another abstraction follows a "continuation first strategy", I wonder if those different abstracts can have significantly varying performance if each parallel task has some level of dependency upon one another.

Something I'm curious about is what cilk_spawn does on a call that is supposed to return something. Let's say you had a local variable in the main thread and you called cilk_spawn to return a value into that local variable. I'd guess that ideally you'd want to suspend the main thread, run the child first, and then place the return value in the main thread's local variable without the main thread waiting at all.

I wonder what the implications are if cilk_sync isn't called. It probably causes race conditions in that when the main thread's function exits, you have no guarantee that any of the cilk_spawn calls have finished, although it is possible. (all of this assuming that cilk_spawn actually runs its functions in a separate thread)

Similar to all the comments above, I agree that the defined implementation above would still be correct but would go against the entire point of Cilk being used as a means of performance upgrade. Building upon the clear conceptual decoupling of Abstraction vs Implementation that Kayvon described, the Cilk implementation is correct.

@viklassic That's an interesting point. I think cilk_spawn may only work for independent workloads, and what you described above requires a serial run. Otherwise the communication costs are too high if threads need to sync with each other - it's also against the natural of distributing parallel work.