Failure to accelerate computing with a quadtree

[optimizer3]

Reproducing the behavior

Thank you very much for inventing such an amazing programming language. However, when I programmed a quadtree using Bend, I found that this code did not work properly.

Running command:

bend run-cu quadtree.bend -s

With code:

type Quadtree(T):
  TreeNode { ~nw: Quadtree(T), ~ne: Quadtree(T), ~sw: Quadtree(T), ~se: Quadtree(T) }
  TreeLeaf { value: T }

def sum(tree):
match tree:
  case Quadtree/TreeLeaf:
    return tree.value
  case Quadtree/TreeNode:
    return sum(tree.nw) + sum(tree.ne) + sum(tree.sw) + sum(tree.se)

def gen(n):
  if n == 0:
    return Quadtree/TreeLeaf{value: 1}
  else:
    return Quadtree/TreeNode{nw: gen(n - 1), ne: gen(n - 1), sw: gen(n - 1), se: gen(n - 1)}

def main():
  quadtree = gen(3)
  #  return quadtree
  return sum(quadtree)
  

Error:

The program fails to stop and no results are output.

Expected behavior:

Like:

Result: 64
- ITRS: 2819
- TIME: 0.00s
- MIPS: 1.04

System Settings

• HVM: [HVM 2.0.22]
• Bend: [Bend 0.2.37]
• OS: [Linux (Ubuntu 24.04.1 LTS)]
• CPU: [Intel(R) Xeon(R) Platinum 8352V CPU @ 2.10GHz]
• GPU: [RTX 4090]
• Cuda Version [release 12.1, V12.1.105]
• GCC: [11.4.0]

Additional context

I have tried:

1. Reading the project documentation, I did not find detailed instructions on this problem.
2. Searching Issues, but did not find anything similar.

I found the program runs correctly with “bend run quadtree.bend -s”:

Result: 64
- ITRS: 2819
- TIME: 0.00s
- MIPS: 1.05

And for another program, using a binary tree to accelerate computing, runs correctly with “bend run-cu binaryree.bend -s":

type MyTree(T):
  Node { ~left: MyTree(T), ~right: MyTree(T) }
  Leaf { value: T }

def gen(n):
  if n == 0:
    return MyTree/Leaf{value : 1}
  else:
    return MyTree/Node{left: gen(n - 1), right: gen(n - 1) }

def sum(tree):
  match tree:
    case MyTree/Leaf:
      return tree.value
    case MyTree/Node:
      return sum(tree.left) + sum(tree.right)

def main():
  binarytree = gen(20)
  return sum(binarytree)

Bend is incredibly powerful, and I’m impressed by its remarkable speed:

Result: 1048576
- ITRS: 71335893
- LEAK: 12550783
- TIME: 0.03s
- MIPS: 2526.24

I really enjoy using this language and can’t wait to improve my algorithms, such as matrix multiplication. However, the implementation of quadtrees has been a persistent challenge for me.

My questions:

1. I don't know why this code fails to output results, even when the data size is small (n = 3). Is this because Quadtree has four member variables while MyTree has only two? These two pieces of code are really similar.
2. Does Bend support multi-parallelism? Like computing "return Quadtree/TreeNode{nw: gen(n - 1), ne: gen(n - 1), sw: gen(n - 1), se: gen(n - 1)}"?
3. If so, how should it be implemented?

Thank you very much for your time and help! I would greatly appreciate any help or guidance. Looking forward to hearing from you.

Best regards,
Siyu Wang

[nicolas-abril]

Hi, sorry for taking so long to respond, your Issue somehow went unnoticed.

Testing a bit, there seems to be a bug with the HVM CUDA runtime, your QuadTree program is supposed to work.
We have to investigate this a bit further, the bug is not immediately apparent to me.

[optimizer3]

Thank you so much for taking the time to respond to my issue. I deeply appreciate your insights and the effort you’ve put into helping me resolve this challenge.

If it would be helpful, I am more than happy to provide additional code snippets or examples, particularly regarding the HVM CUDA runtime, to further clarify the issue or assist in debugging. Please let me know if there’s anything specific you’d like me to share or test.

Once again, thank you for your dedication and support. Your work on Bend continues to inspire, and I’m excited to further explore its potential!