Several times on this blog, I’ve dealt with issues where some kind of benchmarking was required. The method, implementation, environment all play a role and has subsequently been the object of much discussion. In this post let’s see if we can agree on some way of benchmarking.

Benchmarking is 4D

In my oppinion there are 4 dimensions to benchmarking which we need to deal with separately. In industry benchmarking can be crual to architecting your solution correctly and/or dealing with performance issues. Industry benchmarking needs to come as close to the real scenario as possible. If you’re working on a massive scale, benchmarking on a laptop is a no go, if your setup is heavy on I/O you need to clone your production environment in order to produce reliable results, etc etc.

The second type of benchmarking is what is typical for bloggers and I’m no exception: Microbenchmarking. Microbenchmarking is where we take certain routines out and benchmark them individually, my recent Fibonnaci posts are examples of this. Like the commentators pointed out, there needs to be an emphasis on equality where possible. A Ruby solution won’t look like a Clojure solution, but differences like returning or printing the result should be eliminated and defining the specific area to benchmark is very important: Are we timing the function or the inner-loop?

This second form of benchmarking is in divided into 2 distinct categories as well (bringing us up to the 4D benchmarking), because we have many languages which put the JVM to good effect with all the added benefits, but there are also languages that dont. Benchmarking on the JVM requires a good knowledge of both the JVM and HotSpot, whereas benchmarking outside of the JVM requires a good knowledge of whichever compiler you are working with. In that regard I couldn’t do Haskell any favors, for not having a clue about how the compiled code runs, start up times etc?

JVM Benchmarking

Being able to benchmark on the JVM is important and requires some background. I recommend reading this post in particular.

The unix time function is ruled out for the obvious reasons that 1) We dont want to be affected by the startup time of the JVM and 2) We dont need it. Especially when we’re looking at single algorithm/loop etc, what we really want to know is how well that given body of code performs. Its interaction with the rest of our system can be disregarded for the sake of comparison and since we’re often dealing with very small numbers, subtle differences quickly become not so subtle. Before we can get into the actual benchmarking we need to boot the JVM.

What we dont care about

For the sake of blogging/microbenchmarking we’re typically not doing any major optimizations, because usually idioms are being compared. There are exceptions, but we can deal with them once we get there. The JVM is a fantastic eco-system which allows for rigorious introspection — all of which we can disgard for our simple exercises.

Things we can disregard:

JVM Parameters:

–XX:+PrintCompilation — This gives us a heads-up whenever a method is compiled.

–verbose:GC — Lets us keep tabs on when the GC is running

–XX:-PrintGC — Print messages at GC

–XX:-PrintGCDetails — More verbose GC messages

–XX:-TraceClassLoading — Trace the loading of classes

–agentlib:hprof[=options] — Heap/CPU — read this: options

All of these (and dim sum) can be very helpful in tracing performance bottlenecks, but for microbenchmarking they seem overkill. Depending on how much allocation we’re doing we might trigger some heavy GC, but in that case we should account be stripping high/low values from our timings.

The things we cannot disregard:

JVM Paramters:

–Xms128M — The minimum amount of memory the JVM allocation

–Xmx512M — The maximum amount

–server/-client — Depending on which we choose for a given task, you actually get different compilers

We should strive to keep the values identical because depending on the task they can make all the difference. The minimum amount is allocation at the JVM boot, meaning no time will be spent growing the memory space while the program is running if you don’t exceed this. Thought I haven’t checked Jarkko Oranen suggested that the preformance degradation which comes by approaching the Xmx value is due to the GC working double time to free up memory, therefore its important to set the max to an appropriate value — though it varies from test to test we should strive to keep these values identical.

Methodology

I don’t think there’s a set standard for how we benchmark when doing blog comparisons, so allow me to introduce and outline for how we can handle comparisons done on this blog:

Do multiple passes: The code being benched should be executed repeatedly a given number of times, at default for smaller algorithms could be 20 passes.

Because we eventually hit GCs or other burps of the system, multiple passes ensure that we get the overall picture.

Garbage collect: Dont heap it up between runs, but clean after every pass.

This is the simplest way in which you can tame the GC and help get uniform results.

Filter highest and lowest values: Take the highest and lowest value and remove them from the timings.

When timing on the JVM some of the bumps are very significant — You can have a series of runs going at 5ms and then suddenly a pass that takes 40ms — Since its more a reflection of the disturbance than the actual algorithm, it can safely be stripped.

Warm up the JVM: To trigger all the optimizations etc, the main loop should be repeated a number of times

Since we’re blogging, I recommend just going for either 1 pass of the algorithm, or repeated passes of the algorithm until we’ve have been crunching for 1 minute. So if you algorithm takes 30 seconds for 1 pass, it will run twice, if it takes 2 minutes per pass, it will run once.

Implementation

To make this fair I’ll provide a benchmark macro in Clojure and if you are also the happy user of some other JVM language which you want included in future benchmarks on this site, please provide me with a similar function/macro, which I will then both post here and use in future comparisons.

(defmacro microbench
  " Evaluates the expression n number of times, returning the average
    time spent in computation, removing highest and lowest values.

    If the body of expr returns nil, only the timing is returned otherwise
    the result is printed - does not affect timing.

    Before timings begin, a warmup is performed lasting either 1 minute or
    1 full computational cycle, depending on which comes first."
  [n expr] {:pre [(> n 2)]}
  `(let [warm-up#  (let [start# (System/currentTimeMillis)]
                     (println "Warming up!")
                     (while (< (System/currentTimeMillis) (+ start# (* 60 1000)))
                            (with-out-str ~expr)
                            (System/gc))
                     (println "Benchmarking..."))
         timings#  (doall
                    (for [pass# (range ~n)]
                      (let [start#    (System/nanoTime)
                            retr#     ~expr
                            timing#   (/ (double (- (System/nanoTime) start#))
                                         1000000.0)]
                        (when retr# (println retr#))
                        (System/gc)
                        timing#)))
         runtime#  (reduce + timings#)
         highest#  (apply max timings#)
         lowest#   (apply min timings#)]
     (println "Total runtime: " runtime#)
     (println "Highest time : " highest#)
     (println "Lowest time  : " lowest#)
     (println "Average      : " (/ (- runtime# (+ highest# lowest#))
                                   (- (count timings#) 2)))
     timings#))

The code is effectively divded into 3 sections:

Warm-up: A while loop runs for at least 1 minute, trapping all output so we dont see any printing from whatever we’re benchmarking.

Timings: The actually expression is repeatedly run and the milliseconds spent in each pass is returned

Stats: Highest/Lowest values are filtered, results are printed

Using this to test our Fibonacci code from my previous post, then becomes:

user> (microbench 20
              (let [limit (.pow (BigInteger/TEN) 999)]
                   (loop [a 0 b 1 i 1]
                      (if (< b limit)
                          (recur b (+ a b) (inc i))
                          nil))))
Warming up!
Benchmarking...
Total runtime:  110.08787899999999
Highest time :  7.98691
Lowest time  :  5.135988
Average      :  5.386943388888889

Notice the final ‘nil’ in the code. If I had returned ‘i’ instead it would have printed the result of each pass before printing the final stats — It would not affect the timing. Or if we used the more idiomatic (?) version:

user> (microbench 20
                  (let [limit (.pow (BigInteger/TEN) 999)]
                       (count (take-while #(< % limit) fib-seq))))
Warming up!
Benchmarking...
4782
4782
4782
4782
4782
4782
4782
4782
4782
4782
4782
4782
4782
4782
4782
4782
4782
4782
4782
4782
Total runtime:  74.73764200000001
Highest time :  5.031017
Lowest time  :  3.168419
Average      :  3.696567

Of course in that case its cheating, because the fib-seq is calculated once and then kept in memory.

Conclusion

Benchmarks can be fun, but I think its important to 1) Agree on some methodology and 2) Not go nuts over a few milliseconds here and there. Certain algorithms perform better than others, and certain algorithms can be more or less idiomatically expressed in various languages. Ultimately when looking at the results we have to apply some common sense as we’re not always doing 1:1 comparisons. Using these benchmarks to definitely positively declare one language superior to the other should neither be our goal nor is it possible.

If you’ve taken a look at Alex Osbornes attempt at the WideFinder 2 challenge, you saw how he plowed through 45 Gigabytes of text in a blazing 8m 4s blowing both Scala and Java out of the water. Does that then conclusively state that Clojure is faster than both those languages? Of course not, Clojure compiles to bytecode, just like Scala and Java so the exact same speed could be obtained by both of them. The point is, that the concise and elegant Clojure code can be as powerful than other languages without the same level of incidental complexity being put on the user, so it makes sense to focus on the quality of the code while keeping half an eye on the performance. If all that mattered was speed, we’d all still be writing ASM.

This is my proposal for a uniform way to benchmark in the future — let me know what you think, I’m only happy to accept changes, improvements, implementations in other languages etc. And JVM outsiders shouldn’t feel left out.

Last night I did very small superficial comparison, of 3 ways of getting the first fibonnaci number consisting of 1000 digits. This attracted a lot of attention from Rubists, Haskaloonies and Clojurians alike, here I’ll share their contributions.

Preface

Microbenchmarking sucks, especially on the JVM. HotSpot is doing such a great job of optimizing code, that sometimes you end up getting an incorrect idea of how your code performs. Nevertheless I got, many tips for improving performance, so it seems the Internet Performance Rule of Thumb is: Always benchmark the Fibs!

Haskell

Team Haskell weren’t pleased completing the job in 7 msecs, so they suggested that I recompile the program using –O2. I used GHC v. 6.10:

limit = 10^999
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
main = print . length . takeWhile (< limit) $ fibs

(thanks to: “laulau”)

Real time, average of 20: 7 msecs.
Nothing gained, but 7 msecs is blazing.

Ruby

Ruby had big room for improvement as the very clever Matrix approach didn’t yield very satisfying performance. Here’s one commentators approach

limit = 10**999
def fib2(a,b)
 return b,b+a
end
a,b = fib2(0,1)
while b < limit
 a,b = fib2(a,b)
end
puts b

(thanks to: Aaron)

Average on 20 runs: 35 msecs.

Huge improvement and honor is restored to the Ruby camp!

Scala

Camp Scala was good enough to contribute a solution as well:

object Main {
  def main(args: Array[String]) {
    def f(a: BigInt, b: BigInt) = (b, b + a)
    val max = BigInt(10).pow(999)
    var (a, b) = f(0, 1)
    while(b < max) {
      val temp = f(a, b)
      a = temp._1
      b = temp._2
    }
    println("\nb = " + b)
  }
}

(thanks to: Rahul G ‚*updated*)

Average: 18 ms.

Clojure

Clojures loops are recursive and side-effect free, but even still it looks a little clunky:

(time (let [limit (.pow (BigInteger/TEN) 999)]
        (loop [a 0 b 1 i 1]
          (if (< b limit)
            (recur b (+ a b) (inc i))
            i))))

(thanks to: Duc)

Nevertheless, it averages at: 5 msecs. Hooray! It’s a new record!

Conclusion

If nothing else I think its fun to see these challenges approached from different languages, which is also what I like about Project Euler. And I’m certain that this will not be the last time I bring Haskell along for the ride. Last nights post were meant as small reflections on 3 very different languages, so I was a little surprised of the attention that it got — But its positive, I think its great when we all can learn a little from one another.

I’m open for ideas on another arena for comparisons. We could do something crazy like solve Global Warming.. oh wait, I already did that. How about Euler 200 then?

Haskell is a mature, statically typed, functional language which was recently compared to Ruby in an attempt to solve Euler #25. In this post I’ll share the code, the benchmark and add a Clojure version for those interested.

Preface

Normally it’s bad to start with the disclaimer, but for the sake of all you angry young men with ill tempers I’ll say it anyway: Similar to the Clojure Vs Ruby & Scala post this is in no way an exhaustive comparison between the languages, its intended at a superficial glance at a simple challenge, namely Euler #25, all in the name of good clean fun. Haskell is by far too vast, too impressive and too powerful to be fully dealt with in a simple exercise like this, and the Ruby code is still running :)

Euler #25

Create a Fibonnaci sequence and walk through it, until you find the first number which is 1000 digits. The Fibonnacci sequence is exceedingly simple. Its seeded with 0 1 and all consecutive values n, are generated by calculating n-1 + n-2.

0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181.….

Solutions

All 3 versions are compact and powerful — I’m assuming they’re idiomatic, but if I’m wrong let me know. Like I said — If you can produce a better version, please submit it instead of taking this as an invitation to a flamewar :)

Ruby

Ruby goes like this:

require 'matrix'

limit = 10**999
FIBONACCI_MATRIX = Matrix[[1,1],[1,0]]
def fibonacci(n)
  (FIBONACCI_MATRIX**(n-1)) [0,0]
end
i = 1
i+=1 while fibonacci(i) < limit
puts i

The real trick here is building the Fibonnacci seq (fib-seq), which is done by applying the Matrix form, which is a clever way to leverage some differential equations in order to produce the sequence. According to the author this runs faster than a regular memoized variant.

Haskell

Haskell code looks very different from both Ruby and Clojure, but for a simple task like this is reads almost like plain English:

limit = 10^999
fibonacci_numbers = 0:1:(zipWith (+)
                        fibonacci_numbers (tail fibonacci_numbers))

index = length w where w = takeWhile (< limit) fibonacci_numbers

main = do
  putStrLn(show(index))

First the limit is defined as the first number having 1000 digits, and then a sequence seeded with 0 and 1. When you have a sequence which requires a constant look-behind of n-values, it can be represented as a recursive set of vectors. I call that a rule of thumb, Christophe says its a theorem. One thing which is really great about the Haskell code, is the automatic currying which enables the author to do the elegant w = takeWhile (< limit). Although this example is not flaunting it, Haskell is very different from Clojure in that its statically typed and there’s been many discussions back and forth on which is to prefer, dynamic or static typing. The truth is, no one answer fits all but there’s a simple test:

If the arrow and the explanation actually helped you, then static typing is for you.

Clojure

To produce the fib-seq, we can mimic Haskell almost point for point, but where Haskell has direct support for sequences in the syntax, I need to call a few functions:

(def fib-seq (lazy-cat [0 1] (map + fib-seq (rest fib-seq))))

(let [limit (.pow (BigInteger/TEN) 999)]
           (count (take-while #(< % limit) fib-seq)))

The noticeable exterior differences is the call to lazy-cat and the anonymous function, which all readers of this blog should be able to read without any explanation. Under the hood, Haskell is fully lazy where Clojure is now Chunky-lazy. Chunked-seqs mean that I work with the sequences as if they were fully lazy, but under the hood Clojure is realizing the sequence, one chunk at a time. If I take 50 values, 82 may in fact be calculated — this is for improved performance without wrecking the use of infinite sequences. According to one of the authors of this book (which looks extremely promising btw, so go look), Rich Hickey has provided an example which eliminates the need for chunked seqs: here. That is idiomatic Clojure running faster than our old seq implementation written primarily in Java.

Results

So the usual indicators for expressiveness and performance are LOC and runtime speed, so here we go:

Last time I benchmarked Ruby it also came in… a little late, and some commentators suggested trying out other Ruby compilers — The truth is however, that small benchmarks like this really show very little and if you are working in a performance critical zone, you’ll want to test something which mimics the actual project and the actual environment. Secondarily, neither Haskell nor Clojure are optimized for performance which accounts for some of the extra Ruby code.

The lesson we can take away, is that Haskell and Clojure are blazing, and Haskell is blazing to the point where I’m not finding words good enough to describe it.

These days Microsoft is often being hammered in both the news and in Open Source communities across the globe, so on behalf of the Clojure community I would like to submit a small tribute to the man at the wheel, Steve Ballmer.

Preface

Microsoft makes good money, but they are going through tough times. So to make life a little happier at Camp Microsoft, I’ve decided to write a little Image to Ascii Art converter. Demonstrating, among other things, the power of macros. I don’t think I’ll get any arguments, that when you conjoin clojure and ascii-art, you get claskii art — So I’ve named this project appropriately

Processing an image

To convert an image to ascii we need to look at it as a bunch of colored pixels, converting them to characters one at a time. Disregarding the details of which image-holder we will use, we always find ourselves doing some tedious java-interop when working with Java Classes. Here’s a quick example of how to get the brighest color from a pixel:

(defn get-pixel [image x y]
  (let [color (.getRGB image x y)
        red   (.getRed color)
        green (.getGreen color)
        blue  (.getBlue color)]
    (apply max [red green blue])))

Very simple right? Yes, and very boring. What I would like to be able to do, is just get at the fields more directly, like:

claskii> (def image (ImageIO/read (File. "steve-ballmer.jpg")))
#'image
claskii> (get-properties (Color. (.getRGB image 10 10)) .getRed .getBlue)
[8 60]

Which of course isn’t possible, because as soon as .getRed is evaluated I’ll get a Symbol not defined error — Enter Macros! A recommended first step when writing macros is:

• Dont. If you can manage to solve the job without macros, you’re better off that way. Since macros generate code at read time, they’re more complex than regular code and thus more error-prone.

The second advice is

• Write out the code that you want the macro to emit, before writing the macro

In our case we want get-properties to expand into something like

(get-properties object .getRed .getBlue)
>>> [(.getRed object) (.getBlue object)]

So to make this happen we need to walk through our method-list (ie. .getRed .getBlue) and return a sequence which results from applying the methods to the first argument, the object:

(defmacro get-properties [obj & properties]
  (for [property properties]
    (property obj)))

Because Lisp is homoiconic we treat code exactly like data in that (.getRed obj) is nothing more than a list whos first item is .getRed and the second is obj. To see what our macro expands to, call

claskii> (macroexpand-1 `(get-properties (Color. (.getRGB image 10 10)) .getRed .getBlue))
(nil nil)

Not what we wanted! The reason is, that we haven’t taken control of evaluation, using the macro-characters. I recommend you checkout them all before proceeding, as these puppies give you a lot of power, but also make macro-definitions a little hard on the eyes. The backquote stops evaluation, while allowing us to prefix items with a tilde ~ for evaluation, ~@ for splicing ~@(list 1 2 3) => 1 2 3.

(defmacro get-properties [obj & properties]
  `(vector
    ~@(for [property properties]
        (property obj))))

Unfortunately when you check that using macroexpand-1, you’ll see the exact same result as above. The reason is, that when we’re passing .getRed as a symbol and symbols are similar to :keywords in that they are a function of their arguments. When you’re calling the symbol on the object you get nil in return. But why is the symbol being evaluated?

The splicing ~@ forces evaluation within its body, so we need to add an extra backquote:

(defmacro get-properties [obj & properties]
  `(vector
    ~@(for [property properties]
        `(property obj))))

Then check it

claskii> (macroexpand-1 `(get-properties (Color. (.getRGB image 10 10)) .getRed .getBlue))
(clojure.core/vector (claskii/property claskii/obj) (claskii/property claskii/obj))

Now thats more like it! But calling it will throw an error of course, since property is not defined anywhere — Instead of taking property literally we want it evaluated to the ‘property’ var in the for-loop, and although direct evaluation would work in most-cases you always have to be on your toes when using macros, as one day a user will submit an argument, which clashes with one of yours. The solution is (gensym), which generates a unique name for your variables. Gensym can either be called directly or simple using the syntactic sugar #:

(defmacro get-properties [obj & properties]
  `(vector
    ~@(for [property# properties]
        `(~property# ~obj))))

claskii> (macroexpand-1 `(get-properties (Color. (.getRGB image 10 10)) .getRed .getBlue))
(clojure.core/vector
    (.getRed (java.awt.Color. (.getRGB claskii/image 10 10)))
    (.getBlue (java.awt.Color. (.getRGB claskii/image 10 10))))
claskii> (get-properties (Color. (.getRGB image 10 10)) .getRed .getBlue)
[8 60]

Nice! It expands like we want and it gets us the result we want! There are a couple of optimizations which are begging to be done. Firstly the object is being created once for each method argument. This is partly because the macro allows it, and partly because I’m not actually passing an object but rather the code which constructs an object. Secondly, by adding at object with the syntactic ‘(let [obj# ~obj]) gensym, will actually change the gensym with each run of the for-loop. So the ugly, stable and fully functioning version, using manual gensym comes out looking like so:

(defmacro get-properties [obj & properties]
  (let [target (gensym)]
    `(let [~target ~obj]
       (vector ~@(for [property properties]
                   `(~property ~target))))))

Scared yet?

I realize and admit that macro definitions look awful because we need all of our syntactic weapony rolled out in order to get the expansion we want. On the other hand, if you can look past the superficial, Lisps homoiconicity  lets us treat code exactly as data, which is just an incredible tool to be sitting with, as you can freely extend the very language itself by relatively simple means!

Well, to calm the nerves again, look at how easy java-interop has become. We have gone from:

(defn old-school [image]
  (let [w   (.getWidth image)
        h   (.getHeight image)
        r   (.getRed image)
        g   (.getGreen image)
        b   (.getBlue image)]))

To:

(def new-school [image]
     (let [[w h]   (get-properties image .getWidth .getHeight)
           [r g b] (get-properties (.getRGB image 10 10)l .getRed .getGreen .getBlue)]))

Ascii-Art

So making the ascii-art itself should be very simple. This is my strategy:

1. Define a list of ascii characters of descending density
2. Scale the image down to ascii-output-size
3. Look at every pixel
4. Examine the brighest color
5. Divide that color by the amount of characters available and pick the appropriate one
6. Output result

So begin by defining a list which you think looks good:

(def ascii-chars [\# \A \@ \% \$ \+ \= \* \: \, \. \space])

Then pick out the peak value and convert it to an index in the above data, by simple division

(defn ascii [img x y color?]
  (let [[red green blue] (get-properties ( Color. (.getRGB img x y))
                                         .getRed .getGreen .getBlue)
        peak    (apply max [red green blue])
        idx     (if (zero? peak)
                  (dec (count ascii-chars))
                  (dec (int (+ 1/2 (* (count ascii-chars) (/ peak 255))))))
        output  (nth ascii-chars (if (pos? idx) idx 0)) ]

…And depending on the output-type selected by the user, return either that character or an html-version:

    (if color?
      (html [:span {:style (format "color: rgb(%s,%s,%s);" red green blue)} output])
      output)))

Putting it together

Now that we have a way of processing each pixels, we just need to walk them all:

(defn convert-image [uri w color?]
  (let [raw-image   (scale-image uri w)
        ascii-image (->> (for [y (range (.getHeight raw-image))
                               x (range (.getWidth  raw-image))]
                           (ascii raw-image x y color?))
                         (partition w))

So that walks every X for every Y returning the ascii-representation of each pixel. When the for-loop completes you’re sitting with a 1D stream of characters representing the image. In order to distinguish lines you need to partition the sequence, chopping it up every width-number-of-characters. Now we we’re sitting with a sequence of lines, which we can properly format:

        output      (->> ascii-image
                         (interpose (if color? "<BR/>" \newline))
                         flatten)]

The only difference between the html version and ascii at this point, is how to seperate the lines. Once that done we can flatten the sequence of safe printing.

    (if color?
      (html [:pre {:style "font-size:5pt; letter-spacing:1px;
                           line-height:4pt; font-weight:bold;"}
             output])
      (println output))))

Adjust the html-settings to your liking — I’m no Ascii artist so consider this a raw prototype which more creative people can improve upon should they want to. Anyway, now’s the time to test.

Getting Steve Ballmer

First I hit Google to get an image of the guy:

Steve Ballmer

Second, lets try and run it directly from the REPL:

claskii> (convert-image "/home/lau/Desktop/steve.jpg" 50 nil)

Since thats cooked down to only 50 characters it doesn’t really to the guy justice, so lets try the HTML rendere:

claskii> (spit "h.html" (convert-image "steve.jpg" 120 true))

Thats more like it — although I’ll admit that the A’s look bad.

Conclusion

You’ve seen how macros are functions that control evaluation and outputs code. Macros are both fun and tricky so use them carefully. The entire program weighs in at 55 lines and I’ve put it on Github: here.

About 1 week ago I wrote a small Reddit Clone in about 90 lines of Clojure. The amount interest and feedback was unexpectedly high so I’ve decided to extend the example to a whopping 160 lines as well as echo some of the chatter.

Preface

My original Reddit Clone was a reaction to a Common Lisp program which did very much the same thing. The Clojure version added some extra deployment goodness in that in compiled to a cross-platform jar which would launch on any Java supportive OS. Following my blogpost many more or less interesting versions popped up across the web, these caught my eye:

Reddit Clone in 61 minutes and 97 lines of PHP

This guy, actually sat down and wrote out a Reddit Clone in PHP, which I thought was amazing — If PHP could do the same as Clojure in only 6 extra lines I would be greatly impressed — However it lacked the almost every feature except rendering links.

Reddit Clone in 30 minutes and 4 lines of Perl

Wow — Half the time of PHP and only 4 lines! See the code here: Gist

Unfortunately it also lacks every single feature of the PHP version and when you unpack it, it weighs in at about 80 lines which you can read: Here

Reddit Clone in QBasic!

This is by far one of the funniest contributions to this Reddit Clone War — QBasic emitted via CGI-BIN. Despite weighing in at 250 lines, you will probably enjoy the read: here

Echoes

The reason I these, is that I think its a lot of fun to see a project like this performed in various languages, but if we’re to learn something from each other we should aim to offer the same features — So while you guys are catching up, I’ll go ahead and implement user management, as in login/logout, registration etc. :) ps: Can we see some Scala and Haskell versions soon?

Back to work

Since we’re quickly adding pages we should consider extracting as much code as possible into wrapper function. As the code-base itself increases would also make a lot of sense to separate logic from views into their own files and namespaces, but because this is purely for demonstrative purposes of Clojure/Compojure I’ll stick to a single file.

Storing Data

We can store our data in any way shape or form we want, but I’ll stick with the approach of my last post, ie. keeping all the data in memory. Because we run the server (unlike something like PHP) data, functions, threads etc live between the requests.

(def data  (ref {"http://www.bestinclass.dk" {:title "Best in Class" :points 1 :date (DateTime.) :poster "LauJensen"}}))
(def users (ref {"lau.jensen@bestinclass.dk" {:username "LauJensen" :password "way2secret"}}))
(def online-users (ref {}))

The data struct is similar to what I used in the first post, but I’ve added a new keyword :poster, to keep track of who is posting what. The users list would normally be put in a database as it simply contains a list of all registered users. The final list is a hashmap of all logged in users, instead of storing the login-information in cookies with the client, we’ll keep tabs on who is online via the Jetty server.

Why refs? Well, with the current complexity (or lack of), we might actually be able to pull through just using atoms but in a near future we might need coordinated change, hence the STM. Whichever we pick, Clojures language level concurrency support makes it a breeze to handle concurrent users.

For those of you who read the Beating The Arc Challenge post, you might be wondering why I’m tracking the session in my own datastructure instead of using the built-in session/assoc/dissoc functions of Compojure and the simple reason is that I might as well show off both approaches.

Sessions

In order to get to Jetty’s session information, we need to active Compojures Session Middleware, so our old main function becomes:

(defn -main [& args]
  (run-server {:port 8080} "/*" (->> reddit with-session servlet)))

Our routes are passed to the middle-ware and the modified routes are then passed to servlet. Now all of the routes can make use of the ‘session’ variable which contains the Jetty ID — A unique ID which we can use to track users across the site.

Logging In/Out

To log in is simple: We see if the supplied email is live in the system, if it is then we check if the password is a match and if thats the case then we associate the user-details from users with the Jetty ID:

(defn login-user [session [email password]]
  (redirect-to
   (if-let [user (@users email)]
     (if (= password (:password user))
       (dosync
        (alter online-users assoc (:id session) user)
        "/")
       "/login/?msg=Bad username/password combo")
    "/login/?msg=User does not exist")))

Again the hash-maps is making access very simple, so to log out we simple need to disassociate that Jetty ID from the online-users list. The argument might look a little weird to you, but thats a clever way to destructure the session variable — Any hashmap can be broken down into named keys by calling {:keys [k1 k2 k2]}, like so:

(defn logout-user [{:keys [id]}]
  (dosync
   (alter online-users dissoc id))
  (redirect-to "/"))

In a very short space we’ve now written our own backend session handling, so all thats left is given users a way into the system. First I would like to avoid always writing out the same head/css/js includes, so we’ll make a wrapper. Basically all it has to do is write out head-tag with a user supplied title, and then add a login button if the user isn’t logged in. If the user is logged in, we want to see the username instead:

(defn with-head [session title & body]
  (html
   [:head
    [:title title]
    (include-css "/styles/reddit.css")]
   [:body
    (if-let [user (@online-users (:id session))]
      [:div#user (:username user) (link-to "/logout/" "(Log out)")]
      [:div#user (link-to "/login/" "(Log in)")])
    body]))

So with that out of the way, the login form is simply

(defn login-form [session msg]
  (with-head session "Reddit.Clojure - Login screen"
    [:h1 "Login"]
    (when msg [:h4 msg])
    (form-to [:post "/login/"]
             [:table
              [:tr [:td "email"]   [:td (text-field "email") ]]
              [:tr [:td "password"][:td (password-field "psw") ]]]
             (submit-button "Login"))))

Giving you:

When you hit the submit button, this will POST to the backend functions below, resulting in either an error message or the front-page:

Registration

So now users who are in the system can authenticate and submit links which are joined to their usernames. The logical next step is to allow newcomers to register. I would really enjoy doing some kind of fusion between Captcha and an IQ test, but thats probably best left for a separate blogpost.

Starting with the backend, we need to make some kind of fall-through input validation like you saw in the last post and I’ll leave it up to you and your imagination to put stuff in there that makes sense, but if all the input is good then we need to check if the email is live in the system and if so throw an error. If its not live then a user should be created both in users and in online-users joining the latter to the Jetty ID:

(defn add-user [session-id [email user password]]
  (redirect-to
   (cond
    (invalid-email? email) "/register/?msg=Invalid email"
    :else
    (dosync
     (if (@users email)
       "/register/?msg=Email already registered"
       (do
         (alter users assoc email {:username user :password password})
         (alter online-users assoc session-id (@users email))
         "/"))))))

With the backend ready for customers, we just need a simple front-end registration form. This isn’t optimal but I just wanted to show off how make life a little simpler with a small for-loop:

(defn registration-form [session msg]
  (with-head session "Reddit.Clojure - Registration form"
    [:h1 "Registration"]
    (when msg [:h4 msg])
    (form-to [:post "/register/"]
             [:table
              (for [field ["Email" "Username" "Password"]]
                [:tr
                 [:td field]
                 [:td (text-field field)]])]
             (submit-button "Sign up"))))

Instead of adding a specific link to this functionality, I’ll bundle it directly with the route for submitting links, ie. if you’re not logged in you either should, or you should register:

  (GET  "/new/*"      (if (@online-users (:id session))
                        (reddit-new-link session (:msg params))
                        (redirect-to "/register/")))

So if you’re not logged in, submitting a link and subsequently trying to use my email will give you this:

Up ahead

Like I mentioned earlier, the key to Clojure happiness is structure, so if you’re considering booting up a Compojure project split the codebase into logical units, this makes for much faster development later as the project grows. Depending on your network interface, consider where you launch the clone. This morning I checked my referrers list and found an IP calling from port :8080, I figured someone was playing with Compojure so I followed the link — only to find myself looking at my own Reddit Clone launched from somewhere in the US — Cooool :)

Code still: here

Today I had a lot of fun reading about a for-constructs on steroids. The author of that post explores the possibilities which come with the built-in pattern matching in Scalas for-construct, so I’ll do the same with Clojure.

Preface

Before reading this post I hope you’ll at least skim the code in the article I linked above, just to get a feel for the complexity involved. But complex or not, with Scala you’re able to do pattern matching directly in your for-loop, yielding results as you move along. As the author in this post demonstrates, here’s one way to go:

case class Person(firstName:String, lastName: String);

val people = List(
  Person(“Jane”, “Smith”),
  Person(“John”, “Doe”),
  Person(“Jane”, “Eyre”));

for (Person(“Jane”, last) <- people) yield “Ms. ” + last;

» List(“Ms. Smith”, “Ms. Eyre”)

So is that handy? Yes that is absolutely handy, but Clojure doesn’t do steroids, in fact Lisps are almost solely identified by their powerful idioms which you use again and again, basically forming lists/datastructures in new and creative ways. Clojure hosts 2 functions (macros) which act in the same domain (looping/comprehension), but are 2 different beasts entirely.

First we have doseq:

(doseq [i (range 5)]
    (println i))
 0
 1
 2
 3
 4
 nil    ;; return

Notice the final nil? Thats your return from a doseq, since it only acts on the list for the purpose of side-effects, in this case printing. Though it supports the same binding options as for (ie. :let, :while: when) its purpose is totally different. Most people coming from imperative languages will recognize this immediately as it is your typical loop-construct, similar to foreach. In the same arena you’ll find dotimes which is handy for running a body of code multiple times and for that purpose it’s faster than (doseq [i (range 10)]).

For on the other hand

…is list-comprehension at its best:

(for [i (range 5)]
  i)
(0 1 2 3 4)

This is implicitly doing what the yield statement does in Scala and is a nice way to functionally build up a datastructure, ie. totally different from doseq. Don’t mix for with side-effects — both because it’s bad practice but also because for is lazy. But lets say that we want to do matching like the Scala and only see those items with the first name ‘Jane’:

(def people [["Jane" "Smith"] ["John" "Doe"] ["Jane" "Eyre"]])

(for [person people :let [[name surname] person] :when (= "Jane" name)]
  (str "Ms. " surname))

>> ("Ms. Smith" "Ms. Eyre")

So the :when clause only evaluates the body when the predicate (= “Jane” name) is true, however it does not halt the process when the predicate is false, it simply moves on to the next item.

Since for is lazy nothing gets evaluated unless it needs to. Throughout some programs it makes a lot of sense to keep things lazy, because although each item gets some overhead you can usually architect the code so that you end up saving computations. Lets imagine that we’re chewing our way through an endless stream of computational results, but for our final analysis we need only the first 5000 samples:

(for [sample samples :while (< (:id sample) 5000)]
  (:value sample))

That will run 5000 times and then abort. This could also be achieved like so

(take 5000 (for [sample samples ...

(take-while #(< (:id %) 5000) (for [sample ...

But getting comfortable with the full power for/doseq usually ends up giving you a nicer end result. Through all the examples, you’re seeing the power of the seq-abstraction. Lets say you need to work on a nested strucuture, only working on the innermost data — double bound for is your friend. Imagine you have a named set, where each name is bound to  a vector containing the scores achieved that day. Parsing them in a way which handles empty vectors, nil values, int, floats, doubles, whatever you throw at it, looks like this:

(let  [scoreboard {"Allison" [10 11 12 1e3]
                   "Franky"  [5 2.34 1/4]
                   "John"    nil}
       scores     (for [[player scores] scoreboard, score scores]
                    score)]
  (/ (reduce + scores) (count scores)))

>> 148.65571428571428

Notice how the core idioms of Clojure all work together neatly — We’re using for in many ways, adding predicates, abort conditions and also destructuring in breaking down scoreboard into both player and scores, then iterating each score individually. Of course the values could also have been expressed using another idiom:

(mapcat val scoreboard)

But we’ll save mapcat for a rainy day.

Idioms

If you’ve read the first chapter of Joy of Clojure, you have seen this quote

The only difference between Shakespeare and you was the size of his idiom list - not the size of his vocabulary.

– Alan Perlis

Clojure packs many extremely powerful idioms for working with data and in Lisp there’s nothing but data. All of Clojure implicitly treats data as immutable, meaning no freely roaming state, and contrary to many languages you have to be explicit if you want mutability. This greatly reduces the incidental complexity of our programs, leading to a more robust software. Since we are in no shape or form introducing mutability (like iterators), but instead building all our data functionally we don’t wind up with MatchError Exceptions or anything else which results from unexpected state.

Conclusion

This blogpost serves as a primer for using all that for has, but also as a reminder that mutable state should always be handled very very carefully as results quickly can become unpredictable. As you move into the higher layers of programming (read high-level languages), sometimes the fear sets in that you’ll end up missing certain low-level features which used to be so crucial for your application, but I’m very pleased to see that Clojure  is deep enough that you won’t find yourself missing anything, any time soon. On the other hand, while low-level can feel comfy and safe (because we’ve all done it for many years)  it does make for many areas where you need to pay extreme attention to ensure stable bug-free programs.

Recently I had the good pleasure of reading this blog post, which demonstrates how to build a Reddit Clone in 100 lines of Common Lisp. I thought it might be interesting to see a port to Clojure, contrasting a couple of idioms and core functions of both languages.

Preface

Why contrast 2 Lisps you ask? Because the subtle differences are interesting to me and both languages take up about the same amount of code-space. Following the link above you’ll actually be able to see how Sven writes out his entire Clone in a couple of screencasts, demonstrating Lisp Works. Whether you watch it or not, I recommend opening op his code in a 2nd tab while reading this post.

The not so subtle differences

Rich Hickey once remarked, that cl-Loop and cl-Format were in themselves more complex than the entire Clojure language. In this case Common Lisp has a function which I would very much see moved into Clojure, namely format. Format can render your input in more ways than you can think of, automatically figuring out wether to suffix and extra “s” to “sec” and what not — Its an impressive function, which we sadly don’t have in Clojure yet (update: Please see Tom Faulhabers comment below the article — turns out Clojure does have cl-format). As you can see from Svens Reddit Clone he formats the links like so:

Title posted 1 minute 5 seconds ago Up Down

In the absense of format in Clojure I turn to Joda Time to mimic that behavior. Joda lets me define a PeriodFormatterBuilder, which I can use to coerce ‘durations’, which the timespan is, into text formatted like above:

(def formatter
     (.toPrinter (doto (org.joda.time.format.PeriodFormatterBuilder.)
                   .appendDays    (.appendSuffix " day "    " days ")
                   .appendHours   (.appendSuffix " hour "   " hours ")
                   .appendMinutes (.appendSuffix " minute " " minutes ")
                   .appendSeconds (.appendSuffix " second " " seconds "))))

This Printer can then be used to coerce a timestamp into the text you see above, by manually making a Duration (datatype) between the timestamp and DateTime/now:

(defn pprint [stamp]
  (let [retr   (StringBuffer.)
        period (Period. (Duration. stamp (DateTime.)))]
    (.printTo formatter retr period (java.util.Locale. "US"))
    (str retr)))

We can test it by making up a TimeStamp from January 31.th 12:00:00 and 00 milliseconds:

cloneit> (pprint (DateTime. 2010 1 31 12 00 00 00))
"2 hours 52 minutes 4 seconds "

Nice. This in no way emulates all of what cl-format can do, but enough for this exercise.

Rendering Links

To render links we first need to agree on a datastructure and for simplicity I’ll go with a hash-map where the keys are the URLs and the values are hash-maps containing the properties of that URL. This makes for easy access later. To set up some test data:

(def data  (ref {"http://www.bestinclass.dk" {:title "Best in Class" :points 1 :date (DateTime.)}}))

We know that our users will want to sort the data on various columns, so it makes sense to write out a render-links function, to which we can pass our criteria for sorting. Clojure’s sort-by is special in the sense that you can both pass it a function (keyfn) which extracts the data we cant to sort-by, and also a comparator to apply. Render-links thus becomes:

(defn render-links [keyfn cmp]
  (for [link (sort-by keyfn cmp @data)]
    (let [[url {:keys [title points date]}] link]
      [:li
       (link-to url title)
       [:span (format " Posted %s ago. %d %s " (pprint date) points "points")]
       (link-to (str "/up/" url)   "Up")
       (link-to (str "/down/" url) "Down")])))

What that does it walk through every link in the sequence which results from sorting. For every link it extracts the key, which is the URL as well as the keys in the hash-map attached to that key. The return is a sequence of vectors starting with [:li …] compojure know s how to convert this to HTML.

I think the specific compojure helpers like (link-to) are pretty self explanatory, but its worth noting, that if you don’t know them all you could still make a link like so:

[:a {:href "http://www.bestinclass.dk"} "My favorite blog"]

So the entrance fee is pretty low, as you can explore away. Lets say you want to sort all links by the number of points they have, call it like so:

(render-links #(:points (val %))  >)

So that hopefully makes sense right away. You get the key by calling :points on the value of each item, and you sort those using Greater Than as the comparator. Sorting my date might be a little more tricky:

(render-links #(.getMillis (Duration. (:date %) (DateTime.))) >)

As you can see I pull out the age of the each item in milliseconds and also compare them using GT.

Rendering Home

So to render a main-page almost exactly like the one Sven has, we do the following:

(defn reddit-home []
  (html
   [:head
    [:title "Reddit.Clojure"]]
   [:body
    [:h1 "Reddit.Clojure"]
    [:h3 (format "In exactly %d lines of gorgeous Clojure"
                 (->> (this-file) reader line-seq count))]
    [:a {:href "/"} "Refresh"] [:a {:href "/new/"} "Add link"]
    [:h1 "Highest ranking list"]
    [:ol (render-links #(:points (val %))  >)]
    [:h1 "Latest link"]
    [:ol (render-links #(.getMillis (Duration. (:date (val %)) (DateTime.))) >)]]))

The reason I said ‘almost exactly’, is because Svens version outputs “In about 100 lines of Lisp”, where mine will dynamically output the exact number of lines. But looking past that small detail, I think its a very clean representation of that webpage.

To get the actual line count is a little tricky. Clojure stores the filename relative to the classpath when loading then file — that means that the only way to the actual filename is to store it once Clojure is loading my file. As soon as Clojure has moved on to the next file, *file* changes:

(defmacro this-file [] (str "src/" *file*))

Hackery you say? A little, but nevertheless it does dynamically output the number of lines in the source file.

important: If you’re running this program from REPL (ie. not from a .jar file), this-file won’t work because there is no file. Replace it with a dummy value.

Adding Links

So now we need to enable our users to add new links to the website and I’ll implement the same validation as Sven, ie. valid non empty url? non empty title etc. To begin, I’ll make a predicate to verify the URL:

(defn invalid-url? [url]
  (or (empty? url)
      (not (try (java.net.URL. url) (catch Exception e nil)))))

That makes our lives a little easier when writing the main logic. Secondly we need to set up a page which contains the input fields:

(defn reddit-new-link [msg]
  (html
   [:head
    [:title "Reddit.Clojure - Submit to our authority"]]
   [:body
    [:h1 "Reddit.Clojure - Submit a new link"]
    [:h3 "Submit a new link"]
    (when msg [:p {:style "color: red;"} msg])
    (form-to [:post "/new/"]
     [:input {:type "Text" :name "url" :value "http://" :size 48 :title "URL"}]
     [:input {:type "Text" :name "title" :value "" :size 48 :title "Title"}]
     (submit-button "Add link"))
    (link-to "/" "Home")]))

That function takes an argument for the sole reason, that I want to be able to call it with an error message while instructing the user on how to provide good input. You see that directly in the middle:

(when msg [:p {:style "color: red;"} msg])

That only kicks in if msg is non-nil, in which case it will output a p-tag with a red font containing msg. Now that we have all the rendering out of the way, we can implement the logic:

(defn add-link [[title url]]
  (redirect-to
   (cond
    (invalid-url? url) "/new/?msg=Invalid URL"
    (empty? title)     "/new/?msg=Invalid Title"
    (@data url)        "/new/?msg=Link already submitted"
    :else
    (dosync
     (alter data assoc url {:title title :date (DateTime.) :points 1})
     "/"))))

Call that function with both a title and an url (ie. the user input) and it will run a fall-through validation of that data, meaning if none of the predicates are true, then we start an STM transaction in which we associate the url with the title, a Timestamp and an initial point. All the strings you see, as well as the final “/” are the return of the conditional, which then becomes the argument to “redirect-to”.

Rating Posts

Now there’s only 2 things missing, rating and the server-setup. With our data rolled in a native Clojure structure it becomes extremely easy to rate an item:

(defn rate [url mfn]
  (dosync
   (when (@data url)
     (alter data update-in [url :points] mfn)))
  (redirect-to "/"))

That function takes the URL in question, as well as a function (modify-fn). The function can be (inc) (dec) #(+ 5 %) or whatever you’d like, its just a closure. Calling (when (@data url)) extracts the item specified by the url, if this is nil (ie. somebody tried to work around the system), then nothing happens. But if there is an URL by that name in the set, then we alter the data by update [url :points] directly within an STM transaction. That guarantees total concurrency safety even with many users.

Finalizing

So with all of the logic and rendering in place, we just need to bundle it in a set of routes which Compojure then serves our visitors:

(defroutes reddit
  (GET  "/"         (reddit-home))
  (GET  "/new/*"    (reddit-new-link (:msg params)))
  (POST "/new/"     (add-link (map #(params %) [:title :url])))
  (GET  "/up/*"     (rate (:* params) inc))
  (GET  "/down/*"   (rate (:* params) dec))
  (GET  "/styles/*" (serve-file "res" (params :*)))
  (ANY "*"  404))

Firstly we serve the main page to visitors hitting the root. If you request the “/new/” adress you get our input form, but if you post to it, the logic from (add-link) runs. The result as you recall is a redirect, either to the same page with an error or the front page.

The 4th item serves “/up/” and then feeds the remaining of the url into the key “*”. That allows me to feed that directly to (rate) and a the final parameter (inc) which causes the :points property to be incremented by one. The opposite is true for the 5th item.

The call to serve-file allow me to serve statics like CSS, JS files etc.

Finally I have my failsafe (ANY “*” 404), which of course means that all other requests that those I’ve defined above will receive a 404 reponse — its not necessary, just nice to have. Launch these routes on a network interface calling my main function:

(defn -main [& args]
  (run-server {:port 8080} "/*" (servlet reddit)))

Throw in a call to (include-css “res/reddit.css”) and you get this:

Deployment

The reason I felt like following Svens lead in producing a Reddit Clone, was because I think Clojure gives you a lot of mileage in this domain, which hopefully a few of you agree with after reading this. I’ve added the code to a Git Repo which I hope you newcomers will really enjoy:

$ git clone git://github.com/LauJensen/cloneit.git

That gives you the code. Now download Leiningen:

$ wget http://github.com/technomancy/leiningen/raw/stable/bin/lein

Put that on your path and make it executable

$ export PATH=$PATH:/path/to/lein
$ chmod +x lein

And then install it simply by calling

$ lein self-install

Now you’re sitting with my code and one of the build tools which Clojurians use. Why is this great? Its great because now you don’t have to scour the net to find Clojure, Contrib, Joda etc etc, just run

$ lein deps

And you’ll have all of the dependencies on your own system. Want to run my program to experiment with the webservice? No problem:

$ lein compile
$ lein uberjar
$ java -jar cloneit-standalone.jar
2010-01-31 15:22:09.694::INFO:  Logging to STDERR via org.mortbay.log.StdErrLog
cloneit.proxy$javax.servlet.http.HttpServlet$0
2010-01-31 15:22:09.725::INFO:  jetty-6.1.x
2010-01-31 15:22:09.767::INFO:  Started SocketConnector@0.0.0.0:8080
 

Yes — It really is that easy to deploy! Now you have a portable Reddit Clone which will run on Linux, BSD, Mac OSX and even Windows — All with very little effort and less than 100 lines of code!

Conclusion

Now you know how to write a webservice, implement Reddit like functions, build it, handle dependencies and deploy cross platform — The language level support for concurrency is becoming invaluable at every turn these days and with Clojure infrastructure pieces quickly being put in place, Clojure is giving us a lot of mileage. Hope you all have some fun with it.

PS: Big thanks to Sven for getting the ball rolling.

Code here: Github

Nobody who’s connected to the rest of the world, either via TV or the Internet is unaware of Global Warming — This phenomenon which threatens to destroy us all if we don’t collectively assume responsibility for the globe. Here’s my contribution to a solution in 98 lines of heavy computational Clojure!

Preface

As a Danish Citizen I feel its mandatory to engage in this debate. Denmark recently hosted a major conference to facilitate solutions to the climate threats of this the 21.th century. The result as you all probably know what unfortunately a huge failure, so tons of CO2 was needlessly emitted by flying in all the foreign officials, security motorcades etc etc.

I plan on getting a better result. I’ve learned that the National Oceanic and Atmospheric Administration (NOAA) have published about 3 Gigabytes of tarballed weather data, going back as far as 1929. My mission is now to organize and parse that data, to see exactly what the effect of our recent boom in CO2 emission is doing to the environment. From the total effect I’ll be able to approximate Clojures contribution to the Global Warming.

Why should I read this post?

Well if you should read it, it’s because one of more of the following applies:

• I care about Global Warming
• I love heavy computational parallelized Clojure
• I want to know how to stream Tarballs and GZips

Data

First we have to get the data from NOAA. For the sake of all of you who want to repeat these calculations to show the neighborhood kids that they shouldn’t spend their spare time lighting dumpers on fire and generally wasting energy, I’ll go through every step:

#1: Preparing URLS

Every dataset is found on their ftp in a subdirectory named according to the year the data is from and in that directory there’s a tar-ball called gsod_year.tar. I’m not a wget expert so we will tag-team with Clojure:

(spit "urls"
   (apply str
        (map #(format "ftp://ftp.ncdc.noaa.gov/pub/data/gsod/%d/gsod_%d.tar\n" % %)
              (range 1929 2010))))

--- OR ---

(->> (range 1929 2010)
	   (map #(format "ftp://ftp.ncdc.noaa.gov/pub/data/gsod/%d/gsod_%d.tar\n" % %))
	   (apply str)
	   (spit "urls"))

(spit is from clojure.contrib.duck-streams)

I show both variants because you’ll want to get comfortable with both -> (thread as the 2.nd item) and -» (thread as the last item), they’re here to stay and are quite handy. Either of those snippets produce a file called ‘urls’ which contains links to all the tar-balls available (except 2010 which ofc isn’t complete yet), totalling about 3 Gigabytes.

To download all the data issue this command from the terminal

 $ mkdir dataset && cd dataset
 $ wget -i ../urls
--2010-01-20 17:18:53--  ftp://ftp.ncdc.noaa.gov/pub/data/gsod/1929/gsod_1929.tar
           => `gsod_1929.tar'
Resolving ftp.ncdc.noaa.gov... 205.167.25.101
Connecting to ftp.ncdc.noaa.gov|205.167.25.101|:21... connected.
Logging in as anonymous ... Logged in!
==> SYST ... done.    ==> PWD ... done.
==> TYPE I ... done.  ==> CWD /pub/data/gsod/1929 ... done.
==> SIZE gsod_1929.tar ... 71680
==> PASV ... done.    ==> RETR gsod_1929.tar ... done.
Length: 71680 (70K)

100%[=====================================>] 71.680      94,5K/s   in 0,7s

The first file is just 70K as you can see, but the last is 90M — they grow as the number of weather stations increase. Now you’ve got all of your tars sitting in the same directory, so if you wanted to extract the data, do this:

 $ for i in *.tar; do echo $i && tar -xf $i && rm $i; done
(..wait about 20 minutes..)

That would give you about 450.000 number of gzips weighing in at a heavy 10 Gigabytes. If you unroll these files they’ll expand into about 50 Gigabytes of raw text! Expanding that is too ambitious on my little laptop so lets think this through. When we’ve processed all the weather data we need it sorted by year (and perhaps month). To do a running sort of the data we have to carry the head which is close to impossible in this case — even ‘ls’ struggles with the 450k files so Javas Heap will too. The best possible way to attack this problem would be to write tar-ball reader, which lets us peek at the GZips and then a GZip reader which lets us work with the text without any pre-unpacking. Javas IO is centered around Input/Output streams, so if we can expose the data via streams it will be presorted and I don’t have to overload my harddrive.

Processing

We’re looking down the barrel of several Gigabytes of raw text data, so we need to set up some kind of headless processing. When I speak about holding/losing the head, I’m referring to how we handle memory. If you keep the head of the sequence while processing, that entire sequence is accumulated in memory. Not holding the head means only keeps an item/chunk in memory at every given moment.

First we have to narrow the field as much as possible so lets look at how the professionals do:

As we can clearly see the temperatures in the Northen Hemisphere explode near start -> middle of the 1900’s. So we’ll follow Mr. Gores lead and filter out the stations which record temperature in the Northen Hemisphere (NH) — hopefully by the end of this blogpost we can reproduce the Hockey Stick using Clojure.

To do that, download the history file from NOAA’s website, it contains the IDs of all weather stations as well as their position by longitude and latitude. The NH is defined by the longtitude coordinates that are positive. The file starts with 20 lines of information and then many lines like these:

010014 99999 SOERSTOKKEN                   NO NO    ENSO  +59783 +005350 +00490
010015 99999 BRINGELAND                    NO NO    ENBL  +61383 +005867 +03270
010016 99999 RORVIK/RYUM                   NO NO          +64850 +011233 +00140
010017 99999 FRIGG                         NO NO    ENFR  +59933 +002417 +00480
010020 99999 VERLEGENHUKEN                 NO SV          +80050 +016250 +00080
010030 99999 HORNSUND                      NO SV          +77000 +015500 +00120
010040 99999 NY-ALESUND II                 NO SV    ENAS  +78917 +011933 +00080
010050 99999 ISFJORD RADIO                 NO NO    ENIS  +78067 +013633 +00050

The predefined structure of the file is based on indices, meaning I know that the WBAN ID always starts at IDX 8 and ends on 12 (7–11 when zero-based). We cannot split this on words (\w+) because some elements are occasionally left out but the index structure remains. Thats means that we can filter out those stations that are in the Northern hemisphere like so:

(defn northern-stations [filename]
  (let [data   (->> (line-seq (reader filename)) (drop 20))
        north  (for [station data :when (= \+ (nth station 58))]
                 (vec (take 2 (.split station " "))))]
    (reduce #(assoc %1  :stn  (conj (:stn %1) (%2 0))
                        :wban (conj (:wban %1) (%2 1)))
            {} north)))

If you’re a regular here that should be very straight forward, but in case you’re not:

1. Start a line-reader, skip 20 lines
2. Walk the lines and :when the 58.th index is “+” take out the first 2 elements STN and WBAN and bundle them in a vector
3. Reduce that series of vectors into a hashmap ala {:stn [id1 id2 id3] :wban [id1 id2 id3]}

The reason this doesn’t break is that neither STN or WBAN are left out anywhere in the data, NOAA consistently uses 99999 to indicate that a field is blank. With all the valid stations extracted we can now set up a data-parser which only extracts data from these stations.

Gunzip

We can start by unpacking the 1929 tarball manually to inspect the data. Java.util.zip has a few classes for working with GZip archives, so lets try them out and see if we can’t integrate it nicely.

My personal preference would be to write some kind of wrapper, which would enable me to work on the data like so

(with-zipstream [stream "/path/to/gzip.gz"]
   (...work on data...))

Well as you know its easy to conform a Lisp to your liking, so here’s my personal Gunship:

(defmacro with-zipstream [bindings & body]
  `(with-open [~(bindings 0) (->> (FileInputStream. ~(bindings 1))
                                  GZIPInputStream. InputStreamReader.
                                  BufferedReader.)]
     (do ~@body)))

But although its tempting to abstract away using macros, this constitutes macro-abuse, since this is equally helpful:

(defn dump-stream [stream sz]
  (let [buffer    (make-array Byte/TYPE sz)]
    (.read stream buffer 0 sz)
    (ByteArrayInputStream. buffer)))

(defn line-stream
  [tarstream tarentry]
  (with-open [zipfile (->> (dump-stream tarstream (.getSize tarentry))
                           GZIPInputStream. InputStreamReader. BufferedReader.)]
    (doall (for [line (repeatedly #(.readLine zipfile)) :while line] line))))

This does very much the same as cores line-seq, in that it returns a non-lazy (doall) sequence of all the lines in the GZip.

Now you have access to the weather data which looks like so:

STN--- WBAN   YEARMODA    TEMP       DEWP      SLP        STP       VISIB
030050 99999  19291001    45.3  4    40.0  4  1001.6  4  9999.9  0   17.1
030050 99999  19291002    49.5  4    45.2  4   977.6  4  9999.9  0    9.3
030050 99999  19291003    49.0  4    41.7  4   975.7  4  9999.9  0   10.9
030050 99999  19291004    45.7  4    38.5  4   992.0  4  9999.9  0    6.2
030050 99999  19291005    46.5  4    41.5  4   997.8  4  9999.9  0    7.8
030050 99999  19291006    49.5  4    46.5  4   990.1  4  9999.9  0    7.8
030050 99999  19291007    48.2  4    44.8  4   979.1  4  9999.9  0    9.3
030050 99999  19291008    46.5  4    39.2  4   994.3  4  9999.9  0   12.4
030050 99999  19291009    44.7  4    40.0  4  1005.4  4  9999.9  0   10.9
030050 99999  19291010    48.7  4    47.0  4  1000.6  4  9999.9  0    8.4
030050 99999  19291011    48.7  4    39.2  4   995.5  4  9999.9  0   12.4

With direct access to the text compressed away in the GZips its easier to implement a tarball reader, because we can see the result of our experiments immediately — Just printing the binary values from each entry (file) in the tarball wouldn’t tell me much about my success of failure in uncompressing the data.

Tar

To work with tarballs I’ve downloaded this jar file. You can also visit the Javadocs: here. First things first: Lets see if we can peek at the data, starting with the smallest set 1929.

As always when we’re in Java-land we have to think carefully about how we want to abstract methods and workflows. The class TarInputStream lets me view a Tarball as series of TarEntries (compressed files).

With the ability to walk a zipstream as pure text already in place, we can now wrap the Tarball in a process-tarball function. Its handy to go through the data one tarball at a time, both for sorting as I mentioned before but also for getting both cores busy with the data. To give you an idea of what I’m thinking, here’s the top-level processing:

(defn process-tarball
  [filename stn-ids wban-ids headers]
  (println "Parsing: " (.getName filename))
  (flush)
  (let [tarstream    (->> filename FileInputStream. TarInputStream.)
        readings     (extract-readings tarstream stn-ids wban-ids)]
    {:year (re-find #"\d{4}" (.getName filename))
     :mean (if-let [cnt (count readings)]
             (when-not (zero? cnt)
               (/ (reduce + readings) cnt))))}))

If you imagine that extract-readings just does something like walk through all readings and return a map of the temperatures it picks up, then this will collect all readings from a jar and return a hash-map containing the year parsed and the mean temp. for that year– Quite neat for about 20 lines of Clojure.

With the ability to peek through the tar into the GZip and through the compression into the text, we can start writing extract-readings. The easiest thing to do, would be to have a for-loop run through every line of the GZips and merge those line into 1 huge sequence, giving is a line-seq of all the GZips. The problem however, is that Java spends 2 bytes per char in a String. If we apply the math to the set from 2002. It goes like this

77 Mb Tarball => 10.000 Gzips weighing 360 Mb => Strings worth at least 3.6 Gb

That means for a weak system as mine, I’m down from the count once we reach 1950. So that deprives me of the luxury of picking columns out at the higest level of the parser, meaning my extract-readings function needs to be more specific than just pulling out 1 line at a time:

(defn extract-readings
  [tarstream stn-ids wban-ids]
  (->> (Double. (nth (cols data) 3))
       (for [data (rest (line-stream tarstream file))])
       (for [file (repeatedly #(.getNextEntry tarstream))
             :while file
             :when (let [[_ stn wban] (re-find #"(\d+)-(\d+)" (.getName file))]
                     (and (not (.isDirectory file))
                          (or (stn-ids stn) (wban-ids wban))))])
       flatten))

If you’re new to -» thats probably not easy to read. First I know that I want to work on every line of each file, so I pull out the 4.th column from calling ‘cols’ on that line. Cols just splits on spaces. And then I cast that to a Double. That expression is then fed to the first for loop which runs through all of the lines in the file where file is the result of the final for loop. The final for loops runs through all the entries in the tarball, picking out those entries which are not directories and are in the valid stations list, ie. stn-ids & wban-ids respectively.

Currently we’re running about 30 lines of Clojure and we’ve already got our main data extraction function set up. On the JVM we have several options when wanting to process data concurrently: Agents that carry state in asynchronized processes, futures that are just threads, promises and more. For this job there were two ways which seem appealing: Either LinkedBlockingQueue or a Parallelized map. I opted for #2. Pmap walks the data using a ‘sliding window’ approach, meaning if a thread is falling too far behind pmap will wait — This is good because of the heavy memory load inherent to this challenge. With LinkedBlockingQueue you have to decide on a number of workers but with pmap you just have to think in chunks — ie. how big do I want them? For this job its a no-brainer: A chunk = A tarball.

Ready to Launch

Now with the above functions implemented you have very free hands to decide how you want to attack the data, show/save the output etc etc, here’s one way to go:

(defn process-weather-data
  [dataset history-file]
  (let [stations   (northern-stations history-file)
        stn-ids    (disj (set (:stn stations))  "999999")
        wban-ids   (disj (set (:wban stations)) "999999")
        dataset    (->> (File. dataset) file-seq (filter #(.isFile %)) sort)
        headers    [:stn :wban :yearmoda :temp]
        result     (->> dataset
                        (pmap #(process-tarball % stn-ids wban-ids headers))
                        doall)]
    (spit "result" (sort-by :year result))))

(my runtime: 1 hour 20 minutes)

First we pull out the stations on the Northern Hemisphere and break that down into 2 sets (for fast comparisons). Then from both of those I disjoin “999999” which per convention is an empty field (see the README on NOAA). Then I take the path ‘dataset’ and mangle it into a sequence of the files, sorted by ascending order. The sort is nice because 1) It allows me to track progress, 2) The 2 largest data-sets will only have 2 threads running instead of 4 for the majority of the time. Then I manually define some headers, it wouldn’t be hard to rip them from a tarball, but there’s no need. Finally I start off the process calling pmap which launches 4 threads.

To avoid my system buckling (and spending excessive time) and boot a lean Arch installation, which claims less than 100Mb of RAM for itself — After 5 minutes this was the scenario:

5 minutes in

Couldn’t be better, both cores are boiling and the memory isn’t headed toward a heap explosion. After 45 minutes, this was the situation:

45 minutes in

The memory consumption has stabilized at 79.2% and both cores are still going full speed — excellent!

Results — Round 1

With the data ‘spit’ directly into a result file, its easy read it back and mangle it any way we want. For instance:

(doseq [{:keys [year mean]} (read-string (slurp "result"))]
             (println (format "%s\t%s" year (if mean
                                                (str (/ (* (- mean 32) 5) 9) )
                                                "null"))))

That will give you 2 columns of the readings converted to celcius, which you can copy/paste into your favorite Spreadsheet editor and observe the following:

Temperature Graph #1

And now perhaps you’re wondering, where’s the Hockey Stick ? Well one explanation could be, that we’re actually not doing a very good job at picking our input data, as we have simply parsed all available data. Because we see an explosion in the number of weather stations in the years 1995 — 2009 it’s a fair assumption that if these are unevenly distributed then because of their great number they distort the graph quite a bit.

A closer look

So we need to be more picky about the stations we use to avoid distorted data. Lets try to extract all the stations used in 1929 (our first recorded year) and follow their readings throughout the following years — That will give us a clear indication of the variations in global temperatures without any weight distortion. To accomplish this, we can help ourselves by making a function which extracts all station IDs from a given Tarball:

(defn get-stations [filename]
  (let [tarstream    (->> filename FileInputStream. TarInputStream.)
        all-stations (for [file (repeatedly #(.getNextEntry tarstream))
                           :while file
                           :when (not (.isDirectory file))]
                       (let [[_ stn wban] (re-find #"(\d+)-(\d+)-" (.getName file))]
                         {:stn  stn :wban wban}))]
    {:stn  (disj (set (map :stn all-stations)) "99999")
     :wban (disj (set (map :wban all-stations)) "99999")}))

climate> (get-stations "../dataset/gsod_1929.tar")
{:stn #{"037950" "033110" "038940" "034970"
"039800" "033960" "032620" "030750" "030910" "038040" "038560"
"038110" "990061""037770" "036010""039530" "038640""031590" "033790"
"030050" "039730"},
:wban #{}}

So all we need to do in order to follow these stations, is filter out those in the northern hemisphere and re-run the job. For the sake of faster experiments while we wash our data, I’ll accept the station-ids + outputfilename as arguments:

(defn process-weather-data
  [dataset history-file stations output]
  (let [dataset   (->> (File. dataset) file-seq (filter #(.isFile %)) sort)
        nstations (northern-stations history-file)
        stn-ids   (set (filter #((set (:stn  nstations)) %) (:stn  stations)))
        wban-ids  (set (filter #((set (:wban nstations)) %) (:wban stations)))
        headers   [:stn :wban :yearmoda :temp]
        result    (doall
                   (pmap #(process-tarball % stn-ids wban-ids) dataset))]
    (spit (str output ".raw") (with-out-str (prn result)))
    (println "Done")))

(let [tracked-stations  (get-stations "res/dataset/gsod_1929.tar")]
  (process-weather-data "res/dataset/" "res/history"
                        tracked-stations "stats-1929"))

(my runtime: 11 minutes)

Now we don’t have as much data as before (although still a lot), but we know that its not distorted by the addition a huge number of stations in various locations. That gives us the following graph:

Temperature Graph #2 — Tracking 14 stations

Hmm… I’m really starting to wonder how that Hockey Stick was produced because as we can clearly see from following about 14 stations is a gradual decrease in Global Temperature. But lets give Mr. Gore the benefit of the doubt and expand our scope to include all stations used from 1929 — 1940 and then follow those throughout the years. That will give us a ton of data and keep us somewhat safe from weight distortion. I’ll introduce a helper to compile all the stations from a given range:

(defn get-station-series [base start end]
  (apply merge-with into
         (for [i (range start (inc end))]
           (get-stations
            (str base (if (not= \/ (last base)) "/") "gsod_" i ".tar")))))

Call that with your directory containing the tars as a base and then 2 integers (1929 1940) and you’ll get in return a 2 sets containing all stations used in the period. Then all you need to do is start the job with those stations located in the NH filtered:

(let [tracked-stations  (get-stations-series "res/dataset" 1929 1940)]
  (process-weather-data "res/dataset/" "res/history"
                        tracked-stations"stats-1929-1940"))

(my runtime: 10 minutes)

Let that run for a while and you’ll get a lot data resulting in the following graph:

Temperature Graph #3 — Tracking 450 stations

It seems that when we leave out the great number of weather stations that were introduced in the last 50 years or so, that the tendency is absolutely not a rise in temperature.

Final crack at the Hockey Stick

Ok — If at first you don’t succeed, try harder. The reason the data is distorted is because the stations aren’t been weighted correctly. Some areas have a higher density of stations, some stations report more frequently than other — Long story short: We need to visually get an impression of each stations readings. By looking at each station indiviually instead of compressing them to an unevenly weighted average, we will be able to clearly deduce how the weather has changed through the years recorded.

To make this really easy, I’ll introduce a helper which spits out files ready for OpenOffice Spreadsheet:

(defn emit-dataset [data]
  (let [uids (distinct (flatten (map #(map :uid %) (map :reads data))))]
    (with-out-str
      (doseq [{:keys [year reads]} data]
        (print year)
        (doseq [uid uids]
          (if-let [reading (first (filter #(= uid (:uid %)) reads))]
            (print "," (:mean reading))
            (print ",null")))
        (println "")))))

(spit output (emit-dataset result))

As you can see, this little helper just outputs a CSV file, but it does so calling out the :uid on each reading. To get that bit of info I changed the reader, but I won’t go through it here, if you’re interested you can read the source on Github. The last will dump the CSV in a file, so you can place that at the bottom of your main func.

The 1929 stations:

14 stations from 1929 seen individually

Despite the fact that some years are w/o readings, its clear that the general tendency is in direct contradiction with what Mr. Gore has shown — His graph resulting in a massive warmt increase throughout the 1900’s, meaning that the entire graph above should be rising quite drastically — The inconvenient truth seems to be however, that there is no significant rise in temperature.

100+ stations from 1929–33 seen individually

Its hard to get a good grasp of the data when visualized like this, but reviewing over 100 stations we see that a few areas are seeing a rise in temperature while most aren’t. I did a small hack ‘n’ slash sparkline viewer to try and get a feel for the larger sets coming up on 500 stations and they seem to show the same tendency.

Hockey Game is Over

I’ve worked the official numbers from NOAA and now you’re all able to re-run the computations at home. Its clear from the official data that the globe isn’t wildly heating up, in fact in some places it is now cooling down. I’m always a bit skeptic when politicians try to solve the worlds problems using taxes and indeed the proposed Carbon Tax is a dangerous idea. Whenever a human being exhales they emit CO2 so the Carbon Tax is in effect a tax on life. Activists, Greepeace, Lobbyists etc are willing to die, but for what, humanity? No, for knowing neither Math nor Clojure.

Code here: Github

With Hadoop installed on our lean mean Arch machine, we’re ready to fire up the first computations. Hadoop opens a world of fun with the promise of some heavy lifting and in order to feed the beast I’ve written a Reddit-scraper in just 30 lines of Clojure.

The Task

When you start to consider the possibilities which come with Hadoop you can probably think of many interesting stats you want to compute. Amazon describes the top Cluster as “equivalent of a system with 15 GB of memory, 8 EC2 Compute Units (4 virtual cores with 2 EC2 Compute Units each), 1690 GB of instance storage, 64-bit platform.”. That certainly opens up a few options which I don’t have on my little laptop.

For my first experiment I want to scrape some data from Reddits Programming channels, to give me a better overview of what makes the development community there tick. Then maybe for kicks I can try to do a second blogpost which gets a thousand upvotes, but more on social engineering later.

The Scraper

Scraping Reddit is pretty simple. They have been kind enough to let us download each page in JSON simply by appending “.json” to the url. For some obscure reason, they’ve also tagged each item with a hidden ID (it shows up in the JSON, but thats it) that you have to insert into the URL in as the value to ‘after’, ex

http://reddit.com/r/programming/.json?count=25&after=t3_hiddenid

First lets get a page to see what it looks like:

{"kind": "Listing",
 "data": {
         "after": "t3_an6md",
         "children": [{
                     "kind": "t3",
                     "data": {
                             "domain": "dadhacker.com",
                             "media_embed": {},
                             "subreddit": "programming",
                             "selftext_html": null,
                             "selftext": "",
                             "likes": null,
                             "saved": false,
                             "id": "ang32",
                             "clicked": false,
                             "author": "SicSemperTyrannosaur",
                             "media": null,
                             "score": 330,
                             "over_18": false,
                             "hidden": false,
                             "thumbnail": "",
                             "subreddit_id": "t5_2fwo",
                             "downs": 223,
                             "name": "t3_ang32",
                             "created": 1263019161.0,
                             "url": "http://www.dadhacker.com/blog/?p=1193",
                             "title": "DadHacker: Things I am not allowed to do any more",
                             "created_utc": 1263019161.0,
                             "num_comments": 112,
                             "ups": 553}},{
                 ....

You can get the json file yourself: here, and you’ll notice that the raw data looks a little different from what I pasted just above but thats only because I let a little Emacs Keyboard Macro loose on it. The thing to notice is the structure which is “data” -> “children” -> a sequence of 25 “data“‘s.

\data
---after
---children
------data
------data
------data

Each of those final data-items are the actual posts on Reddit with all their individual properties. The top ‘after’ tag contains also the hiddenid mentioned above but more important its “null” when there are no more subpages.

To extract the data in first data-item, you could do this

user> (first ((json-as-string "data") "children"))
{"data" {"domain" "dadhacker.com", "media" nil, "clicked" false, "saved" false,
"created" 1.263019161E9, "hidden" false, "author" "SicSemperTyrannosaur",
"name" "t3_ang32", "thumbnail" "", "num_comments" 112, "created_utc" 1.263019161E9,
"url" "http://www.dadhacker.com/blog/?p=1193", "downs" 223, "selftext_html" nil,
"over_18" false, "score" 330, "ups" 553,
"title" "DadHacker: Things I am not allowed to do any more", "selftext" "",
"id" "ang32", "subreddit_id" "t5_2fwo", "likes" nil, "subreddit" "programming", "media_embed" {}}, "kind" "t3"}

If you follow through on that thought, you could move through all the ‘data’ items using a for-loop (list comprehension), and on each stop extract

{:id (item “id”) :url (item “url”) :author (item “author”)}

(repetitive patterns colored red/blue)

When you are accustomed to Lisp (any Lisp) and you see that kind of repetitive action, you can be sure it’s a chance to optimize. In our case we’re writing each key (“author” :author”) twice, and we’re repeatedly writing “item”. Using Clojure’s powerful zipmap we can eliminate all repetition:

(defn parse-page [url]
  (let [page (read-json-string (download-url url))
        ks   [:id :title :domain :author :ups :downs :subreddit :num_comments]
        vmap (vec (for [child ((page "data") "children")]
                    (zipmap ks (map #((child "data") (name %)) ks))))]
    (if-not (nil? ((page "data") "after"))
      vmap
      [vmap :done])))

Pass that an URL and in return get the data you want attached to keys in a hashmap wrapped in a vector. The final expression helps us determine when we’ve run out of subpages and then abort the scrape in case we haven’t reached the ‘max’ number of subpages. **Caution**: Because the ID of the last post is carried over in the URL, you have to query for the :id, the rest are optional.

This was the page procesing, so the 2 details we need are

1. Emitting the data in a way which Hadoop can read
2. Walking through all subpages, accumulating data

Starting with (1) we have very free hands. Hadoop will run a Clojure-job, so we can read the data any way we want. For now I’ll just walk through the data and print it as a string. The data is structured as a vector of pages, every page being a vector of items and we need to call ‘prn’ of all items:

(defn emit-results [outfile data]
  ((if (.isFile (java.io.File. outfile)) append-spit spit)
   outfile (with-out-str (->> (butlast data)
                              (map #(doall (map prn %)))
                              doall))))

The ‘if’ statement just checks if the file already exists to determine if we’re appending or writing a new file. The rest should make sense when you consider the datas structure. The reason I remove the last item, is that parse-pages appends a :done which we don’t want hanging on to every channels data.

Now for the accumulation and parsing of all subpages I’ll define a scraper which takes a maximum number of subpages, an output file for the dataset and finally the name of the channel we want to rip. For convenience I’ve pasted the entire program, so you can run it at home:

(use 'clojure.contrib.json.read
     'clojure.contrib.duck-streams)

(defn download-url [url]
  (let [s (.openStream (java.net.URL. url))]
    (apply str
           (map #(char %) (take-while pos? (repeatedly #(.read s)))))))

(defn parse-page [url]
  (let [page (read-json-string (download-url url))
        ks   [:id :title :domain :author :ups :downs :subreddit :num_comments]
        vmap (vec (for [child ((page "data") "children")]
                    (zipmap ks (map #((child "data") (name %)) ks))))]
    (if (nil? ((page "data") "after"))
      [vmap :done] vmap)))

(defn emit-results [outfile data]
  ((if (.isFile (java.io.File. outfile)) append-spit spit)
   outfile (with-out-str (->> (butlast data)
                              (map #(doall (map prn %)))
                              doall))))

(defn scrape-channel [max target channel]
  (let [base   (format "http://reddit.com/r/%s/" channel)
        page   (fn [data idx]
                 (str base ".json?count=" idx "&after=t3_"
                      (-> data peek peek :id)))
        scrape (reduce (fn [data idx]
                         (if (= :done (-> data peek peek))
                           data
                           (conj data (parse-page (page data idx)))))
                       [(parse-page (str base ".json"))]
                       (take max (iterate #(+ 25 %) 0)))]
    (emit-results target scrape)))

Originally I wrote that as a loop/recur, but as my old buddy Meikel pointed out: Most loops can/should be implemented as Reduce. If you’re really digging in, consider adding a Thread/sleep to give poor Reddit some time for recovery and perhaps avoid an IP Blacklisting as well, I didn’t come across any query limits when reading the API. (**update**): An official from Reddit has asked that sleeps be inserted into the code, so please add (Thread/sleep 200) or something similarly appropriate as the first line of parse-page.

Letting this puppy loose on your favorite channels look like so:

(click to enlarge)

The Data

Now that we’re sitting with almost unlimited insight into the posts which make Redditors tick, we can think of many stats that would be fun to compute. Since this is a tutorial I’ll go with the simplest version, ie. something like calculating total number of upvotes per domain/author, but for a future experiment it would be fun to pull out the top authors/posts and also scrape the URLs they link, categorizing them after content length, keywords, number of graphical elements etc, just to get the recipe for a succesful post.

Hadoop-De-Doop

To interface with Hadoop we need to compile a JAR file, which is then passed to Hadoop as a job. Hadoop handles the distribution and computation. If it wasn’t for two interesting contributions to the Clojure community I would have to take you through a gruesome exercise in Java Interop. Fortunately for us, the team behind FlightCaster have released Crane which is their home-grown tool for Hadoop jobs (platform specific) and Stuart Sierra has also released Clojure-Hadoop which simplifies job-creation substantially. For this post I’ll run with Stuarts lib first and hopefully find enough room for improvement, so that I can fork it, extend it and give it a proper name like Hadoop-de-Doop or Cladoop.

Creating The Job

To create a job, we need to set up a project which we can build. For this we have several options

1. Ant
2. Leiningen
3. Clojuresque

For Clojure projects both Leiningen and Clojuresque should work almost equally well, I think Clojuresque has a small advantage in its ant-task interop, but I dont know for sure. For kicks I’ll go with Leiningen this time ’round.

You need to set up a directory structure like so:

haddit/project.clj
haddit/src/haddit.clj
haddit/lib/clojure-hadoop-1.0-SNAPSHOT.jar
haddit/lib/clojure-hadoop-1.0-SNAPSHOT-job.jar

I started out by wasting some time by depending on clojure-hadoop from Clojars, but as I learned that .jar file is broken (which is often the case with Clojars?). Therefore you need to clone the Git Repo and build it as Stuart instructs in the readme. The project.clj is what Leiningen uses to handle the compilation process, you can set that up first:

(defproject haddit "0.0.1"
  :description      "Unifying Clojure/Hadoop power!"
  :url              "http://www.bestinclass.dk"
  :library-path     "lib/"
  :namespaces       [haddit]
  :dependencies     [[org.clojure/clojure "1.1.0-alpha-SNAPSHOT"]
                     [org.apache.hadoop/hadoop-core "0.20.2-dev"]])

As I mentioned above I couldn’t handle all my dependencies directly through Leiningen, so to get around that I manually link the “lib/” directory and put clojure-hadoop in there. Now we can get to the fun part, namely the map-reduce job.

Map-Reduce jobs differ from Clojures Map/Reduce functions, in that they work on key/value pairs and return them as well. Clojures reduce returns a single item. There’s also the added trickery of data-types as Hadoop comes with its own set, which doesn’t naturally work with Clojures many functions for data munging.

CH (Clojure-Hadoop) has defined map-reduce-readers in the wrap.clj which come with the promise of letting us work purely in Clojure so lets try that out first. Create a new file in haddit/src/haddit.clj and start by declaring the namespace and doing your necessary imports:

(ns haddit
  (:gen-class)
  (:require [clojure-hadoop.wrap :as wrap]
            [clojure-hadoop.defjob :as defjob])
  (:import  [java.io BufferedReader InputStreamReader]))

It used to be the case, that if you wanted a stand-alone jar which you could run with java –jar myjar.jar then you had to start out with (:gen-class :main true), but I’ve learned that it’s no longer the case. If you want this jar to be executable, just add “:main haddit” to your project.clj and compile with ‘lein uberjar’.

With the formalities in order we can move on to defining both our mapper and reducer. Since we dumped all our data using the printed representation of a hashmap, the idea is that using CH we can have our mapper work on each line individually seeing it as a hashmap. So to get the ball rolling, let’s say that we want to use the domain name as key and its ‘up votes’ as the value, that way we can sum up all the up-votes each domain got. The mapper is then:

(defn mapper [key value]
  (let [{:keys [domain ups]} value]
    [[domain ups]]))

I get in a hash-map with all the data I made available in the scraper and I extract the 2 keys I want to look at, domain and ups. They are then fed back to the Clojure-writer function which looks in the outer vector for key/value pairs. It’ll find one where the domain is the key and ups is the value.

When the reducer is passed this data, it’ll get 1 domain name as the key and all of the ‘ups’ which have been found for that domain name as the value-fn. When you evaluate value-fn, you get the values. The trick is then only to get the sum of all the ‘ups’ ie. the values:

(defn reducer [key values-fn]
  (let [values  (values-fn)]
    [[key (reduce + values)]]))

The return type is similar to the mappers, and you see me first evaluating the values and then calling reduce + on it — treating it like any other Clojure structure. But this is theoretical still, lets prepare the test run. Hadoop needs some info about the job, which we can elegantly define using defjob:

(defjob/defjob   job
  :map           mapper
  :reduce        reducer
  :map-reader    wrap/clojure-map-reader
  :inputformat :text)

Check out wrap.clj from CH to see the other readers which Stuart has made available for us. The clojure-map-reader does what the name leads you to think: Calls read-string on each line giving us the Clojure datatype. The inputformat is set to :text which is Hadoops default. That ensures that the input file is split by Hadoop on newlines and the byte offset thus becomes the key.

Now we need to compile the thing, and you set everything up like I’ve outlined here you compile it like so:

$ cd haddit/
$ lein uberjar
[INFO] snapshot org.clojure:clojure:1.1.0-alpha-SNAPSHOT: checking for updates from central
[INFO] snapshot org.clojure:clojure:1.1.0-alpha-SNAPSHOT: checking for updates from clojure-snapshots
[INFO] snapshot org.clojure:clojure:1.1.0-alpha-SNAPSHOT: checking for updates from clojars
Compiling haddit
Including haddit.jar
Including ant-launcher-1.7.0.jar
Including commons-cli-1.2.jar
Including commons-logging.jar
Including clojure-hadoop-1.0-SNAPSHOT.jar
Including ant-1.7.0.jar
....

After about 30 more lines inclusions, you’ll get haddit-standalone.jar out. If lein fails because of some file named src/#.something its because you haven’t saved your Emacs file and its holding a lock on it. This is a good failsafe.

To avoid spending uncessary time on the Hadoop server, we start by testing the job locally:

$ java -Xmx1024m -Xms512m -cp haddit-standalone.jar clojure_hadoop.job -job haddit/job -input data/dataset -output out
10/01/11 11:03:05 INFO jvm.JvmMetrics: Initializing JVM Metrics with processName=JobTracker, sessionId=
10/01/11 11:03:05 INFO mapred.FileInputFormat: Total input paths to process : 1
10/01/11 11:03:05 INFO mapred.JobClient: Running job: job_local_0001
10/01/11 11:03:05 INFO mapred.FileInputFormat: Total input paths to process : 1
10/01/11 11:03:05 INFO mapred.MapTask: numReduceTasks: 1

After about 20 more lines the job will hopefully stop with no errors and the JobClient will print out some stats. The result is now stored in the out/ directory in a Hadoop sequence file which you can read+pipe like so:

$ java -cp haddit-standalone.jar org.apache.hadoop.fs.FsShell -text out/part-00000 >> rawtext
10/01/11 11:05:18 WARN util.NativeCodeLoader: Unable to load native-hadoop library for your platform... using builtin-java classes where applicable
10/01/11 11:05:18 INFO compress.CodecPool: Got brand-new decompressor
10/01/11 11:05:18 INFO compress.CodecPool: Got brand-new decompressor
10/01/11 11:05:18 INFO compress.CodecPool: Got brand-new decompressor
10/01/11 11:05:18 INFO compress.CodecPool: Got brand-new decompressor

And if you open the file ‘rawtext’, you’ll see that all the domains from our scrape now has an integer next to it, indicating how many total upvotes that domain has, sorted alphabetically. If everything looks good start up your Hadoop server and launch the job on it:

[hadoop@myhost]$ scp youruser@192.168.ur.ip:/home/you/scraper/dataset .
[hadoop@myhost]$ scp youruser@192.168.ur.ip:/home/you/haddit/haddit-standalone.jar .
[hadoop@myhost]$ hadoop fs -put dataset dataset
[hadoop@myhost]$ hadoop jar haddit-standalone.jar clojure_hadoop.job -job haddit/job -input dataset -output hadditresult

First I download the files from the host system into the virtual box using scp, then I put the dataset on the HDFS — Hadoops filesystem. Now the Hadoop server starts crunching like there’s no tomorrow:

(click to enlarge)

In addition to showing progress on the CLI you can also keep track of your jobs using the JobTracker WebUI:

Once both the mapper and reducer jobs are 100% complete you can retrieve the result from the HDFS like so

[hadoop@myhost]$ hadoop fs -get hadditresult

That will download that folder from the HDFS and it will also contain a Hadoop Sequence file, identical to the one produced on your local test.

Sorting the Set

When you examine the data you’ll have one grievance — Its alphabetically sorted and not sorted per number of upvotes. To change that its helpful to look at the structure with which Hadoop works:

(click to enlarge)

Hadoop sends a chunk of data to the reader, which then set up the type classes as you’d like, passes that data to the mapper which works on it and then passes it to the reader, which returns the data to Hadoop. Hadoop now sitting with the mapped data sends it further down the stream with the keys all in correct sequence, hence the alphabetical sort you just saw.

If you want to sort this set by the number of upvotes, you really only need two things

1. Set the :inputtype to :seq
2. Make the mapper return [value key] instead of [key value], promoting the value to key.

Ah but then you’ll have a problem! Clojure-Hadoop doesn’t currently provide the necessary configuration options, to make the reader/writer functions handle keys of the type LongWritable. Thats perfect! Now I have a chance to do Hadoop-De-Doop! More on that later :)

(update: Shortly following this post Stuart Sierra compiled version 1.0 of CH and added the missing configuration options!)

Conclusion

I saw a benchmark showing how Hadoop sorted 9TB of data in 1.5 hours. As data-sizes continue to rise it’s important to be able to harness the power of distributed computing. Hadoop offers an extremely friendly and powerful way of doing that. With much of the JavaInterop being hid inside Clojure-Hadoop we as Clojurians can keep doing what we do best: Write beautiful functional highway tearing, forrest burning, bytecode blazing run-like-the-wind code.

Since we’ve had so much fun with multiple cores running at once, how about upping the game to play with multiple servers? Hadoop is a framework for distributed computing, which lets us process jobs on multiple servers at once giving more power *grunt*. In this first post I’ll run through how to set up your first Hadoop server running in a VirtualBox using Arch.

Why Arch?

I’m doing these experiments on my tiny Macbook Pro laptop, so I want my Linux installation in the VBox to be as lean and clean as possible. Arch strikes a perfect balance between functionality and bloat and for something as simple as running a Hadoop server it’s very easy to set up.

I think its a beautiful thing when a cleanly installed linux replies “No entries” to the “netstat –lnput” after installation. Arch lets you build your system from the ground up and although that takes a little longer than Ubuntu, it might just make for a better end result.

Why Hadoop?

Clojure is an excellent language for writing data parsers et al, so what could be more fun than taking our regular code and process it on a multiserver network? In industry, many tasks are of such dimensions that its pointless to run it on a single server, so if you have something like Flightcaster in mind, you need to get comfortable with distributed computing. Secondly its Java based, meaning that to get my hands all the way from Clojure into the Engine Room is very doable.

Worth mentioning as well is the fact that there is already a couple of Clojure Interfaces out in the open. As most people know the crew behind Flightcaster released Crane and secondly Stuart Sierra released the creatively named clojure-hadoop library.

The Installation

Thanks to the kind donations I was able to purchase Vimeo Plus, so that you can now follow the screencasts in HD, hopefully giving you a clearer rendering of the text! If you know all there is to know about installing Arch and getting Hadoop up an running in Pseudo Distributed Mode, then feel free to skip this entire post. It’s a mandatory first stop for me, to ensure that everyone can follow future experiments using Hadoop.

Since this is HD 2x click for fullscreen or go to the Vimeo site.

The Video (16 min)

(double click for full-screen — if you’re not seeing it, try hitting F5 or using Firefox)

Configuration

For your own set up, these are the things you need to change:

/etc/hosts.allow

sshd: ALL: ALLOW

java: ALL: ALLOW

/etc/rc.conf   (to autostart services)

daemons=(… sshd rsyncd …)

~/hadoop/conf/hadoop-env.sh

export JAVA_HOME=/usr/lib/jvm/java-6-openjdk

Hadoop XML configs

~/hadoop/conf/core-site.xml

Pseudo xml:  property: name: fs.default.name value: hdfs://localhost:9000

~/hadoop/conf/hdfs-site.xml

Pseudo xml: property: name: dfs.replication value: 1

~/hadoop/conf/mapred-site.xml

Pseudo xml: property: name: mapred.job.tracker value: localhost:9001

All of the XML configuration files are 6 lines long — I hope everybody is cool with that :)

Next Up

This was this obligatory step which we just have to get over with. The next step is making/using some kind of Clojure Interface with Hadoop in order to run jobs on it. Stay tuned for round #2.