The Computer Language
24.06 Benchmarks Game

binary-trees Dart jit #5 program

source code

/* The Computer Language Benchmarks game
   https://salsa.debian.org/benchmarksgame-team/benchmarksgame/

   Contributed by Aldo Román 
*/

import "dart:async" show Completer;
import "dart:io" show exit;
import "dart:isolate" show Isolate, SendPort, RawReceivePort;

const int numberOfProcessors = 4;
const int minDepth = 4;

class TreeNode {
  final TreeNode? left, right;
  const TreeNode(this.left, this.right);
}

TreeNode buildTree(int depth) => 0 < depth
    ? TreeNode(buildTree(depth - 1), buildTree(depth - 1))
    : TreeNode(null, null);

int itemCheck(TreeNode node) {
  if (null == node.left) {
    return 1;
  } else {
    return 1 + itemCheck(node.left!) + itemCheck(node.right!);
  }
}

void _isolate(SendPort parentPort) {
  final port = RawReceivePort((List params) {
    final int start = params[0];
    final int end = params[1];
    final int maxDepth = params[2];
    final SendPort resultPort = params[3];

    final String result =
        Iterable.generate(end - start, (i) => i + start).map((i) {
      final int depth = i * 2 + minDepth;
      final int iterations = 1 << (maxDepth - depth + minDepth);
      final int check = Iterable.generate(iterations)
          .fold(0, (acc, _) => acc + itemCheck(buildTree(depth)));
      return "${iterations}\t trees of depth $depth\t check: $check";
    }).join("\n");

    resultPort.send(result);
  });

  parentPort.send(port.sendPort);
}

Future<String> spawnWorker(int start, int end, int maxDepth) {
  final Completer<String> c = Completer.sync();
  final resultPort = RawReceivePort(c.complete);
  final initPort = RawReceivePort((SendPort sendPort) {
    sendPort.send([start, end, maxDepth, resultPort.sendPort]);
  });
  Isolate.spawn(_isolate, initPort.sendPort);
  return c.future;
}

void main(List<String> args) {
  final int n = args.length > 0 ? int.parse(args[0], radix: 10) : 0;

  final int maxDepth = (minDepth + 2 > n) ? minDepth + 2 : n;

  final int stretchDepth = maxDepth + 1;
  final int check = itemCheck(buildTree(stretchDepth));
  print("stretch tree of depth $stretchDepth\t check: $check");

  final TreeNode longLivedTree = buildTree(maxDepth);

  final int totalTasks = (maxDepth - minDepth) ~/ 2 + 1;
  final int numberOfWorkers =
      totalTasks > numberOfProcessors ? numberOfProcessors : totalTasks;
  final int tasksPerWorker = totalTasks ~/ numberOfWorkers;
  final int offset = totalTasks % numberOfWorkers;

  final tasks = Iterable.generate(numberOfWorkers, (i) {
    final int start = i * tasksPerWorker + ((i == 0) ? 0 : offset);
    final int end = start + tasksPerWorker + ((i == 0) ? offset : 0);
    return spawnWorker(start, end, maxDepth);
  });

  Future.wait(tasks)
      .then((resultsPerWorker) => resultsPerWorker.join("\n"))
      .then(print)
      .then((_) {
    print(
        "long lived tree of depth $maxDepth\t check: ${itemCheck(longLivedTree)}");
    exit(0);
  });
}
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
Dart SDK version: 3.4.1 (stable)
Tue May 21 15:46:25 2024



 Tue, 28 May 2024 21:50:47 GMT

MAKE:
/opt/src/dart-sdk/bin/dart analyze 
Analyzing tmp...
No issues found!

2.87s to complete and log all make actions

COMMAND LINE:
 /opt/src/dart-sdk/bin/dart run  binarytrees.dartjit-5.dartjit 21

PROGRAM OUTPUT:
stretch tree of depth 22	 check: 8388607
2097152	 trees of depth 4	 check: 65011712
524288	 trees of depth 6	 check: 66584576
131072	 trees of depth 8	 check: 66977792
32768	 trees of depth 10	 check: 67076096
8192	 trees of depth 12	 check: 67100672
2048	 trees of depth 14	 check: 67106816
512	 trees of depth 16	 check: 67108352
128	 trees of depth 18	 check: 67108736
32	 trees of depth 20	 check: 67108832
long lived tree of depth 21	 check: 4194303