Benchmark script to measure performance of different ways to compute the profile of a tetris stack.

tetris-benchmark.scala

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")
    }
  }
}

My results:

original:    2.070s,        2.044s,        1.973s,        1.973s,        1.973s
maxihatop:   0.492s,        0.483s,        0.490s,        0.490s,        0.489s