Hi Amith, Very glad you're seeing the performance increase there too! I think you're right about both the extraneous type hints and the unchecked-math. I tend to turn on unchecked-math in a leiningen profile that I use while developing, but leave it set to default for normal builds. Because of that, I'm in the habit of using unchecked-inc. For the extra type hints there, I think I had originally used the :member syntax and changed it to the .member syntax but had left the type hints in. It would have been better to just use .member and leave the type hints out as you noted.
For some/sequences vs. loop-recur/arrays, I haven't done a deep enough analysis and don't want to say something incorrect. Here's some notes in looking at it just now: - get - using get [1] calls to RT[2], which in turns does some instanceof checks to then call the specific type's function for getting a value. With PersistentVector[3], that should translate to the ILookup.valAt() call, which in turn calls nth. Compared to the inlined aget[4][5] call, it's a lot more layers of functions. - some[6] - this ends up calling first and next[7], which ends up calling first and next in PersistentVector[8], which ends up allocating a new ChunkedSeq. Granted, object allocation on the JVM is super cheap (pointer bump) compared to allocating memory with something like malloc in C, there's still a cost there + the setting of fields in the constructor. It's all very cheap operations on their own but I'm guessing that in this context of a critical loop, plus the logic to check for boundaries in the first/next calls, are adding up compared to just indexing into the full array. - some vs. loop-recur/rest - In this case, I'm not sure. It might be due to how you coded the loop with the call to empty? (assuming the commented out code in your example is what you used). I guess then all of this becomes a series of tradeoffs and trying to find the right balance. IMO, sequences offer so many benefits over arrays. It's really only in certain critical sections of code where the performance costs might outweigh programmer benefits. I guess even then, the amortized cost of the sequence compared to array goes down if the the operations on the individual items becomes more expensive. In this case it happened to be that the cost of the operation on the set of values was pretty small compared to the cost of calling first/next. Maybe in other scenarios the use of an array won't give the same benefit. Well, hopefully if I missed something in the analysis above someone here will correct me. :) Cheers! steven [1] - https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L1421-L1429 [2] - https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L719-L744 [3] - https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentVector.java#L657-L671 [4] - https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L2321-L2323 [5] - https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L2321-L2323 [6] - https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L2321-L2323 [7] - https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L651-L679 [8] - https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L651-L679 On Wed, May 20, 2015 at 9:37 AM, Amith George <strider...@gmail.com> wrote: > Oh, a few more things I observed; > > - I figured out how to use *unchecked-math* and *warn-on-reflection* :) > > Earlier, I was setting them within a binding, but that didn't seem to do > anything. Seems the correct way is to set them at the very top of the file, > the first 2 lines after the namespace declaration. > > https://github.com/amithgeorge/reddit-dailyprogrammer-clojure/blob/0f49b7979f9c2e0e7a522f5ad875de0807d4e2da/src/rdp/214_intermediate_arr.clj#L4-L5 > > - With the warnings now being generated properly, I was able to figure > out where the type hints needed to be added. For example, > > (defn- covered? > [^long canvas-x ^long canvas-y ^Paper paper] > (and (<= ^long (.x1 paper) canvas-x ) (<= canvas-x ^long (.x2 paper)) > (<= ^long (.y1 paper) canvas-y ) (<= canvas-y ^long (.y2 paper)))) > > > The `^long` type hint is not needed within the `<=` forms. As paper is > typed to `Paper` and the various `x1, x2 etc` fields are of type long in the > Paper definition. > > - Also, > > (recur (unchecked-inc i)) > > > can be > > (recur (inc i)) > > > because `*unchecked-math*` is set to a truthy value. > > Please correct me if I misunderstood anything :) > > > On Tuesday, 19 May 2015 23:02:11 UTC+5:30, Steven Yi wrote: >> >> Hi Amith, >> >> One last optimization yields a 4x increase over the last version, and >> now 12x over the original: >> >> "Elapsed time: 22848.384642 msecs" >> >> Code here: >> >> https://gist.github.com/kunstmusik/db6e14118e818abf3bb8 >> >> Changes from last version: >> >> - parse-inputs - Put parsed Paper objects into an array instead of a >> vector. >> - visible-color iterates through the array of Paper objects using a >> loop-recur >> >> I spent a moment looking at this using JVisualVM and saw from the >> previous version that there was a lot of time spent in sequence >> related stuff and in the some function. I realized from using some it >> was going through the vector items pretty often, and since that list >> of items is static, are read-only within the context of the code, and >> the values aren't shared around a codebase, I went ahead and optimized >> it to use a fixed array. >> >> Hope this runs well on your side too! >> steven >> >> >> On Tue, May 19, 2015 at 12:49 PM, Steven Yi <stev...@gmail.com> wrote: >> > Hi Amith, >> > >> > Just got back from a trip and had a chance to look at this again. I'm >> > not sure why you didn't see a change there; I'm running the same >> > version of Clojure and Java here. >> > >> > I did another change to move from using a reduce to nested >> > loop-recurs. That with a some additional type hints for ^Paper, and >> > moving the retrieval of :height and :width outside of the loops got a >> > performance increase of almost 3x from the original: >> > >> > "Elapsed time: 109335.307414 msecs" >> > >> > The modified code is here: >> > >> > https://gist.github.com/kunstmusik/e1081d417142a90d5cfa >> > >> > Some general notes: >> > >> > - covered? - type-hinted ^Paper >> > - visible-color - switched to pass in ^long x and y, used fn form for >> > passed-in function and type-hinted ^Paper argument >> > - visible-color-frequencies - switched to nested loop-recur, moved out >> > height and width to single call outside critical loop >> > >> > Could you try the version from the gist there to see if you get a >> > similar speedup? >> > >> > Cheers! >> > steven >> > >> > On Tue, May 19, 2015 at 4:38 AM, Amith George <strid...@gmail.com> >> > wrote: >> >> Hi, >> >> >> >> Thanks for taking the time to profile the code. I implemented the two >> >> suggestions (using the two argument arity of lte and using aset instead >> >> of >> >> aset-long). >> >> >> >> >> >> https://github.com/amithgeorge/reddit-dailyprogrammer-clojure/blob/2655a83f7fcf51e4fedae164d7d17386a0c8854f/src/rdp/214_intermediate_arr.clj >> >> >> >> lein run -m rdp.214-intermediate-arr 1 true >> >> ;; took around 250s. >> >> >> >> The changes didn't seem to make a difference. The before and after runs >> >> all >> >> take between 250 - 260s. I kept the reduce as-is. From your reply, it >> >> looks >> >> like these two changes reduced the execution time by almost 30s. Any >> >> thoughts of why there isn't much of a difference for me? - I am using >> >> Clojure 1.7.3-beta3 and Oracle Java 1.8.0_45 on OSX Mavericks. >> >> >> >> On Saturday, 16 May 2015 08:32:12 UTC+5:30, Steven Yi wrote: >> >>> >> >>> Ah, I see. Well, I think then you can ignore the stuff about warming >> >>> up, as this certainly takes a while to run here: >> >>> >> >>> "Elapsed time: 314763.666693 msecs" >> >>> >> >>> I tried profiling with Yourkit and saw a couple of things to change: >> >>> >> >>> ;; I think lte with more than two args ends up being slower than >> >>> unrolling out here >> >>> ;; I also tried type-hinting values from paper to ^long to avoid lte >> >>> calls with Number >> >>> (defn- covered? >> >>> [[^long canvas-x ^long canvas-y] paper] >> >>> (and (<= ^long (:x1 paper) canvas-x ) (<= canvas-x ^long (:x2 >> >>> paper)) >> >>> (<= ^long (:y1 paper) canvas-y ) (<= canvas-y ^long (:y2 >> >>> paper)))) >> >>> >> >>> ;; for the reduce function in visible-color-frequencies-arr >> >>> ;; using aset instead of aset-long, as it looked like aset-long was >> >>> using reflection >> >>> (aset colorCounts color (+ 1 (aget colorCounts color))) >> >>> >> >>> That got it down to: >> >>> >> >>> "Elapsed time: 279864.041477 msecs" >> >>> >> >>> I suspect you might get improvement too if you change >> >>> visible-color-frequencies-arr to use loop-recur instead of reduce >> >>> since you're doing a bit of magic there. >> >>> >> >>> Unfortunately I have to stop at the moment as I have to leave on a >> >>> trip early in the morning, but hopefully that's useful. >> >>> >> >>> steven >> >>> >> >> -- >> >> 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 a topic in the >> >> Google Groups "Clojure" group. >> >> To unsubscribe from this topic, visit >> >> https://groups.google.com/d/topic/clojure/JgxFQLP2E34/unsubscribe. >> >> To unsubscribe from this group and all its topics, send an email to >> >> clojure+u...@googlegroups.com. >> >> For more options, visit https://groups.google.com/d/optout. > > -- > 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 a topic in the > Google Groups "Clojure" group. > To unsubscribe from this topic, visit > https://groups.google.com/d/topic/clojure/JgxFQLP2E34/unsubscribe. > To unsubscribe from this group and all its topics, send an email to > clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. -- 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/d/optout.
