Thanks for your thorough reply, Ken. On May 10, 5:43 pm, Ken Wesson <kwess...@gmail.com> wrote: > > [...] > > 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.
Yeah, I know, the program is just meant to be something a bit less trivial than an empty loop, for (very simple) run time comparison purposes, and also to help me get a taste of various languages. However, I'm interested in actually learning Clojure for machine learning applications and so am trying to understand its implementation details in more depth. (BTW, as you could probably tell from the code, I am not actually trying to implement a practical test for primality. On the other hand, you probably couldn't tell that I'm actually a number theorist. :-) > 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. Just to make sure I understand: type hints don't cause Clojure to optimize these things out by itself? (I had been supposing that type hints would propagate through functions and function calls so that boxing, for example, would be avoided.) > 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. Thanks, I will do that. > 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. Does the built-in Clojure (time ...) expression that I used from the SLIME REPL actually include things like JVM startup time? user> (time (primeQ 71378569)) "Elapsed time: 11047.721488 msecs" Also, do you happen to know of a good reference for how/when the JVM does JIT compilation? > 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? Thanks, I will do that in the future - I just read about that Clojure convention shortly after posting. :-) > 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). Yeah, I am trying to do an apples-to-apples comparison while using the tools that Clojure provides (e.g., type hints) to make the code as efficient as possible. Thanks again for your help. Carl -- 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
