Java to the Limit

A Good Day for Erjang

A New Contributor

I am extremely happy no now have a really substantial contribution from Erik, who have made significant improvements to the exception handling translation, and moved us several steps closer to the OTP boot prompt. OTP boot progress is now at 85.5% and compile progress is at 92.5%. Thanks!

All the while Erik has been busy doing a lot of stuff, all I have done the last three weeks has been to hunt down a single off-by-one error, but it was very difficult to debug. Line-level debugging with breakpoints would indeed be wonderful!

Going forward

I think we will soon be at the point where Erjang can get to the OTP boot prompt, and that will be a major milestone. From there, it will be much easier for people to pick up Erjang and try some real stuff, write unit tests, etc.

Here is a (more or less) random list of things that I think would be interesting to work on going forward with Erjang.

Unit Testing

The first thing to do when we reach the boot prompt is to make a setup for unit tests; so that there is a simple way to add new erlang code to a unit testing framework.

Bytecode Interpreter

Joe has suggested this several times, to do a bytecode interpreter as part of Erjang. One of the reasons people don't use HiPE much (he says) is that it uses a lot more memory [for code presumably]. This will likely be the same for Erjang, where the compiled code presently uses ~3-4 x the java byte code compared to beam code. A mixed-mode runtime which starts out interpreted, selectively compiling code hotspot-style would probably be good. That would also allow us to do even more inlining of non-external calls, and also inlining of the call sequences needed to realize tail recursion semantics. That would reduce the overhead of the code injected by Kilim too.

As part of HotRuby I have done this mixed-mode vm style before, and there it was possible to match the performance of MRI (ast-interpreter) in a byte-code interpreter written in Java. So this project would indeed be entirely doable.

Compile from Abstract Representation

At present, compiled beam code has no line number information and also no local-variable names. Compiling from abstract representation (which is present in beam files compiled with +debug_info) would allow us to add that. We likely need both the beam compiler and and the abstract representation compiler because it cannot be assumed that all files are compiled with with debug info flag.

This feature could likely make erjang very attractive as it would allow you to use Java debuggers with single stepping and variable presentation.

A .beam file reader

I think we need to look into writing a pure Java beam file reader too. Right now we depend on lib_beam to interpret beam code, and that is indeed fine to get up and running, but I think we can do several things more cleanly if we have the ability to read and understand beam files in the vm directly. There is a lot of code in beam_* modules, so this is not a trivial task.

And now, ... back to my day job.

Erjang - Preliminary Performance Numbers

So, today Erjang made it's fist public appearance [read: live demo] at one of Trifork's open geek nights, and I talked a little about Erjang performance towards the end. So here are some initial numbers.

I have been reluctant to publish numbers because it is really difficult to say anything when the implementation is incomplete. But I think that for these tests I have the machinery and error checking in place; so as far as I can see there should be no extra error checking or the like that will be needed going forward. Luckily, I have lots of ideas for how to improve performance. Erjang is still very young.

Computing Fibonacci Numbers

The first test is a tail recursive fibonacci. The code is Fast tail recursive fibonacci, and also in the github repo here. The version I'm using runs a series of fibonacci computations three times, and I take the result of the third run. On a JVM, there is a significant gain in letting the virtual machine "warm up". On the BEAM VM, the numbers are very consistent.

The x-axis is simply the input to the fibonacci function; y-axis is the log of the running time. You can see that Erjang catches up with BEAM on fib(N), when N gets large. As numbers get higher, time is dominated by big number multiplication, and less so by erjang/erlang proper.

For applications that have some non-trivial Java code, this is a good outlook. The more "plain java" code in the application, the more the VM can optimize. Such as the implementation of bignums, which in Java's case is written in pure Java.

This JVM profile shows how over all computation time is dominated by bignums.

Flat profile of 12.31 secs (157 total ticks): Thread-0

  Interpreted + native   Method                        
  94.8%    73  +     0    java.math.BigInteger.multiply
   2.6%     2  +     0    java.math.BigInteger.subtract
   1.3%     1  +     0    erjang.m.erlang.ErlBif.eqxp
  98.7%    76  +     0    Total interpreted

 Thread-local ticks:
  51.0%    80             Blocked (of total)
   1.3%     1             Class loader

So it's not really a test of Erjang. The only visible erlang piece in there is ErlBif.eqxp which is short for =:= used as a guard. Hmm... Looking forward to have enough there to see some real tests.

Next Up: "The Ring"

The other interesting example is how Well Erjang does on context switch. Sriram Srinivasan and Alan Mycroft published these numbers at ECOOP'2008, so I had my hopes high.

With the various overheads imposed by implementing Erlang semantics, numbers ended up being a little disappointing. We're only at-par. The numbers below represent this ring example from Alex Miller's blog, actual used code is here at github

Running 10,000 cycles in a 10,000-process ring, total of 100,000,000 messages (each with a context switch) takes ~120 seconds, for both BEAM and Erjang on my MacBook Pro. Over time, Erjang seems a little faster as the JVM warms up.

Actual run times here [BEAM]

2> ring:main().
{1263,330690,192865} Starting message, cycles=10000
{1263,330812,106399} Around ring 10000 times 
10000 == 10000 ... stop 
Start={1263,330690,192952} Stop={1263,330812,106697} Elapsed=121913745us
{1263,330812,193086} Starting message, cycles=10000
{1263,330955,949775} Around ring 10000 times 
10000 == 10000 ... stop 
Start={1263,330812,193298} Stop={1263,330955,950028} Elapsed=143756730us
{1263,330956,39000} Starting message, cycles=10000
{1263,331078,695922} Around ring 10000 times 
10000 == 10000 ... stop 
Start={1263,330956,45864} Stop={1263,331078,696187} Elapsed=122650323us
{1263,331078,770597} Starting message, cycles=10000
{1263,331225,267266} Around ring 10000 times 
10000 == 10000 ... stop 
Start={1263,331078,770701} Stop={1263,331225,267941} Elapsed=146497240us
{1263,331225,341222} Starting message, cycles=10000
{1263,331370,629837} Around ring 10000 times 
10000 == 10000 ... stop 
Start={1263,331225,341327} Stop={1263,331370,629947} Elapsed=145288620us
ok

and Erjang [io:format is not really implemented, in this output I just print out the arguments]:

io:format "~p Starting message, cycles=~p~n" [{1263,329908,204000},10000]
io:format "~p Around ring ~p times ~n" [{1263,330069,516000},10000]
io:format "~p == ~p ... stop ~n" [10000,10000]
io:format "Start=~p Stop=~p Elapsed=~pus~n" [{1263,329908,497000},    {1263,330069,516000},161019000]
io:format "~p Starting message, cycles=~p~n" [{1263,330069,673000},10000]
io:format "~p Around ring ~p times ~n" [{1263,330194,857000},10000]
io:format "~p == ~p ... stop ~n" [10000,10000]
io:format "Start=~p Stop=~p Elapsed=~pus~n" [{1263,330069,693000},{1263,330194,858000},125165000]
io:format "~p Starting message, cycles=~p~n" [{1263,330194,915000},10000]
io:format "~p Around ring ~p times ~n" [{1263,330309,547000},10000]
io:format "~p == ~p ... stop ~n" [10000,10000]
io:format "Start=~p Stop=~p Elapsed=~pus~n" [{1263,330194,927000},{1263,330309,548000},114621000]
io:format "~p Starting message, cycles=~p~n" [{1263,330309,910000},10000]
io:format "~p Around ring ~p times ~n" [{1263,330450,834000},10000]
io:format "~p == ~p ... stop ~n" [10000,10000]
io:format "Start=~p Stop=~p Elapsed=~pus~n" [{1263,330309,922000},{1263,330450,834000},140912000]
io:format "~p Starting message, cycles=~p~n" [{1263,330450,867000},10000]
io:format "~p Around ring ~p times ~n" [{1263,330567,340000},10000]
io:format "~p == ~p ... stop ~n" [10000,10000]
io:format "Start=~p Stop=~p Elapsed=~pus~n" [{1263,330450,886000},{1263,330567,340000},116454000]

The Erjang numbers are for a configuration of a size-1 thread pool. If I increase the pool size, then a congestion problem shows up in Kilim's scheduler; here is a snapshot from jprofiler. The more threads I add, the worse the problem.

So this seems like something that can be improved. It looks like there is allocation going on inside a synchronized block, and that is never good. But at least somewhere to look to improve it; an ideal project for a new contributor? Let me know.

Conclusions?

So ... it looks like we are on-track to match BEAM on performance. We will need much more info than this to really assert overall performance. Micro benchmarks are not really a good indication of application performance, but it looks like we're in the right ballpark.

One thing that needs to be looked into is also memory usage. It looks like I use significantly more memory than BEAM, which does not surprise me, but is an issue of cause. I think that a good chunk of the memory is used by .class data, and so it might make very good sense to write a byte code interpreter; and then only generate java code for "HotSpots". If so, then we could do even more aggressive compilation and inlining.

Cheers!

Update. @hilmer wrote up this nice post

kr@b.log - Breadcrumbs for a Worthwhile Read

Started a separate blog for things worth reading that I find around the web; kr@b.log at http://krab.typepad.com/breadcrumbs/.  

Plain blog feeds are annoying - I find that I don't like to have these things thrown in my own reader, but it is nice to have to come back to.

Pragmatic Thinking

This christmas, I spent some time reading a 100-year old book How We Think by John Dewey. Amazingly, it is as relevant as ever. My sister who works as a management consultant suggested that I take a look at some of his work, and so I did.

John Dewey was an american philosopher and educational reformer, and I have seen this particular book recommended as the "easy read" as compared to some of his other works. It is about as hard to read as Einstein's popular book on relativity, or Hawking's A Brief History of Time.

John Dewey was called a "pragmatist", because he represented a school of thinking that sought to integrate theory and practice. At some point in recent scientific history those two terms somehow split, and that disconnect is a cause of much trouble.

From this viewpoint, the book gives an excellent, pragmatic and accessible discourse of such terms as logic, induction, deduction, reasoning, idea, judgement, conclusions, and so on. The cool thing is how this book is theoretical, yet very much connected to reality; a connect which is often missing in scientific discourse.

Relevance for me?

So, this book is also extremely interesting as a programmer and a programming language researcher, because programming is really about the connect between your thinking and your practice. Programming is about analyzing a problem, form an idea of how to comprehend this situation, write down your ideas, thereby turning those ideas into something very concrete (the program), and do it in a fashion so that other people can read your code. And these processes are exactly the things described in the book.

From a programming language point of view this link between theory and practice, is like the link between Aristotle's theories for categories, logic and meta-physics, and the incarnation of these things in object-oriented programming languages.

Don't laugh. This connect is real, it is not an afterthought, or an induction I have made after the fact. I have had the fortune to talk to, and discussions these relationships with several of the people who created the very idea of object-oriented programming, and you can read several accounts of how the people who have shaped our technologies really do care about the fundamental connect between theory and practice. My previous post "Actor Thinking" has some of those references at the bottom.

It's all about the way our tools shape the way we think.

The book How We Think is really written with the intention to change the way teaching was done around 1900 in most places: teach the kids skill and knowledge using drill. Dewey was quite successful in changing the American school system for the better. He wanted to change that so that we teach kids logical thinking, i.e. the ability to understand situations, come up with ideas, and reach conclusions; teach them how to analyze a problem, judge it and reach a sentence. With the current focus on PISA evaluations for our children, this is as relevant as ever. God, please do give our politicians courage to trust people who have studied these issues, without resorting to popular decisions just to be seen as a man of action.

There are an amazing number of books available for download from the internet archive; pop it into your Kindle, and off you go!

Cheers!

Actor Thinking

My Quest for the Holy Grail

For many years, I have been searching for what I call the "holy grail of concurrent programming." I have been looking for a set of abstractions as powerful as classes and objects which describes activities and their coordination. Just as was the case for the medieval quest for the holy grail, I am not alone. Many other researchers are searching for this. I remember that at the time when I started doing my Ph.D. in 1996, I was talking to Doug Lea about this subject; and he urged me to continue this line of thought. My thesis subject ended up going down another path, but the issue has persisted at the back of my mind, ready to jump up whenever I experienced new evidence that might guide me.

For the last couple of years I have been pursuing these issues more persistently; as chief editor of the JAOO and QCon conferences I have invited speakers that have something related to this on their hearts and mind, and the last six months - since working more intensively with the Erlang programming language - they have started to grow into a more consistent picture.

So here is a little essay and some ramblings on some of the things I have found out so far.

The Danger of Understanding How Things Work

When I was 16 years old, I started programming on a Commodore 64; I was learning MOS 6510 machine code, interrupt programming and all kinds of crazy low level stuff. In the process I learned a lot of things about how operating systems work - too much for my own good. For 25 years, these learnings has hunted me, because they ruined my abilities to think in many ways. Because I actually understand what is going on one level down, it is difficult to abstract from that knowledge. It seems that because I know the computer is organized in the way it is, I tend to also think that way. When I think of a problem that I need to solve, I tend to jump straight to thinking how is this possible in terms of what I want the computer to ultimately do to solve this. Whereas this kind of thinking can be good from a performance point of view - and I have used this knowledge to that purpose at many occasions - it ruins the resulting program in terms of understandability and maintainability.

But I'm not the only one. Everywhere around us, we are trying to solve problems with the tools at hand (what else can we do?) And these tools shape the way we think of problems, and for the case of thinking of concurrent activities - a.k.a. processes - this is a big issue.

Imagine implementing Asteroids, the game. What would your model look like? One process for each of those 1000 things on the screen? Or one object/data structure for each thing, and then have some sort of scheduler that runs a task every N milliseconds, asking each object to move itself and check for collisions?

Well, processes are so expensive, so it's not good to have a process for each thing on the screen; maybe 1000 processes just for that, are you crazy? More over, how are you supposed to coordinate all those processes? Crazy idea, we can't do it with processes with our current tools.

Sidebar: In 1996 me and a colleague won a programming contest at the first Java One conference - the "JavaCup International". Our feat? We wrote a framework for writing games, and the example app was ... ta da ... asteroids. The design was the way you would think, with objects and a scheduler.

Because we think of processes as "somewhat expensive", our intuitive reaction to modeling systems that have processes in them is fundamentally wrong. My thesis is - much inspired by Joe Armstrong - that once you get used to programming in a system in which processes are "very cheap" (by some relative measure), the way you model things changes significantly. Consider this quote from Joe Armstrong "Imagine an object-oriented language that would only allow 500 objects; that is how constrained we are with processes today". I predict, that 10 years from now, we will look back at 2009 thinking the same things that we do now of the pre-OO era. We will say things like "Life is much easier when modeling with processes, how could we have missed that?".

This change will be for the better in terms of understandability, readability and maintainability of the resulting system. And if our systems are better in these regards, they are also less likely to have errors; and they are easier to improve - even improve performance if that is the issue.

The Power of Object-Oriented Thinking

BUT! ... it is not enough to have "cheap processes" and message passing like Erlang has it, though I believe that having cheap processes is a necessary element of a solution. We also need to have a way to think of processes that is so that we can draw on our (vast) previous experience from the physical world to reason about them, and to structure our thinking about processes. That's the magic that will make processes manageable.

In the early 90's, Dave Ungar - a researcher at Stanford and later at Sun Labs - came up with a crazy idea. He started out a project to create a new object-oriented programming language to support a certain style of programming without worrying about performance in the design. He then took it as an engineering/researching challenge to make it run fast. The language he was designing was called Self, and even though you might not have heard of it; it changed our world. This fundamental shift in attitude towards language design literally revolutionized programming language implementations. Not many people know Dave, but he and his team ended up coming up with all the major innovations that are making Java and C# run fast today. So even though his original project did not fly, he paved the way for other object-oriented programming languages to enable object-oriented thinking without having to understand too much when writing programs in such languages.

I believe that giving programmers good high-level abstractions as part of programming languages have always been the most powerful way to improve programs in general. In my opinion, object-oriented thinking has proven this big time. The concepts of objects and classes have empowered developers to structure many aspects of problems in a more intuitive fashion, releasing their intuition to reason about these structures in terms of a mental model that resembles our "natural intuition" (read: our schooling in aristotelian logic) rather than how the computer works.

The kind of intuition released by objects and classes is "good" in the sense that it stems from our ability to make deductions from observations and experience out side of the programming domain. All the fundamental concepts in object-orientation are concepts that we learned as children: object identity (two similar looking objects being not-the-same), classification (kinds of things), composition (putting things together or taking them apart) and basic notions of relations between things. Such concepts are natural to us, and thus if we can fit them into our programming language constructs, they release our natural curiosity and ability to reason about things based on outside experiences without having to divert into (too) artificial concepts that are only applicable in context of programming.

Some of our core concepts however, did not make it into the first generation of object-oriented languages: notion of time/space, location, places, activities and their concurrent execution. It is time we start figuring out how to make that happen.

Joe Armstrong, one of the original creators of Erlang, has been advocating against object-oriented programs on the grounds that it does not support concurrency. This is not an unjust argument given the state of object-oriented programming languages, but it is unfair to the idea of object-oriented thinking. Object-oriented thinking is about modeling systems in a fashion that makes the resulting software resemble the "real world", so as to better aid our natural abilities to reason about the resulting system.

Thinking of Activities

The tools we have available today in main stream programming languages for working with processes are fundamentally variations over the concepts of threads and locks. (Yes, I know that is a gross simplification, but not entirely untrue none the less.) Whereas threads and locks are indeed fine tools to create processes, they are lousy when it comes to managing and coordinating the outcome. And this is why we "hate threads" - threads are impossible to manage. Let a thread loose in your code, and it will run all over the place; it's not confined to a part of your program, it has no scope and no concept of time/space. Threads shoot themselves in the foot all the time, running into each other; creating havoc in their path. Unlike objects, which as discussed above have some resemblance of "real things", a thread i more like an electric current that runs through your objects. It's just difficult to cope with.

So if we look around us, and try to see the things in our real world that resemble processes, activities and such. What are they like? Here is just a sample of things that are related to real-life processes:

• An agenda, A recipe, or a script for a play; these are things that prescribe how an activity should unfold. Many activities have an associated prescriptive artifact that describes what steps are involved in carrying out the activity.
• A cook following a specific recipe, or an actor who is acting a specific role in a play. These are live objects that are themselves active or "live." The the cook or the actor are not themselves the activity, the activity is something they carry out; something separate from the live object, and also separate from the recipe or script. However, they need to keep track of how far they are so they have a conception of what to do next. Keep your index finger right there on line 7 in the recipe, it's the program counter.
• An ensemble playing Hamlet. The "play" is a coordinated effort of multiple actors, an aggregate activity composed of the activities carried out by a multitude of actors, each doing their "part". We could similarly describe what happens in a restaurant as a coordinated aggregate activity played out by chefs, waiters, the hostess, and the guy doing the dishes out back.
• A party entering the restaurant have their own agenda, but they interact with the people in the restaurant in some coordinated fashion. To make the interaction easier, the restaurant has prepared a menu - which is by en large the only "interface" you have to interact with the restaurant.

If we look hard enough in the above examples, I think we can find the abstractions we need, without diverting into artificial abstractions that have the distinct smell of hardware, interrupts, threads and locks.

On the other hand, there is a long way from this list of examples, to the formalisms required to make a programming language, but I hope that you can by now follow my train of thought on the importance of grounding our abstractions in the real world. I think this kind of discourse is important, because it is important that we have an opinion on how to think about programs disconnected from the code representation.

Process == Object

Now that I have studied Erlang for a while, and from reading some of Alan Kay's old writings [see references below] I have come to this idea that "process" and "object" are quite compatible, object-oriented thinking, and erlang-style process thinking are, with the right interpretation, very compatible. And I think that we need to wrap erlang-style concurrency in an object-oriented presentation to make the main stream swallow it.

The kind of encapsulation that Erlang has for processes is the kind of encapsulation objects should have had. An Erlang process encapsulates it's own mutable state, and everything a process shares with the outside world is in the form of immutable values. An Erlang process' mutable state is (a) its process dictionary, which is like a set of "thread-local variables" or "process instance variables", and (b) the state of stack/arguments and the program counter. Everything shared with the outside world is immutable. Can we combine those notions with an object-oriented way of thinking? I think so.

One of my mental troubles with Erlang is that it is not clearly visible what code [in a module] is inside a process and which code is on the "surface" of the process i.e., code that is used to encapsulate interactions with the process. In an object-oriented programming language, this distinction is quite clear because the boundary is the methods. Trouble is that this distinction in most (all?) object-oriented programming languages is wrong, because they permit mutable state to escape. So how do we fix that?

Another thing that has challenged me with process thinking is how to manage "multiple conversations" from a single process. [And this could be the subject of a larger discourse] Since an Erlang process has just one message queue, you need to be able to look ahead into the queue and select messages that are relevant for the conversation you want to have. In effect, multiple channels of communication are multiplexed onto a single message queue. That seems to work just fine, but perhaps things are more clear if we simply have the multiple channels explicitly as in CSP / Go?

Where to go from Here?

Alistair Cockburn likes to tell this story, ...

A tourist in the highlands was lost. He stops a passing farmer and asks for directions to Glasgow. The farmer says, “Och, if I were goin’ ta Glasgow, I wouldna’ start from here!”

We need to grow a way to think more coherently about processes, a way which is compatible with our experience of the real world. Only then can we make concurrent programs comprehensible. Trying to warp your mind like this, and continue programming Java is probably not a compatible mix.

Cheers!

References

Collecting a comprehensive list of the various researchers and practitioners that have influenced my ideas here is close to impossible, but here are some of them...

A heavy influence is naturally my schooling in object-oriented thinking, my thesis supervisor Ole Lehrmann-Madsen, all the good writings on what it means to think in an object-oriented style [OOPSLA 88-96'ish]. Chapter 18 of the BETA programming language book provides one such overview.

During my Ph.D. I visited Akinori Yonezawa at Todai for a semester. Lots of interesting work by his teams on ABCL/x and friends. I've also studies available material on several kinds of concurrent Smalltalks; most interestingly OTI's Actra Smalltalk.

The list of "real life activities" is inspired by Kristen Nygaard's work, and particularly his ECOOP'97 talk Goods to appear on stage, and his talk at JAOO 2001.

My recent encounter with Erlang, has led me to think of processes in a new way; that light weight processes are really possible. Joe Armstrong's presentation at the JAOO Conference 2007 opened my eyes to how constrained we are, by his quote "Imagine an object-oriented language that would only allow 500 objects; that is how constrained we are with processes today". You can also find his JAOO presentation at InfoQ.com.

Alan Kay's HOPL paper An Early History of Smalltalk. Also of interest is this quote from Alan on the Squeak List.