Why is this “more efficient” version of a Scala Collatz solution slower than tail recursion?

Question

I implememted two versions of the collatz problem and felt an icy terror in the pit of my stomach as an optimized solution was slower than tail. The tail recursion is simple:

// calculate the next term in a Collatz sequence
def nextTerm(term: Long): Long = 
  if (term % 2 == 0) term / 2 else (3 * term) + 1

def byTailRecursion(upperbound: Long) = {
  range(upperbound)
    .map(x => (x, tailRec(x)))
    .maxBy(_._2)
}

@tailrec
def tailRec(term: Long, length: Int = 0): Int =
  term match {
    case x if x == 1l => length + 1
    case x => tailRec( nextTerm(x), length+1)
}

I believed that the nextTerm function would be the most computationally expensive because of the modulo and division involved. The attempt to optimize it was to save sequence lengths in a map identified by the current number. If during a computation a collatz sequence already was computed we would get the length of it and avoid unnecessary calculations:

def savePaths(upperbound: Long) = {
  var cLengths = scala.collection.mutable.Map(1l -> 1)
  for(i <- 2l to upperbound) {
    var queue = new mutable.Queue[Long]
    queue.enqueue(i)
    var j = nextTerm(i)
    while(!cLengths.contains(j)) {
      queue.enqueue(j)  
      j = nextTerm(j)
    }
    queue.dequeueWhile((term) => {
    cLengths(term) = queue.size + cLengths(j)
    queue.size > 0
    })
  }
  cLengths.maxBy(_._2)
}

However, in practice as numbers got large the "optimized" savePaths solution became significantly slower. When the upperbound was 1,000,000 tailrecursion ran in one-fourth of the time on average from the savePaths version. the nextTerm function, however, was called approximately 1 million times less than with tail recursion.

I suppose the major offender is lookups in the cLengths map? The other possibility is that Scala is parallelizing the tail recursion call but I'm not sure.

Answer 1

Answer: You are comparing two entirely different algorithms, and in one of them you use tail recursion instead of a loop. I suggest you write a third version which just does a loop without storing anything, so you can measure the effect of tail recursion and the effect of storing values separately. You can't change two variables and assume that a difference in results is due to changing the first variable.

PS What does your language do in case of overflow? Silently give the wrong results?