The Computer Language
Benchmarks Game

binary-trees Kotlin program

source code

/**
 * The Computer Language Benchmarks Game
   https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
 *
 * based on Tristan Dupont version which was
 * based on Jarkko Miettinen's Java program
 * contributed by Hank Grabowski
 */

import java.util.concurrent.ExecutorService
import java.util.concurrent.Executors
import java.util.concurrent.TimeUnit

object binarytrees {

    private val MIN_DEPTH = 4
    private val EXECUTOR_SERVICE = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors())

    @Throws(Exception::class)
    @JvmStatic
    fun main(args: Array<String>) {
        var n = 0
        if (args.isNotEmpty()) {
            n = Integer.parseInt(args[0])
        }

        val maxDepth = if (n < MIN_DEPTH + 2) MIN_DEPTH + 2 else n
        val stretchDepth = maxDepth + 1

        println("stretch tree of depth " + stretchDepth + "\t check: "
                + bottomUpTree(stretchDepth).itemCheck())

        val longLivedTree = bottomUpTree(maxDepth)

        val results = arrayOfNulls<String>((maxDepth - MIN_DEPTH) / 2 + 1)

        var d = MIN_DEPTH
        while (d <= maxDepth) {
            val depth = d
            EXECUTOR_SERVICE.execute {
                var check = 0

                val iterations = 1 shl maxDepth - depth + MIN_DEPTH
                for (i in 1..iterations) {
                    val treeNode1 = bottomUpTree(depth)
                    check += treeNode1.itemCheck()
                }
                results[(depth - MIN_DEPTH) / 2] = iterations.toString() + "\t trees of depth " + depth + "\t check: " + check
            }
            d += 2
        }

        EXECUTOR_SERVICE.shutdown()
        EXECUTOR_SERVICE.awaitTermination(120L, TimeUnit.SECONDS)

        for (str in results) {
            println(str)
        }

        println("long lived tree of depth " + maxDepth +
                "\t check: " + longLivedTree.itemCheck())
    }

    private fun bottomUpTree(depth: Int): TreeNode {
        return if (0 < depth) {
            TreeNode(bottomUpTree(depth - 1), bottomUpTree(depth - 1))
        } else TreeNode()
    }

    private class TreeNode (private val left: TreeNode? = null, private val right: TreeNode? = null) {

        fun itemCheck(): Int {
            // if necessary deallocate here
            return if (null == left) {
                1
            } else 1 + left.itemCheck() + right!!.itemCheck()
        }

    }

}
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
kotlinc-jvm 1.4-M1 (JRE 14+36-1461)
openjdk 14 2020-03-17
OpenJDK Runtime Environment (build 14+36-1461)
OpenJDK 64-Bit Server VM (build 14+36-1461, mixed mode, sharing)



Mon, 23 Mar 2020 23:11:08 GMT

MAKE:
mv binarytrees.kotlin binarytrees.kt
/opt/src/kotlin-compiler-1.4-M1/bin/kotlinc binarytrees.kt -include-runtime -d binarytrees.jar
OpenJDK 64-Bit Server VM warning: Options -Xverify:none and -noverify were deprecated in JDK 13 and will likely be removed in a future release.

6.95s to complete and log all make actions

COMMAND LINE:
/opt/src/openjdk-14/bin/java -Xmx984M -Xms32M -classpath ./binarytrees.jar binarytrees 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