He's using vectors with clojure and lists with lisp. Why? It looks like he's concatenating vectors, which is O(n), with clojure, but cons'ing lists, which is O(1), with lisp. As much as I like seeing clojure's performance get critiqued, this comparison doesn't seem fair at all. Why aren't the implementations identical?
You need to remember that clojure vectors are NOTHING like arrays. They're persistent ultra-wide tree structures. I was curious if you were right and vectors were the wrong choice, so I profiled the code.
I had the big-test function run several times to actually show the real numbers (you need to prime the JVM to get a real indication of its speed):
I do see a lot of vector activity, but no smoking gun. As other people have pointed out in this thread, SBCL is notorious for being very good at recursing down big data structures. It's also notorious for being totally terrible with lots of other common tasks. I suspect this is just a case where the algorithm runs in such a way that languages that compile down all the way have a big advantage.
I've asked some more experienced hands in #clojure on freenode to take a stab at it. There are a lot of recent optimization developments in the clojure-1.1.0 release that I don't know how to use well yet. Hopefully someone there can tackle it.
Vectors may be implemented very differently from mutable arrays, but it is my understanding that they allow for efficient appends and updates, not efficient prepends. I would still switch to using lists, if only because when doing performance comparisons between languages and implementations you want the code and data structures to be as identical as possible.
SBCL is very impressive. Until recently[1], it was far and away the quickest implementation for a dynamic language. Considering we have yet to see invokedynamic or tail calls on the JVM, I'm rather unsurprised by SBCL's comfortable lead in performance.
There are other Lisp compilers which are about as fast as SBCL. For example on my Mac, the 64bit LispWorks is for many tasks faster than SBCL. SBCL is faster for some numerics, but 'typical' Lisp programs are running faster in the 64bit LispWorks. Then there is Scieneer CL, which is also forked from CMUCL, like SBCL.
There are many more compilers for dynamic languages that people usually don't know. I would be careful to claim 'fastest', given that only few advanced compilers in that area are known to people.
It seems easy to hit some implementation wart that makes performance abysmal - it's hard to believe that a JVM targeted language would be 20x times slower. Case in point - I tried the benchmark with a bigger input - the performance ratio between the 'fast' implementations remained the same. Incredibly, though, the CL implementation took nearly 2 minutes to construct the input string, something that is essentially instant in the Clojure version.
time sbcl --noinform --load palindromes.lisp --eval "(progn (big-test) (quit))"
30000 X ' amanaplanacanalpanama '
fast :
Evaluation took:
0.197 seconds of real time
0.191206 seconds of total run time (0.186952 user, 0.004254 system)
[ Run times consist of 0.006 seconds GC time, and 0.186 seconds non-GC time. ]
96.95% CPU
471,342,768 processor cycles
13,802,832 bytes consed
real 1m55.551s
user 1m51.954s
sys 0m0.778s
Because the CL code to create the string is completely inefficient. It starts that he prints a string with format, using a format directive. Instead of (FORMAT s "~a" string) use (write-string string s). Also, if the result string length is known, one can just allocate a result string and copy the source string repeatedly into the result string...
It's clear that it's inefficient and I'm no expert in either CL or FORMAT but it's not just inefficient, it's staggeringly inefficient. 2 minutes to make a few hundred k string on a 2+ghz CPU is hard to fathom, even if one assumes the method is imperfect, generates piles of garbage, etc, etc. It'd be interesting if someone could explain how this actually happens.
I don't know much about optimization, but...it looks like he's timing the Clojure version with Clojure already loaded, but timing the SBCL version with SBCL not loaded. Would that change the measurements much?
Nah, that's not what's happening. The (time ...) special form is what prints the timing results, and it's squarely in the (big-test) function. All is right under the sun.
I am looking into the cl-cookbook at sourceforge. It looks very interesting and worth investigating more. This specific benchmark seemingly would benefit from multiple threads on multiprocessors, if I could read its implementations correctly.
cl-cookbook is mostly outdated. use bordeaux-threads; it works across all lisps :-) and it's multicore for sbcl linux and clozure everything else (dunno about the commercial lisps)
