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

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.

• as the numbers got larger, the map too should get larger and hence (1) more allocations, (2)the map index too might get inefficient or require rebuild unless you have an index method already defined based on the data domain. Nov 24, 2019 at 5:37
• That's a good point. I'll look into configuring this he map differently Nov 24, 2019 at 12:39
• Also memosiation may be causing paging to occur to the disk, which is probably an ssd, but still slower than main memory < cache < registers. If you are going to take this approach you may want to consider wiring memory, and perhaps have a retention policy to selectively maintain resume points. May 25, 2020 at 5:04