CODEWITHSUNDEEP
scalaperformancerecursiontail-recursion
Raman Mishra
Raman Mishra

Reputation: 2686

Time taken by a while loop and recursion

I am not asking should i use recursion or iteration, or which is faster between them. I was trying to understand the iteration and recursion time taken, and I come up with an interesting pattern in the time taken of the both, which was what ever was on the top of the file is taking more time than the other.

For example: If I am writing for loop in the beginning it is taking more time than recursion and vice versa. The difference between time taken in both of the process are significently huge aprox 30 to 40 times.

My questions are:-

  1. Is order of a loop and recursion matters?
  2. Is there something related to print?
  3. What could be the possible reason for such behaviour?

following is the code I have in the same file and the language I am using is scala?

  def count(x: Int): Unit = {
    if (x <= 1000) {
      print(s"$x ")
      count(x + 1)
    }
  }

  val t3 = System.currentTimeMillis()
  count(1)
  val t4 = System.currentTimeMillis()
  println(s"\ntime taken by the recursion look = ${t4 - t3} mili second")

  var c = 1

  val t1 = System.currentTimeMillis()
  while(c <= 1000)
    {
      print(s"$c ")
      c+=1
    }
  val t2 = System.currentTimeMillis()

  println(s"\ntime taken by the while loop = ${t2 - t1} mili second")

In this situation the time taken for recursion and while loop are 986ms, 20ms respectively.

When I switch the position of loop and recursion which means first loop then recursion, time taken for recursion and while loop are 1.69 sec and 28 ms respectively.

Edit 1: I can see the same behaviour with bufferWriter if the recursion code is on the top. But not the case when recursion is below the loop. When recursion is below the loop it is taking almost same time with the difference of 2 to 3 ms.

Upvotes: 1

Views: 295

Answers (2)

Andrey Tyukin
Andrey Tyukin

Reputation: 44918

If you wanted to convince yourself that the tailrec-optimization works, without relying on any profiling tools, here is what you could try:

  • Use way more iterations
  • Throw away the first few iterations to give the JIT the time to wake up and do the hotspot-optimizations
  • Throw away all unpredictable side effects like printing to stdout
  • Throw away all costly operations that are the same in both approaches (formatting numbers etc.)
  • Measure in multiple rounds
  • Randomize the number of repetitions in each round
  • Randomize the order of variants within each round, to avoid any "catastrophic resonance" with the cycles of the garbage collector
  • Preferably, don't run anything else on the computer

Something along these lines:

def compare(
  xs: Array[(String, () => Unit)],
  maxRepsPerBlock: Int = 10000,
  totalRounds: Int = 100000,
  warmupRounds: Int = 1000
): Unit = {
  val n = xs.size
  val times: Array[Long] = Array.ofDim[Long](n)
  val rng = new util.Random
  val indices = (0 until n).toList
  var totalReps: Long = 0

  for (round <- 1 to totalRounds) {
    val order = rng.shuffle(indices)
    val reps = rng.nextInt(maxRepsPerBlock / 2) + maxRepsPerBlock / 2
    for (i <- order) {
      var r = 0
      while (r < reps) {
        r += 1
        val start = System.currentTimeMillis
        (xs(i)._2)()
        val end = System.currentTimeMillis
        if (round > warmupRounds) {
          times(i) += (end - start)
        }
      }
    }
    if (round > warmupRounds) {
      totalReps += reps
    }
  }

  for (i <- 0 until n) {
    println(f"${xs(i)._1}%20s : ${times(i) / totalReps.toDouble}")
  }
}

def gaussSumWhile(n: Int): Long = {
  var acc: Long = 0
  var i = 0
  while (i <= n) {
    acc += i
    i += 1
  }
  acc
}

@annotation.tailrec
def gaussSumRec(n: Int, acc: Long = 0, i: Int = 0): Long = {
  if (i <= n) gaussSumRec(n, acc + i, i + 1)
  else acc 
}

compare(Array(
  ("while", { () => gaussSumWhile(1000) }),
  ("@tailrec", { () => gaussSumRec(1000) })
))

Here is what it prints:

           while : 6.737733046257334E-5
        @tailrec : 6.70325653896487E-5

Even the simple hints above are sufficient for creating a benchmark that shows that the while loop and the tail-recursive function take roughly the same time.

Upvotes: 2

Tim
Tim

Reputation: 27356

Scala does not compile into machine code but into bytecode for the "Java Virtual Machine"(JVM) which then interprets that code on the native processor. The JVM uses multiple mechanisms to optimise code that is run frequently, eventually converting the frequently-called functions ("hotspots") into pure machine code.

This means that testing the first run of a function does not give a good measure of eventual performance. You need to "warm up" the JIT compiler by running the test code many times before attempting to measure the time taken.

Also, as noted in the comments, doing any kind of I/O is going to make timings very unreliable because there is a danger that the I/O will block. Write a test case that does not do any blocking, if possible.

Upvotes: 2

Related Questions