[concurrency-interest] FJ stack bounds

thurstonn thurston at nomagicsoftware.com
Mon Dec 1 18:03:04 EST 2014


I was wondering if there was any way to compute a maximum bound for the
stack size/height (in frames, not bytes) for a given FJ problem.

So given n = # of FJT created.
Let's keep the math simple and say n = 256

and your RecursiveTasks just split "themselves" into 2 separate
RecursiveTasks which are then forked and joined (idiomatic FJ)

At first glance, it would seem that this would be classic log(n) - but is
it?  In the simple example that would mean a max stack height of 8.

Given that worker threads engage in work-stealing (and combined with the
fact that I can't tell from looking at the code what invariants there are
(if any) in determining which actual FJT will be #exec()'d), is it possible
that (given some unlucky and unlikely "timing"), that a single worker thread
could effect a stack height much > 8? even, perhaps 256? (I realize this is
unlikely, I'm just asking if it's possible)

As best I could tell, there seems to be some logic (#doJoin/#tryUnpush) that
"defaults" to executing the joined task only if it is at the top of the
current thread's task stack (workerqueue), else . . . try to "help" by
executing some other (arbitrarily chosen?) task.
Does that mean that:
left = . . .fork()
right = . . . fork()  //Top of this thread's worker queue

return left.join() + right.join()
is different than
return right.join() + left.join()
in terms of the possible stack heights that can result?

I want to make it clear that I haven't encountered any runtime problems with
stack overflow errors, just wanted to know if there was some theoretical
bound that can be statically computed


View this message in context: http://jsr166-concurrency.10961.n7.nabble.com/FJ-stack-bounds-tp11552.html
Sent from the JSR166 Concurrency mailing list archive at Nabble.com.

More information about the Concurrency-interest mailing list