binary-trees Dart #4 program

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

   Contributed by Jos Hirth, transliterated from Jarkko Miettinen's Java program
   Optimized and parallelized by by Dwayne Slater
   modified by Isaac Gouy
   mostly same but do stretch tree and longLivedTree earlier
   + null safety 
*/

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

const int minDepth = 4;

/// Number of workers to startup. A number below the number of processors on the
/// current system works best.
const int workerCount = 4;

/// Whether to output debug information for workers.
const bool workerDebug = false;

class Worker {
  final SendPort workPort;
  bool ready = true;
  Capability? workItem;

  Worker(this.workPort);

  void submitWork(List work) {
    workPort.send(work);
    ready = false;
    workItem = work[2];
  }
}

void worker(SendPort managerPort) {
  // Make worker port
  final worker = RawReceivePort((message) {
    // `message` is a work item
    final List workItem = message;

    // Process the work item
    final int iterations = workItem[1];
    int check = 0;
    for (int i = 1; i <= iterations; i++) {
      check += TreeNode.itemCheck(TreeNode.bottomUpTree(workItem[0]));
    }

    managerPort.send([check, workItem[2]]);
  });

  managerPort.send(worker.sendPort);
}

/// Manages distributing work to available workers
class Manager {
  final RawReceivePort managerPort;
  final List<Worker> workers;
  final List<List> queuedWork = [];
  final Map<Capability, Completer<int>> workCompleters = {};

  Manager(this.managerPort, this.workers) {
    managerPort.handler = (message) {
      if (message is List) {
        final cap = message[1];
        final value = workCompleters.remove(cap);
        if (value != null) {
          value.complete(message[0]);
        }
        for (int i = 0; i < workers.length; i++) {
          final worker = workers[i];
          if (worker.workItem == cap) {
            if (queuedWork.isNotEmpty) {
              if (workerDebug) print("Submitting more work to $i");
              worker.submitWork(queuedWork.removeLast());
            } else {
              if (workerDebug) print("Worker $i idle");
              worker.ready = true;
            }
            break;
          }
        }
      }
    };
  }

  Future<int> enqueue(int depth, int iterations) {
    final cap = Capability();
    final work = [depth, iterations, cap];
    final completer = Completer<int>.sync();
    workCompleters[cap] = completer;

    // Try submit work item to a ready worker
    for (int i = 0; i < workers.length; i++) {
      final worker = workers[i];
      if (worker.ready) {
        if (workerDebug) print("Dispatched work to worker $i");
        worker.submitWork(work);
        return completer.future;
      }
    }

    // Otherwise, throw into work queue for work stealing
    if (workerDebug) print("Work added to queue");
    queuedWork.add(work);
    return completer.future;
  }

  static Future<Manager> init(int workerCount) async {
    // Spawn and wait for all workers to come online
    final workers = <Worker>[];
    final completer = Completer<void>();
    final managerPort = RawReceivePort((workerPort) {
      workers.add(Worker(workerPort));
      if (workers.length == workerCount) {
        completer.complete();
      }
    });
    for (int i = 0; i < workerCount; i++) {
      Isolate.spawn(worker, managerPort.sendPort);
    }
    await completer.future;
    return Manager(managerPort, workers);
  }
}

Future<void> main(List<String> args) async {
  int n = args.length > 0 ? int.parse(args[0]) : 0;

  // Start up the workers, then dispatch work to them
  final futureManager = Manager.init(workerCount);
  final manager = await futureManager;

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

  int check = TreeNode.itemCheck(TreeNode.bottomUpTree(stretchDepth));
  print("stretch tree of depth $stretchDepth\t check: $check");

  TreeNode longLivedTree = TreeNode.bottomUpTree(maxDepth);

  List<Future<int>> workFuture = [];
  for (int depth = minDepth; depth <= maxDepth; depth += 2) {
    int iterations = 1 << (maxDepth - depth + minDepth);
    workFuture.add(manager.enqueue(depth, iterations));
  }

  for (int depth = minDepth; depth <= maxDepth; depth += 2) {
    int iterations = 1 << (maxDepth - depth + minDepth);
    final check = await workFuture.removeAt(0);
    print("${iterations}\t trees of depth $depth\t check: $check");
  }

  print(
      "long lived tree of depth $maxDepth\t check: ${TreeNode.itemCheck(longLivedTree)}");

  // It takes time to clean up the workers, so just exit instead
  exit(0);
}

class TreeNode {
  final TreeNode? left, right;

  const TreeNode([this.left, this.right]);

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

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

NOTES:
64-bit Ubuntu quad core
Dart SDK version: 3.5.4 (stable)
Wed Oct 16 16:18:51 2024



 Wed, 23 Oct 2024 02:28:44 GMT

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

/opt/src/dart-sdk/bin/dart compile exe binarytrees.dartexe-4.dartexe -o binarytrees.dartexe-4.dartexe_run
Generated: /home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/binarytrees.dartexe-4.dartexe_run

4.73s to complete and log all make actions

COMMAND LINE:
 ./binarytrees.dartexe-4.dartexe_run 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