On Tue, May 10, 2011 at 2:21 PM, Carl Cotner <carl.cot...@gmail.com> wrote: > Hi, > > Is it possible to make Clojure run the following toy program faster > (without changing the algorithm)? > > (defn primeQ [n] (primes 2 (/ n 2) n)) > > (defn divQ [d n] (= (mod n d) 0)) > > (defn primes [d2 t2 n2] > (loop [d (int d2) t (int t2) n (int n2)] > (if (divQ d n) false > (if (> d t) true > (recur (inc d) t n))))) > > Running this on my machine: > > user> (time (primeQ 71378569)) > "Elapsed time: 11047.721488 msecs" > > is roughly 13 times slower than running the comparable Java program. > It seems like one should be able to do much better for such a > straightforward program. Is there anything I can do to make this > program faster?
Several things, though at the expense of idiomaticity of the code in many cases. 1: Algorithmic smarts. Division is expensive. Replace divQ's implementation in terms of mod with the algorithm binary GCD and it will probably be faster. Likewise the / n 2 in primeQ can be changed to a bit-shift-right. 2: Algorithmic smarts. There are more sophisticated algorithms for checking for primality, for example only checking for divisibility by primes smaller than or equal to the square root of the number rather than every number from 2 to half the number. 3: Technical speedups. Avoid function calls inside inner loops, which cause boxing and require var dereferencing. Fold divQ into primes, since it's only used once in there. 4: Technical speedups. Use unchecked primitive math throughout, if you know the range of a Java long will not be exceeded. With Clojure 1.2, use unchecked-inc and such (also in the binary GCD that will now be in primes in place of the divQ call) and make sure the primitives stay unboxed -- in particular, use loop/recur in primes (which means you may as well fold primes into primeQ as well) to avoid boxing at the end of each iteration. 5: Technical speedups. Make sure to use java -server to run it. 6: Benchmarking accuracy. Don't include the JIT compilation, the overhead of calling the primeQ function and of the benchmarking itself, or, God forbid, the JVM startup time; do a few thousand repetitions of the whole thing with a small (e.g. four-digit) prime to get the JITting done and then do a big number several times and average the results, using a timing macro of some sort from inside the running Clojure session to avoid counting the JVM startup time. The timing/call overhead will be lost in the noise if the number tested in the timed runs is big enough. By the way, you can (and generally should) name your Clojure predicates with a question-mark, e.g. div? instead of divQ or div-p. I take it you're used to another Lisp? If you're trying to do an apples-to-apples comparison of Java and Clojure, though, rather than make the fastest Clojure primality tester, then you will want to ignore points 1 and 2 above unless you make the same algorithmic improvements to both versions and you will want the timing loop to be internal (rather than a shell thing wrapping the JVM invocation) in both cases (Clojure has more dependencies, so takes a bit longer to start up the JVM, but this won't matter in any sane situation, whereas math speed will). -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
