Why Stream/lazy val implementation using is faster than ListBuffer one

Question

I coded the following implementation of lazy sieve algorithms using Stream and lazy val below :

def primes(): Stream[Int] = {
   lazy val ps = 2 #:: sieve(3)
   def sieve(p: Int): Stream[Int] = {
       p #:: sieve(
            Stream.from(p + 2, 2).
             find(i=> ps.takeWhile(j => j * j <= i).
                     forall(i % _ > 0)).get)
  }
  ps
}

and the following implementation using (mutable) ListBuffer:

import scala.collection.mutable.ListBuffer
def primes(): Stream[Int] = {
    def sieve(p: Int, ps: ListBuffer[Int]): Stream[Int] = {
        p #:: { val nextprime =
            Stream.from(p + 2, 2).
            find(i=> ps.takeWhile(j => j * j <= i).
                 forall(i % _ > 0)).get
            sieve(nextprime, ps += nextprime)
         }
    }       
    sieve(3, ListBuffer(3))}

When I did primes().takeWhile(_ < 1000000).size , the first implementation is 3 times faster than the second one. What's the explanation for this ?

I edited the second version: it should have been sieve(3, ListBuffer(3)) instead of sieve(3, ListBuffer()) .

Answer 1

Well, my guess is this line:

find(i=> ps.takeWhile(j => j * j <= i).forall(i % _ > 0)).get

On ListBuffer, takeWhile creates a temporary collection (which keeps getting bigger and bigger). Meanwhile, Stream, because of its non-strictness, avoids doing so. As soon as the forall fails, it stops computing the takeWhile.