4 ms·

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(

by sreque 17y ago

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?

KirinDave 17y ago
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): ~/Projects/palindromes % 〕bin/run-tests 1000 X ' amanaplanacanalpanama ' naive : (skipped) fast : "Elapsed time: 449.397 msecs" "Elapsed time: 182.432 msecs" "Elapsed time: 149.721 msecs" "Elapsed time: 162.804 msecs" "Elapsed time: 159.086 msecs" http://gist.github.com/264369 http://gist.github.com/264369 CPU SAMPLES BEGIN (total = 205) Sun Dec 27 10:52:27 2009 rank self accum count trace method 1 1.46% 1.46% 3 301336 clojure.template__init.load 2 1.46% 2.93% 3 300339 java.lang.Class.forName0 3 0.98% 3.90% 2 301445 clojure.lang.PersistentHashMap.containsKey 4 0.98% 4.88% 2 301456 clojure.lang.RestFn.invoke 5 0.98% 5.85% 2 301486 clojure.lang.PersistentVector$TransientVector.editableTail 6 0.98% 6.83% 2 301487 clojure.lang.PersistentVector$TransientVector.conj 7 0.98% 7.80% 2 301465 clojure.lang.PersistentVector.chunkedSeq 8 0.98% 8.78% 2 301489 palindromes$ext_centers__96$fn__101.invoke 9 0.98% 9.76% 2 301498 clojure.lang.PersistentList.first 10 0.98% 10.73% 2 301482 clojure.lang.PersistentVector$TransientVector.conj 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.
- sreque 17y ago
  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.
jgrant27 17y ago
Using lists instead of vectors brings the Clojure version down to around 10X the speed of the CL code. user=> (#'i27.palindromes/big-test) 1000 X ' amanaplanacanalpanama ' fast : "Elapsed time: 183.748 msecs"

by sreque 17y ago

KirinDave 17y ago

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): ~/Projects/palindromes % 〕bin/run-tests 1000 X ' amanaplanacanalpanama ' naive : (skipped) fast : "Elapsed time: 449.397 msecs" "Elapsed time: 182.432 msecs" "Elapsed time: 149.721 msecs" "Elapsed time: 162.804 msecs" "Elapsed time: 159.086 msecs" http://gist.github.com/264369 http://gist.github.com/264369 CPU SAMPLES BEGIN (total = 205) Sun Dec 27 10:52:27 2009 rank self accum count trace method 1 1.46% 1.46% 3 301336 clojure.template__init.load 2 1.46% 2.93% 3 300339 java.lang.Class.forName0 3 0.98% 3.90% 2 301445 clojure.lang.PersistentHashMap.containsKey 4 0.98% 4.88% 2 301456 clojure.lang.RestFn.invoke 5 0.98% 5.85% 2 301486 clojure.lang.PersistentVector$TransientVector.editableTail 6 0.98% 6.83% 2 301487 clojure.lang.PersistentVector$TransientVector.conj 7 0.98% 7.80% 2 301465 clojure.lang.PersistentVector.chunkedSeq 8 0.98% 8.78% 2 301489 palindromes$ext_centers__96$fn__101.invoke 9 0.98% 9.76% 2 301498 clojure.lang.PersistentList.first 10 0.98% 10.73% 2 301482 clojure.lang.PersistentVector$TransientVector.conj 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.

sreque 17y ago
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.

jgrant27 17y ago

Using lists instead of vectors brings the Clojure version down to around 10X the speed of the CL code. user=> (#'i27.palindromes/big-test) 1000 X ' amanaplanacanalpanama ' fast : "Elapsed time: 183.748 msecs"