Производительность Clojure - почему "уродливый" "трюк подкачки массивов" улучшает производительность lcs?

Question

Это продолжение ответа @cgrand на вопрос "Эффективность Clojure для дорогих алгоритмов". Я изучал его и пытался применить некоторые из его приемов к моей экспериментальной настройке Clojure.

Одна вещь, которая меня интересует, - это "уродливый" "трюк с обменом массивами"

      (set! curr prev)
      (set! prev bak)

Как и почему это улучшает производительность по сравнению с оригинальным подходом? Я подозреваю, что массивы Clojure иногда не являются истинными массивами примитивов Java? При необходимости, пожалуйста, укажите основной источник Clojure в своем ответе.

Answer 1

Как упоминает Час, циклы с примитивными подсказками проблематичны. Clojure пытается сохранить ints без коробки, когда вы предоставляете подсказку, но он (по большей части) молча терпит неудачу, когда не может выполнить подсказки. Поэтому он заставляет это случиться, создавая deftype с изменяемыми полями и устанавливая их внутри цикла. Это ужасный хак, но он обходит некоторые ограничения в компиляторе.

Answer 2

На самом деле, это связано с распределением объектов. Вот оригинальный алгоритм с аннотациями:

(defn my-lcs [^objects a1 ^objects a2]
  (first
    (let [n (inc (alength a1))]
      (areduce a1 i 
        ;; destructuring of the initial value 
        [max-len ^ints prev ^ints curr] 
        ;; initial value - a vector of [long int[] int[]]
        [0 (int-array n) (int-array n)] 
        ;; The return value: a vector with the prev and curr swapped positions.
        [(areduce a2 j max-len (unchecked-long max-len)  ;; 
           (let [match-len 
                 (if (.equals (aget a1 i) (aget a2 j))
                   (unchecked-inc (aget prev j))
                   0)]
             (aset curr (unchecked-inc j) match-len)
             (if (> match-len max-len)
               match-len
               max-len)))
         curr prev])))) ;; <= swaps prev and curr for the next iteration

Согласно версии Java, prev а также curr "повторно используются" - подход динамического программирования, аналогичный тому, что описан здесь. Однако для этого необходимо выделить новый вектор на каждой итерации, который передается следующему сокращению.

Поместив prev а также curr вне areduce и делая их ^:unsynchronized-mutable Члены вольера IFn объект, он избегает выделять постоянный вектор на каждой итерации, и вместо этого просто платит за упаковку long (возможно, даже не это).

Таким образом, "уродливый" трюк заключался не в предыдущей итерации его кода Clojure, а в версии Java.