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.

Answer 2

Not really answering the question but since I spent some times benchmarking various combinations...

You can get better performance if you use Iterator, ArrayBuffer and avoid takeWhile in the inner loop, to minimize memory allocations.

def primes2(): Stream[Int] = {
  def sieve(p: Int, ps: ArrayBuffer[Int]): Stream[Int] = {
    def hasNoDivisor(prime_? :Int, j: Int = 0): Boolean = {
      val n = ps(j)
      if (n*n > prime_?) true
      else if (prime_? % n == 0) false else hasNoDivisor(prime_?, j+1)
    }
    p #:: { 
      val nextprime = Iterator.from(ps.last + 2, 2).find(hasNoDivisor(_)).get
      sieve(nextprime, ps += nextprime)
    }
  }     
  sieve(3, ArrayBuffer(3))
}

Here is a version with Iterator instead of Stream, it's faster and you can always use primes3().toStream to get a Stream if needed.

def primes3() = List(2,3).iterator ++ new Iterator[Int] {
  val ps = ArrayBuffer[Int](3)
  def hasNoDivisor(prime_? :Int, j: Int = 0): Boolean = {
    val n = ps(j)
    if (n*n > prime_?) true
    else if (prime_? % n == 0) false else hasNoDivisor(prime_?, j+1)
  }
  def hasNext = true
  def next() = {
    val nextprime = Iterator.from(ps.last + 2, 2).find(hasNoDivisor(_)).get
    ps += nextprime
    nextprime
  }
}

Results:

primes : warming...
primes : running...
primes : elapsed: 3.711
res39: Int = 283145
primes2: warming...
primes2: running...
primes2: elapsed: 1.039
res40: Int = 283145
primes3: warming...
primes3: running...
primes3: elapsed: 0.530
res41: Int = 283146

I also tried replacing from, find and hasNoDivisor with a couple of while loops, and that was faster, but less comprehensible.