3 ms·
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 we
by 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 agoVectors 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.