Clojure HashMap 查找的性能问题

Question

我试图根据这篇论文实现纯函数式埃拉托色尼筛法算法:https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

按照所有步骤，我最终得到了一个非常高效的 Haskell 代码，并且我尝试将它移植到 Clojure。问题是，Clojure 的版本非常慢:它就像尝试测试所有数字以检查它们是否可整除一样慢。我最终得到的代码如下:

(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 被评论了，因为那是 Haskell 的方式，但它更慢)。

对于 30000 个质数，Haskell 版本的运行时间为 39 毫秒，Clojure 版本为 483 毫秒。因此，我将我的 Clojure 版本移植到了 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())
}

它运行了 39 毫秒。然后，我下载了 VisualVM 并对我的代码进行了采样，以查看:

请注意，大多数时候，性能 killer 是 HashMap 键查找和 assoc。我的代码有问题吗？

Answer 1

尝试 OP 的代码，我确实看到 scala 的实现大约需要 30 毫秒，而 clojure 的大约需要 500 毫秒。这很奇怪。

所以我比较了结果，发现 scala 实现给了我很多偶数作为质数。经过一番挖掘后，我了解到 scala 实现中存在两个错误。第一个:

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

这个错误导致评估完成得更快，因为结果中包含了很多非素数。

scala 版本的第二个错误是 Int 的使用。在达到第 30000 个素数之前发生溢出:

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

所以，我也解决了这个问题，因为 scala 没有 Stream.from(Long)，所以也必须写那个(我不会说流利的 scala，所以可能有更好的方式..):

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())
  }
}

再次运行它，我得到了 scala 和 clojure 的可比运行时间:

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

和 clojure 的版本:

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

这实际上是 30000th prime !