Home

Event-Based Programming without Inversion of Control

Event-Based Programming without Inversion of Control. Philipp Haller and Martin Odersky.

Scala is different from other concurrent languages in that it contains no language support for concurrency beyond the standard thread model offered by the host environment. Instead of specialized language constructs we rely on Scala's general abstraction capabilities to define higher-level concurrency models. In such a way, we were able to define all essential operations of Erlang's actor-based process model in the Scala library.

However, since Scala is implemented on the Java VM, we inherited some of the deficiencies of the host environment when it comes to concurrency, namely low maximum number of threads and high context-switch overhead. In this paper we have shown how to turn this weakness into a strength. By defining a new event-based model for actors, we could increase dramatically their efficiency and scalability. At the same time, we kept to a large extent the programming model of thread-based actors, which would not have been possible if we had switched to a traditional event-based architecture, because the latter causes an inversion of control.

(There's not really a proper abstract. The above is from the conclusion.)

I enjoyed this paper. It's a quick read and a nice demonstration of some of Scala's cool features. It's also a good example of using exceptions as delimited control operators, and in fact the one substantial restriction is imposed by the lack of the more powerful operators. They use Scala's type system to reduce the burden of this restriction, however, since they're able to state that a particular statement never returns normally (and thus must not be followed by more statements).

Those interested in the language/library boundary will also find it interesting for this reason:

The techniques presented in this paper are a good showcase of the increased flexibility offered by library-based designs. It allowed us to quickly address problems with the previous thread-based actor model by developing a parallel class hierarchy for event-based actors. Today, the two approaches exist side by side. Thread-based actors are still useful since they allow returning from a receive operation. Event-based actors are more restrictive in the programming style they allow, but they are also more efficient.

They have some fairly impressive empirical scalability results as well.

By Matt Hellige at 2006-07-12 22:00 | Object-Functional | Parallel/Distributed | other blogs | 35458 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Similar results...

I am in the process of implementing a "workflow" language in Java. Its somewhat different in goals and design, but the language does have the same Erlang-derived concurrency primitives as they are implementing. I was going for something more in the vein of SMAWL[PDF] which caught my attention in this thread. Despite a very different method of implementation(starting with Java rather than Scala, using a heap-based stack, etc.), I still get results similar to theirs.

My "compiler" however, doesn't create JVM byte-codes, instead I have a set of "opcode objects" which I assemble into a tree from the AST. These objects have a "step" method which returns a list of "continuation" objects(I won't claim I fully understand continuations enough, but it seemed appropriate to call this heap-based "stack" a continuation). The list is because so far the spawn primitive returns two continuations :).

Anyway, I have a trampolined interpreter with a minor variation. I use reflection to allow calls out to arbitrary java code(with the caveat that the class to invoke the method has to be fully qualified...). Anyway the opcode to invoke an "external" method places its continuation in a "deferment" queue which is picked up by a deferment manager which has a stable of worker threads(which "step" a continuation and return it into the master thread queue), this keeps calls out to arbitrary Java code from blocking the interpreter.

Of course, my language is meant to be very simple(in a good way...) and static to make analysis easier(it has no real form of indirection, and the only way to access array elements is via the "foreach" construct, and constructing arrays is either via an expression or a "push" function. This has the nice side effect of eliminating array bounds exceptions).

Anyway, its interesting to see how their results came out similar to mine(from a performance standpoint, their language is very different...).

For instance, with a 256MB heap, a "forkbomb" written in my language:

function void main()
{
	forkMeHarder();
}

function void forkMeHarder()
{
	spawn: forkMeHarder();
	return forkMeHarder();
}

created 427,000+ threads before running out of heap(FYI, I implement tail-call optimizations too, mostly at least...).

Ah well, I guess I need to finishing writing up my language so I can post here to get some criticisms...

I guess my excitement stems from the "Whoa" I get everytime I see someone using lightweight threading make lots of threads and it doesn't bog or crash the machine :). It makes me wonder why lightweight threading isn't more common...

By Matt Estes at Thu, 2006-07-13 02:47 | login or register to post comments

Workflow, continuations, and threads

Would that be something similar to: Dragos A. Manolescu, Workflow enactment with continuation and future objects? Manolescu does not, as I recall, specifically discuss threading, but it seems to be kind of bundled up together....

I'm looking forward to hearing more about your language; I get the same "Whoa".

By Tommy McGuire at Thu, 2006-07-13 16:55 | login or register to post comments

I've only skimmed the paper,

I've only skimmed the paper, but basically yes. Our language is basically a parallel language with Erlang-style concurrency primitives. Our motivation was a tool to handle state in web applications, and coordinate external code that actually does the work.

Our decision to call it a "workflow language" is partially a marketing decision. That said, I felt the programming problem I was trying to solve was a special case of what workflow languages were trying to do, and that I could leverage their work to help me solve my problem AND provide a general purpose tool to others.

The language itself is focused on being mostly static. It is not difficult to produce documentation like a flow chart from the source, nor is it difficult to take a flow chart and turn it into the skeleton of a program. I also took some ideas from Tim Sweeney's slides referenced here. For instance, Tim mentioned that around 80% of int's in the Unreal code are used for array indices. The only construct I have for getting the elements of an array is:

foreach(val type in myArray) { ... code .. }

Array's must be constructed with a literal like [1,2,"a", 5] or 1..5. To add elements to an array only 2 methods are provided: "push" and "pushUnique"(which treats the array like a set).

Anyway, I'm afraid I'm in danger of not following proper community etiquette, and I really do need to finish my write-up(alas, one can't post undocumented JAR files on the web and hope to get much of a response). Feel free to email me and we can continue this discussion...

By Matt Estes at Thu, 2006-07-13 18:14 | login or register to post comments

Any news?

The system sounds interesting! What's the latest word on your workflow language?

By raould at Tue, 2007-02-27 07:13 | login or register to post comments

Overcoming limitations

I don't see how “this weakness is turned into a strength”. What is the advantage of simulating threads with source-language CPS transformation on an uncooperative runtime, over using a runtime which provides lightweight threads on the lower level?

I know what is the disadvantage: they have to organize code such that receive statements are tail called, so they can't be wrapped in a function which returns normally; they can only be wrapped in a function which takes the continuation as an explicit argument. This is hardly “without inversion of control”. I prefer to code in the natural style with function calls being allowed to block, and let the rumtime manage lightweight threads.

By Qrczak at Thu, 2006-07-13 10:41 | login or register to post comments

Wrong comparison?

I think you're making the wrong comparison... If you take the JVM as a given (which the authors do, as Philipp's comment below makes clear), the "weakness" is that naive thread-based actors don't scale under the JVMs threading model. This is turned into the strength that event-based actors scale better even than a direct thread-based implementation.

Of course, on the one hand this is well-known. No large-scale ("enterprise"), heavily concurrent Java application would think of going to production without a thread pooling library of some kind. (So one way to think of this work is "a better interface to the thread pool", showing the strengths of Scala.) On the other hand it is indeed a much better interface for a thread pool, and it is a pleasant surprise that event-based actors can be made so efficient on the JVM.

I agree that the existing restrictions are still a bit onerous, however.

By Matt Hellige at Thu, 2006-07-13 18:30 | login or register to post comments

I would second this, both

I would second this, both about the restrictions and the thread pool. My work is in similar vein, although we chose a different set of tradeoffs(for instance, we *do* use a "user" stack simulated with heap, and have a more limited language embeddedable in Java, and don't produce byte-codes), and we a got a similar result in scalability.

The take away from this, for me at least, is that lightweight threading techniques are a big win over OS threads, and that using thread-pools to hand potentially blocking operations is easy enough to incorporate into a lightweight threading approach(FYI, one tradeoff we get from the interpreter based approach is that we don't have to guess when worker threads are done).

By Matt Estes at Thu, 2006-07-13 18:42 | login or register to post comments

Blocking calls

An (IMHO, huge) advantage is that our code runs on all >=1.4 JVMs out there.

Note that you are explicitly allowed to call blocking functions. By lazily creating worker threads, our scheduler makes sure that event-based actors make progress even in that case (see section 3.4).

By hallerp at Thu, 2006-07-13 15:27 | login or register to post comments

distel

From the intro section of this paper, it sounds like how Luke added event-based programming to Emacs Lisp in distel.

By Darius Bacon at Tue, 2006-07-18 02:02 | login or register to post comments

distel has moved

The link provided for distel is dead. I found an active open source version on Google Code at distel.

By David Biesack at Fri, 2008-08-15 12:29 | login or register to post comments

distel akward

I found this programming model pretty crappy to work with in Distel. The really boring part is when you want to insert blocking operations into existing programs and have to hoist stuff up out of the stack. The more this happens the more your programs resemble continuation-passing style which is a sure sign you're using the wrong language!

I wonder if there's some nice trick to improve the situation in Scala? I didn't see it when leafing through the paper so I suspect people exposed to Erlang won't accept that "this is not a severe restriction in practice, as programs can always be organized in a way so that the rest of the computation of an actor is executed from within a receive."

There's still the Distel paper on citeseer sorry about fresh.homeunix.net falling off the internet. I have all the files but no convenient webhost at this moment. I'd hoped the internet archive would suffice but perhaps not :-)

By Luke Gorrie at Sat, 2008-08-16 07:58 | login or register to post comments

This paper is related to

This paper is related to Philipp Haller's PhD thesis.

By Niels Hoogeveen at Sat, 2006-07-22 16:36 | login or register to post comments

Not my PhD thesis

Actually, this is not my PhD thesis but my diploma thesis (6 months) for my graduate degree (roughly comparable to a master's degree) from University of Karlsruhe. Second referee (besides Martin Odersky) is Gerhard Goos from IPD.

By hallerp at Mon, 2006-07-24 16:48 | login or register to post comments