22 Feb 2015

Non-blocking Programming Languages

Most programming languages support blocking calls for long-running operations like I/O and network operations like RPCs. They also support asynchronous, callback-based interfaces, but that’s always in addition to synchronous, blocking calls, not instead of.

Javascript is perhaps the language that’s known most for the asynchronous style of programming, but Javascript also supports blocking operations, such as synchronous XmlHttpRequest and alert(). When you call alert(), it puts up a dialog box, and doesn’t return until the user dismisses it. What if we get rid of these blocking method calls, and make everything non-blocking?

Can we design a programming language that does not permit blocking calls [1]? What benefits might such a language have?

If you have blocking calls, you need multiple threads to do things in parallel. Threads have a number of problems:

- Thread switches happen at non-deterministic times, causing race conditions [2].

- Creating too many threads causes lower performance because of the overhead of switching between them. It’s often not clear how many threads to create to make optimum use of the CPU. For example, if you have a server that supports 8 hardware threads, how many threads should you create, assuming you’re the only task running on the server? 8? No, because each of your threads will spend some of its time blocked, so you probably need more than 8. But is that 10? 20? 200? 2000? You have no idea.

On the other hand, if threads can’t block, then you can create exactly as many as the CPU supports hardware threads, and know that you’re making optimum use of the CPU. You’re not losing any performance to excessive context-switching, nor are you leaving any of the CPU capacity unused and therefore wasted.

- Threads suffer from deadlock.

- Threads give you no control over scheduling. But with an event-driven approach, you can choose which task you take up next for execution using logic that makes sense for your application.

Many or all these problems will go away if you have a language that doesn’t permit threads to block.

In most languages, writing blocking code is easier, while asynchronous calls impose less overhead. This becomes a tradeoff between programmer productivity and efficiency, which in turn translates into things like the number of servers you need to serve a given amount of traffic, which boils down to the cost of running your service.

Some languages like Go have tried to resolve this tradeoff by reducing the performance overhead of threading, thus encouraging programmers to create as many as needed, and to writing blocking, synchronous code. But performance is only one problem with threads, as we’ve seen above. So I’d like to look at this problem from the other direction: Why should asynchronous code be harder to write and later read than synchronous, blocking code? Might we design a language that makes asynchronous, callback-based code just as easy?

I have a proposal to do that.

Imagine a function that generates a string saying, “Hello <name>”:

String getGreeting() {
   String name = getName();
   return “Hello ” + name;
}

This is blocking code, and is trivial to follow.

Now suppose the getName() method was changed to become asynchronous. That is, instead of returning a String, it returned a Promise<String>. A Promise is an object on which you add a callback [3], like this:

Promise<String> promise = getName();

promise.addCallback(function(String name) {
   // Do something with name.
});

So, if getName() becomes asynchronous, we’d normally have to change its caller, getGreeting() to something like:

Promise<String> getGreeting() {
 Promise<String> nameCallback = getName();

 return new Promise<String> {
     public void addCallback(Callback<String> callback) {
       nameCallback.addCallback(function(String name) {
         callback(“Hello ” + name);
       });
     }
   };
}

Here, we’re creating a new Promise that builds on top of the earlier promise, and does a string concatenation. Notice how much more convoluted and hard to read this is. You can immediately see the problem with writing asynchronous code in Java-like languages.

But what if the compiler could transform the original code into the asynchronous version? The only thing the programmer needs to do is to change the return type to a Promise. Here’s the original method again:

String getGreeting() {
  String name = getName();
  return “Hello ” + name;
}

Now, if getName() becomes async, the programmer should have to only change the return type to:

Promise<String> getGreeting() {
  String name = getName();
  return “Hello ” + name;
}

The compiler should figure out the rest. How would it do that? Well, if you were to run this code through a Java compiler, for example, you’d get two errors: one saying that the compiler doesn’t know how to convert a Promise<T> to a T, and likewise a T to a Promise<T>. But these operations are straightforward.

Let’s first look at converting a T to a Promise <T>. If I have a method

Promise<String> getGreeting() {
   return “Hello”;
}

This code effectively requests the compiler to convert a T to a Promise<T>. It’s trivial for the compiler to do so, by transforming the code into:

Promise<String> getGreeting() {
  return new Promise<String>() {
     public void addCallback(Callback<String> callback) {
       callback(“Hello”);
      }
   }
}

This transformation effectively converts a T to a Promise<T>.

Conversely, if I have a method:

void doSomething() {
   String name = getName();  // getName() returns a Promise<String>.
   System.out.println(name);
}

This code effectively requests the compiler to convert a Promise<T> to a T. It’s easy for the compiler to do so, by transforming the code into:

void doSomething() {
   Promise<String> namePromise = getName();
   namePromise.addCallback(function(String name) {
     System.out.println(name);
   });
}

This transformation effectively converts a Promise<T> to a T.

These are powerful transformations. Putting the two together, the compiler can transform

String getGreeting() {
   String name = getName();
   return “Hello ” + name;
}

into

Promise<String> getGreeting() {
   Promise<String> name = getName();

   return new Promise<String> {
     public void addCallback(Callback<String> callback) {
       name.addCallback(function(String name) {
         callback(“Hello ” + name);
      });
     }
   };
}

The outer callback is for the return [T -> Promise<T>], and the inner callback is for getName() [Promise<T> -> T] [4] [5]

So, putting all this together, if you start with synchronous code

String getGreeting() {
   String name = getName();
   return “Hello ” + name;
}

… and getName() suddenly becomes async, the programmer should have to only change the return type:

Promise<String> getGreeting() {
   String name = getName();
   return “Hello ” + name;
}

… and leave everything else for the compiler to take care of. Asynchronous code is as easy to write as synchronous code [6]. To handle situations where a synchronous method becomes asynchronous, it’s easy to have a refactoring tool that goes and changes the return types of all its callers, which in turn changes the return types of THEIR callers, and so on. That’s all that’s needed to convert synchronous code to asynchronous. The compiler handles the rest.

The conclusion is amazing: that asynchronous code is no harder to write than synchronous code, if the compiler can do some basic code transformations. This in turn means that we can have a programming language that doesn’t permit blocking for I/O or other external operations, which in turn brings a whole host of advantages.

[1] Leaving aside hacks like busy waiting:

while(time() < targetTime) {
}

[2] Languages like Go have try to make such bugs rare, by having processes that communicate by passing messages rather than by threads that directly access shared memory. This is good, but doesn’t eliminate the problem — when a process receives a message, it acts differently based on its internal state. A message received at a different time may have a different result, or change the state of the process in a different way. Which means that we can still have the problem of race conditions, because exactly when a message is received is non-deterministic.

[3] Adding a callback is the only thing you can do on a Promise. Unlike Java’s Future, there’s no get(), since we don’t want to block.

[4] The inner one is nested in the outer one, because the alternative doesn’t make sense – the return statement should be outside the callback. If it were inside, first callbacks have a return type of void, so a return statement doesn’t belong there. And getGreeting() has a non-void return type, so it needs a return statement.

[5] Alternatively, the compiler could transform the code into:

Promise<String> getGreeting() {
   Promise<String name = null;

   return new Promise<String> {
      public void addCallback(Callback<String> callback) {
        if (name == null) {
          name = getName();
        }

        name.addCallback(function(String name) {
        callback(“Hello ” + name);
     });
   }
 };
}

This code has the effect of not getting the name if there isn’t a callback registered to receive the name. This could save RPCs or database requests or other heavyweight operations if the results aren’t needed. This could be because of an oversight on the part of the programmer. Or it could be that the results of the aysnc call are used in only some cases. If that is the situation, only those calls whose results are used are made. This could save resources and be a powerful optimisation.

But, if the results are in fact used, delaying the request adds latency to the overall process. So, this optimisation is probably not safe for the compiler to make by default. Maybe this can be triggered only if the programmer puts a @Lazy annotation on the original method. Or it can be the default, and turned by off by @Eager annotation.

[6] If you have many asynchronous calls in a function, like:

String getGreeting() {
   String firstName = getFirstName();
   String lastName = getLastName();
   return “Hello ” + firstName + lastName;
}

the compiler converts it into code that calls getFirstName(), and when the result is available, calls getLastName(), and when ITS result is available, does a concat.  The compiler can’t parallelise getting the first and the last name, because that changes the execution order of the code. Programmers normally expect (synchronous) code to execute in the order in which its written, and changing that will cause bugs. For example, the first call can change some global state (or change the state of an external system such as a database or the file system) which affects the behaviour or return value of the second call. In general, these optimisations are not safe for a compiler to automatically make. Yes, this means that the code will be less efficient than it could be, such as waiting for two RPCs one after the other when it could parallelise them. But it’s the only safe option.

But what if the programmer explicitly wants both the getters to execute in parallel? Then he can write:

String getGreeting() {
   Promise<String> firstName = getFirstName();
   Promise<String> lastName = getLastName();
   return “Hello ” + firstName + lastName;
}

The only change is the type of the local variables firstName and lastName. The code still executes in order. But since the first statement no longer tries to convert the Promise<String> to String, it doesn’t need to block the execution of subsequent lines of code. The only blocking happens in the last line, where the string concat implicitly converts Promise<String> to String. But by then, both RPCs have been fired in parallel.

Note that both this code and the original version of the code implicitly convert a Promise<String> to a String, just at different places in the code. The original version did:

String firstName = getFirstName();

which implicitly converted a Promise<String> to a String.

The new version does:

Promise<String> firstName = getFirstName();

return “Hello ” + firstName + …;

here the Promise<String>  to String conversion is being implicitly done in the concatenation. But at a high level, both versions of the code rely on implicit Promise<T> to T conversions.

No comments:

Post a Comment