Должны ли алгоритмы рекурсивной файловой системы обрабатываться в императивном стиле?

Question

Я только что закончил читать "Программирование параллелизма на JVM" Venkat Subramaniam, и в этой книге автор использует в качестве одного из своих примеров подсчет размеров файлов в дереве каталогов. Он показывает реализации без параллелизма, использования очередей, защелки и использования акторов scala. В моей системе все параллельные реализации (очереди, защелки и акторы scala) могут выполняться менее чем за 9 секунд при выполнении итерации по моему каталогу / usr (OSX 10.6.8, Core Duo 2 ГГц, Intel G1 ssd 160 ГБ).

Я изучаю Clojure и решил портировать версию актера Scala на Clojure с использованием агентов. К сожалению, у меня было в среднем 11-12 секунд, что значительно медленнее, чем у остальных. Потратив DAYS, потянув меня за волосы, я обнаружил, что виновным был следующий фрагмент кода (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)}))))

Вы заметите, что я пытался использовать подсказки типа и переходный процесс для повышения производительности, но все безрезультатно. Я заменил приведенный выше код следующим:

(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 / lower для содержимого каталога, является более "функциональной", чем довольно обязательная обработка каталога второй версией, она намного менее эффективна, поскольку содержимое каталога повторяется несколько раз. Поскольку ввод-вывод файловой системы медленный, страдает вся программа.

Предполагая, что я прав, разве не безопасно сказать, что любой рекурсивный алгоритм файловой системы должен предпочитать императивный подход к производительности?

Я абсолютный новичок в Clojure, поэтому не стесняйтесь копировать мой код в клочья, если я делаю что-то глупое или идиоматическое.

Answer 1

Я отредактировал первую версию, чтобы сделать ее более читабельной.У меня есть несколько комментариев, но нет окончательно полезных утверждений:

1. Вы добавили кратковременные переходы и печатные шрифты без реального доказательства того, что замедляло ситуацию.С небрежным применением этих операций вполне возможно значительно замедлить процесс, поэтому рекомендуется создать профиль, чтобы узнать, что на самом деле замедляет процесс.Ваш выбор кажется разумным, но я удалил шрифты, которые явно не имели никакого эффекта (например, компилятору не требуется подсказка, чтобы знать, что (File. ...) возвращает объект File).

2. Clojure (на самом деле, любой лиспис) сильно предпочитает some-agent someAgent.Синтаксис префикса означает, что можно не беспокоиться о том, что - может быть проанализирован как вычитание с помощью бессмысленного компилятора, поэтому мы можем позволить себе более правильно расположенные имена.

3. Вы включаете вызовы в группуфункций, которые вы здесь вообще не определяете, например tallyResult и addFileToProcess.Предположительно они работают хорошо, так как вы используете их в отличной версии, но, не включив их, вы затруднили кому-то еще возиться и посмотреть, что ускоряет процесс.

4. Рассмотрим отправку вместо отправки для операций, связанных с вводом / выводом: при отправке используется ограниченный пул потоков, чтобы избежать перегрузки вашего процессора.Здесь это, вероятно, не имеет значения, так как вы используете только один агент, и он сериализуется, но в будущем вы столкнетесь с случаями, когда это имеет значение.

В любом случае, как и было обещано,более разборчивое переписывание вашей первой версии:

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

Редактировать: вы используете переходные процессы неправильным образом, отбрасывая результат вашего сокращения.(assoc! m k v) - это , разрешено изменять и возвращать объект m, но может возвращать другой объект, если это более удобно или эффективно.Таким образом, вам нужно что-то вроде (persistent! (reduce ...))