It is not clear to me under which conditions on T one can pass T around between threads. If I run the following program

import threadpool


type Tree = object
  d: int
  left, right: ref Tree

template `~`[T](a: T): ref T =
  var x: ref T
  new(x)
  x[] = a
  x

proc tree(depth: int): Tree =
  if depth == 0:
    Tree(d: 0)
  else:
    Tree(d: depth, left: ~tree(depth - 1), right: ~tree(depth - 1))

proc main() =
  let t = spawn tree(3)
  sync()
  let s = ^t
  echo s

main()

I get the error Error: cannot create a flowVar of type: Tree. It must have to do something with the self reference, but I am not sure why this limitation exists

2017-03-15 17:32:35

Is it, the error, more like defining reference object within thread?

I did it, defining ref object, with thread primitive and all I got was executable crash. Only after I defined the ref object in main thread, it could be used for another thread.

I haven't tried threadpool though.

2017-03-15 22:41:09

I'm not sure this is relevant but the manual says :

Due to technical limitations not every type T is possible in a data flow variable: T has to be of the type ref, string, seq or of a type that doesn't contain a type that is garbage collected. This restriction is not hard to work-around in practice.

So, it might be because your tree contains a ref (which is GC'd) and it is not itself a ref

2017-03-16 10:56:08
cy

making a Tree() puts it on the stack, and makes it scoped, which is neat, but probably not what you're looking for. What you're doing is like this in C:

struct Tree {
  struct Tree* left;
  struct Tree* right;
};

struct Tree make_tree(int n) {
  struct Tree ret;
  ret.left = malloc(sizeof(struct Tree));
  struct Tree notleft = make_tree(n+1);
  memcpy(ret.left,&notleft,sizeof(struct Tree));
  ...
  return ret;
}
void foo() {
  ...
  
  struct Tree t = make_tree(3);
}

Not only is that very confusing, there's no point since you're dynamically allocating the memory anyway, then blitting it from off the stack. It'd be faster to have (in the C) make_tree return a malloc'd pointer, and initialize the malloc'd data directly, without making a temporary tree structure on the stack. Problem with that is, you made your tree root an object, not a ref object.

struct Tree* make_tree() {
  ...malloc(...)...
}

void foo() {
  struct Tree t = *(make_tree()); // uh...
}

In general, when working with recursive data structures, I think it's a good idea to make everything a pointer. The child nodes must be pointers, so you should have a pointer to the root of any tree, which is memory managed the same way as the children. Nim has a lot of support for that pretty transparently, by creating a type of "ref object".

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:
    Tree(d: 0)
  else:
    Tree(d: depth, left: tree(depth-1), right: tree(depth-1))

proc main() =
  let t = spawn tree(3)
  let s = ^t
  echo(s)

main()

No weird memory copying twiddle operator needed then, and the only caveat is that your root node is also a pointer, rather than arbitrarily being a structure on the stack.

2017-03-16 18:20:13
cy

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()

2017-03-16 20:56:32