Desempenho de Clojure para algoritmos caros

Eu implementei um algoritmo para calcular a subsequência comum contígua mais longa (não deve ser confundida com a subsequência mais longa comum, embora não seja importante para essas questões). Eu preciso apertar o máximo desempenho disso porque eu vou chamar muito isso. Eu implementei o mesmo algoritmo no Clojure e no Java para comparar o desempenho. A versão do Java é executada de forma significativamente mais rápida. Minha pergunta é se há algo que eu possa fazer na versão do Clojure para acelerar o nível de Java.

Aqui está o código 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  maxLen) { maxLen = matchLen; } } int[] swap = prev; prev = curr; curr = swap; } return maxLen; } 

Aqui está a versão do Clojure do mesmo:

 (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)))) 

Agora vamos testar isso na minha máquina:

 (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))))) 

Java:

 (time (Ratcliff/lcs a1 a2)) "Elapsed time: 1521.455 msecs" 

Clojure:

 (time (lcs a1 a2)) "Elapsed time: 19863.633 msecs" 

O Clojure é rápido, mas ainda assim uma ordem de magnitude mais lenta que o Java. Existe alguma coisa que eu possa fazer para diminuir essa lacuna? Ou eu maximizei e uma ordem de grandeza é a “sobrecarga mínima do Clojure”.

Como você pode ver, eu já estou usando a construção de loop de “baixo nível”, estou usando arrays Java nativos e insinuei os parâmetros para evitar reflexões.

Há algumas otimizações de algoritmo possíveis, mas não quero ir para lá agora. Estou curioso para saber o quão perto do desempenho do Java posso obter. Se eu não puder fechar a lacuna, vou apenas com o código Java. O restante deste projeto está no Clojure, mas talvez às vezes seja necessário o desempenho do Java para o desempenho.

EDIT: Adicionado uma versão mais rápida mais rápida abaixo do primeiro.

Aqui está minha opinião:

 (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])))) 

Principais diferenças com o seu: a[gs]et vs a[gs]et-int , uso de unchecked- ops (implicitamente através de areduce ), uso de um vetor como valor de retorno (e mecanismo “swap”) e max-len coagido a primitivo antes do loop interno (loops de valor primitivo são problemáticos, um pouco menos desde 1.5RC2, mas o suporte ainda não é perfeito, no entanto *warn-on-reflection* não é silencioso).

E eu mudei para .equals vez de = para evitar a lógica no equiv de Clojure.

EDIT: vamos ficar feio e restaurar o truque de troca de arrays:

 (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))) 

Na minha checkbox, é 30% mais rápido.

Aqui estão algumas melhorias:

  1. Nenhuma vantagem para sugerir tipo de fantasia, basta usar objects ^
  2. aset-int é obsoleto, acredito – apenas o aget antigo é mais rápido, em cerca de 3x no geral, parece

Além disso (e a dica do tipo longo sobre a recorrência mencionada acima), não vejo nenhuma maneira óbvia de melhorar ainda mais.

 (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" 
    Intereting Posts