Just for fun, I went and parallelized creation of each branch of the tree.
There's a race condition between "preferSpawn" and "spawn" so it occasionally
locks up, since you can't stop another thread from spawning new workers between
preferSpawn and spawn. You can't wrap that code in a lock either, since that
lock has to release after the spawn will not block, but before the recursive
call tries to acquire it again.
But it's sort of neat. I wanted to use "parallel:" but you can't use spawn
twice in that, so it can only parallelize loops.
import threadpool
from strutils import repeat
type Tree = ref object
d: int
left, right: Tree
proc toString(root: int, o: Tree): string;
proc `$`(o: Tree): string =
toString(o.d,o)
proc toString(root: int, o: Tree): string =
if o.isNil:
return "nil"
let tab: string = ' '.repeat(2*(root - o.d))
result = "Tree " & $o.d & "\n"
result.add(tab & "- left\n")
result.add(tab & " ")
result.add(toString(root,o.left))
result.add("\n")
result.add(tab & "- right\n")
result.add(tab & " ")
result.add(toString(root,o.right))
proc tree(depth: int): Tree =
if depth == 0:
return Tree(d: 0)
else:
result = Tree(d: depth)
if not preferSpawn():
result.left = tree(depth-1)
result.right = tree(depth-1)
else:
let left = spawn tree(depth-1)
let right = spawn tree(depth-1)
discard awaitAny([left.FlowVarBase,right.FlowVarBase])
result.left = ^left
result.right = ^right
proc main() =
let t = tree(3)
echo(t)
main()
