java - Clojure Performance For Expensive Algorithms -

java - Clojure Performance For Expensive Algorithms -

i have implemented algorithm calculate longest contiguous mutual subsequence (not confused longest mutual subsequence, though not of import questions). need squeeze maximum performance because i'll calling lot. have implemented same algorithm in clojure , java in order compare performance. java version runs faster. my question whether there can clojure version speed level of java.

here's java code:

public static int lcs(string[] a1, string[] a2) { if (a1 == null || a2 == null) { homecoming 0; } int matchlen = 0; int maxlen = 0; int a1len = a1.length; int a2len = a2.length; int[] prev = new int[a2len + 1]; // holds info previous iteration of inner loop int[] curr = new int[a2len + 1]; // used 'current' iteration of inner loop (int = 0; < a1len; ++i) { (int j = 0; j < a2len; ++j) { if (a1[i].equals(a2[j])) { matchlen = prev[j] + 1; // curr , prev padded 1 allow assignment when j=0 } else { matchlen = 0; } curr[j+1] = matchlen; if (matchlen > maxlen) { maxlen = matchlen; } } int[] swap = prev; prev = curr; curr = swap; } homecoming maxlen; }

here clojure version of same:

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

now let's test these on machine:

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

clojure quick still order of magnitude slower java. there can close gap? or have maxed out , 1 order of magnitude "minimal clojure overhead."

as can see using "low level" build of loop, using native java arrays , have type-hinted parameters avoid reflection.

there algorithm optimizations possible, don't want go there right now. curious how close java performance can get. if can't close gap i'll go java code. rest of project in clojure, perhaps dropping downwards java performance necessary.

edit: added faster uglier version below first one.

here take:

(defn my-lcs [^objects a1 ^objects a2] (first (let [n (inc (alength a1))] (areduce a1 [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]))))

main differences yours: a[gs]et vs a[gs]et-int, utilize of unchecked- ops (implicitly through areduce), utilize of vector homecoming value (and "swap" mechanism) , max-len coerced primitive before inner loop (primitive-valued loops problematic, less since 1.5rc2 back upwards isn't perfect yet, *warn-on-reflection* not silent).

and switched .equals instead of = avoid logic in clojure's equiv.

edit: let's ugly , restore arrays swap trick:

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

on box, it's 30% faster.

java performance clojure