Re: Clojure Performance For Expensive Algorithms
I didn't know reduce could be short circuited! I assume from the code below this is done calling the function reduced? Is this in Clojure 1.5 only and is where is this documented? On Wednesday, February 27, 2013 4:59:33 AM UTC-5, Christophe Grand wrote: On Wed, Feb 27, 2013 at 10:21 AM, Marko Topolnik marko.t...@gmail.comjavascript: wrote: (defn blank? [s] (every? #(Character/isWhitespace %) s)) Have you ever wondered about its performance? Here you go: user (time (dotimes [_ 1] (blank? ))) Elapsed time: 3887.578 msecs To give a more complete picture, this version (defn blank? [s] (every? #(Character/isWhitespace ^char %) s)) is only six times slower than the expanded version, and keeping an eye on reflection warnings is not such a drag. So, if it could be demonstrated that in general the properly type-hinted, but otherwise idiomatic Clojure is not more than 10 times slower than idiomatic Java, I'd consider that at least a good starting point. Now that reduce can be short-circuited, redifining every?, some and al on top of it would yield some interesting gains: (defn revery? [pred coll] (reduce (fn [t x] (if (pred x) t (reduced false))) true coll)) (defn rblank? [s] (revery? #(Character/isWhitespace ^char %) s)) (defn blank? [s] (every? #(Character/isWhitespace ^char %) s)) = (dotimes [_ 10] (time (dotimes [_ 10] (blank? Elapsed time: 515.371 msecs Elapsed time: 500.408 msecs Elapsed time: 507.646 msecs Elapsed time: 644.074 msecs Elapsed time: 529.717 msecs Elapsed time: 482.813 msecs Elapsed time: 557.563 msecs Elapsed time: 486.573 msecs Elapsed time: 493.636 msecs Elapsed time: 481.357 msecs nil = (dotimes [_ 10] (time (dotimes [_ 10] (rblank? Elapsed time: 227.692 msecs Elapsed time: 99.937 msecs Elapsed time: 95.922 msecs Elapsed time: 91.193 msecs Elapsed time: 90.794 msecs Elapsed time: 94.765 msecs Elapsed time: 89.842 msecs Elapsed time: 120.551 msecs Elapsed time: 90.843 msecs Elapsed time: 93.523 msecs nil Christophe -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure Performance For Expensive Algorithms
This is pretty neat. Thanks! Yeah the swapping of prev and curr seems to be a stumbling block. On Sunday, February 24, 2013 6:08:39 PM UTC-5, Aria Haghighi wrote: I have a solution (gist here https://gist.github.com/aria42/5026109, key bits pasted below). It's pretty short (15 lines) and readable (I think) and only 50% slower than the Java version on my machine (averaging over 25 runs of your benchmark function). Generally, I've found it's really easy when you just translate Java code like this into Clojure, the Clojure will read worse than the original Java; to boot it will also be slower! And not to be insulting, but I think the other Clojure solutions I saw in this thread seem to have this property. You usually have to pull out some abstraction in order to regain on the readability and concentrate on performance there. Here, I think it's a macro you'll probably use all over the place, arr-max, which will find the largest value of an expression looping over an array's index and values. Then lcs is just nested uses of arr-max that I think is pretty reasonable. The thing which clutters the remaining code are the prev/cur swapping which I don't have a slick way of handling. (defmacro arr-max return maximum value of `expr` over the indices and values of array `arr`, where `idx-symb` and `val-symb` are bound to index and values of `arr` [arr idx-symb val-symb expr] `(let [arr# ~arr n# (alength arr#)] (loop [~idx-symb 0 max-val# java.lang.Long/MIN_VALUE] (if (= ~idx-symb n#) max-val# (let [~val-symb (aget arr# ~idx-symb) val# ~expr] (recur (inc ~idx-symb) (if ( val# max-val#) val# max-val#))) (defn lcs [^objects a1 ^objects a2] (let [prev-ref (atom (long-array (inc (alength a2 cur-ref (atom (long-array (inc (alength a2] (arr-max a1 i v1 (let [^longs prev @prev-ref ^longs cur @cur-ref max-len (arr-max a2 j v2 (let [match-len (if (.equals v1 v2) (inc (aget prev j)) 0)] (aset cur (inc j) match-len) match-len))] (reset! prev-ref cur) (reset! cur-ref prev) (long max-len) On Sunday, February 24, 2013 12:45:18 PM UTC-8, Marko Topolnik wrote: On Sunday, February 24, 2013 9:15:45 PM UTC+1, puzzler wrote: As I mentioned before, I'm generally happy with Clojure's performance, but the few times I've had performance problems, I ended up rewriting the code at least three different ways in order to try to find the magic combination that would boost performance. Lately I've leaned towards going full monty the first time out: stop guessing and optimize everything past the entry point to the critical section. It sounds like more work up front, but in the end it's the smart approach that results in more total effort. Fortunately, dropping down to Java is relatively painless. But I still wonder whether there might be some benefit to having a low-level DSL within Clojure, a mode that lets you choose to write your code in a way where the semantics are closer to the underlying platform. Just one feature would make a huge difference: reassignable locals. I haven't used Clojurescript much, but I get the impression that Clojurescript is already a step in that direction, with a simpler story regarding how mutation, arrays, and primitives are translated to the underlying platform, arguably making it easier to get good performance when you need it. The gap between Clojure and JavaScript is far less than Java because both are dynamic. I think that plays a big part in why ClojureScript can be more transparent. -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure Performance For Expensive Algorithms
Well I'll just say that my opinion on this matter is not well formed at the moment since this is the first time I have encountered this issue. For now I've stuck with the Java algorithm so I can move on with my project, but I do plan to revisit this at some point. In fact, it may be important for my project to keep it all Clojure. At the moment I don't find the Clojure solution simple, but again this may simply be to lack of exposure. Have you written a lot of performance optimized Clojure? On Sunday, February 24, 2013 8:50:01 AM UTC-5, bernardH wrote: On Thursday, February 21, 2013 10:27:11 PM UTC+1, Geo wrote: Man, this is exactly how I feel after all this tinkering! It was great for learning Clojure a bit more in depth, but in the end I am going to stick with the Java solution. Especially since it's so easy to mix Java and Clojure in the same project! I just specify :java-source-paths [src/java] in my project.clj and I just call that one method when I need it and the rest of the project is in Clojure. I think when performance if critical idiomatic Clojure is to just drop down to Java :) Christophe's second function actually achieves Java speed or very close (within 5-10%), but it's ugly and there's a bit more to my algorithm which would make it even uglier if I were to go that route. There would be no point in me to argue with you whether Chrispohe's version really is ugly or not for you, but I'd like to rephrase it as hard on the eye. Because I find this performance oriented Clojure vs Java fits quiet well in the easy vs simple mindeset.[*]. Adding Java code in a Clojure project is certainly easy if you happen to already know the language, while no amount of prior experience in idiomatic Clojure will help you in writing perfomance oriented Clojure as it can be a completely new idiom. But I do believe that the resulting code (as a whole, not just the small performance critical bit of code) is simpler with two idioms in one language than with two languages. FWIW, I, for one, am really glad that Clojure allows us to select precisely which nice tools we want (have to) throw away (persistent data structures, dynamic typing, synchronized) when the need arises. Reminds me of the don't pay for what you don't use motto of C++ except done right (i.e. the other way around, because you don't want to pay wrt simplicity rather than performance, cf. premature optimization…) Cheers, Bernard [*] https://www.youtube.com/watch?v=rI8tNMsozo0 -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure Performance For Expensive Algorithms
Just wanted to say I am getting a lot out of this discussion. -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure Performance For Expensive Algorithms
It is in fact the longest common substring problem, but applied to words in a text rather than characters in a string, hence the algorithm operates on arrays of strings. I am aware of the O(M+N) algorithm, but it involves suffix trees with which I am unfamiliar and don't want to spend the time investigating right now. The DP solution works today and I want to focus on other parts of the project :) Also the size of the alphabet in this case is the set of all words in a particular language, most commonly English. I am not sure what the implications of that are for the performance of the suffix tree algo. On Saturday, February 23, 2013 7:54:01 PM UTC-5, Leif wrote: This may be slightly off topic, but your longest contiguous common subsequence problem sounds like the longest common substring problem. Your code uses the dynamic programming solution, which is O(M*N), but there are O(M+N) algorithms that might be faster depending on the length and alphabet of your input sequences. On Monday, February 18, 2013 11:16:51 PM UTC-5, Geo wrote: Hello, I am cross-posting my Clojure question from StackOverflow. I am trying to get an algorithm in Clojure to match Java speed and managed to get the performance to within one order of magnitude and wondering if more is possible. The full question is here: http://stackoverflow.com/questions/14949705/clojure-performance-for-expensive-algorithms Thank you. On Monday, February 18, 2013 11:16:51 PM UTC-5, Geo wrote: Hello, I am cross-posting my Clojure question from StackOverflow. I am trying to get an algorithm in Clojure to match Java speed and managed to get the performance to within one order of magnitude and wondering if more is possible. The full question is here: http://stackoverflow.com/questions/14949705/clojure-performance-for-expensive-algorithms Thank you. -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure Performance For Expensive Algorithms
Man, this is exactly how I feel after all this tinkering! It was great for learning Clojure a bit more in depth, but in the end I am going to stick with the Java solution. Especially since it's so easy to mix Java and Clojure in the same project! I just specify :java-source-paths [src/java] in my project.clj and I just call that one method when I need it and the rest of the project is in Clojure. I think when performance if critical idiomatic Clojure is to just drop down to Java :) Christophe's second function actually achieves Java speed or very close (within 5-10%), but it's ugly and there's a bit more to my algorithm which would make it even uglier if I were to go that route. On Thursday, February 21, 2013 4:55:13 AM UTC-5, Marko Topolnik wrote: Whatever the final performance achieved, the fact remains that the original Java code was much cleaner, simpler, and more comprehensible than the big ball of mud the performant Clojure version is turning into. I have my own piece of performance-critical code that I used to maintain and improve over a timespan of many months. I finally gave in and recoded the thing in Java. It took only a couple of hours and the result was nice, clean, idiomatic Java code, with completely predictable performance characteristics, as opposed to the Clojure version where it took many hours of staring at ridiculuously counterintuitive stacktraces in VisualVM to find what to optimize and how. The amount of code is about the same at either end. On Thursday, February 21, 2013 10:41:55 AM UTC+1, Christophe Grand wrote: I updated my answer on SO, with a deftype-based one that gives me an additional 30% boost. On Tue, Feb 19, 2013 at 6:38 PM, Geo ggrig...@gmail.com wrote: What about the call to .equals? On Tuesday, February 19, 2013 12:20:28 PM UTC-5, Marko Topolnik wrote: The difference between String[] and Object[] is that a member of the former doesn't need a checked cast to String, but the latter does need one. In the code under consideration, however, nothing specific to String is used, so even in the Java code you can freely replace String[] with Object[] and everything still works. If, on the other hand, you needed to invoke say *substring*, you'd see a small penalty due to the checked cast operation. On Tuesday, February 19, 2013 5:52:31 PM UTC+1, Andy Fingerhut wrote: ^objects is a Clojure synonym for ^[Ljava.lang.Object;. Note that there are such synonyms for only a few Java types, not everything, e.g. there is no ^strings. What you are hinting is that a1 and a2 are Java arrays of objects. I think this might speed up (aget a1 i) expressions, since it is known that a1 is an array of objects, but I'm not sure about that. I believe under the hood in the JVM all arrays of Objects are treated the same, regardless of whether those Objects are String, Integer, java.awt.Color, etc. Andy On Feb 19, 2013, at 8:46 AM, Geo wrote: One thing I don't get is that switching the type hints from [#^[Ljava.lang.String; a1 #^[Ljava.lang.String; a2] to [^objects a1 ^objects a2] didn't seem to have any negative impact on performance. Can anyone explain why hinting ^objects is just as good as specifying that it's an array of Strings? What are you hinting with ^objects that Clojure doesn't already know? -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clo...@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+u...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- On Clojure http://clj-me.cgrand.net/ Clojure Programming http://clojurebook.com Training, Consulting Contracting http://lambdanext.eu/ -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure Performance For Expensive Algorithms
Thanks. The unchecked math didn't make any difference. But after I switching to aset I did indeed get to within 4x of Java. Then at the suggestion of Christophe Grand on StackOverflow I switched to .equals instead of = and that got me to ~133% of Java performance. Very close! On Tuesday, February 19, 2013 2:16:28 AM UTC-5, Andy Fingerhut wrote: This won't get you all of the way to Java speeds, or at least it didn't for me, but try these things: Use: (set! *warn-on-reflection* true) (set! *unchecked-math* true) The first won't speed anything up, but it will warn you about some things that are slow. The second will use unchecked match wherever it can, meaning primitive operations on arithmetic values like longs, that will silently wrap instead of checking for overflow. Java doesn't check for overflow in primitive operations, either. Also use aset instead of aset-int. I don't know why, but the aset-* operations are typically slower than aset, as long as the type hints on the aset arguments are good enough. I got within 4x Java speed with those changes. Andy On Feb 18, 2013, at 8:16 PM, Geo wrote: Hello, I am cross-posting my Clojure question from StackOverflow. I am trying to get an algorithm in Clojure to match Java speed and managed to get the performance to within one order of magnitude and wondering if more is possible. The full question is here: http://stackoverflow.com/questions/14949705/clojure-performance-for-expensive-algorithms Thank you. -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure Performance For Expensive Algorithms
Using long-array instead of int-array seems to produce a very slight but noticeable improvement. (~2.1 sec - ~1.8 sec) = 1.16x improvement One other thing is that loop seems to return boxed primitives, so by wrapping the inner loop with (long ) I got another slight performance gain. (~2.5 sec - ~2.0 sec) = ~1.25x improvement On Tuesday, February 19, 2013 4:16:24 AM UTC-5, puzzler wrote: Another idea: try using arrays of longs, rather than ints, since that is what Clojure prefers. -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure Performance For Expensive Algorithms
One thing I don't get is that switching the type hints from [#^[Ljava.lang.String; a1 #^[Ljava.lang.String; a2] to [^objects a1 ^objects a2] didn't seem to have any negative impact on performance. Can anyone explain why hinting ^objects is just as good as specifying that it's an array of Strings? What are you hinting with ^objects that Clojure doesn't already know? -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure Performance For Expensive Algorithms
Note that I'm not very confident that using long-array instead of int-array is a true improvement vs. just noise. On Tuesday, February 19, 2013 11:46:21 AM UTC-5, Geo wrote: Using long-array instead of int-array seems to produce a very slight but noticeable improvement. (~2.1 sec - ~1.8 sec) = 1.16x improvement One other thing is that loop seems to return boxed primitives, so by wrapping the inner loop with (long ) I got another slight performance gain. (~2.5 sec - ~2.0 sec) = ~1.25x improvement On Tuesday, February 19, 2013 4:16:24 AM UTC-5, puzzler wrote: Another idea: try using arrays of longs, rather than ints, since that is what Clojure prefers. -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure Performance For Expensive Algorithms
What about the call to .equals? On Tuesday, February 19, 2013 12:20:28 PM UTC-5, Marko Topolnik wrote: The difference between String[] and Object[] is that a member of the former doesn't need a checked cast to String, but the latter does need one. In the code under consideration, however, nothing specific to String is used, so even in the Java code you can freely replace String[] with Object[] and everything still works. If, on the other hand, you needed to invoke say *substring*, you'd see a small penalty due to the checked cast operation. On Tuesday, February 19, 2013 5:52:31 PM UTC+1, Andy Fingerhut wrote: ^objects is a Clojure synonym for ^[Ljava.lang.Object;. Note that there are such synonyms for only a few Java types, not everything, e.g. there is no ^strings. What you are hinting is that a1 and a2 are Java arrays of objects. I think this might speed up (aget a1 i) expressions, since it is known that a1 is an array of objects, but I'm not sure about that. I believe under the hood in the JVM all arrays of Objects are treated the same, regardless of whether those Objects are String, Integer, java.awt.Color, etc. Andy On Feb 19, 2013, at 8:46 AM, Geo wrote: One thing I don't get is that switching the type hints from [#^[Ljava.lang.String; a1 #^[Ljava.lang.String; a2] to [^objects a1 ^objects a2] didn't seem to have any negative impact on performance. Can anyone explain why hinting ^objects is just as good as specifying that it's an array of Strings? What are you hinting with ^objects that Clojure doesn't already know? -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure Performance For Expensive Algorithms
Cool. Thanks for the explanation. On Tuesday, February 19, 2013 12:47:05 PM UTC-5, Marko Topolnik wrote: Naturally, it's Object#equals. String's override of equals gets involved without the checked downcast. On Tuesday, February 19, 2013 6:38:07 PM UTC+1, Geo wrote: What about the call to .equals? On Tuesday, February 19, 2013 12:20:28 PM UTC-5, Marko Topolnik wrote: The difference between String[] and Object[] is that a member of the former doesn't need a checked cast to String, but the latter does need one. In the code under consideration, however, nothing specific to String is used, so even in the Java code you can freely replace String[] with Object[] and everything still works. If, on the other hand, you needed to invoke say *substring*, you'd see a small penalty due to the checked cast operation. -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Clojure Performance For Expensive Algorithms
Hello, I am cross-posting my Clojure question from StackOverflow. I am trying to get an algorithm in Clojure to match Java speed and managed to get the performance to within one order of magnitude and wondering if more is possible. The full question is here: http://stackoverflow.com/questions/14949705/clojure-performance-for-expensive-algorithms Thank you. -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Clojure count and get functions much faster on strings than direct interop with .length and .charAt
I am writing an expensive algorithms in Clojure and while trying to optimize the code I discovered something that puzzled me. Clojure count and get functions are much faster on strings than direct interop with .length and .charAt. On my machine I get the following: (def sss (apply str (repeat 1000 \a))) I execute each of the following tests a few times: (time (dotimes [_ 1000] (count sss))) Elapsed time: 0.56 msecs Elapsed time: 0.539 msecs Elapsed time: 0.551 msecs Elapsed time: 0.453 msecs Elapsed time: 0.612 msecs (time (dotimes [_ 1000] (.length sss))) Elapsed time: 170.819 msecs Elapsed time: 114.892 msecs Elapsed time: 10.111 msecs Elapsed time: 32.106 msecs Elapsed time: 10.803 msecs Even after something under the hood warms up (feel free to enlighten me :). .length is still significantly slower. (time (dotimes [_ 1000] (get sss (rand-int 1000 Elapsed time: 4.651 msecs Elapsed time: 3.699 msecs Elapsed time: 3.672 msecs Elapsed time: 4.561 msecs Elapsed time: 3.742 msecs (time (dotimes [_ 1000] (.charAt sss (rand-int 1000 Elapsed time: 13.211 msecs Elapsed time: 14.874 msecs Elapsed time: 32.044 msecs Elapsed time: 13.849 msecs Elapsed time: 39.493 msecs .charAt is also significantly slower than get. By replacing .length with count and .charAt with get I was able to reduce the running time of my algo by orders of magnitude. These results are surprising and puzzling. You'd think direct interop with Java would be the faster. Can anyone venture a guess or explain what's going on here? -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure count and get functions much faster on strings than direct interop with .length and .charAt
Thank you! Adding type hints solves the problem. The interop now slightly outperforms Clojure's get and count. So how come Clojure's get and count don't incur the reflection penalty? On Sunday, February 17, 2013 9:17:55 AM UTC-5, Geo wrote: I am writing an expensive algorithms in Clojure and while trying to optimize the code I discovered something that puzzled me. Clojure count and get functions are much faster on strings than direct interop with .length and .charAt. On my machine I get the following: (def sss (apply str (repeat 1000 \a))) I execute each of the following tests a few times: (time (dotimes [_ 1000] (count sss))) Elapsed time: 0.56 msecs Elapsed time: 0.539 msecs Elapsed time: 0.551 msecs Elapsed time: 0.453 msecs Elapsed time: 0.612 msecs (time (dotimes [_ 1000] (.length sss))) Elapsed time: 170.819 msecs Elapsed time: 114.892 msecs Elapsed time: 10.111 msecs Elapsed time: 32.106 msecs Elapsed time: 10.803 msecs Even after something under the hood warms up (feel free to enlighten me :). .length is still significantly slower. (time (dotimes [_ 1000] (get sss (rand-int 1000 Elapsed time: 4.651 msecs Elapsed time: 3.699 msecs Elapsed time: 3.672 msecs Elapsed time: 4.561 msecs Elapsed time: 3.742 msecs (time (dotimes [_ 1000] (.charAt sss (rand-int 1000 Elapsed time: 13.211 msecs Elapsed time: 14.874 msecs Elapsed time: 32.044 msecs Elapsed time: 13.849 msecs Elapsed time: 39.493 msecs .charAt is also significantly slower than get. By replacing .length with count and .charAt with get I was able to reduce the running time of my algo by orders of magnitude. These results are surprising and puzzling. You'd think direct interop with Java would be the faster. Can anyone venture a guess or explain what's going on here? -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Clojure count and get functions much faster on strings than direct interop with .length and .charAt
Clojure is full of pleasant surprises :) -- -- 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 --- You received this message because you are subscribed to the Google Groups Clojure group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: Lazy sequences to replace looping?
Thanks. I investigated it, which led to another related question as to whether lazy seqs are always chunked (it appears not!). I posted this on stack overflow here: http://stackoverflow.com/questions/12412038/in-clojure-are-lazy-seqs-always-chunked -- 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
Lazy sequences to replace looping?
Hello, I am just getting started with Clojure and I had a question. I have to following code: (get-rss-entry (get-rss-feeds h-res) url) The call to get-rss-feeds returns a lazy sequence of URLs of feeds that I need to examine. The call to get-rss-entry looks for a particular entry (whose :link field matches the second argument of get-rss-entry). It examines, one-by-one, the lazy sequence returned by get-rss-feeds. Evaluate each item requires an http request across the network to fetch a new rss feed. Therefore, to minimize the number of http requests it's important to examine the sequence one-by-one and stop as soon as there is a match. Here is the code: (defn get-rss-entry [feeds url] (first (drop-while empty? (map #(entry-with-url % url) feeds entry-with-url returns a lazy sequence of matches or an empty sequence if there is no match. First, I want to make sure I understood lazy evaluation correctly and that I did this right. I tested this and it seems to work correctly. Second, not sure if I am solving this problem idiomatically. In Java, for example, this would likely be solved with a loop examining some data structure. At first I did it with a loop/recur but that didn't seem like the right way to do it. Also I saw somewhere that looping in considered low level in Clojure or something to that effect. I would appreciate your feedback. Thanks for your help. -- 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
