I don't know how Cilk works, but I recall needing to fix a quicksort implementation on an embedded platform that could overflow the stack with recursion. The fix was to use a recursive call for the smaller "half" of the data and process the larger "half" inside the function (i.e., tail recursion). Sorted (or reverse sorted) lists would always trigger overflow since the depth of the call graph was equal to the number of elements in the list.
Can you use the debugger to find out what causes the crash? Can you dump data to a log file on each entry into swap()
, and then see what the function calls before crash looked like? Is it possible to dump the size of the stack on each call? Does each Cilk task have its own stack that is possibly smaller than the stack used in the non-Cilk version?
You could track stack usage by adding a parameter to swap()
with a stack address. The first call and any new Cilk thread uses NULL. Each recursive call uses that parameter if it wasn't NULL, or the address of one of its local variables to establish where its stack is. Dump the difference in addresses, or track it in a global and only report it when it exceeds the previous maximum.