Berlin: I've got a start at programs for solving two of the problems solved in many other languages on "The Computer Language Benchmarks Game" web site:
http://shootout.alioth.debian.org In particular, the k-nucleotide problem has as a significant part of its computation time a similar task to what you have done -- tallying the number of times each unique item appears in a collection, using a map (which most programs on the web site implement with a mutable hash table, not a persistent map like in Clojure). I also have adapted some solutions for calculating complex numbers in the Mandelbrot set from a discussion in this group from several months back, and addded a bit of code so the input/output match what is expected for the Mandelbrot benchmark. I don't have Clojure implementations for the other problems on the web site, yet (I'd be happy to add them to my collection if you'd like to send them to me). Here are some comparisons of run times on my iMac with 2.2 GHz Intel Core 2 Duo, 2 GB RAM. I make no claims that these are the best Clojure implementations that could be made, but I have done several versions that were slower and/or didn't finish due to running out of memory, before getting to the Clojure versions I have now. This is intended to be viewed in a fixed width font. You can also look at the RESULTS file in the zip/tar.gz files linked below, where you can get the full programs and test inputs I used. Times are real / user / sys on my iMac. real means elapsed time from start to finish, which can be less than (user+sys) in the cases where the program explicitly uses both processor cores. | sbcl | perl | ghc | java | clj ----------------------------------------------------- mand- | wrong | out of | 32.7 | 28.6 | 340.4 elbrot | output | mem | 59.3 | 54.4 | 350.5 | | (?) | 0.8 | 0.4 | 4.7 k-nuc- | 190.9 | 306.0 | 90.5 | 52.4 | 1677.6 (27m 57.6s) leotide | 187.9 | 302.7 | 130.8 | 89.6 | 2245.1 (37m 25.1s) | 2.4 | 1.9 | 4.6 | 1.8 | 24.2 ( 24.2s) For these two programs at least, the Clojure implementations have a total CPU time (the sum of the 2nd and 3rd numbers reported above) of 6.5 times more for Clojure vs. Java on the mandelbrot program, and 25 times more for Clojure vs. Java on the k-nucleotide program. Here are links to zip and .tar.gz files containing the programs and input files used to produce these results. They've been tested in Mac OS X, but I suspect they ought to work on Linux with little or no modification. Windows users would need to do a little more to run the programs, but it shouldn't be difficult. Sorry, they are each about 75 Mbytes, primarily because a few of the sample input and expected output files are quite large. http://homepage.mac.com/jafingerhut/files/language-shootout.tar.gz http://homepage.mac.com/jafingerhut/files/language-shootout.zip For the k-nucleotide program, I think this may be a fundamental issue with persistent implementations of maps / hash tables, but I'd be happy to find a better implementation of them, if that would help similar Clojure programs to speed up. I haven't read Chris Okasaki's book on functional data structures yet, but I suspect a good understanding of its contents might lead to some improvements. I've read that Okasaki's book doesn't spell out an implementation for hash tables, but leaves it as an exercise for the reader, so don't rush off and buy the book expecting to have a quick job of translating some pseudo-ML into Java. I thought it was interesting that even the Haskell entry to the k- nucleotide benchmark uses a *mutable* hash table (at least, I think they are from the discussion on the Wiki page linked below -- my Haskell knowledge isn't extensive enough to understand all of their code). I don't think that is idiomatic Haskell, but the people writing the Haskell entry are apparently willing to forego pure functional programming when they can get significantly better performance from a mutable data structure. http://www.haskell.org/haskellwiki/Shootout/Knucleotide In terms of what instructions the processor is running every time a mutable hash table is updated, it is roughly "calculate the hash function, look up the corresponding entry in the hash table, compare the keys for exactness and perhaps traverse more entries looking for the exact match, then add 1 to the count when you find the matching entry". Clojure's persistent hash map is calculating the hash function, then I believe the basic idea is looking that hash value up in a tree of nodes, each of which is a Java array of 32 elements. When it finds the matching entry in that tree, doing the "assoc" to "modify" the count of an entry involves copying that array of 32 elements, with one element in the copy different than the original, and then going back up the tree to the root, creating new copies of arrays of 32 elements, each with one element different than the original, pointing at the new copied child. I'm sure there are special cases for small maps, but I think that is the behavior for sufficiently large hash maps. If so, then it is pretty easy to see that the processor is doing significantly more work for each map update, i.e. assoc call, than any implementation that uses mutable hash tables. Of course, Clojure makes it easy to call Java code implementing mutable hash tables, if performance is all-important for such a task, and you realize the issues with having a mutable data structure vs. Clojure's persistent data structures. Andy On Jul 27, 10:06 am, BerlinBrown <berlin.br...@gmail.com> wrote: > I was coming up with some performance tests for Clojure, going back > and forth between different JVM languages (JRuby, Scala) and mainly > looking at pure Java code. So far I have found that clojure is about > 5-10 times as slow as comparable code in Clojure. Of course this is > before any optimizations. > > Here is my question, do you have any code both Clojure and Java where > there is a one to one match between code where Clojure runs as fast as > Java. It could be anything. > > Here is one example: > This is code from clojure/contrib to convert a list of data into a > frequency count map. Pretty standard stuff. > > (defn frequencies > "Returns a map from distinct items in coll to the number of times > they appear." > [coll] > ;;;;;;;;; > (reduce (fn [counts x] > (assoc counts x (inc (get counts x 0)))) > {} coll)) > > (dotimes [x 4] > (println "i: " (int (Math/pow 10.0 x))) > (time > (dotimes [_ (int (Math/pow 10.0 x))] > (let [a (for [_ (range 1000)] (random-string 3))] > (frequencies a))))) > > ---------------------- > > public static Map frequencies(final List list) { > final Map map = new HashMap(); > // Simple Box and then unbox the count as the value for this > map // > for (Iterator it = list.iterator(); it.hasNext(); ) { > final Object o = it.next(); > final String s = o.toString(); > Integer prev = (Integer) map.get(s); > if (prev == null) { > // Put a new value on th map > final Integer count = ONE; > map.put(s, count); > } else { > final Integer inc = new Integer(prev.intValue() + 1); > map.put(s, inc); > } // End of the if - else // > } > return map; > } > ---------------------- > > Clojure Results (same machine 1.5 JDK) > > i: 1 > "Elapsed time: 51.657859 msecs" > i: 10 > "Elapsed time: 212.568221 msecs" > i: 100 > "Elapsed time: 1623.107702 msecs" > i: 1000 > "Elapsed time: 16356.185166 msecs" > (used:2M/0M [2M,63M ]) > Done > Performing simple garbage collection cooldown > (used:2M/0M [2M,63M ]) > (used:2M/0M [2M,63M ]) > > ------------- > > Here are the Java results. > > 14.631606999999999 ms > 4.828342999999999 ms > i: 10 > Elapsed time: 9.803628 msecs > i: 100 > Elapsed time: 97.562451 msecs > i: 1000 > Elapsed time: 972.775771 msecs > (used:1M/0M [1M,63M ]) > (used:1M/0M [1M,63M ]) > (used:1M/0M [1M,63M ]) > > NOTE:!!! This is just one example. All my other examples, ended up > the same way. I hope you don't nitpick this one. > > I know we should take performance tests with a grain a salt. But at > the same time, I feel we should at least try to measure the speed of > some of our code. I haven't found many speed tests out there on > clojure. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
