Performance problems with Clojure HashMap's lookup

Question

I was trying to implement a pure functional Sieve of Eratosthenes' algorithm, based on this paper: https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Following all the steps, I end up with a very performant Haskell code, and I tried to port it to Clojure. Problem is, the Clojure's version is very slow: it's as slow as trying to test all numbers to check if they are divisible or not. The code I ended up was the following:

(defn- sieve2 [[x & xs] table]
  (let [reinsert (fn [table prime]
                  ;  (merge-with concat table {(+ x prime) [prime]})
                   (update table (+ x prime) #(cons prime %)))] ;(vec %) prime)))]
    (if x
      (if-let [facts (get table x)]
        (recur xs (reduce reinsert (dissoc table x) facts))
        (lazy-seq (cons x (sieve2 xs (assoc table (* x x) [x])))))
      '())))

(defn real-sieve [xs] (sieve2 xs {}))

(merge with concat is commented because that was the Haskell's way, but its even slower).

With 30000 prime numbers, Haskell's version ran in 39ms, and Clojure, in 483ms. So, I ported my Clojure version to Scala:

val primes2 = {
  def sieve(xs: Stream[Int], table: Map[Int, Vector[Int]]): Stream[Int] =
  xs match {
    case Stream() => xs
    case x #:: xs => table get x match {
      case Some(facts) =>
        sieve(xs, facts.foldLeft(table - x) { (table, prime) =>
          val key = x + prime
          val value = table.getOrElse(key, Vector()) :+ x
          table + (key -> value)
        })
      case None => x #:: sieve(xs, table + (x*x -> Vector(x)))
    }
  }
  sieve(Stream.from(2), Map())
}

And it ran on 39ms. Then, I downloaded VisualVM and sampled my code, to see this:

Notice that most of the time, the performance killers are the HashMap key lookup and assoc. Is there some problem with my code?

Answer 1

Trying out OP's code, I indeed saw that the scala implementation was taking around 30 ms, while clojure's was about 500ms. That was odd.

So I compared the results, and found that the scala implementation was giving me lots of even numbers as primes. After some digging I learned that there were two bugs in the scala implementation. The first:

val value = table.getOrElse(key, Vector()) :+ x     // bug
val value = table.getOrElse(key, Vector()) :+ prime // corrected

This bug caused the evaluation to finish much quicker, since lots of non-prime numbers were included in the result.

The second bug with the scala version is the use of Int. Way before the 30000'th prime is reached an overflow occurs:

scala> 92683*92683
res1: Int = 203897 // an odd square?? 

So, I fixed that as well, and since scala does not have a Stream.from(Long), had to write that too (I dont speak fluent scala, so there might be a better way..):

object Test {
  def sieve(xs: Stream[Long], table: Map[Long, Vector[Long]]): Stream[Long] =
        xs match {
            case Stream() => xs
            case x #:: xs = {
              table get x match {
              case Some(facts) =>
                sieve(xs, facts.foldLeft(table - x) { (table, prime) =>
                  val key = x + prime
                  val value = table.getOrElse(key, Vector()) :+ prime
                  table + (key -> value)
                })
                case None =>  {
                     x #:: sieve(xs, table + (x*x -> Vector(x)))
                }}}}   
  def fromLong(start:Long) : Stream[Long] = Stream.cons(start, fromLong(start+1))

  def main(args: Array[String]) {
     sieve(fromLong(2), Map())
  }
}

Running this again gave me comparable elapsed times for both scala and clojure:

scala> Test.time {Test.sieve(Test.fromLong(2), Map()).take(30000).last}
Elapsed time: 583 msecs
res14: Long = 350377

And clojure's version:

(time (last (take 30000 (real-sieve a))))
"Elapsed time: 536.646696 msecs"
 350377

And this is in fact, the 30000th prime!