clojure - 递归文件系统算法是否应该以命令式方式处理？

Question

我刚刚读完 Venkat Subramaniam 所著的《JVM 上的并发编程》，在那本书中，作者使用了计算目录树中的文件大小作为示例之一。他展示了不使用并发、使用队列、使用闩锁和使用 scala actor 的实现。在我的系统上，当遍历我的/usr 目录(OSX 10.6.8、Core Duo 2 Ghz、Intel G1 ssd 160GB)时，所有并发实现(队列、闩锁和 scala actor)都能够在 9 秒内运行。

我正在学习 Clojure，并决定使用代理将 Scala actor 版本移植到 Clojure。不幸的是，我的平均时间为 11-12 秒，这比其他人慢得多。在花了几天时间后，我发现下面的代码是罪魁祸首(processFile 是我发送给文件处理代理的函数:

(defn processFile
  [fileProcessor collectorAgent ^String fileName]
  (let [^File file-obj (File. ^String fileName)
        fileTotals (transient {:files 0, :bytes 0})]
    (cond
      (.isDirectory file-obj)
        (do
          (doseq [^File dir (.listFiles file-obj) :when (.isDirectory dir)]
            (send collectorAgent addFileToProcess (.getPath dir)))
          (send collectorAgent tallyResult *agent*)
          (reduce (fn [currentTotal newItem] (assoc! currentTotal :files (inc (:files currentTotal))
                                                                  :bytes (+ (:bytes currentTotal) newItem)))
                  fileTotals
                  (map #(.length ^File %) (filter #(.isFile ^File %) (.listFiles file-obj))))
          (persistent! fileTotals))

      (.isFile file-obj) (do (send collectorAgent tallyResult *agent*) {:files 1, :bytes (.length file-obj)}))))

您会注意到我尝试使用类型提示和 transient 来提高性能，但都无济于事。我用以下代码替换了上面的代码:

(defn processChildren
  [children]
  (loop [entries children files 0 bytes 0 dirs '()]
    (let [^File child (first entries)]
      (cond
        (not (seq entries)) {:files files, :bytes bytes, :dirs dirs}
        (.isFile child) (recur (rest entries) (inc files) (+ bytes (.length child)) dirs)
        (.isDirectory child) (recur (rest entries) files bytes (conj dirs child))
        :else (recur (rest entries) files bytes dirs)))))

(defn processFile
  [fileProcessor collectorAgent ^String fileName]
  (let [{files :files, bytes :bytes, dirs :dirs} (processChildren (.listFiles (File. fileName)))]
    (doseq [^File dir dirs]
      (send collectorAgent addFileToProcess (.getPath dir)))
    (send collectorAgent tallyResult *agent*)
    {:files files, :bytes bytes}))

该版本的性能与 Scala 版本相当(如果不是更快的话)，并且与 Scala 版本中使用的算法几乎相同。我只是假设该算法的函数式方法也同样有效。

所以......这个冗长的问题可以归结为以下几点:为什么第二个版本更快？

我的假设是，虽然第一个版本对目录内容使用 map/filter/reduce 比第二个版本对目录的命令式处理更“实用”，但它的效率要低得多，因为目录的内容正在被处理。迭代了多次。由于文件系统 I/O 很慢，整个程序都会受到影响。

假设我是对的，可以肯定地说任何递归文件系统算法都应该更喜欢命令式方法来提高性能吗？

我是 Clojure 的初学者，所以如果我做了一些愚蠢或不惯用的事情，请随意将我的代码撕成碎片。

Answer 1

我编辑了第一个版本以使其更具可读性。我有一些评论，但没有确实有用的陈述:

1. 您添加了瞬变和类型提示，但没有真正的证据表明是什么导致速度变慢。如果不小心应用这些操作，完全有可能显着减慢速度，因此最好进行分析以找出实际减慢速度的原因。您的选择似乎很合理，但我删除了显然没有效果的类型提示(例如，编译器不需要提示即可知道 (File. ...) 生成 File 对象)。

2. Clojure(事实上，任何 lisp)都强烈喜欢 some-agent 而不是 someAgent。前缀语法意味着不必担心 - 会被无知的编译器解析为减法，因此我们可以提供更间隔良好的名称。

3. 您包含了对一堆您根本没有在此处定义的函数的调用，例如tallyResult 和addFileToProcess。想必它们表现良好，因为您在高性能版本中使用它们，但如果不包含它们，其他人就很难研究它并了解什么可以加快速度。

4. 对于 I/O 绑定(bind)操作，请考虑使用 send-off 而不是 send:send 使用有界线程池来避免处理器陷入困境。在这里，这可能并不重要，因为您只使用一个代理并且它会序列化，但将来您会遇到重要的情况。

无论如何，正如所 promise 的，对您的第一个版本进行更清晰的重写:

(defn process-file
  [_ collector-agent ^String file-name]
  (let [file-obj (File. file-name)
        file-totals (transient {:files 0, :bytes 0})]
    (cond (.isDirectory file-obj)
          (do
            (doseq [^File dir (.listFiles file-obj)
                    :when (.isDirectory dir)]
              (send collector-agent addFileToProcess
                    (.getPath dir)))
            (send collector-agent tallyResult *agent*)
            (reduce (fn [current-total new-item]
                      (assoc! current-total
                              :files (inc (:files current-total))
                              :bytes (+ (:bytes current-total) new-item)))
                    file-totals
                    (map #(.length ^File %)
                         (filter #(.isFile ^File %)
                                 (.listFiles file-obj)))) -
            (persistent! file-totals))

          (.isFile file-obj)
          (do (send collector-agent tallyResult *agent*)
              {:files 1, :bytes (.length file-obj)}))))

编辑:您以错误的方式使用 transient ，丢弃了减少的结果。 (assoc!m k v)允许修改并返回m对象，但如果更方便或更高效的话，可能会返回不同的对象。所以你需要更像 (persistent! (reduce ...))