Deep recursion benchmark

Benchmarking various approaches to deep recursion computations of depth on deep tree of 100K nodes.

class Tree(val left: Tree?, val right: Tree?)
val n = 100_000 // tree depth
val deepTree = generateSequence(Tree(null, null)) { prev ->
    Tree(prev, null)
}.take(n).last()

The basic recursive algorithm:

fun depthRecursive(t: Tree?): Int =
    if (t == null) 0 else maxOf(
        depthRecursive(t.left), // recursive call one
        depthRecursive(t.right) // recursive call two
    ) + 1

All measured algorithms:

recursive and recursiveOpt are baseline implementations. Opt version avoids an extra leaf call for null reference. They are running for 100K nodes tree without StackOverflowError due to -Xss64m option.
manualState is a manual translation of state machine. It should be compared to Opt version, since it does not use stack for leaf calls.
manualDFS is an optimized implementation via graph DFS that does not need to maintain state. It should be compared to Opt version, since it does not use stack for leaf calls.
corouitiesBasic and coroutinesBasicOpt are simple implementations as explained in Deep recursion with coroutines story.
coroutinesFull and coroutinesFullOpt use a productized version with support for a mutual recursion from this gist.

Results:

# CPU: Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz
# VM version: JDK 11.0.6, Java HotSpot(TM) 64-Bit Server VM, 11.0.6+8-LTS
# VM options: -Xss64m

Benchmark                                  Mode  Cnt  Score    Error  Units
DeepRecursionBenchmark.coroutinesBasic     avgt   20  4.370 ±  0.067  ms/op
DeepRecursionBenchmark.coroutinesBasicOpt  avgt   20  2.376 ±  0.022  ms/op
DeepRecursionBenchmark.coroutinesFull      avgt   20  4.403 ±  0.163  ms/op
DeepRecursionBenchmark.coroutinesFullOpt   avgt   20  2.309 ±  0.045  ms/op
DeepRecursionBenchmark.manualDFS           avgt   20  0.599 ±  0.001  ms/op
DeepRecursionBenchmark.manualDFSFast       avgt   20  0.287 ±  0.001  ms/op
DeepRecursionBenchmark.manualState         avgt   20  1.359 ±  0.022  ms/op
DeepRecursionBenchmark.recursive           avgt   20  0.581 ±  0.021  ms/op
DeepRecursionBenchmark.recursiveOpt        avgt   20  0.413 ±  0.008  ms/op

elizarov/DeepRecursionBenchmark

Deep recursion benchmark