воскресенье, 23 января 2011 г.

Поиск файлов на Clojure


Решил на днях написать на Clojure утилиту поиска файлов по шаблону – аналог утилиты find. Это один из классических учебных примеров, который пишут при изучении нового языка. Основная процедура по поиску файлов выглядит так.

(defn find-files [matcher-func directory]
   (if (or (nil? directory) (nil? matcher-func))
     nil
     (let [current (File. directory)
            cur-list (seq (.list current))
            dirs (filter #(and (not (= % ".")) (not (= % "..")))
                    (filter #(.isDirectory (File. (concat-dirs directory %))) cur-list))
            files (filter #(.isFile (File. (concat-dirs directory %))) cur-list)
            found (vec (map #(concat-dirs directory %)
                              (filter #(matcher-func %) files)))]
    (loop [d dirs
               f found]
      (if (or (nil? d) (empty? d))
        f
        (recur (next d)
                   (join f (find-files matcher-func
                                              (concat-dirs directory (first d))))))))))

В current создается объект File с указанной директорией; cur-list содержит список всех файлов и поддиректорий в указанной директории; dirs содержит только поддиректории; files – только файлы указанной директории; found – только файлы, совпавшие с указанным регулярным выражением. В цикле loop для каждой поддиректории запускается эта же функция find-files, а результат накапливается в переменной f. Когда цикл закончится, функция вернет вектор всех найденных файлов.
Здесь не показаны функции concat-dirs (соединение базовой директории с поддиректорией или файлом при помощи File.separator), matcher-func (функция содержит откомпилированный Pattern для сравнения с именем файла) и join, которая объединяет элементы двух векторов в один.
Впринципе, функция работает хорошо и находит файлы довольно шустро. Но Clojure знаменит тем, что в нем concurrency работает «из коробки», поэтому хотелось бы как-нибудь ее распараллелить.
Например, можно было бы поиск файлов в каждой директории выполнять в отдельном параллельном потоке. Но что будет, если директорией значительно больше, чем ядер процессора? Значительное время уйдет на коммуникацию между потоками и на переключение между ними. Поэтому я решил в отдельный поток пускать только процесс сравнения файлов с заданным шаблоном. Изменить в исходники пришлось совсем немного.

(defn find-files [matcher-func directory]
   (if (or (nil? directory) (nil? matcher-func))
     nil
     (let [current (File. directory)
            cur-list (seq (.list current))
            dirs (filter #(and (not (= % ".")) (not (= % "..")))
                   (filter #(.isDirectory (File. (concat-dirs directory %))) cur-list))
            files (filter #(.isFile (File. (concat-dirs directory %))) cur-list)
            found (future (vec (map #(concat-dirs directory %)
                                          (filter #(matcher-func %) files))))]
    (loop [d dirs
               f []]
      (if (or (nil? d) (empty? d))
        (join f @found)
        (recur (next d)
                   (join f (find-files matcher-func
                                             (concat-dirs directory (first d))))))))))

Как видите, главное изменение в том, что теперь в переменной found содержится не мгновенно вычисленный список совпавших с шаблоном файлов, а объект «future», который вычисляет этот список в отдельном потоке. В тот момент, когда нужно получить вычисленное значение, обращаться нужно к переменной так: @found. При таком обращении к переменной found, Clojure заблокирует текущий поток до вычисления future. Впрочем, на большом количестве директорий и файлов, вряд ли когда-либо приходится включать блокировку; в большинстве случаев этот параллельный поток по поиску файлов завершается раньше основного.
Весь исходник программы можно посмотреть здесь: https://gist.github.com/792198 .
Интересно было сравнить производительность моей программы с существующими. Для сравнения я использовал поиск на большом количестве файлов и директорий при помощи следующих утилит: Nautilus 2.32.0, find 4.4.2, find-file-st – первая, однопоточная версия программы на clojure; find-file-mt – вторая, многопоточная версия. Сравнение проводил на ноутбуке Acer Aspire 5745G, Ubuntu 10.10 (32-битная). Искал по паттерну «A.*» среди залежей своих книжек, сгруппированных по темам.

Получилось вот что:


Nautilus Find-file-st Find-file-mt Find
2min 20sec 34sec 18sec 2sec




Любопытно отметить следующее. Утилита find является однопоточной (по крайней мере мне не удалось найти упоминание создания потоков в ее исходниках), но явно очень круто оптимизированной. Никаких других объяснений ее волшебной скорости я не нашел.
Nautilus же поиск выполняет во многопоточном режиме, при том судя по всему на каждую директорию он создает отдельный поток (проверял в htop-е). В результате отвратительной реализации поиска, Nautilus значительно отстает по скорости не только от find, но даже от однопоточной версии моей программы, работающей, кстати, под jvm.
В общем, разрабатывать конкурентные программы на clojure удобно и быстро.

Комментариев нет:

Отправить комментарий