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.

Erjang/OTP 22% there ...

Update: Adding support for file_readdir (listing a directory) suddently jumped this to 78%; so perhaps my measure of progress is not linear with the effort :-) Still, I am happy with it. Next up is to implement that special variant of open_port that reads/writes file descriptors; in this case to handle stderr. Cheers!

I know, 22% doesn't sound like much, but I've been making good progress on OTP. The graph below shows my two measures of progress on Erjang/OTP, the blue line is OTP modules the Erjang compiler can successfully compile to valid JVM byte code, the red line is how far an OTP boot comes before bailing out (measured as #modules loaded by Erjang vs #modules needed to boot OTP on beam as reported by /sw/bin/erl -loader_debug < /dev/null | grep '{return,{ok' | wc -l).

The last 8 days of work has brought Erjang/OTP from 7% to 22% on this measure, and I am yet to discover something "really hard", no reason to believe we cannot go on. But things will likely be slow over the christmas break.

Now I can go on christmas break with some peace. Next up is to complete file I/O as needed by gb_sets, which is the last module to load before it bails.

Wierd exceptions

There has been a few issues with the beam -> jvm compiler, but it is getting more and more stable. One of the funny things is that erlc seems to do CSE (common subexpression elimination) which gets in the way of exception handling.

I.e. in code_server there is code looking like this:

handle_call({load_native_partial,Mod,Bin}, {_From,_Tag}, S) ->
    Result = (catch hipe_unified_loader:load(Mod,Bin)),
    Status = hipe_result_to_status(Result),
    {reply,Status,S};

handle_call({load_native_sticky,Mod,Bin,WholeModule}, {_From,_Tag}, S) ->
    Result = (catch hipe_unified_loader:load_module(Mod,Bin,WholeModule)),
    Status = hipe_result_to_status(Result),
    {reply,Status,S};

Notice how the two last line of each function clause are equal, and they happen to coincide with being an exception handler. The resulting beam code is [pseudo]:

LabelA:
    {catch LabelC}
    hipe_unified_loader:load(Mod,Bin)
    goto LabelC

... other code goes here, maybe from another function clause ...

LabelB:
    {catch LabelC}
    hipe_unified_loader:load_module(Mod,Bin,WholeModule)
LabelC:
    {catch_end}
    Status = hipe_result_to_status(Result),
    {reply,Status,S};

You see the issue? I have to generate java code such that there are two code blocks that are different places in the method, but share the same exception handler [the code at LabelC]. I was wierded out for a while there, but it seems to work now.

Clojure to the Rescue!

Another stumbling block this week has been implementing ets (erlang term store), which is kind of an STM-thing (shared transactional memory) in erlang, that can be used to share data structures across erlang processes.

It is not complete; I am implementing BIFs as I run into them, but the structure is there, and I have a few insert/delete/lookup methods as needed so far by Erlang/OTP booting. There is also a parser/evaluator for match_spec's. A nice future optimization would be to generate JVM bytecode for compiled match_spec [That would be a good subproject for a new contributor].

Anyway, for ets, I have used Clojure's persistent data structures and the transactional cell, clojure.lang.Ref. This handles the transactionsl requirements on ets operations, and further would allow us to implement transactions across ets operations.

As an example, this is the implementation of ets:insert(tid, [tuple, ...]) for set type (implemented as an IPersistentMap).

@Override
protected void insert_many(final ESeq values) {
    LockingTransaction.runInTransaction(new Callable() {
        @Override
        protected Object run() {        
            IPersistentMap map = (IPersistentMap)mapRef.deref();
            for (ESeq seq = values; !seq.isNil(); seq = seq.tail()) {
                ETuple value = values.head().testTuple();
                if (value == null) throw ERT.badarg(values);
                map = map.assoc(get_key(value), value);
            }
            mapRef.set(map);
            return null;
        }});
}

For clojure folks out there: In Erjang an ESeq is similar to a clojure.lang.ISeq, it is the representation of a well-formed list.

Chrome won't open html files?

This has happened to me several times; when I click on an HTML document in Finder, Chrome will tell me "Nope dude, that's not my kind of file".

Notice the subtle way they distance themselves from that foreign document format by enclosing "HTML document" in quotes! What are these guys thinking? What other kind if file could I possibly imagine to open in Chrome? Remarkably, HTML documents originating from the net usually work fine :-) Is there some kind of hidden message in there? Are they contemplating just doing away with file systems all together?

OTP Boot Progress...

For a few days I have been spending some time on OTP boot, and there is still some way to go here :-) I am booting an off-the-shelf OTP R13B2. So all you need is erjang.jar, and the path to the pre-loaded beam files.

java -cp erjang-0.1.jar \
    -Derjpath=/sw/lib/erlang/lib/erts-5.7.3/ebin \
    erjang.OTPMain \
        -boot start_clean \
        -root /sw/lib/erlang \
        -init_debug -loader_debug

There is no special versions of the erlang beam files, which is pretty cool - me thinks.

Below I have included the output from the above command. You can compare this progress to running the command "erl -init_debug -loader_debug" on your system. As you will see, there a lots of modules Erjang has not yet loaded, but it seems to me that I have hit that sweet spot where progress is extremely fast, because there is never any doubt about what to do next.

The specific problem below has to do with that Kilim weaver was designed to run as a command-line tool, and I am adapting it to run as part of the virtual machine which is loading the woven code. Not to worry.

So: This is an excellent base for progress. The fundamental mechanics is in place in the VM, and we have the first gen_event server running - the error_logger. From this point forward, it is very simple to pick up the next problem. This is test-driven development indeed. Just someone else wrote all the tests.

If you want to help you're welcome. Just pick up the code here, and search for TODO or throw new NotImplemented().

Next Up: Erlang Term Store (ets). Right now I have hit a compiler problem in compiling ets.beam, and as soon as that is resolved I will have to provide an implementation for the ets BIFs. That will be interesting - because all of the core ets functionality is implemented in BIFs; which is on one hand an excellent opportunity to do some Java code.

Update: Have solved the immediate compiler problem, now pondering options for how to implement ets. Any good suggestions for an open-source embedded Java key-value store? experience with any of these would be appreciated Also still seriously considering H2 Database.

Enjoy!

Kresten

%%%%%%%%%%%%%%%%%%%%%%%%%%
%% output of running 
%%
%%  java -cp erjang-0.1.jar -Derjpath=/sw/lib/erlang/lib/erts-5.7.3/ebin \
%%     erjang.OTPMain -boot start_clean -root /sw/lib/erlang -init_debug -loader_debug
%%
%% Slightly edited and shortened for presentation here.

prompt% ./boot_otp.sh
{get_file,"./start_clean.boot"}
{return,{error,enoent}}
{get_file,"/sw/lib/erlang/bin/start_clean.boot"}
{return,{ok,<<131,104,3,100,0,6,115,99,114,105,112,116,104,2,107,0,15,79,84,80,...,106>>}}
{progress,preloaded}
{read_file_info,"/sw/lib/erlang/lib/kernel-2.13.3/ebin"}
{return,{ok,{file_info,2346,directory,read,{{2009,11,8},{12,1,32}},{{2009,11,8},{12,1,32}}, {{2009,11,8},{12,1,32}},320,1,0,0,-42,0,0}}}
{read_file_info,"/sw/lib/erlang/lib/stdlib-1.16.3/ebin"}
{return,{ok,{file_info,-28,directory,read,{{2009,11,8},{12,1,31}},{{2009,11,8},{12,1,31}},  {{2009,11,8},{12,1,31}},320,1,0,0,-12425,0,0}}}
{get_file,"/sw/lib/erlang/lib/kernel-2.13.3/ebin/error_handler.beam"}
{return,{ok,<<70,79,82,49,0,0,17,164,66,69,65,77,65,116,111,109,0,0,1,133,...,0>>}}
{progress,kernel_load_completed}
{read_file_info,"/sw/lib/erlang/lib/kernel-2.13.3/ebin"}
{return,{ok,{file_info,2346,directory,read,{{2009,11,8},{12,1,32}},{{2009,11,8},{12,1,32}}, {{2009,11,8},{12,1,32}},320,1,0,0,-42,0,0}}}
{read_file_info,"/sw/lib/erlang/lib/stdlib-1.16.3/ebin"}
{return,{ok,{file_info,-28,directory,read,{{2009,11,8},{12,1,31}},{{2009,11,8},{12,1,31}},{{2009,11,8},{12,1,31}},320,1,0,0,-12425,0,0}}}
{progress,modules_loaded}   
{read_file_info,"/sw/lib/erlang/lib/kernel-2.13.3/ebin"}
{return,{ok,{file_info,2346,directory,read,{{2009,11,8},{12,1,32}},{{2009,11,8},{12,1,32}},{{2009,11,8},{12,1,32}},320,1,0,0,-42,0,0}}}
{read_file_info,"/sw/lib/erlang/lib/stdlib-1.16.3/ebin"}
{return,{ok,{file_info,-28,directory,read,{{2009,11,8},{12,1,31}},{{2009,11,8},{12,1,31}},{{2009,11,8},{12,1,31}},320,1,0,0,-12425,0,0}}}
{start,heart}
    resolving heart:start/0
{get_file,"/sw/lib/erlang/lib/kernel-2.13.3/ebin/heart.beam"}
{return,{ok,<<70,79,82,49,0,0,31,156,66,69,65,77,65,116,111,109,0,0,2,80,...,0>>}}
{start,error_logger}
    resolving error_logger:start_link/0
{get_file,"/sw/lib/erlang/lib/kernel-2.13.3/ebin/error_logger.beam"}
{return,{ok,<<70,79,82,49,0,0,38,204,66,69,65,77,65,116,111,109,0,0,2,154,...,0>>}}
    resolving gen_event:start_link/1
{get_file,"/sw/lib/erlang/lib/kernel-2.13.3/ebin/gen_event.beam"}
{return,{error,enoent}}
{get_file,"/sw/lib/erlang/lib/stdlib-1.16.3/ebin/gen_event.beam"}
{return,{ok,<<70,79,82,49,0,0,98,220,66,69,65,77,65,116,111,109,0,0,5,193,...,0>>}}
    resolving gen:start/6
{get_file,"/sw/lib/erlang/lib/kernel-2.13.3/ebin/gen.beam"}
{return,{error,enoent}}
{get_file,"/sw/lib/erlang/lib/stdlib-1.16.3/ebin/gen.beam"}
{return,{ok,<<70,79,82,49,0,0,32,140,66,69,65,77,65,116,111,109,0,0,1,213,...,0>>}}
    resolving proc_lib:start_link/5
{get_file,"/sw/lib/erlang/lib/kernel-2.13.3/ebin/proc_lib.beam"}
{return,{error,enoent}}
{get_file,"/sw/lib/erlang/lib/stdlib-1.16.3/ebin/proc_lib.beam"}
{return,{ok,<<70,79,82,49,0,0,77,76,66,69,65,77,65,116,111,109,0,0,5,40,...,0>>}}
ignored options to send: [noconnect]
{start,application_controller}
    resolving application_controller:start/1
{get_file,"/sw/lib/erlang/lib/kernel-2.13.3/ebin/application_controller.beam"}
{return,{ok,<<70,79,82,49,0,0,237,168,66,69,65,77,65,116,111,109,0,0,13,119,...,0>>}}
resolving ets:new/2
{get_file,"/sw/lib/erlang/lib/kernel-2.13.3/ebin/ets.beam"}
{return,{error,enoent}}
{get_file,"/sw/lib/erlang/lib/stdlib-1.16.3/ebin/ets.beam"}
{return,{ok,<<70,79,82,49,0,0,162,104,66,69,65,77,65,116,111,109,0,0,10,57,...,0>>}}
[compiling ets...]
Dec 14, 2009 8:39:01 AM erjang.m.erlang.ErlBif load_module
SEVERE: cannot load module
java.lang.InternalError: erjang.m.ets.ets$FN_$2Dtab2file$2F3$2Dfun$2D0$2D__3
    at kilim.analysis.TypeDesc.commonSuperType(TypeDesc.java:242)
    at kilim.analysis.TypeDesc.mergeType(TypeDesc.java:178)
    at kilim.analysis.Value.merge(Value.java:82)
    at kilim.analysis.Frame.merge(Frame.java:88)
    ...
    at erjang.beam.Compiler.compile(Compiler.java:330)
    at erjang.ERT.load_module(ERT.java:618)
    at erjang.m.erlang.ErlBif.load_module(ErlBif.java:1009)
    at erjang.m.erlang.ErlBif.load_module(ErlBif.java:999)
    at erjang.m.erlang.ErlBif$FN_load_module__2.invoke(Unknown Source)
    at erjang.m.init.init.load_mod_code__3(Unknown Source)
    at erjang.m.init.init$FN_load_mod_code__3.go(Unknown Source)
    at erjang.m.init.init.load_mod__2$call(Unknown Source)
    at erjang.m.init.init.ensure_loaded__2(Unknown Source)
    at erjang.m.init.init.ensure_loaded__2$call(Unknown Source)
    at erjang.m.init.init.boot_loop__2(Unknown Source)
    at erjang.m.init.init$FN_boot_loop__2.go(Unknown Source)
    at erjang.EProc.execute(EProc.java:256)
    at kilim.Task._runExecute(Task.java:380)
    at kilim.WorkerThread.run(WorkerThread.java:36)

raise [{ets,new,[ac_tab,[set,public,named_table]]},{application_controller,init,2},{erlang,apply,3}]

{get_file,"/sw/lib/erlang/lib/kernel-2.13.3/ebin/io_lib.beam"}
{return,{error,enoent}}
{get_file,"/sw/lib/erlang/lib/stdlib-1.16.3/ebin/io_lib.beam"}
{return,{ok,<<70,79,82,49,0,0,77,136,66,69,65,77,65,116,111,109,0,0,3,221,...,0>>}}
resolving erl_scan:reserved_word/1
{get_file,"/sw/lib/erlang/lib/kernel-2.13.3/ebin/erl_scan.beam"}
{return,{error,enoent}}
{get_file,"/sw/lib/erlang/lib/stdlib-1.16.3/ebin/erl_scan.beam"}
{return,{ok,<<70,79,82,49,0,0,249,28,66,69,65,77,65,116,111,109,0,0,8,172,...,0>>}}
resolving lists:flatten/1
{get_file,"/sw/lib/erlang/lib/kernel-2.13.3/ebin/lists.beam"}
{return,{error,enoent}}
{get_file,"/sw/lib/erlang/lib/stdlib-1.16.3/ebin/lists.beam"}
{return,{ok,<<70,79,82,49,0,1,42,188,66,69,65,77,65,116,111,109,0,0,7,29,...,47>>}}
{"could not start kernel pid",application_controller,"{undef,[{ets,new,[ac_tab,[set,public,named_table]]},{application_controller,init,2},{erlang,apply,2}]}"}
...

exiting PID<init:1> with: erjang.NotImplemented [{erlang,processes,0},{init,alive_processes,0},{init,get_pids,1},{init,kill_all_pids,1},{init,shutdown_pids,3},{init,clear_system,2},{init,new_kernelpid,3},{init,boot_loop,2}]
    at erjang.m.erlang.ErlProc.processes(ErlProc.java:450)
    at erjang.m.erlang.ErlProc$FN_processes__0.invoke(Unknown Source)
    at erjang.m.init.init.alive_processes__0(Unknown Source)
    at erjang.m.init.init.alive_processes__0$call(Unknown Source)
    at erjang.m.init.init.get_pids__1(Unknown Source)
    at erjang.m.init.init.get_pids__1$call(Unknown Source)
    at erjang.m.init.init.kill_all_pids__1(Unknown Source)
    at erjang.m.init.init.kill_all_pids__1$call(Unknown Source)
    at erjang.m.init.init.shutdown_pids__3(Unknown Source)
    at erjang.m.init.init.shutdown_pids__3$call(Unknown Source)
    at erjang.m.init.init.clear_system__2(Unknown Source)
    at erjang.m.init.init.clear_system__2$call(Unknown Source)
    at erjang.m.init.init.new_kernelpid__3(Unknown Source)
    at erjang.m.init.init.new_kernelpid__3$call(Unknown Source)
    at erjang.m.init.init.boot_loop__2(Unknown Source)
    at erjang.m.init.init$FN_boot_loop__2.go(Unknown Source)
    at erjang.EProc.execute(EProc.java:256)
    at kilim.Task._runExecute(Task.java:380)
    at kilim.WorkerThread.run(WorkerThread.java:36)

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