Блог

Я застрял в программе Clojure, обрабатывающей очень большой объем данных (данные изображения). Когда изображение было больше 128×128, программа завершала работу с исключением 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 , похоже, не извлекает выгоды из оптимизации конечных вызовов или выполняет какое-либо последовательное применение функций. Кажется, что он просто составлял вещи базовым способом, который при наличии 65 тысяч функций по понятным причинам переполняет стек. Вот исправленная версия:

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

recur гарантирует, что рекурсия оптимизируется для конечного вызова, предотвращая накопление стека.

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

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

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

#<StackOverflowError...
  

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

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

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

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

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

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

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

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

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

Конечно, обратите внимание, что это не обрабатывает несколько функций, как это делает базовая версия.

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