Java to the Limit

Why I Want to Learn Erlang

Some time back, I started to take a serious look at Erlang. I would like to take the time to share with you why I think it is an important thing to learn.

Before we start, perhaps it would be in place to say something about where I am coming from. I am CTO of Trifork, a Danish software and consulting house with some 120+ employees. We mostly make relatively large information systems, one example is the new nation wide danish shared medication records system. We have been quite successfully building these systems with Java for the last 10 years, and that is all fine and dandy indeed. It is always dangerous to "change horses" - if it ain't broken, don't fix it?

I think there are two trends in particular that are challenging, and will eventually push us to consider new implementation technologies.

We routinely build distributed systems. Call it cloud computing or whatever. We are getting a lot of benefits from building systems that utilize existing network-available services. However, the challenge in this is that our systems are increasingly consisting of complex interconnected systems, which are distributed, they may sometimes be down or otherwise unavailable, or in general just outside of the control of the team building an application.

Computers are no longer getting faster. We have reached the limit of how fast a computer can be; and so the only way forward is to use more computers or multi cpu/multi core computers. So we need to figure out how to program such beasts effectively, both in terms of raw performance, and in terms of our ability to mentally manage and reason about such, so that we can build them with some repeatable success and also understand and maintain them afterwards.

Java has been good to us, indeed. For many of us in the software industry Java has grown and matured and become a reliable work horse for building these kinds of information systems. It was conceived in another time however, and it's limitations in terms of meeting the above two challenges are starting to hurt.

Moving forward, I think the most important thing to learn - as a software professional - is to learn tools that enable asynchronous programming which is - I believe - the "key" to tackle the challenges mentioned above. We need to do away with this fundamental thinking of ours, that all interactions are request-reply style; but that it should be just as natural to just send one-way messages. With request-reply style (synchronous), you escalate problems too easily and introduce a lot of waste. Michael Nygard's splendid book Release It has several good examples of this for Java folks.

In Erlang, asynchronous programming is the default. It is the fundamental building block, and they have figured out the things that the language need to be able to cope with it.

I have this strong sensation that "erlang people" some how have a magical ability to cope with asynchronous programming. And I think that ability comes from the mental model that Erlang gives them. And that is why I want to learn Erlang.

Asynchronous programming cannot stand on it's own, in particular if you want to use it in combination with parallel execution. It needs language support, or you will shoot yourself in the foot. This is why I am luke-warm on Scala's actors: if the language does not force you to not share mutable data, it is too tempting to do it. For some things like this, you don't want a policy, you want law. A cool (new) thing is node.js, which is asynchronous but single threaded - fine indeed.

So what is Erlang's role? Well, it was really built as an platform for building infrastructure - telco infrastructure. It is not a system's programming language like C or Go. I am also not sure if it is good for writing end-user applications. I think it is mostly for these "things in the middle". From what I have learned till now, I see Erlang as a programmable middleware that can replace a lot of the stuff we do today, for coordinating and distributing applications.

Erlang also has many other things to teach us, I think. Erlang was built as a tool to create not just distributed but reliable distributed systems. And people often forget the "reliable" in distributed systems. How is it that Erlang can help us make distributed systems reliable?

Erlang is also a functional programming language. But it is so with a twist, that makes it much more amenable for us object-heads. Inside of a process, Erlang is functional. But when you look at the system as a whole, it is not - each process is like an object with state. And the way you communicate between these "objects" is so that you cannot change other process' state. The process has to willingly receive a message ann act on it.

From what I have seen now, it looks good and I want to learn more. It feels good to learn Erlang.

Yet Another Ruby-on-JVM implementation (dormant project)

A few years back - about the time when JRuby started getting traction - I was also working on a JVM-based Ruby that I called HotRuby (and yes, I do know that there is also another project by that name).  The project has been dormant for two years, but recently Charles Nutter asked me about it, and so I promised to make it available.   It's up on GitHub here: http://bit.ly/5XrKA2 .  I did a talk to the London Ruby User's Group which is also linked from the GitHub wiki.

Nobody has been actively working on this for several years.  I did this as an exercise learn Ruby and I stopped, when I decided that I didn't particularly like the language, and I was overwhelmed by the amount of cruft in the core libraries that needed bug-for-bug compatibility to be useful.  

The VM is at the state where it can run some simple performance tests, and it can kind-of run RUnit.   

An interesting aspect of this project is that it does a two-phase compilation (similar to hotspot).  First, it generates byte codes (not JVM ones), and runs an interpreter on that.  This is much faster than running an AST interpreter. Then later it selectively performs an "agressive" compilation on hot methods, turning the code in to JVM code.  The purpose of this is the same as for Java HotSpot - get up and running fast, and only spent time and effort where it matters.  "agressive" compilation means that it specializes methods for the receiver type, so it compiles methods to JVM under the assumption hat "self" has a specific statically known type.  This permits access to ivars to be very fast.

Both the interpreted and compiled mode run on the same MOP, so object-layouts are decided early.  When a Ruby-level class is instantiated the first time, I generate a class for it in which all the instance variables that are referenced in methods applicable for that objet are turned into real java fields.  

The interpreted mode runs at ~MRI performance, and with compilation-to-jvm enabled it can run as much as ~2.5 x YARV performance.  Or at least that was the numbers back when I did the presentation/demo for LRUG.

This was before there was anything called invokedynamic.  Method lookup in HotRuby is done via a "JVM-bytecode compiled HashMap" thing.  Think of the method lookup table as a hash map (sitting at the call site), in which each potential receiver type is a key.  Then, I implement something similar to Self's PIC (Polymorphic Inline Caching) by dynamically bytecode-generating a new class whenever this lookup table needs to have a new key inserted. Urgh!  It ends up generating a lot of classes, but it is fast because a method invocation turns into a double virtual dispatch and a cast.  If the cast fails, then it is because the compiled hash-map needs to be re-generated.

So perhaps this can be used as inspiration for furhter JRuby work, or inspiration for other people.  I'm happy to answer any questions you might have.

Kresten

Tail recursion in Erjang

Tail-recursive calls are important for Erlang indeed.  If you need to know why, you'll have to read that elsewhere.  In this blog post I'll explain how Erjang handles tail-recursion.

When functions are self-recursive (the trivial case), a tail-recursion simply turns into a loop.  For other cases things get a little more involved.  Luckily however, it turns out to be quite efficient. Here is an outline of how Erjang does it:

• Every function is compiled to a class F with one method named body(EProc proc, EObject arg1, ... EObject argN).  The function takes the EProc (a reference to the light-weight process) and the N arguments. The class F is marked final.  This function contains the result of compiling an Erlang function into Java.
• If the function takes 2 arguments then F is a subclass of class EFun2, a class provided by Erjang.  Erjang has a class loader that triggers when such a class is missing and generates EFunN classes on the fly. 
• From the generated superclass, class F inherits the virtual methods invoke(EProc proc, EObject arg1, ... EObject argN) and go(EProc proc).  

A normal call is encoded by simply calling F_instance.invoke(proc, arg1, ... argN), where F_instance is a statically allocated instance of class F.

A tail-recursive call to function G (assuming two arguments) is encoded thus:

• // save the arguments into fields of the EProc object
  proc.arg1= value1; proc.arg2 = value2;    
  
• // save the target function singleton object a field of the EProc object
  proc.tail = G_instance                       
  
• // return a special global singleton tail marker.
  return TAIL_MARKER;   

The method body (which contains the real function body) is never invoked directly, but always indirectly via invoke or go.  Those two functions collaborate to ensure that the caller never sees the TAIL_MARKER.

• Method invoke(EProc proc, EObject arg1, ... EObject argN) is used for "normal" invocations, and what it does is to first call res = this.body(proc, arg1, ... argN), and then loop as long as res is the TAIL_MARKER, repeatedly calling res = proc.tail.go() until the result of the tail-recursion is available.  
• The method go simply calls this.body(EProc proc, EObject arg1, ... EObject argN) by taking the argument values from the proc object.  Notice here that this refers to the function called in tail-position (G_instance) above.

Closures are encoded in a similar way, but the free variables are saved in a fresh instance of the Fun object, so they can be used repeatedly.

The net effect of all this is that

• We preserve proper tail-recursion semantics in the sense that the stack doesn't grow.  A tail-recursive call pops a call frame (returning from body) and creates a new one (called from go).
• Other aspects of the code generation ensure that function objects like F and G in many cases statically typed whenever possible, the JVM can inline calls to invoke andbody (remember, they are final classes).  This is the case whenever calling non-external functions.
• The final touch is this: saving arguments into the proc object is surprisingly cheap, because it is very likely to be on CPU-cache.  Granted, it does require memory access, but on a modern processor it is probably not more expensive than saving them to the stack!

The overhead of all this is naturally a class with one method per function.  Similar to how most other functional languages on JVM or CLR do it.

Further to this is that the JVM is likely to support tail calls in the near future, it seems.  With native tail-call support we might do even better, but this encoding is actually already surprisingly fast.  

As Per Bothner points out here, this is similar to other techniques.

Erjang, Why?

It's been three days since I announced the existence of Erjang - a JVM-based Erlang VM - and I thought it would be appropriate to do a wrap-up of the comments received so far.  Mind you, there is no release, just a bag of files over at github. 

But Why?

Some commenters question the very idea of doing an Erlang on the JVM, asking - assuming it is doable - why this is even a good idea.  Erlang already has a great VM, so why another one?  See for instance the discussion here at reddit.

• Erjang is different from BEAM (the Erlang VM).  It will never have the same (soft) real-time characteristics that BEAM has.  For instance,
  • With Erjang, you will will experience global garbage collection every once on a while, whereas with BEAM this doesn't happen because every process has it's own heap.
  • The flip side of this is that Erjang doesn't copy messages, so you can pass large data structures (immutable, of course) between processes at minimal cost.  This is ideal for sharing things like persistent data structures (as Clojure has them). [in fact, integrating clojure is an interesting idea to work on...]
  • So from this, Erjang can feasibly provide better over-all performance, assuming you can live without the real-time promises.   
• Erlang is a great language, even for applications that don't have soft real-time requirements, but "just" want the great concurrency model, the distribution features, and the extensive set of Erlang libraries. 
• A good language deserves more than one implementation, so I think Erjang will only further strengthen it's reach.
• IMHO, the best thing about Java is it's virtual machine. [In fact the language is horrible in many ways and I am not proud of having been part of putting generics in there].   The JVM however - is the finest piece of machinery built since I don't know when, and it is an area that has received enormous engineering and innovation attention the last 15 years.  In particular the HotSpot team (folks with Self-DNA) and the IBM VM's (people with OTI-dna) have done great things. I have been following these, and it is clear to me that virtual machine technology is an area where other people still have a lot to learn [hello, CLR team!].
• The Java platform is widely trusted and depended upon.  Granted, there has also been many failures, but that comes with the success of the platform.  I think providing a Java-based implementation of a language strengthens its position, because it makes it an easier choice for some.  

Even if Erjang is not as fast as BEAM, it might be a sensible choice for some.  

• Erjang can run within a WebSphere or WebLogic server with no "native code".  Maybe that will make it a good choice when organizations are "stuck" on those platforms, for whatever reasons.
• Erjang can potentially run anywhere there is a decent JVM, which includes stuff like AS/400, extending the reach of the platform.
• Erjang can directly use existing java-based integration infrastructure out there.  And there is a lot of that.

But I think - and hope - that Erjang will be faster than BEAM.  But probably, there is some way to go before we match HiPE.  What do you think?

An Instantaneous Surprise

The other day I downloaded Google's Protocol Buffers tools for a project I was working on. It took a while to compile the tools; ok; but the real surprise was the speed of the tools themselves. Wow; I had [almost] forgotten how fast a C/C++ program launches! Just enter protoc --java_out <file>; hit enter; and boom it is instantaneously done. I was amazed; perhaps I have been living too long in Java land?

Programming

The Cache is the Killer

I've been doing business finding people's memory leaks for a number of years, and it is a recurring problem for people to manage caches in large Java applications. As is often the case, caches are inserted to improve performance, but often they end up causing more trouble than they solve.

The typical killer cache looks like this:

   Map cache = Collections.synchronizedMap(new HashMap());

This kind of cache has two fundamental flaws:

• the cache is never cleared of old/stale entries
• this cache will certainly cause heavy lock congestions

In fact, I typically scan the code looking for any use of Collections.synchronizedMap, and then try to figure out (ask the developers) if they think this is something that may be used often.

There are many simple things that can be done to handle this. The easy solution is to find an open source implementation of a real cache somewhere, such as OSCache. OSCache is quite simple to use, simpy do something like this:

  // public Cache(boolean useMemoryCaching, 
  //              boolean unlimitedDiskCache, 
  //              boolean overflowPersistence, 
  //              boolean blocking, 
  //              String algorithmClass, 
  //              int capacity)
  //
  com.opensymphony.oscache.base.Cache cache = 
       new Cache(true, false, true, false, null, 1000)

Setting capacity to zero creates an unlimited cache; setting it to a given size will create a »least recently used« (LRU) cache. Enabling overflow persistence (in combination with a capacity) ensures that data is kept in the cache, but the least recently used ones are chosen to be »swapped« to disk when the capacity is reached. Disk overflow requires that objects are serializable, which may be an issue in many contexts. Setting blocking to true will make readers wait for each other while the cache content is being constructed/loaded from the source.

With OSCache, the interaction with cache.getFromCache throws a NeedRefreshException if the entry is missing. In such cases the caller must either call cache.putInCache(key,content) or cache.cancelUpdate(), a reasonable pattern looks like this:

  Object getValue(String key, boolean createIfAbsent) {
     try {
        return cache.getFromCache(key);
     } catch (NeedsRefreshException ex) {
        if (createIfAbsent) {
           Object content = locateContent(key);
           if (content == null) {
             cache.putInCache(key, content);
           } else {
             cache.cancelUpdate();
           }
           return content;
        } else {
           cache.cancelUpdate(key);
        }
     }
  }

The above code will do something reasonable regardless of the cache configuration. The operation locateContent is intended to be whatever is needed to get the relevant content entry.

If you're using an unlimited cache (for instance, when you use overflowPersistence), then you need to have a mechanism in place to remove cache entries. You can do this by passing an EntryRefreshPolicy to cache.putInCache. For instance, to use a 60-minute cache expity, do:

 static EntryRefreshPolicy EXPIRY = 
      new ExpiresRefreshPolicy(60);
 ...
 cache.putInCache(key, content, EXPIRY);

If the cache is somehow tied into a JSP/Servlet application, You may well want to tie the caching strategy to session. This can be done by defining am javax.servlet.http.HttpSessionListener, and then use OSCache grouping to group cache values in the same HttpSession. The method HttpSessionListener.sessionDestroyed() can then be used to remove all cache entries that belong to the given session. Implementation is left as an exercise to the reader.

Some Objects are more Serializable than Others

Quick java puzzle: What does this program print?

  import java.io.*;
  class A { 
    public A() {  System.out.print("A");  } 
  }
  class B extends A implements java.io.Serializable { 
    public B() {  System.out.print("B");  } 
  }
  public class Test {
     public static void main(String[] args) throws Throwable {
       ObjectOutputStream oo = new ObjectOutputStream(
          new FileOutputStream("/tmp/xx"));
       oo.writeObject(new B());
       oo.close();
       System.out.println("--");
       ObjectInputStream oi = new ObjectInputStream(
          new FileInputStream("/tmp/xx"));
       B b = (B)oi.readObject();
       System.out.println("--");
     }  
  }

Welll, I'll spare you the thinking and go straight to the answer, which is

  pc-183:/tmp krab$ java Test
  AB--
  A--

When reading an instance of B from the serializable stream, class B's constructor is not called! This blog is about why that is so, and the kind of trouble we had to go through in our Java EE implementation because of this.

Here's an interesting piece of history: The only piece of Trifork's Java EE implementation which is not »pure« is hidden within our RMI/IIOP implementation. You may ask why we implemented RMI/IIOP ourselves, so let me answer this before I dive into the actual subject of this posting: Having our own implementation of CORBA, RMI and the integration between these two allowed us to simplify many other things by using the same invocation mechanism universally for local and remote EJB invocations. Further, having the code under our control allowed us to architect everything together for better overall performance. These advantages came however at a pretty high price, since maintaining this part (ans especially interoperability with other peoples CORBA, RMI and/or RMI/IIOP implementations has been a challenge).

Whereas most of RMI logic can be expressed in terms of what is possible with Java reflection, there are two places where java.lang.reflect comes short, both of which are related to object creation in context of unmarshalling.

• when you need to instantiate (unmarshal) an object using the special »serializable« semantics, in which constructors are not called.
• when you need to deserialize an object with final instance variables

For almost any kind of Java field, java.lang.reflection provides means to assign values to them - even private and other hidden fields. Class java.lang.reflect.Field has this magic method setAccessible which allows one to circumvent access rules (if you have authority to do so). Static variables are never transferred as part of serialization, but, but, but, ... there is no magic wand that grants write-access to final fields within the Java realm. For a long time, we had a piece of native code hanging around to handle this, because surprisingly enough JNI's equivalent of java.lang.reflect.Field does allow assigning values to final fields. But it was always a burden to carry a chunk of native code around, and kind of annoying when it was just this tiny little piece, so we figured a hack was in place, and started writing some JVM-specific code to access the classes used to implement java.lang.reflect.Field.

So, the hack for final instance variables is to use sun.misc.Unsafe. This singleton object is available for HotSpot implementations and gives access to not just read/write any kind of field but also many other things. For HotSpot-based JVMs and most of IBMs VMs this hack is also avaiable.

As for handling classes that have no default constructor, we have to follow a similar - albeit much more ugly - hack. Reverse-engineering java.io.ObjectStreamClass lets one find the - typically private static (and native) - methods that can do this for a given VM. The semantics needed is to (a) create a new blank instance of the given class, and (b) find the first superclass of the given class which is not serializable, and then call it's no-arg construtor. If the first such not-serializable class does not have a default constructor, the algorithm fails. For example:

class A extends Object { 
  A() { print("A"); } 
} 

class B extends A { 
  B(int x) { print("B"); } 
} 

class C extends B implements Serializable { 
  C() { super(1); print ("C"); } 
} 

When you say »new C()«, it will print »ABC«, but if such an object is deserialized, it fails! since class B does not have a default constructor. In this case, class C is not serializable at all. Interestingly enough, this is not verifies when the object is written to an ObjectOutputStream, so you're up for a surprise. Even though class C has a default constructor, it not called.

For the intersted reader, out RMI/IIOP implementation is now part of Apache Yoko.

Welcome

I just realized, it's ten years since I started programming Java, and I am still to write a "real Java program".

Although I have written thousands of lines of Java code, it has almost exclusively been Java programs that control or reason about other Java programs. Not real programs in the sense that there is some "normal user" out there. I've worked my way through a J2EE stack (Trifork T4), various other Java middleware, Java profilers, and even a JVM.

Even during five years with Objective-C (including my time at NeXT), I never wrote a "real Objective-C program" either. I guess this is just my place in life.

All the way thorugh this endavour, I have often been working at the "border of doable" in Java, a place where most people never come. It's like an exotic trek, or vacation, out in the bushes meeting the natives, and feeling the limitations of your capacities.

This is a blog about what happens right here at the edge of the Java universe. Enjoy!