title: Clojure Performance For Expensive Algorithms
body: <p>I have implemented an algorithm to calculate the longest <em>contiguous</em> 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. <strong>My question is whether there is anything I can do to the Clojure version to speed it up to the level of Java.</strong></p>
  
  <p>Here's the Java code:</p>
  
  <pre><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 &lt; a1Len; ++i) {
          for (int j = 0; j &lt; 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 &gt; maxLen) {
                  maxLen = matchLen;
              }
          }
  
          int[] swap = prev;
          prev = curr;
          curr = swap;
      }
  
      return maxLen;
  }
  </code></pre>
  
  <p>Here is the Clojure version of the same:</p>
  
  <pre><code>(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 (&lt; i a1-len)
          (recur (inc i)
                 (loop [j 0 max-len max-len]
                   (if (&lt; 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))))
  </code></pre>
  
  <p>Now let's test these on my machine:</p>
  
  <pre><code>(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)))))
  </code></pre>
  
  <p>Java:</p>
  
  <pre><code>(time (Ratcliff/lcs a1 a2))
  "Elapsed time: 1521.455 msecs"
  </code></pre>
  
  <p>Clojure:</p>
  
  <pre><code>(time (lcs a1 a2))
  "Elapsed time: 19863.633 msecs"
  </code></pre>
  
  <p>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."</p>
  
  <p>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.</p>
  
  <p>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.</p>