Производительность Clojure для дорогих алгоритмов
Я реализовал алгоритм для вычисления самой длинной непрерывной общей подпоследовательности (не путать с самой длинной общей подпоследовательностью, хотя это и не важно для этих вопросов). Мне нужно выжать максимальную производительность из этого, потому что я буду часто это называть. Я реализовал тот же алгоритм в Clojure и Java, чтобы сравнить производительность. Версия Java работает значительно быстрее. У меня вопрос, могу ли я что-нибудь сделать с версией Clojure, чтобы ускорить ее до уровня Java.
Вот код Java:
public static int lcs(String[] a1, String[] a2) {
if (a1 == null || a2 == null) {
return 0;
}
int matchLen = 0;
int maxLen = 0;
int a1Len = a1.length;
int a2Len = a2.length;
int[] prev = new int[a2Len + 1]; // holds data from previous iteration of inner for loop
int[] curr = new int[a2Len + 1]; // used for the 'current' iteration of inner for loop
for (int i = 0; i < a1Len; ++i) {
for (int j = 0; j < a2Len; ++j) {
if (a1[i].equals(a2[j])) {
matchLen = prev[j] + 1; // curr and prev are padded by 1 to allow for this assignment when j=0
}
else {
matchLen = 0;
}
curr[j+1] = matchLen;
if (matchLen > maxLen) {
maxLen = matchLen;
}
}
int[] swap = prev;
prev = curr;
curr = swap;
}
return maxLen;
}
Вот версия того же Clojure:
(defn lcs
[#^"[Ljava.lang.String;" a1 #^"[Ljava.lang.String;" a2]
(let [a1-len (alength a1)
a2-len (alength a2)
prev (int-array (inc a2-len))
curr (int-array (inc a2-len))]
(loop [i 0 max-len 0 prev prev curr curr]
(if (< i a1-len)
(recur (inc i)
(loop [j 0 max-len max-len]
(if (< j a2-len)
(if (= (aget a1 i) (aget a2 j))
(let [match-len (inc (aget prev j))]
(do
(aset-int curr (inc j) match-len)
(recur (inc j) (max max-len match-len))))
(do
(aset-int curr (inc j) 0)
(recur (inc j) max-len)))
max-len))
curr
prev)
max-len))))
Теперь давайте проверим это на моей машине:
(def pool "ABC")
(defn get-random-id [n] (apply str (repeatedly n #(rand-nth pool))))
(def a1 (into-array (take 10000 (repeatedly #(get-random-id 5)))))
(def a2 (into-array (take 10000 (repeatedly #(get-random-id 5)))))
Джава:
(time (Ratcliff/lcs a1 a2))
"Elapsed time: 1521.455 msecs"
Clojure:
(time (lcs a1 a2))
"Elapsed time: 19863.633 msecs"
Clojure быстрый, но все же на порядок медленнее, чем Java. Могу ли я что-нибудь сделать, чтобы закрыть этот пробел? Или я довел это до максимума, и один порядок величины - это "минимальные накладные расходы Clojure".
Как вы можете видеть, я уже использую конструкцию цикла "низкого уровня", я использую нативные массивы Java, и я подсказал параметры типа, чтобы избежать отражения.
Возможны некоторые алгоритмы оптимизации, но я не хочу идти туда прямо сейчас. Мне любопытно, как близко к производительности Java я могу получить. Если я не могу сократить разрыв, я просто пойду с кодом Java. Остальная часть этого проекта находится в Clojure, но, возможно, иногда необходимо перейти на Java для повышения производительности.
2 ответа
РЕДАКТИРОВАТЬ: Добавлена более быстрая уродливая версия ниже первой.
Вот мое взятие:
(defn my-lcs [^objects a1 ^objects a2]
(first
(let [n (inc (alength a1))]
(areduce a1 i
[max-len ^ints prev ^ints curr] [0 (int-array n) (int-array n)]
[(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]))))
Основные отличия с вашими: a[gs]et против a[gs]et-intиспользование unchecked- ops (неявно через areduce), использование вектора в качестве возвращаемого значения (и механизма "swap") и max-len приведено к примитиву перед внутренним циклом (примитивно-значные циклы проблематичны, немного меньше, чем 1.5RC2, но поддержка еще не совершенна), тем не мение *warn-on-reflection* не молчит).
И я перешел на .equals вместо = чтобы избежать логики в эквиваленте Clojure.
РЕДАКТИРОВАТЬ: давайте уродимся и восстановим трюк подкачки массивов:
(deftype F [^:unsynchronized-mutable ^ints curr
^:unsynchronized-mutable ^ints prev]
clojure.lang.IFn
(invoke [_ a1 a2]
(let [^objects a1 a1
^objects a2 a2]
(areduce a1 i max-len 0
(let [m (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) (unchecked-int match-len))
(if (> match-len max-len)
match-len
max-len)))
bak curr]
(set! curr prev)
(set! prev bak)
m)))))
(defn my-lcs2 [^objects a1 a2]
(let [n (inc (alength a1))
f (F. (int-array n) (int-array n))]
(f a1 a2)))
На моей коробке это на 30% быстрее.
Вот пара улучшений:
- Нет никакой пользы для модных подсказок, просто используйте объекты ^
- Я полагаю, что aset-int устарела - просто старое поколение быстрее, примерно в 3 раза больше
Кроме этого (и длинный указатель типа на повторение, упомянутое выше), я не вижу никаких очевидных способов дальнейшего улучшения.
(defn lcs
[^objects a1 ^objects a2]
(let [a1-len (alength a1)
a2-len (alength a2)
prev (int-array (inc a2-len))
curr (int-array (inc a2-len))]
(loop [i 0 max-len 0 prev prev curr curr]
(if (< i a1-len)
(recur (inc i)
(long (loop [j 0 max-len max-len]
(if (< j a2-len)
(if (= (aget a1 i) (aget a2 j))
(let [match-len (inc (aget prev j))]
(do
(aset curr (inc j) match-len)
(recur (inc j) (max max-len match-len))))
(do
(aset curr (inc j) 0)
(recur (inc j) max-len)))
max-len)))
curr
prev)
max-len))))
#'user/lcs
user> (time (lcs a1 a2))
"Elapsed time: 3862.211 msecs"