Add 2 benchmarks for Ctries.

2 files changed, 112 insertions, 0 deletions

diff --git a/test/benchmarking/ParCtrie-bfs.scala b/test/benchmarking/ParCtrie-bfs.scala
new file mode 100644
index 0000000000..59149fff8c
--- /dev/null
+++ b/test/benchmarking/ParCtrie-bfs.scala
@@ -0,0 +1,73 @@
+
+
+
+
+
+import collection.parallel.mutable.ParCtrie
+
+
+object Bfs extends testing.Benchmark {
+  val length = sys.props("length").toInt
+  val par = sys.props("par").toInt
+  
+  type Node = (Int, Int);
+  type Parent = (Int, Int);
+  
+  def up(n: Node) = (n._1, n._2 - 1);
+  def down(n: Node) = (n._1, n._2 + 1);
+  def left(n: Node) = (n._1 - 1, n._2);
+  def right(n: Node) = (n._1 + 1, n._2);
+  
+  // create a map and a target
+  val target = (length / 2, length / 2);
+  val map = Array.tabulate(length, length)((x, y) => (x % 3) != 0 || (y % 3) != 0 || (x, y) == target)
+  def onMap(n: Node) = n._1 >= 0 && n._1 < length && n._2 >= 0 && n._2 < length
+  
+  // open and closed lists
+  val open = ParCtrie[Node, Parent]()
+  val closed = ParCtrie[Node, Parent]()
+  
+  collection.parallel.ForkJoinTasks.defaultForkJoinPool.setParallelism(par)
+  
+  override def setUp() {
+    open.clear()
+    closed.clear()
+    
+    // a couple of starting positions
+    open((0, 0)) = null
+    open((length - 1, length - 1)) = null
+    open((0, length - 1)) = null
+    open((length - 1, 0)) = null
+  }
+  
+  def run() = {
+    // greedy bfs path search
+    while (open.nonEmpty && !open.contains(target)) {
+      for ((node, parent) <- open) {
+        def expand(next: Node) {
+          if (onMap(next) && map(next._1)(next._2) && !closed.contains(next) && !open.contains(next)) {
+            open(next) = node
+          }
+        }
+        expand(up(node))
+        expand(down(node))
+        expand(left(node))
+        expand(right(node))
+        closed(node) = parent
+        open.remove(node)
+      }
+    }
+  }
+  
+  override def tearDown() {
+    // print path
+    var pathnode = open(target)
+    while (closed.contains(pathnode)) {
+      print(pathnode + "->")
+      pathnode = closed(pathnode)
+    }
+    println()
+  }
+  
+}
+
diff --git a/test/benchmarking/ParCtrie-nums.scala b/test/benchmarking/ParCtrie-nums.scala
new file mode 100644
index 0000000000..76d1966d1f
--- /dev/null
+++ b/test/benchmarking/ParCtrie-nums.scala
@@ -0,0 +1,39 @@
+
+
+
+
+
+import collection.parallel.mutable.ParCtrie
+
+
+case class Entry(num: Double) {
+  var sqrt = num
+}
+
+
+object Nums extends testing.Benchmark {
+  val length = sys.props("length").toInt
+  val par = sys.props("par").toInt
+  var entries: Seq[Entry] = null
+  var results: ParCtrie[Double, Entry] = null
+  
+  collection.parallel.ForkJoinTasks.defaultForkJoinPool.setParallelism(par)
+  
+  override def setUp() {
+    entries = (1 until length) map { num => Entry(num.toDouble) }
+    results = ParCtrie()
+    for (e <- entries) results += ((e.num, e))
+  }
+  
+  def run() = {
+    while (results.nonEmpty) {
+      for ((num, e) <- results) {
+        val nsqrt = 0.5 * (e.sqrt + e.num / e.sqrt)
+        if (math.abs(nsqrt - e.sqrt) < 0.01) {
+          results.remove(num)
+        } else e.sqrt = nsqrt
+      }
+    }
+  }
+}
+