ziggystar · March 30, 2015 20:06 · Mar 30, 2015
diff --git a/tetris-benchmark.scala b/tetris-benchmark.scala
@@ -0,0 +1,113 @@
+import java.lang.management.ManagementFactory
+
+/**
+ * Benchmark to measure performance of computing profile of Tetris stack.
+ * http://stackoverflow.com/questions/29309942/how-to-compute-the-height-profile-of-a-tetris-stack-most-efficiently
+ *
+ * This code may be used under MIT license.
+ */
+
+val width = 10
+val height = 22
+
+val data: Vector[(Vector[Int], Vector[Int])] = Vector(
+  (Vector(1021, 1015, 439, 246, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),Vector(3, 4, 4, 1, 5, 4, 4, 4, 3, 2)),
+  (Vector(511, 1006, 511, 191, 510, 370, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),Vector(4, 6, 5, 5, 6, 6, 6, 5, 6, 2)),
+  (Vector(991, 895, 1022, 1015, 511, 30, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),Vector(5, 6, 7, 6, 6, 5, 5, 5, 5, 4)),
+  (Vector(503, 503, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),Vector(2, 3, 3, 0, 2, 2, 2, 2, 2, 0)),
+  (Vector(1019, 1021, 511, 879, 494, 74, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),Vector(4, 6, 5, 7, 3, 5, 6, 5, 5, 4)),
+  (Vector(639, 511, 511, 1007, 1021, 1021, 1021, 1015, 511, 471, 451, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),Vector(11, 11, 10, 9, 10, 9, 11, 11, 11, 8)),
+  (Vector(511, 1021, 1022, 1007, 959, 391, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),Vector(8, 6, 6, 5, 5, 5, 4, 6, 6, 5)),
+  (Vector(767, 959, 511, 1015, 511, 1007, 735, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),Vector(8, 8, 7, 7, 7, 6, 7, 7, 6, 7)),
+  (Vector(1007, 511, 1022, 1019, 1019, 511, 1019, 767, 895, 511, 1021, 767, 991, 956, 24, 0, 0, 0, 0, 0, 0, 0),Vector(13, 13, 14, 15, 15, 14, 13, 14, 14, 14)),
+  (Vector(991, 1022, 1022, 511, 511, 511, 959, 567, 35, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),Vector(9, 9, 8, 7, 8, 9, 6, 7, 7, 8)))
+
+//the stacks as integer arrays
+val stacks: Array[Array[Int]] = data.map(_._1.toArray).toArray
+
+
+
+//this function needs to be implemented, the second shall store the result;
+//we use a pre-allocated array to maximize implementation-dependent variance
+type ProfileFun = (Array[Int],Array[Int]) => Unit
+
+//my original solution
+def original(stack: Array[Int], result: Array[Int]): Unit = {
+  var col = 0
+  while(col < width){
+    var row = 0
+    var max = 0
+    while(row < height){
+      if(((stack(row) >> col) & 1) == 1)
+        max = row + 1
+      row += 1
+    }
+    result(col) = max
+    col += 1
+  }
+}
+benchmark("original",original)
+
+//maxihatops solution
+val bit2ndx: Array[Int] = Array(-1, 0, 1, 8, 2, 4, 9, 7, 3, 6, 5)
+
+def maxihatop(input: Array[Int], result: Array[Int]): Unit = {
+  // Convert (1 << n) to n for n == 0-10
+  var row = height - 1
+  // create bitset for columns for check
+  var testbits: Int = (1 << width) - 1
+  // Iterate rows from up to bottom, and while exist columns for check
+  while(row >= 0 && testbits != 0) {
+    var rowtestbits = testbits & input(row)
+    while(rowtestbits != 0) {
+      // extract lowest bit_1 from bitset rowtestbits
+      val curbit = rowtestbits & -rowtestbits
+      result(bit2ndx(curbit % 11)) = row + 1
+      rowtestbits = rowtestbits ^ curbit
+      testbits    = testbits ^ curbit
+    }
+    row -= 1
+  }
+}
+benchmark("maxihatop", maxihatop)
+
+
+
+def benchmark(name: String, impl: ProfileFun): Unit = {
+  checkImpl(name,impl)
+  val result = new Array[Int](width)
+  def run(): Unit = {
+    var n = 1000000
+    while(n > 0){
+      var si = 0 //pointer to stack
+      while(si < stacks.length){
+        impl(stacks(si),result)
+        si += 1
+      }
+      n -= 1
+    }
+  }
+  println(name)
+  (1 to 5).foreach{_ =>
+    val (_,time) = cpuTime(() => run())
+    println(f"\t$time%.3fs")
+  }
+}
+
+def cpuTime[A](f: () => A): (A,Double) = {
+  val threadBean = ManagementFactory.getThreadMXBean
+  val start = threadBean.getCurrentThreadCpuTime
+  var r = f()
+  (r,(threadBean.getCurrentThreadCpuTime - start).toDouble * 1e-9)
+}
+
+def checkImpl(name: String, impl: ProfileFun): Unit = {
+  val ok = (stacks zip data.map(_._2)).foreach{ case (s,p) =>
+    val result = new Array[Int](width)
+    impl(s,result)
+    if(result.toIndexedSeq != p) {
+      println(s"$name: wrong result")
+      println(s"got ${result.deep} but expected $p")
+    }
+  }
+}
No results found