Re: Performance tips for Clojure
There is a interface 'Counted' that a lot of Clojure data structures implement to indicate that they provide O(1) for (count). Thanks, Stu On Fri, Mar 13, 2009 at 4:59 AM, Christophe Grand christo...@cgrand.netwrote: Christian Vest Hansen a écrit : I think that count is O(n) for lists, no? Count is O(1) for lists but O(n) for a chain of conses. Clojure user= (let [l (apply list (range 10))] (time (dotimes [_ 100] (count l Elapsed time: 169.710116 msecs nil user= (let [l (apply list (range 40))] (time (dotimes [_ 100] (count l Elapsed time: 167.664046 msecs nil user= (let [l (reduce #(cons %2 %1) nil (range 10))] (time (dotimes [_ 100] (count l Elapsed time: 662.121862 msecs nil user= (let [l (reduce #(cons %2 %1) nil (range 100))] (time (dotimes [_ 100] (count l Elapsed time: 5316.110567 msecs nil -- Professional: http://cgrand.net/ (fr) On Clojure: http://clj-me.blogspot.com/ (en) --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Performance tips for Clojure
Hi! I have been programming in clojure for a few months now. I really like the language. Something that I have noted is that it is very easy to write slow Clojure code. After doing some programming and spending time optimizing things, I decided to write on my blog some points on how to write efficient Clojure code. http://devlog.bigmonachus.org/2009/03/performance-tips-for-clojure.html There are a couple of obvious ones, but also some others that I haven't seen documented (like, map is much faster on lists than on vectors since rest is O(1) for lists). The list is not complete. Maybe you can tell me some other tips --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: Performance tips for Clojure
On Fri, Mar 13, 2009 at 2:18 AM, Sergio bigmonac...@gmail.com wrote: There are a couple of obvious ones, but also some others that I haven't seen documented (like, map is much faster on lists than on vectors since rest is O(1) for lists). You're right that 'rest' is O(1) for lists, but it's O(1) for vectors as well. Your blog post include this table: rest - O(1) for lists. O(n) for vectors. count - O(1) for lists and vectors nth - O(n) for lists. O(1) for vectors. cons - O(1) for lists, O(n) for vectors This has a couple errors. Both 'rest' and 'cons' are O(1) on vectors. I'm not sure what in the source code led you to believe otherwise. Both 'rest' and 'cons' create a seq from the vector, but this is an O(1) operation. You can also run some timing experiments and see that 'map' is at least as fast on vectors as on lists. (defn timemap [c] (time (dotimes [i 100] (last (map identity c) (timemap (into [] (range 1))) == Elapsed time: 158.464048 msecs (timemap (into [] (range 10))) == Elapsed time: 1690.745615 msecs Note that multiplying the length of the vector by 10 increased the time by roughly 10 -- this suggests an O(n) operation, as we would expect. (timemap (into () (range 1))) == Elapsed time: 185.460957 msecs (timemap (into () (range 10))) == Elapsed time: 1821.346964 msecs Again we see evidence of 'map' being O(n), but when walking across a list it appears to run slightly *slower* than across a vector, though probably not by enough to be significant. We can even time 'rest' itself: (defn timerest [c] (time (dotimes [i 100] (rest c (timerest (into [] (range 1))) == Elapsed time: 125.826519 msecs If 'rest' were O(n) on vectors, we should be able to multiply the length of the vector by 100 and see the time go up by roughly 100x: (timerest (into [] (range 100))) == Elapsed time: 147.096976 msecs The amount of time it takes to build the vector goes up significantly, but the timed part, calling 'rest' a million times, doesn't take anywhere near 100 times longer. --Chouser --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: Performance tips for Clojure
Sorry =( I am horribly mistaken
I should have taken my time before posting..
But still, I really thought cons on vectors was O(n) base on
PersistentVector.java, line 148 (The version I'm reading is not the
current SVN head, so I don't know if it is that line for you)
Here is the snippet:
if(tail.length 32)
{
Object[] newTail = new Object[tail.length + 1];
System.arraycopy(tail, 0, newTail, 0, tail.length);
newTail[tail.length] = val;
return new PersistentVector(meta(), cnt + 1, shift, root,
newTail);
}
I thought it was O(n) because of the System.arraycopy. I'm guessing
that for length32 that is considered constant and the rest of the
cons function does something else.
Here is the microbenchmark that made me think map was slower on
vectors:
(def ls (list (range 100)))
(def vc (vec (range 100)))
(time (dorun (map (fn [x]) ls)))
Elapsed time: 3.184435 msecs
(time (dorun (map (fn [x]) vc)))
Elapsed time: 498.535303 msecs
Maybe you can explain it to me (On my blog I posted that maybe it was
because map was converting the vector to a seq and that was O(n), but
you just told me that converting vector to seq is O(n).
On Mar 13, 12:49 am, Chouser chou...@gmail.com wrote:
On Fri, Mar 13, 2009 at 2:18 AM, Sergio bigmonac...@gmail.com wrote:
There are a couple of obvious ones, but also some others that I
haven't seen documented (like, map is much faster on lists than on
vectors since rest is O(1) for lists).
You're right that 'rest' is O(1) for lists, but it's O(1) for vectors as well.
Your blog post include this table:
rest - O(1) for lists. O(n) for vectors.
count - O(1) for lists and vectors
nth - O(n) for lists. O(1) for vectors.
cons - O(1) for lists, O(n) for vectors
This has a couple errors. Both 'rest' and 'cons' are O(1) on vectors.
I'm not sure what in the source code led you to believe otherwise.
Both 'rest' and 'cons' create a seq from the vector, but this is an
O(1) operation. You can also run some timing experiments and see that
'map' is at least as fast on vectors as on lists.
(defn timemap [c]
(time
(dotimes [i 100]
(last (map identity c)
(timemap (into [] (range 1))) == Elapsed time: 158.464048 msecs
(timemap (into [] (range 10))) == Elapsed time: 1690.745615 msecs
Note that multiplying the length of the vector by 10 increased the
time by roughly 10 -- this suggests an O(n) operation, as we would
expect.
(timemap (into () (range 1))) == Elapsed time: 185.460957 msecs
(timemap (into () (range 10))) == Elapsed time: 1821.346964 msecs
Again we see evidence of 'map' being O(n), but when walking across a
list it appears to run slightly *slower* than across a vector, though
probably not by enough to be significant.
We can even time 'rest' itself:
(defn timerest [c]
(time
(dotimes [i 100]
(rest c
(timerest (into [] (range 1))) == Elapsed time: 125.826519 msecs
If 'rest' were O(n) on vectors, we should be able to multiply the
length of the vector by 100 and see the time go up by roughly 100x:
(timerest (into [] (range 100))) == Elapsed time: 147.096976 msecs
The amount of time it takes to build the vector goes up significantly,
but the timed part, calling 'rest' a million times, doesn't take
anywhere near 100 times longer.
--Chouser
--~--~-~--~~~---~--~~
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
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
-~--~~~~--~~--~--~---
Re: Performance tips for Clojure
list doesn't do what you think it does. You've just created a list of one element. On Fri, Mar 13, 2009 at 12:10 AM, Sergio bigmonac...@gmail.com wrote: (def ls (list (range 100))) --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: Performance tips for Clojure
On Fri, Mar 13, 2009 at 7:49 AM, Chouser chou...@gmail.com wrote: On Fri, Mar 13, 2009 at 2:18 AM, Sergio bigmonac...@gmail.com wrote: There are a couple of obvious ones, but also some others that I haven't seen documented (like, map is much faster on lists than on vectors since rest is O(1) for lists). You're right that 'rest' is O(1) for lists, but it's O(1) for vectors as well. Your blog post include this table: rest - O(1) for lists. O(n) for vectors. count - O(1) for lists and vectors I think that count is O(n) for lists, no? nth - O(n) for lists. O(1) for vectors. cons - O(1) for lists, O(n) for vectors This has a couple errors. Both 'rest' and 'cons' are O(1) on vectors. I'm not sure what in the source code led you to believe otherwise. Both 'rest' and 'cons' create a seq from the vector, but this is an O(1) operation. You can also run some timing experiments and see that 'map' is at least as fast on vectors as on lists. (defn timemap [c] (time (dotimes [i 100] (last (map identity c) (timemap (into [] (range 1))) == Elapsed time: 158.464048 msecs (timemap (into [] (range 10))) == Elapsed time: 1690.745615 msecs Note that multiplying the length of the vector by 10 increased the time by roughly 10 -- this suggests an O(n) operation, as we would expect. (timemap (into () (range 1))) == Elapsed time: 185.460957 msecs (timemap (into () (range 10))) == Elapsed time: 1821.346964 msecs Again we see evidence of 'map' being O(n), but when walking across a list it appears to run slightly *slower* than across a vector, though probably not by enough to be significant. We can even time 'rest' itself: (defn timerest [c] (time (dotimes [i 100] (rest c (timerest (into [] (range 1))) == Elapsed time: 125.826519 msecs If 'rest' were O(n) on vectors, we should be able to multiply the length of the vector by 100 and see the time go up by roughly 100x: (timerest (into [] (range 100))) == Elapsed time: 147.096976 msecs The amount of time it takes to build the vector goes up significantly, but the timed part, calling 'rest' a million times, doesn't take anywhere near 100 times longer. --Chouser -- Venlig hilsen / Kind regards, Christian Vest Hansen. --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Re: Performance tips for Clojure
Christian Vest Hansen a écrit : I think that count is O(n) for lists, no? Count is O(1) for lists but O(n) for a chain of conses. Clojure user= (let [l (apply list (range 10))] (time (dotimes [_ 100] (count l Elapsed time: 169.710116 msecs nil user= (let [l (apply list (range 40))] (time (dotimes [_ 100] (count l Elapsed time: 167.664046 msecs nil user= (let [l (reduce #(cons %2 %1) nil (range 10))] (time (dotimes [_ 100] (count l Elapsed time: 662.121862 msecs nil user= (let [l (reduce #(cons %2 %1) nil (range 100))] (time (dotimes [_ 100] (count l Elapsed time: 5316.110567 msecs nil -- Professional: http://cgrand.net/ (fr) On Clojure: http://clj-me.blogspot.com/ (en) --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
