Композиция Clojure не оптимизирует вызовы (может создать исключение StackOverflow)

Question

Я застрял в программе Clojure, обрабатывающей очень большой объем данных (данных изображений). Когда размер изображения был больше, чем 128x128, программа зависала с исключением из StackOverflow. Поскольку он работал для небольших изображений, я знал, что это не бесконечный цикл.

Было много возможных причин высокого использования памяти, поэтому я потратил время на копания. Убедитесь, что я правильно использовал ленивые последовательности, убедитесь, что вы используете recur в зависимости от ситуации и т. Д. Поворотный момент наступил, когда я понял, что это:

at clojure.core$comp$fn__5792.invoke(core.clj:2569)
at clojure.core$comp$fn__5792.invoke(core.clj:2569)
at clojure.core$comp$fn__5792.invoke(core.clj:2569)

относится к функции comp.

Итак, я посмотрел, где я его использовал:

(defn pipe [val funcs]
  ((apply comp funcs) val))

(pipe the-image-vec
  (map
    (fn [index] (fn [image-vec] ( ... )))
    (range image-size)))

Я делал операции для каждого пикселя, сопоставляя функцию каждому пикселю для его обработки. Интересно, что comp, похоже, не выигрывает от оптимизации хвостового вызова и не выполняет какого-либо последовательного применения функций. Кажется, что это было просто составление вещей основным способом, который, когда есть 65k функций, понятно переполняет стек. Вот исправленная версия:

(defn pipe [val funcs]
  (cond
    (= (count funcs) 0) val
    :else               (recur ((first funcs) val) (rest funcs))))

recur обеспечивает оптимизацию рекурсии, предотвращая наращивание стека.

Если кто-нибудь может объяснить, почему comp работает таким образом (или, скорее, не работает таким образом), я бы хотел быть просветленным.

Answer 1

Во-первых, более простой MCVE:

(def fs (repeat 1e6 identity))
((apply comp fs)  99)

#<StackOverflowError...

Но почему это происходит?Если вы посмотрите на (сокращенный) comp источник:

(defn comp
  ([f g] 
     (fn 
       ([x] (f (g x)))
  ([f g & fs]
     (reduce1 comp (list* f g fs))))

Вы можете увидеть, что все это в основном всего 2 части:

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

• Сокращение над функциями с использованием comp.

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

Итак, почему ТШО не может помочь здесь?Поскольку в отличие от большинства StackOverflowErrors, рекурсия здесь не является проблемой.Рекурсивные вызовы только когда-либо достигают одного кадра глубоко в вариационном случае внизу.Проблема заключается в создании массивной функции, которую нельзя просто оптимизировать.

Почему вы смогли это исправить?Поскольку у вас есть доступ к val, вы можете оценивать функции по ходу работы, а не создавать одну функцию для последующего вызова.comp был написан с использованием простой реализации, которая отлично работает в большинстве случаев, но не работает в крайних случаях, таких как тот, который вы представили.Хотя написать специализированную версию, которая обрабатывает огромные коллекции, довольно тривиально:

(defn safe-comp [& fs]
  (fn [value]
    (reduce (fn [acc f]
              (f acc))
            value
            (reverse fs))))

Конечно, обратите внимание, что она не обрабатывает несколько массивов, как в основной версии.

Честно говоря,за 3 года использования Clojure я ни разу не написал (apply comp ...).Хотя, безусловно, возможно, что вы столкнулись с делом, с которым мне никогда не приходилось иметь дело, более вероятно, что вы используете не тот инструмент для этой работы.Когда этот код будет завершен, опубликуйте его в Code Review, и мы сможем предложить лучшие способы выполнения того, что вы пытаетесь сделать.