Tuesday, December 11, 2007

Concurrency-Oriented Programming

You may have read Todd's earlier post about Erlang. We like it, in part, because it's designed for concurrency. We can write highly concurrent programs without fighting a continuous uphill battle against races and deadlocks. In fact, we barely worry about these things at all. Does this sound like magic to you? It's real, and it's quite relieving. We don't owe this debt to the presence of some clever language feature. On the contrary... Erlang's strength is in the absence of a particularly detrimental feature.

Mutable data.

Yes, we have essentially declared war on the assignment operator. Does this sound bizarre to you? How do we do without it? Well, a long time ago, delete and free() were pretty important. Language designers got rid of them, programmers had a paradigm shift, and we all moved on. Today's assignment operator is evolving into something new... the single-assignment operator. You instantiate a chunk of data, assign an initial value, and promise never to modify it.

The danger of mutability becomes apparent when we investigate the causes of race conditions. You may have noticed that read-only data structures don't need to be locked. Readers don't race with each other. Put a writer on the scene... and locks have to be introduced. Figuring out your locking is probably the most painful and least forgiving part of coding. So, if we nip the problem in the bud, and make all data read-only... then we obviate the need for locking.

The absence of mutable data makes concurrency a trivial problem.

If we can't change our data, how do we pass information between threads? We use a special language construct to do this... message passing. It takes 3 easy steps. Prepare the message you want to send, aim it at another thread, and fire. It is just like opening a socket and sending data over TCP/IP. As long as the language designers provide a sound implementation, you won't have to worry about race conditions.

The next question is, if we can't change our data... how do we program at all? Namely, how do we maintain state? Well, believe it or not, Erlang has a solution for this as well. It's called concurrency-oriented programming, where processes each maintain private state. By making processes extremely lightweight (quick to spawn, completely user-level, having a memory footprint of a few hundred bytes) we can replace objects with processes.

This is the Java code for a thread-safe counter:

class Counter {

private int value;

public Counter(int value) {
this.value = value;
}

public synchronized int get() {
return value;
}

public synchronized void incr() {
value++;
}
}


This is the Erlang code for a thread-safe counter:

-module(counter).
-export([new/1, get/1, incr/1]).

new(Value) ->
spawn(fun() -> loop(Value) end).

get(Counter) ->
Counter ! {self(), get},
receive
{Counter, Value} -> Value
end.

incr(Counter) ->
Counter ! incr,
ok.

loop(Value) ->
receive
{From, get} -> From ! {self(), Value}, loop(Value);
incr -> loop(Value+1)
end.


There you have it. We've translated a stateful, encapsulated object into a stateful, encapsulated process. Notice we haven't used the assignment operator. It took just a little bit more code (note that Erlang provides nice libraries to abstract away the looping and the message passing). Feel free to instantiate as many as you want; processes are about as cheap as objects.

Inexpensive concurrency makes the absence of mutable data a trivial problem.

The benefits here are numerous. It is automatically race-free, and does not use lock-based synchronization. Work can be done asynchronously (a function can essentially return a value before finishing its computation). The process and caller can transparently live on different machines.

This also fully exploits the power of multi-core processors. An Erlang program might have millions of processes (just like a Java program could have millions of objects). Therefore, you will not exhaust your speedup potential until you're using a million-core processor. Whereas, a Java program with 10 threads maxes out on a 10-core processor, and does not speed up when adding more cores.

I haven't even discussed internals, like garbage collection, which leverage immutability immensely.

While OOP provides proper encapsulation and modularity... COP takes us to the next level and helps us embrace our highly-concurrent world. It's time for another paradigm shift.

No comments: