The Computer Language
24.06 Benchmarks Game

binary-trees Dart jit #7 program

source code

/* The Computer Language Benchmarks Game
   https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
  
   contributed by Isaac Gouy
   TreeNode borrowed from Andrey Filatkin's JavaScript program
*/

import 'dart:io';
import 'dart:isolate';

final nIsolates = Platform.numberOfProcessors;

void main(List<String> args) {
  final mainIsolate = ReceivePort();
  final n = (args.length > 0) ? int.parse(args[0]) : 6;

  final stretchDepth = n + 1;
  final check = itemCheck(bottomUpTree(stretchDepth));
  print('stretch tree of depth $stretchDepth\t check: $check');
  final longLivedTree = bottomUpTree(n);

  var i = nIsolates;
  while (i-- > 0) {
    Isolate.spawn(other, mainIsolate.sendPort);
  }
  final requests = <RequestReply>[];
  final replies = <RequestReply>[];
  for (var depth = 4; depth <= n; depth += 2) {
    final iterations = 1 << n - depth + 4;
    requests.add(RequestReply(iterations, depth));
  }
  var awaited = requests.length;

  mainIsolate.listen((dynamic reply) {
    if (reply is SendPort) {
      if (requests.isNotEmpty) {
        reply.send(requests.removeLast());
      }
    } else if (reply is RequestReply) {
      replies.add(reply);
      if (--awaited == 0) {
        replies.sort((a, b) => a.depth.compareTo(b.depth));
        for (var reply in replies) {
          print('${reply.iterations}\t ' +
              'trees of depth ${reply.depth}\t ' +
              'check: ${reply.check}');
        }
        print('long lived tree of depth $n\t ' +
            'check: ${itemCheck(longLivedTree)}');

        mainIsolate.close();
      }
    }
  });
}

void other(SendPort p) {
  final otherIsolate = ReceivePort();
  p.send(otherIsolate.sendPort);

  otherIsolate.listen((dynamic request) {
    if (request is RequestReply) {
      for (int i = 0; i < request.iterations; i++) {
        request.check += itemCheck(bottomUpTree(request.depth));
      }
    }
    p.send(request);
    p.send(otherIsolate.sendPort);
  });
}

class RequestReply {
  var iterations = 0, depth = 0, check = 0;
  RequestReply(this.iterations, this.depth);
}

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

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

TreeNode bottomUpTree(int depth) {
  return depth > 0
      ? TreeNode(bottomUpTree(depth - 1), bottomUpTree(depth - 1))
      : TreeNode(null, null);
}

    

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:47:56 GMT

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

2.99s to complete and log all make actions

COMMAND LINE:
 /opt/src/dart-sdk/bin/dart run  binarytrees.dartjit-7.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