Experimental setup: I start from commit 18701bf.
The experiment is to run a Fibonacci computation (or similarly, any program with a fork-join pattern that runs an exponential number of tasks in total) using Fut.spawn, with a small cutoff leading to the creation of too many tasks. I expect the fifo scheduler to behave terribly in this case, but the surprising part (the bug report) is that ws also behaves badly.
The expected part
If you run
sh bench_fib.sh -psize 4 -n 40 -cutoff 8 -kind fifo -await
then this takes very long and I observe (using top) that the memory usage grows over time, eventually it consumes gibibytes of memory.
This is expected, as a bad property of the global fifo scheduling policy. When you run fibo or some other tree-traversing computation, popping a task pushes a certain number of smaller subtasks, which can be visualized as the children of the popped task in a tree. The task queue contains a frontier of the tree at any point in time. With the fifo scheduling policy, you do a breadth-first traversal (BFS) of the tree, so you can get up to 2^N tasks in your queue at worst (or maybe 1.5^N because it's fibonacci, you get the idea) -- here N=40.
The unexpected part
The problem is that using the work-stealing scheduler, which should solve the issue, does not solve it.
sh bench_fib.sh -psize 4 -n 40 -cutoff 8 -kind pool -await
This has the same behavior of eating all my memory on my machine.
(Note: in contrast, using -dl returns a result with constant, small memory consumption.)
This should not happen because when each worker has a work-stealing deque, it pushes and pops from the same end of the deque, which corresponds to a depth-first traversal of the tree; the number of tasks on the queue should be of the order of N, the depth of a path from the root to a leaf of the tree. Steals from other workers will take from the other end so they steal "large" tasks, and this is good because it guarantees that steals are rare (you get a lot of work to do after each steal).
This unexpected memory usage is a problem because it means that if our sequential cutoffs are not strict enough, we may get a memory blowup, which is significantly more annoying than just things taking more time than they should; and none of the current schedulers seem able to avoid this.
My hazardous guess as to what the issue is
Your work-stealing pool implementation uses a bounded deque, above 256 items it sends extra tasks to a global queue. The global queue has the BFS behavior that makes memory blow up. So I guess that we are observing an overflow of the per-worker queues. This is a bit strange because fibonacci(40) should put around 40 tasks on the queue at the same time, not more. It may be that there is something subtle going on that explains why more than 256 tasks are pushed in normal operation, or that there is a subtle bug in the ws-pool or ws-deque implementations that make them refuse to push tasks locally when it should be working.
My recommendation would be to use a resizing queue as implemented by the Saturn library (you could just copy their implementation?). I suppose, but I have not tried, that this would make the issue go away.
Experimental setup: I start from commit 18701bf.
The experiment is to run a Fibonacci computation (or similarly, any program with a fork-join pattern that runs an exponential number of tasks in total) using
Fut.spawn, with a small cutoff leading to the creation of too many tasks. I expect thefifoscheduler to behave terribly in this case, but the surprising part (the bug report) is thatwsalso behaves badly.The expected part
If you run
then this takes very long and I observe (using
top) that the memory usage grows over time, eventually it consumes gibibytes of memory.This is expected, as a bad property of the global
fifoscheduling policy. When you runfiboor some other tree-traversing computation, popping a task pushes a certain number of smaller subtasks, which can be visualized as the children of the popped task in a tree. The task queue contains a frontier of the tree at any point in time. With thefifoscheduling policy, you do a breadth-first traversal (BFS) of the tree, so you can get up to 2^N tasks in your queue at worst (or maybe 1.5^N because it's fibonacci, you get the idea) -- here N=40.The unexpected part
The problem is that using the work-stealing scheduler, which should solve the issue, does not solve it.
This has the same behavior of eating all my memory on my machine.
(Note: in contrast, using
-dlreturns a result with constant, small memory consumption.)This should not happen because when each worker has a work-stealing deque, it pushes and pops from the same end of the deque, which corresponds to a depth-first traversal of the tree; the number of tasks on the queue should be of the order of N, the depth of a path from the root to a leaf of the tree. Steals from other workers will take from the other end so they steal "large" tasks, and this is good because it guarantees that steals are rare (you get a lot of work to do after each steal).
This unexpected memory usage is a problem because it means that if our sequential cutoffs are not strict enough, we may get a memory blowup, which is significantly more annoying than just things taking more time than they should; and none of the current schedulers seem able to avoid this.
My hazardous guess as to what the issue is
Your work-stealing pool implementation uses a bounded deque, above 256 items it sends extra tasks to a global queue. The global queue has the BFS behavior that makes memory blow up. So I guess that we are observing an overflow of the per-worker queues. This is a bit strange because fibonacci(40) should put around 40 tasks on the queue at the same time, not more. It may be that there is something subtle going on that explains why more than 256 tasks are pushed in normal operation, or that there is a subtle bug in the ws-pool or ws-deque implementations that make them refuse to push tasks locally when it should be working.
My recommendation would be to use a resizing queue as implemented by the Saturn library (you could just copy their implementation?). I suppose, but I have not tried, that this would make the issue go away.