I have implemented an algorithm to calculate the longest *contiguous* common subsequence (not to be confused with longest common subsequence, though not important for this questions). I need to squeeze maximum performance from this because I'll be calling it a lot. I have implemented the same algorithm in Clojure and Java in order to compare performance. The Java version runs significantly faster. **My question is whether there is anything I can do to the Clojure version to speed it up to the level of Java.**

Here's the Java code:

```
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;
}
```

Here is the Clojure version of the 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 (< 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))))
```

Now let's test these on my 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 is quick but still an order of magnitude slower than Java. Is there anything I can do to close this gap? Or have I maxed it out and one order of magnitude is the "minimal Clojure overhead."

As you can see I am already using the "low level" construct of loop, I am using native Java arrays and I have type-hinted the parameters to avoid reflection.

There some algorithm optimizations possible, but I don't want to go there right now. I am curious how close to Java performance I can get. If I can't close the gap I'll just go with the Java code. The rest of this project is in Clojure, but perhaps sometimes dropping down to Java for performance is necessary.

7more comments