FoemBlog

New Job!

2008-11-21T22:43:00.006-06:00

I've just finished my second week here at DRW Trading Group. So far I've been extremely impressed by the quality of the people, the number of interesting projects going on, and the overall energy of the place. It's also been fun catching up with the various ThoughtWorkers roaming the halls here.

Windows XP was installed on my machine when I first arrived, but I'm happy to say that's been remedied and I'm now up and running with Ubuntu 8.10. Combined with a dual quad-core machine and a 30" monitor (plus a 19" side monitor) it's definitely the nicest workstation I've ever had. Much appreciated.

As for what I'm actually working on here at DRW, all I can say is that I'm in the "algorithmic trading group", of which the first rule is "don't talk about the algorithmic trading group" (intellectual property and all). So we'll leave it at that for now...

Erlang R12B-4 Released

2008-09-08T19:02:00.004-05:00

The erlang-otp repository at GitHub has been updated.

Some folks were having trouble building the previous releases, due to a well-known "feature" in git that causes it to ignore empty directories. I've modified my import script to add empty.gitignore files where necessary, so that those empty directories come out the other end. The build scripts should now run out of the box.

LLVM Buzz

2008-09-03T23:30:00.001-05:00

I've been playing around with the Low Level Virtual Machine toolkit a bit recently, which is a whole suite of tools for implementing compilers, virtual machines, and other goodies only a C.S. major could love. I'd always been vaguely aware of the project, but a couple of recent developments made me think it's time to take a serious look at it:

FlaCC

The first was the presentation that Scott Peterson of Adobe gave at the 2008 LLVM Developer's Meeting a few weeks ago (slides and video here). Scott's managed to get LLVM bytecode running on top the the Flash VM, which has all sorts of interesting implications (although it seems a bit backwards - shouldn't the high-level virtual machine i.e. Flash run on top of the low-level virtual machine - not the other way around?). In particular, it means that you could potentially run arbitrary C programs in the browser, since a C-to-LLVM bytecode compiler already exists.

Most of the major programming languages out there have interpreters written in C, so it follows that you could then run Ruby or Python or whatever in the modified Flash runtime without a whole lot of work. The browser would become even more like an OS, hosting arbitrary applications and giving them low-level APIs for accessing the DOM and other resources, instead of imposing particular languages or object models. Huzzah.

Unfortunately, it doesn't look like FlaCC will be supported anytime time, which means we'll have to limp along with Javascript and Actionscript for the time being. And to be honest I can't see a reason why Adobe would want to support this - if I could run vanilla Ruby in the browser, why would I pony up the big bucks for all those ActionScript development tools?

Snow Leopard

The second interesting development is Apple's use of LLVM in the next release of their operating system, code named Snow Leopard. It appears that both Grand Central (which distributes processing across cores) and OpenCL (which distributes processing between the CPU and the GPU) will make use of LLVM. In fact, Apple seems to be throwing so much weight behind the LLVM project, that it makes be wonder if they're building their own LLVM-based browser plugin. There does seem to be a rather gaping hole in this chart:

Company	Preferred Language	Virtual Machine
Microsoft	C#, Visual Basic	.NET CLR
Adobe	ActionScript	Flash
Sun	Java	Java Virtual Machine
Apple	Objective-C	???

Since Apple refuses to support Flash on the iPhone, and they haven't been shy about using iTunes as a way to get users to install other Apple software, my guess is that they will release an LLVM-based browser plugin at some point. Just a hunch.

Anyway, to get the hang of things I'm working on a LLVM backend for a Lisp-like language. More to come...

Erlang, Multiple Assignment, and Closures

2008-08-01T11:25:00.000-05:00

There's been some discussion on the tubes recently about the value of Erlang's single-assignment semantics, with people weighing in on both sides.

However, no one seems to be asking the key question, namely what happens when you mix closures (which already exist in Erlang) with multiple-assignment variables? That's probably because the answer is a bit messy: you get an object-oriented language.

To see why this is the case, let's go ahead and define a Person class in this (hypothetical) Erlang variant. The Person class has a single Name field and corresponding getter and setter methods:

-record(person,{get_name,set_name}).

new_person(Name) ->
    #person{
        get_name=fun() -> 
            Name 
        end,
        set_name=fun(NewName) -> 
            Name = NewName   % Multiple assignment
        end  
    }.

That's all there is to it. The arguments to the function (i.e. Name) act as the fields of the object, and the anonymous functions assigned to the record (i.e. get_name and set_name) act as the methods. This means we can now create Person objects, pass them around, and modify them whenever we want:

Person = new_person("Sean Combs"),
print(Person#person.get_name()),
Person#person.set_name("Puff Daddy"),
print(Person#person.get_name()).
etc...

Why does this matter? Because objects have identity, and identity's a real bitch when it comes to distributed systems. In particular, a lot of questions pop up when you try to send an object over the wire to another process. Do you:

Copy the object, in which case any changes made to it on the remote process won't be visible locally

Send a reference to the object, such that any time the object is referred to in the remote process, a call is made back to the original process (at great cost to performance)

Let the developer indicate on an object-by-object basis which of the previous two options they would prefer

Punt, and simply forbid access to mutable variables from within closures.
This is pretty limiting, to the point where it makes it impossible to even write a simple foreach function. For example, the following code, which adds the numbers [1,2,3] together, wouldn't be allowed (since Sum is mutable and accessed from a closure):
```
Sum = 0, 
foreach(fun(N)-> Sum += N end, [1,2,3]), 
print(Sum)
```
Assuming we're OK with this, we still have to deal with the fact that we now have two types of variables in the language: mutable and immutable. Therefore we must either:
- Prefix immutable variables with "final" to indicate they can be used within a closure
- Prefix mutable variables with "var" to indicate they cannot be used within a closure
- Rely on the compiler to infer which variables are mutable and which are used within closures (possibly producing some very cryptic error messages)
- Take a "snapshot" of all variables in scope when a closure is created, and ignore any subsequent changes to the variable. For example, the following code would print "foo":
```
Name = "foo",
PrintName = fun() -> print(Name) end,
Name = "bar",
PrintName().
```
  But this would print "bar":
```
Name = "foo",
Name = "bar",
PrintName = fun() -> print(Name) end,
PrintName().
```
  Confusing, to say the least.

Personally, I don't find any of these options very appealing. But if you really want multiple-assignment variables in Erlang, you're going to have to pick one of them.

RESTful Protocol Buffers

2008-07-19T16:19:00.001-05:00

I'm considering adding support for Protocol Buffers to the RESTful application that I'm currently working on, and was wondering what people thought.

I'm aware of all the arguments against using binary formats in REST APIs - but we deal with some pretty big sets of data on our project, and the speed and compactness of Protocol Buffers compared to XML/JSON is just too tempting. So here's how I'm thinking we might implement things:

XML will remain the default representation for all resources.

If the client includes the application/x-protobuf MIME type in their Accept header, the server will return a Protocol Buffer instead (and set the Content-Type to application/x-protobuf).

When a Protocol Buffer is returned, the HTTP response will also include an X-Protobuf-Schema header containing the URI for the .proto schema file.

Is anyone else doing something similar? It would probably make sense to coordinate on MIME types, etc...

Erlang R12B-3 Released

2008-06-11T15:47:00.010-05:00

There's a new release of Erlang/OTP out today, which you can download from the usual location. I've also imported it into the erlang-otp repository at GitHub.

According to the readme, this release contains an "experimental" regular expression module called re. The module wraps a lower-level PCRE library and is "many times faster than the pure Erlang implementation". It also looks like it works equally well with both binary- and list-based strings. So I guess the race is one to see who can get their WideFinder implementation up and running first...

Updated Erlang/OTP Repository at GitHub

2008-06-08T19:19:00.008-05:00

I ended up deleting and recreating the erlang-otp repository at github today, in case anyone's having problems accessing it. My original import script had a bug that prevented files from being deleted correctly between versions, which meant the files in the repository didn't exactly match the files in the source tarballs. It should be fixed now, but you were using the old repo you'll probably need to do a clean git clone to get things working again.

Message Ordering in Erlang

2008-06-01T19:12:00.003-05:00

I've noticed that when people first learn Erlang (myself included), they tend to assume that messages sent between processes must be handled in the same order they're received. Turns out this isn't the case - you can pluck a message out from anywhere in a process's inbox, assuming you know a pattern that uniquely matches it. This is called a "selective receive".

For example, let's say we fire off a couple of messages to a process registered as myserver:

myserver ! {name, "World"},
myserver ! {greeting, "Hello"}

Even though the we're sending the greeting message after the name message, it's possible for the receiver to process the greeting first, by matching on the greeting atom in the first position of the tuple:

Greeting = receive {greeting,G} -> G end,
Name = receive {name,N} -> N end

Here the first line removes the second message (the greeting) from the inbox, and the second line removes the first message (the name).

This may not seem like a big deal, but there are a lot of cases where this behavior comes in extremely handy. Below are couple of examples: synchronous messaging, and parallel processing of lists:

Synchronous Messaging

Layering synchronous messaging (i.e. your basic remote request/response) on top of the asynchronous stuff built into Erlang seems like it should be easy - you just send a message to another process, and wait until you get a message back. And a lot of the time that's all there is to it.

However, it's possible that your client process has lots of messages coming in from different places, in which case there's no guarantee that the first message you receive after sending a request will be the actual response to your request. You'll have to do a selective receive to filter out the irrelevant messages.

An easy way to do this is to include a unique token with each request, and have the server include it in its response. That way the client can just pattern match on the token.

For example, say we have a time server that sends the current time back to any process that requests it (plus the token):

time_server() ->
    receive
        {get_time, Pid, Token} ->
            Pid ! {time, time(), Token}
        end,
    time_server().

We can then get the time from the server using the following two functions. The first is responsible for sending the get_time message to the time server. It uses make_ref the generate the token:

request_time(TimeServer) -> 
    Token =  make_ref(),
    TimeServer ! {get_time, self(), Token},
    Token.

The second is responsible for taking that token and using it to selectively retrieve the response from the inbox:

receive_time(Token) ->
    receive {time, Time, Token} -> Time end.

That's pretty much it. We just need to put the two together:

get_time(TimeServer) ->
    Token = request_time(TimeServer),
    receive_time(Token).

We now have a function that will send a request to another process and block until it receives a response, without affecting any of the other messages in the inbox.

Parallel Processing Of Lists

Now let's say we want to make calls to a bunch of different servers. And we'd like those servers to execute the calls in parallel because, well, that's just how we do things in Erlang.

So continuing our previous example, assume we have a list of time_server processes. We want to send our get_time message to all of them, and we want to block until we receive all of the responses. We'd also like the responses to be returned as a list whose order corresponds with the original list, so that we know which time value goes with which time_server. (We can't just use the order the responses are received, since that's basically random.)

A very concise way to implement all this in Erlang is to use two list comprehensions: one to send the requests out and generate the list of tokens, and another to take the list of tokens and selectively receive the responses. For example:

get_times(TimeServers) ->
    Tokens = [ request_time(TimeServer) || TimeServer <- TimeServers],
    [ receive_time(Token) || Token <- Tokens ].

That's all it takes to execute those calls in parallel, and to put the results in the right order. Not bad for two lines of code.

And More...

We could take this example a lot further: maybe we want to ignore time servers that don't respond within a certain amount of time; or automatically restart them when they crash; or process the responses as they come in instead of collecting them in a list; and so on.

All these scenarios are easy to implement using selective receives (and other language features like linked processes). The interprocess communication built into Erlang seems simple, but it's been carefully designed to give you a lot of flexibility when designing your system.

"Hello, World" Revisited - Automatic Reloading

2008-05-09T13:10:00.011-05:00

My last post contained some code for a minimal "Hello, World" webapp in Erlang. However, that code wasn't very Erlangy - if you wanted to make a change to the application, you had to kill the shell and restart it. That's clearly not going to impress the "nine nines uptime" crowd. Plus it's annoying to develop that way.

So here's some bonus code that will cause the server to compile and reload changes on the fly, without having to restart the server. It probably won't get you to nine nines, but it's a start. Just append the following to the original "hello_world.erl" file:


reload(SessionID, Env, Input) ->
    case make:all([load]) of
        up_to_date ->
            hello_world:service(SessionID, Env, Input);
        _ ->
            mod_esi:deliver(SessionID, [
                "Content-Type: text/plain\r\n\r\n", 
                "compilation error"
            ])
    end.

The reload function acts as a wrapper around our original service function, calling make:all (which will compile and reload any out of date code) before forwarding the request.

You'll also need to stick an export at the top of the file, after the module declaration:


-export([reload/3]).

Last but not least, you'll need to create a file called "Emakefile", which tells Erlang what to compile during the call to make:all. In our case, the file is pretty simple:


{'*', []}.

Now start up the erl shell and run the same steps as before:


Eshell V5.6  (abort with ^G)
1> c(hello_world).
{ok,hello_world}
2> inets:start().
ok
3> hello_world:start().
{ok,<0.51.0>}

But this time, use the following URL to test the app, which will hit our new reload function:

http://localhost:8081/erl/hello_world:reload

You should now be able to make changes to hello_world.erl (e.g. change the message from "Hello, world" to something else), hit refresh in your browser, and immediately see the changes.

What's really happening here?

When I first started learning Erlang, I'd assumed that whenever you reloaded modules (via make:all or code:load_file or whatever) that those changes would go into effect immediately, similar to the way the load command works in Ruby. However, that's not quite how things work - just because changes to a module have been loaded doesn't necessarily mean they will be executed. This is because Erlang gives you very fine grained control over when code changes take effect.

The key to all this is the ':' operator. On the surface, it just looks like a namespace separator, used to disambiguate between functions with the same name in different modules. For example, within our hello_world module, you would think that the following two lines of code would be identical, and that the hello_world: in the first line would be redundant:


hello_world:service(SessionID,Env,Input).
service(SessionID,Env,Input).

However, they're not quite the same. The call in the first line actually checks to see if a newer version of the hello_world module has been loaded, and if so, dispatches to that version. The call in the second line always dispatches to the same version as is currently running, even if a newer version has been loaded. If a new version of the module has not been loaded, their behavior is the same.

The upshot of this is that you can have two versions of your code running at the same time (Erlang doesn't let you have more than two, however). This is similar to the way some web servers have a "graceful" restart option, that allows currently executing requests to continue using the old configuration, while new requests use a different configuration. Except in Erlang you can pick the exact function call in your application where these upgrades happen. Very cool.

You can test this behavior by leaving out the hello_world: prefix in the fourth line of the reload function. You'll notice that your changes are no longer picked up immediately, but are picked up on the next invocation (since the initial call to hello_world:reload by the HTTP server will trigger an update).

"Hello World" Webapp in Erlang

2008-05-04T17:33:00.005-05:00

When I first started using Erlang it took a fair bit of trial and error to create a server that generated dynamic HTTP content. The main problem is the lack of good tutorials out there for doing these kinds of things. The documentation that comes with Erlang is good for reference, but is not that helpful if you're just learning the language.

In particular, there didn't seem to be a basic "Hello World" example for building web applications. So here's my attempt to fix that. Below is some code that starts up an HTTP server, and dynamically generates a simple "Hello, World" page:


-module(hello_world).
-export([start/0,service/3]).

start() ->
 inets:start(httpd, [
  {modules, [
   mod_alias, 
   mod_auth, 
   mod_esi, 
   mod_actions, 
   mod_cgi, 
   mod_dir, 
   mod_get, 
   mod_head, 
   mod_log, 
   mod_disk_log
  ]},
  {port,8081},
  {server_name,"hello_world"},
  {server_root,"log"},
  {document_root,"www"},
  {erl_script_alias, {"/erl", [hello_world]}},
  {error_log, "error.log"},
  {security_log, "security.log"},
  {transfer_log, "transfer.log"},
  {mime_types,[
   {"html","text/html"},
   {"css","text/css"},
   {"js","application/x-javascript"}
  ]}
 ]).
 
service(SessionID, _Env, _Input) ->
 mod_esi:deliver(SessionID, [
  "Content-Type: text/html\r\n\r\n", 
  "<html><body>Hello, World!</body></html>"
 ]).

To run it, save the code to a file called hello_world.erl, and create two subdirectories next to it called "www" and "log" (these subdirectories can be empty, but they need to be there for the server to start). Then fire up erl and run the following three commands:


Eshell V5.6  (abort with ^G)
1> c(hello_world).
{ok,hello_world}
2> inets:start().
ok
3> hello_world:start().
{ok,<0.51.0>}

You should now be able to browse to the following URL and see your message (if for some reason it doesn't work for you please let me know):

http://localhost:8081/erl/hello_world:service

For more info, here are the reference docs for the relevant Erlang modules:

inets

httpd

mod_esi

Erlang/OTP Source at GitHub

2008-04-25T15:04:00.006-05:00

I wrote a little script the other day to download all of the Erlang/OTP source releases that were available at erlang.org, and stick them in a single git repository. I've uploaded it to GitHub, if anyone's interested:

http://github.com/mfoemmel/erlang-otp/tree/master

I found out after the fact that archaelus had done something similar, and has a git repository hosted here:

http://git.erlang.geek.nz/?p=erlang-otp.git;a=summary

The main difference between the two is that the one at GitHub includes releases going a lot further back (R6B-0 vs R11B-5) - which is good if you're curious about how Erlang has evolved over time, but also means the repository is that much bigger when it comes time to do a clone (Erlang includes a bunch of binary files in their "source" releases, which don't seem to compress very well). Archaelus also includes a few 3rd party patchsets in his repository, which may be of interest.

The nice thing about GitHub, however, is that it makes it really easy for anyone to branch a project and make changes, and then make those changes available to everyone else (who can then merge them back into their own branches, and so on). Maybe this could help open up the Erlang development process a bit?

Erlang 12B-2 Released

2008-04-10T18:22:00.001-05:00

Looks like the second service pack for Erlang/OTP 12B has been released.

One nice change is that the percept application no longer depends on libgd. This should make compiling for Mac OS X a bit easier, since Leopard doesn't ship with GD by default.

They also appear to have fixed some of the other OS X related build issues that cropped up in the first service pack.

Switching to Blogger

2008-01-13T13:55:00.001-06:00

In an attempt to reduce the total number of machines in my life that I need to administer, I'm moving my blog over to Blogger. This will probably break my RSS feeds - my apologies. If you notice any other issues please let me know at blog@foemmel.com.

Erlang R12B Released

2007-12-05T22:02:00.000-06:00

New version of Erlang out today - release notes here.

For newbies like me, a big reason to upgrade is the much improved error reporting in the Erlang shell. For example, here's how the previous version reports a divide-by-zero exception:

Eshell V5.5.5  (abort with ^G)
1> 1/0.
** exited: {badarith,[{erlang,'/',[1,0]},
                    {erl_eval,do_apply,5},
                    {shell,exprs,6},
                    {shell,eval_loop,3}]} **

=ERROR REPORT==== 5-Dec-2007::23:32:41 ===
Error in process <0.31.0> with exit value: {badarith,[{erlang,'/',[1,0]},{erl_eval,do_apply,5},{shell,exprs,6},{shell,eval_loop,3}]}

New version:

Eshell V5.6  (abort with ^G)
1> 1/0.
** exception error: bad argument in an arithmetic expression
   in operator  '/'/2
      called as 1 / 0

Better!

I ran into one small hitch building the new version on my Mac, namely a "libgd not found" error while running "./configure". I installed version 2.0.36RC1 from here, which did the trick:

http://www.libgd.org/releases/

Periscope: An Agile Dashboard

2007-12-02T20:13:00.000-06:00

My colleagues Ben Erickson and Ben Feng have put together a nice little tool for tracking progress on Agile/XP projects, called Periscope. The idea is that you can use Jira (or potentially some other tool) to track your stories, and Periscope will occasioanally read that data, combine it with your build results, and generate reports indicating how far along you are.

It's still in its "alpha" stage, but I'd recommend checking it out.

Erlang: Initial Thoughts

2007-11-18T23:07:00.004-06:00

As an experiment, I recently tried porting some code from a Java project at work to Erlang, to see if that might be a direction we'd want to head in. The code being converted is very functional (e.g. almost all data structures are immutable) and easily parallelizable, so it seemed like a good fit.

I was hoping to quickly find some excuse for why Erlang wouldn't be suitable for the kind of work we're doing. The little voice in my head has been nagging me for a while that "Java is the wrong language for this project" and I was hoping to shut it up, a least for a while, so that I could get back to work.

But so far it's been pretty clear sailing. Erlang is famous for its concurrency features, but the thing that surprised me was how concise a language it is. Of the handful of classes I've converted, the Erlang versions were pretty consistently about 25% the size of the Java versions (and I'm sure they'll get even smaller once I know Erlang better).

The reasons for the big difference seem to be:

Higher-order Functions

A lot of our code involves iterating through lists, performing some action on each element, and aggregating the results. For example, in Java, if you want to go through a list of items and add up all of their "quantity" fields, you might do something like:


  public int totalQuantity(List<item> items) {
    int totalQuantity = 0;
    for(Item item : items) {
      totalQuantity += item.getQuantity();
    }
    return totalQuantity;
  }

Whereas in Erlang you can use higher-order functions ("map" in this case) to do this in one line:


  total_quantity(Items) -> sum(map(fun(Item) -> quantity(Item) end, Items)).

Erlang also supports list comprehensions, which can make things a bit more readable:


  total_quantity(Items) -> sum([quantity(Item) || Item <- Items]).

This is pretty standard functional programming stuff - no real surprises. (Java will hopefully improve on this front with the introduction of closures in JDK7.)

Pattern Matching

I was more surprised by how handy Erlang's pattern matching facilities were. For example, using a single "=" operator, you can do multiple things like check that a status code equals "ok", assert that a list contains at least two items, and extract the first item from that list:


{ok, [H|_|_]} = foo().

If you've only ever used languages where "=" means assignment, this statement may look a bit strange. I won't get into how it all works here, since it's a big topic, but I will say that once you get the hang of it, it's hard to go back.

From a language perspective, Erlang's pervasive use of pattern matching is probably what differentiates it most from some of the more mainstream programming languages. Patterns are used everywhere, including function parameters, case/if statements, and when receiving messages from other processes.

Tuples

Being able to create new data structures on the fly, without having to define a new class, is a big time saver. For example, to create a value representing an item and its quantity, you can just do:


Item = {"Carrots", 3}.

These types of structures are a pain to deal with in Java, since you need to create an entirely new class. It's easy to blame static typing for this, but the .NET folks can do something similar, thanks to anonymous types.

Summary

So, I've yet to hit any major roadblocks. That's not to say that Erlang isn't without its quirks - the error messages it spits out can be quite cryptic, and the way it deals with strings seems clumsy. But so far no showstoppers.

JRake and Raven

2007-01-29T12:00:00.000-06:00

Just a quick note to let everyone know that Matthieu Riou (creator of Raven) and I have decide to join forces, and are currently in the process of merging the JRake and Raven codebases. The work is being done in the Raven repository over at Rubyforge, for those of you who would like to follow along. The combined effort will eventually become Raven 2.0.

Matthieu has a few more details over at his blog, so check it out.

JRake, Part 4: Multithreading

2007-01-08T12:00:00.000-06:00

First off, I'd like to thank everyone for all the feedback I've received so far regarding JRake. It's been extremely helpful - please keep it coming.

One of the things I should probably clarify is that JRake, in its current form, is not really a standalone tool that people should be considering for real world use. It's a series of spikes, meant to kick JRuby's tires and to test out some ideas I've had for how to build a better build tool. I decided to blog about it as I was pleasantly surprised by how well it all worked, and thought others might be interested in seeing the types of things you can now do with JRuby (it's come a long way).

My hope is that JRake eventually will evolve into a production-quality tool, either as a standalone codebase or part of another project, but we're not there yet. In the mean time, all the features I mention here should be considered "experimental".

With that in mind, let's check out the next hack:

Parallel JRake

In the previous posts, we tackled performance by eliminating the number JVM startups during the build. In the end, we got that number down to zero, so we can't really follow that line of attack much further.

The next logical step (assuming we don't want to start tearing apart the actual javac code) is to start executing tasks in parallel, where possible. This won't help folks running on single-processor/single-core machines, and in practice won't really help folks who just need to recompile one or two files; but there's a potential big win for those doing clean builds on multi-processor/multi-core machines.

The idea is not new, and most existing build tools support at least some sort of parallel processing. For example, ant has a parallel task that can be used to execute subtasks in parallel, and (standard) rake has a multitask task. These are examples of explicit parallelism, as the user must declare exactly which tasks are to be run in parallel.

The alternative is implicit parallelism, which is supported by tools like make (via its -j option, explained here). In this case, the tool uses the dependencies specified in the build script to automatically infer which steps can be run in parallel. For example, consider a simple client/server application with the following build targets:

Here we have a "test" target, which depends on both the "client" and "server" targets, which in turn depend on the "common" target. There is no direct dependency between the "client" and "server" targets, however. A build tool that supports implicit parallelism will note this, and build those targets in parallel if it can. This can lead to big improvements in build times, depending on the complexity of the build script (more targets equals more chances for parallelism) and the type of computer its running on (the more processors the better).

Of the two, I believe implicit parallelism is the way to go. Multicore machines are becoming the standard, and the number of developers who will be able to take advantage of parallel builds is going to increase quite a bit over the next few years, so having that be the default makes sense. Plus it will be easier to bake it in from the start, than to try and tack it on later.

Implementation

To get it working, I ended up bypassing the normal Rake methods for determining execution order, and created my own TaskCoorindator class. It uses a pool of worker threads to handle task execution, while the main thread does the work of figuring out which tasks to submit to the pool. The worker threads use a blocking queue to communicate the results of each task execution back to the main thread.

Here's the TaskCoordinator code (for whatever subset of you happen to be familiar with both JRuby/Rake and the java.util.concurrent package):

class TaskCoordinator

 def initialize(pool_size=2)
   @thread_pool = java.util.concurrent.Executors.newFixedThreadPool(pool_size)
 end

 def execute(root)
   @result_queue = java.util.concurrent.LinkedBlockingQueue.new
   @leafs = Set.new # tasks with no prereqs
   @children = {} # maps task -> tasks it depends on 
   @parents = {} # maps task -> tasks that depend on it
  
   analyze_dependencies(root)
  
   @leafs.each do |leaf|
     execute_task(leaf)
   end
  
   # Keep pulling task results from the queue, until we get to the root target
   # Remove non-root targets from the dependency graph
   #   (i.e. delete the relevent members in the children/parent hash maps)
   # If this results in any tasks with no children (i.e. no more prereqs to execute)
   #   then submit that task to the thread pool for execution.
   while (result = @result_queue.take).task != root
     @parents[result.task].each do |posttask|
       list = @children[posttask]
       list.delete(result.task)
       if list.empty?
         @children.delete(posttask)
         execute_task(posttask)
       end
     end
    
     @parents.delete(result.task)
   end
 end

 def shutdown
   @thread_pool.shutdown
 end

private

 # Stores the relationship between the tasks involved in this 
 # build, using the "children" and "parents" hash tables
 def analyze_dependencies(task, analyzed=Set.new)
   return if analyzed.member?(task)
  
   analyzed << task
  
   prereqs = task.prerequisite_tasks
   if prereqs.empty?
     @leafs << task
   else
     prereqs.each do |child|
       (@children[task] ||= Set.new) << child
       (@parents[child] ||= Set.new) << task
       analyze_dependencies(child,analyzed)
     end
   end
 end

 # Wraps the task in a TaskRunner and passes it to the
 # thread pool for execution
 def execute_task(task)
   @thread_pool.execute(TaskRunner.new(task, @result_queue))
 end
end

TaskResult = Struct.new(:task, :exception)

class TaskRunner < java.lang.Runnable
 attr_reader :task

 def initialize(task, queue)
   super()
  
   @task = task
   @queue = queue
   @exception = nil
 end

 def run
   begin
     @task.execute
   rescue Exception => exception
     puts exception
     @exception = exception
   ensure
     @queue.add(TaskResult.new(@task, @exception))
   end
 end
end

Sample Output

I set up a simple build script using the client/server dependency graph shown above. The following output demonstrates how the build script runs when we only use one thread:

[pool-1-thread-1] common - begin
[pool-1-thread-1] common - end
[pool-1-thread-1] client - begin
[pool-1-thread-1] client - end
[pool-1-thread-1] server - begin
[pool-1-thread-1] server - end
[pool-1-thread-1] test - begin
[pool-1-thread-1] test - end

real    0m3.230s
user    0m0.007s
sys     0m0.013s

Just as we would expect: the tasks are executed serially and there is no overlap.

Below is the output when running with two threads:

[pool-1-thread-2] common - begin
[pool-1-thread-2] common - end
[pool-1-thread-1] client - begin
[pool-1-thread-2] server - begin
[pool-1-thread-2] server - end
[pool-1-thread-1] client - end
[pool-1-thread-2] test - begin
[pool-1-thread-2] test - end

real    0m2.542s
user    0m0.007s
sys     0m0.012s

As you can see, the "client" and "server" tasks overlap, and the total build time is reduced.

Danger

Unfortunately, Parallel JRake has the same problem as all multithreaded code: nondeterminism. With the exception of explicitly declared dependencies between tasks, users can't control the order in which things get executed.

Using the example above, this means that sometimes "client" will get compiled first, sometimes "server" will get compiled first, and sometimes they will overlap. In theory, we shouldn't care. However, if there is actually is some sort of dependency between the two tasks, but this hasn't been explicitly declared in the rakefile, the build might succeed one time and fail the next.

There are couple ways that I can think of to lessen the impact of this, though it can't be completely eliminated. One way is to use Raven style tasks, where the values for properties like "output directory" and "classpath" are automatically supplied by the tool itself (by analyzing the tasks dependencies). That way, the only way to get things to compile is to declare your dependencies correctly.

On top of this, it might make sense to introduce some nondeterminism even when running in single-threaded mode. For example, we could intentionally randomize whether we execute the "client" task or the "server" task first. That won't prevent bugs from occurring in the build script, but should help us catch them faster.

Source Code

Once again, I've made the complete project available via subversion, if anyone would like to play with it:

svn://svn.foemmel.com/blog/jrake/parallel

To run the server, go to the project root directory and run:

bin/jraked

You can then build specific targets like this (you'll need to have curl installed):

bin/jrake unit

bin/jrake clean

Alternatively, you can run builds from your browser, by visiting a URL like this:

http://localhost:3030/unit

http://localhost:3030/clean

Other Changes

I've also made a few other tweaks to JRake since my last post, in case anyone is interested:

You can now send an HTTP request to the JRake server to build any target, using the URL syntax: http://localhost:3030/targetname. The build log will be sent back to the client as text/plain so you can just use curl or wget to run builds. This eliminates the need for the JRake Shell.
The autoreload servlet will now only perform a reload when the use hits "refresh" in their browser. A "hard refresh" (ctrl-F5) is required in IE, and it doesn't work at all with Safari. So it still needs some work...

JRake, Part 3: Running

2006-12-18T12:00:00.000-06:00

So far, we've managed to compile and test our Java code using 100% JRuby. Now we just need a way to run it.

Assuming our application is web-based, the obvious solution is to wrap it up in a war file and deploy it into a container. But as anyone who has worked on a large project knows, creating and deploying war files can be a painfully slow process. Our original mission was to cut as much time as possible off our edit-compile-run cycle, so this clearly isn't the right solution. (We will need to generate war files at some point, of course, for deploying into production environments, but we'll save that work for another day).

Some app servers have an "autodeploy" feature that lets you deploy your app into an already running server, which is a huge step in the right direction - though things can still take a fair bit of time to deploy. Even when autodeploy works, it requires an extra alt-tab (command-tab for you mac users) over to the shell to kick off the build, followed by an alt-tab over to the browser to see the results, which wastes another second or two. There's also timing issue: if you hit "refresh" in the browser before the build and deploy have finished, you won't see your changes (or worse, you'll see some of your changes). So while autodeploy is definitely a big improvement, it's still not an ideal solution.

What we really want is for Java code to work the same way that dynamically typed languages do: you change your code, hit "save", and view the results in the browser.

JRake Server

I think I've managed to achieve something close to this, by setting up a Jetty server to act as a kind of proxy for my main application. Whenever a request comes in, it performs the following steps:

Calls out to the JRake script to compile any out-of-date code.
Creates a new classloader, and uses it to reload the application's main servlet class.
Creates an instance of the servlet and forwards the original HTTP request on to it.

The upshot is that I can now make changes in my IDE, and see those changes (almost) immediately in my browser. No new virtual machines are started up along the way, no extra alt-tabs are needed, and I don't have to worry about hitting the web page before the deploy is complete. These may seem like minor points, but when you're doing this stuff eight hours a day, those little annoyances can add up.

Here's the code for the main program, which starts up the Jetty server:

require 'java'
require 'reload_handler'

server = org.mortbay.jetty.Server.new(3030)
handler = ReloadHandler.new('lib/rakefile.rb', :main_compile, ['tmp/main/'], 'com.example.HelloWorldServlet')
server.set_handler(handler)

server.start
puts "\nHit  stop server\n\n"
$stdin.readline
server.stop

And the code for the reload handler:

require 'java'
require 'rake'
require 'jrake'

class ReloadHandler < org.mortbay.jetty.Handler

 # todo: Should extend AbstractHandler
 #   (need JRuby to support extending abstract classes)

 def initialize(rakefile, target, classpath, classname)
   super()
  
   @rakefile = rakefile
   @target = target
   @classpath = classpath
   @classname = classname
 end

 def handle(target,request,response,dispatch)   
   begin
     # Compile any out of date files
     Rake.application.clear
     load @rakefile
     target = Rake.application.lookup(@target)
     raise "Target not found: #{@target}" if target.nil?
     target.invoke

     # Load the servlet class, create an instance, and delegate to it
     servlet_class = load_class(@classpath, @classname)     
     servlet = servlet_class.new_instance     
     param_types = to_java_array(java.lang.Class, [
         javax.servlet.ServletRequest,
         javax.servlet.ServletResponse
     ])
     method = servlet_class.get_method("service", param_types)
     args = to_java_array(java.lang.Object, [request,response])
    method.invoke(servlet, args)     
  
   rescue Exception => e
       trace = "#{e.class}: #{e.message}<br/>#{e.backtrace.join('<br/>')}"
       response.writer.write("
         <html>
           <body>
             <pre>{trace}</pre>
           </body>
         </html>
       ")
   end
  
   request.handled = true   
 end

 def start
 end

 def stop
 end

 def setServer(server)
   @server = server
 end

 def getServer
   @server
 end
end

Again, I've set up a sample project that includes all the pieces - JRuby, Rake, Jetty, and associated scripts. You can get it from subversion here:

svn://svn.foemmel.com/blog/jrake/running

If you're interested in the scripts but don't want to download all the third-party stuff, just check out the lib directory:

svn://svn.foemmel.com/blog/jrake/running/lib

JRake, Part 2: Testing

2006-12-11T12:00:00.000-06:00

In my previous post I showed how to integrate JRuby/Rake with javac, in a way that eliminated the need to start up a new virtual machine for each compilation. This was fairly straightforward - I used JRuby's high level java integration to load the compiler class from the system classloader, then invoked its compile method.

Next on my list was integration with JUnit, which turned out to be a bit more complicated. I was able to load the main JUnit classes (e.g. org.junit.runner.JUnitCore) using the same high level mechanism as before, but for the actual test classes, I had to use a separate, non-system classloader. That way I could specify the location of my test classes from within the rakefile (as opposed to having to include those directories on the system classpath) plus I could recompile and rerun my tests without having to start up a new virtual machine.

In the end I got it working without too much trouble. The junit method below takes two arguments: the location of the directory containing the test classes, and the classpath to use when running the tests. It then creates a new classloader for the specified classpath, uses it to load the test classes, and passes those test classes into JUnitCore for execution:

def junit(test_class_dir, class_path)

# Append the test_class_dir to the class_path, if necessary
class_path += [test_class_dir] unless class_path.member?(test_class_dir)

# Make sure test_class_dir has trailing slash
unless test_class_dir[-1,1] == '/'
 test_class_dir = test_class_dir + '/'
end

# Scan test_class_dir for test class files
class_names = []
FileList["#{test_class_dir}/**/*Test.class"].each do |class_file|
 class_names << class_file[test_class_dir.length,
class_file.length - test_class_dir.length - '.class'.length].gsub('/', '.')
end
fail "No test classes found" if class_names.empty?

# Load the test classes via a new classloader
classes = load_classes(class_path, class_names)

# Run the tests
runner = org.junit.runner.JUnitCore.new
runner.add_listener(org.junit.internal.runners.TextListener.new)
result = runner.run(to_java_array(java.lang.Class, classes))
fail("Unit tests failed") unless result.was_successful
end

def load_classes(class_path, class_names)

# Make sure directories have a trailing slash, otherwise URLClassLoader ignores them
class_path.each { |element| element << '/' if FileTest.directory?(element) && element[-1,1] != '/' }

# Convert classpath elements to URLs
urls = to_java_array(java.net.URL, class_path.map { |element| java.net.URL.new('file:' + element) })

# Create a class loader for the specified class path
loader = java.net.URLClassLoader.new(urls)
return class_names.map { |class_name| loader.loadClass(class_name) }

end

Unfortunately, I had to use the internal JUnit TextListener to display the results of the tests, since JRuby doesn't currently support extending existing Java classes in such a way that I could provide my own subclass of RunListener. This will hopefully be fixed in a future version of JRuby.

Interactive JRake

Now, while all these classloading tricks are nice, they don't really help if all we do is start up the virtual machine, run the tests, shutdown, and repeat, since the original goal was minimize those startups. I've therefore created an "interactive" version of JRake, to keep the virtual machine warmed up between tests. All it does is sit in a loop, prompting the user for targets to build, and building them. A sample session looks like this:

jrake shell v0.0

Valid targets:
 clean        - deletes all generated files
 main_compile - compiles the main code
 unit_compile - compiles the unit test code
 unit_test    - runs the units tests
 help         - displays this help text
 exit         - quits the application

A blank line repeats the previous command.

jrake> main_compile
compiling 1 java file(s)...done
jrake> unit_test
compiling 1 java file(s)...done
.
Time: 0.009

OK (1 test)

jrake> clean unit_test
deleting 10 file(s)...done
compiling 1 java file(s)...done
compiling 1 java file(s)...done
.
Time: 0.002

OK (1 test)

jrake> exit

You can download the entire sample project via subversion here:

svn://svn.foemmel.com/blog/jrake/testing

Just run the "build.bat" or "build.sh" scripts with no arguments to bring up the JRake Shell. If any arguments are passed in, the behavior is the same as before i.e. the targets will be built then the script will terminate.

Next Steps

Now we just need to get the app up and running...

JRake, Part 1: Compiling

2006-12-06T12:00:00.000-06:00

For as long as I've been working with Java, I've been in search of a build tool that didn't drive me, and those around me, bat-shit crazy. I've come to realize I have two somewhat conflicting requirements for such a tool:

Must be based on a scripting language

Builds get complicated, and I need a tool that will let me do arbitrarily complex things, preferably in a well-known scripting language with lots of supporting libraries.
Must run on the Java platform

The Java virtual machine takes time to start up. Since most tools that deal with Java code (e.g. javac) are themselves written in Java, this means there is a rather annoying interval between when you invoke them, and when they start doing actual work. This delay may seem insignificant, but on a large project where a build consists of many calls to many tools and gets run many times a day, all that wasted time can really harsh your flow.

The solution is for the build tool to treat all of the supporting tools as libraries, not command line applications. For example, instead of calling javac directly, just invoke the method com.sun.tools.javac.Main.main(String[]). That way you only incur the VM startup time once.

The tools I've used in the past don't meet these requirements, of course. Specifically:

make fails on both counts (along with most other tools).
ant fails on the first count, as it's not based an existing scripting language. While it's true that you can drop down to Java and do complicated things by writing your own tasks, the context switch is pretty jarring. One problem is that you have the extra step of compiling your tasks before you compile your code - and therefore your build script now needs a build script. But the real issue is that Ant tasks only let you put custom logic at the task level, not at the level that actually manages the tasks. For example, if you want to define some dependencies between projects in one place, and use that to drive a bunch of build steps for each project, you're in for a tough time. It can be done (we used XSLT to generate ant scripts on one project) but it ain't pretty.
rake, running on top of standard C-Ruby, fails to meet the second requirement. However, Rake itself is a damn nice tool. See Martin Fowler's article for a good summary.

Rake and JRuby

The solution, obviously, is to run Rake on top of JRuby (I will henceforth call this two-headed monster "JRake"). That way we have the power of Ruby at our disposal, with all the snappy goodness of a JVM based tool. The trick is to get JRake to invoke the main javac class directly, without starting a new VM. This actually isn't much of a trick, since integrating with Java is exactly what JRuby was designed for.

And so, after a bit of trial and error, here is a rakefile that does just that. It compiles any out-of-date java files in the "src" directory and puts the resulting class files in the "tmp" directory:

require 'java'

task :default => :compile

task :compile do
 src_dir = 'src'
 dest_dir = 'tmp'

 Dir::mkdir(dest_dir) unless File::exist?(dest_dir)

 javac(src_dir, dest_dir)
end

def javac(src_dir, dest_dir)
 java_files = get_out_of_date_files(src_dir, dest_dir)

 unless java_files.empty?
   print "compiling #{java_files.size} java file(s)..."

   args = ['-d', dest_dir, *java_files]

   buf = java.io.StringWriter.new
   if com.sun.tools.javac.Main.compile(
 to_java_array(java.lang.String, args), java.io.PrintWriter.new(buf)) != 0
     print "FAILED\n\n"
     print buf.to_s
     print "\n"
     fail 'Compile failed'
   end
   print "done\n"
 end
end

def get_out_of_date_files(src_dir, dest_dir)
 java_files = []
 FileList["#{src_dir}/**/*.java"].each do |java_file|
   class_file = dest_dir + java_file[src_dir.length,
 java_file.length - src_dir.length - '.java'.length] + '.class'
  
   # todo: figure out why File.ctime doesn't work
   unless File.exist?(class_file)
 && java.io.File.new(class_file).lastModified > java.io.File.new(java_file).lastModified
     java_files << java_file
   end
 end
 return java_files
end

def to_java_array(element_type, ruby_array)
 java_array = java.lang.reflect.Array.newInstance(element_type, ruby_array.size)
 ruby_array.each_index { |i| java_array[i] = ruby_array[i] }
 return java_array
end

If you want to play around around with this script but can't be bothered to install JRuby, Rake, and the other bits, I've created a complete "Hello World" project that includes everything you need. You can get it from subversion here:

svn://svn.foemmel.com/blog/jrake/compiling

Just checkout the project, make sure JAVA_HOME points to your JDK, and run the "build" script to see it go.

Next Steps

I've gotten JUnit and a few other cool things working with JRake, which I'll write about in my next post.