Kilim: Actor framework for Java (in bytecode)

[Patrick Wright]

This popped up on one of the Scala mailing lists today: Kilim [1]

"Kilim is a message-passing framwork for Java that provides
ultra-lightweight threads and facilities for fast, safe, zero-copy
messaging between these threads.

It consists of a bytecode postprocessor (a "weaver"), a run time
library with buffered mailboxes (multi-producer, single consumer
queues) and a user-level scheduler and a type system that puts certain
constraints on pointer aliasing within messages to ensure
interference-freedom between threads."

or, to really whet your appetite

"Abstract. This paper demonstrates an architecture for suspending and resuming
methods in Java using a restricted form of continuation passing style (CPS)
transformation. It describes Kilim1, a toolkit to portably weave threads of
control called Fibers, through Java code. The chief contributions of this paper
are the set of design choices made for both space and time efficiency
in getting
one-shot continuations to work on the JVM (in some cases, 60x faster than
competing approaches) and to address some tough issues traditionally passed
over by others, such as handling of local subroutines and constructors. We are
able to support hundreds of thousands of threads of control with switching
times of the order of 3 to 4 μs on a low-powered laptop with Sun's JVM."

In the one paper I've had time to read through, there are comparisons
with JavaFlow, RIFE, PicoThreads, among others.

There's code to download, a couple of papers linked on the page near
the bottom, as well as a link to a talk presented at Google and
available online. The paper I had time to read is very well-written to
boot.

Am bcc'ing the project's mailing list.

Regards
Patrick

1] http://www.malhar.net/sriram/kilim/

[Charles Oliver Nutter]

Patrick Wright wrote:
> This popped up on one of the Scala mailing lists today: Kilim [1]
>
> "Kilim is a message-passing framwork for Java that provides
> ultra-lightweight threads and facilities for fast, safe, zero-copy
> messaging between these threads.

I wonder if it isn't time to reconsider an m:n threading model for JVM.
Seems like there's demand for it, and while these hacks are clever they
don't scale across the whole of third-party and core Java libraries a
typical app is going to encounter. Enlisting the JVM in microthreading
directly seems like it would be the best long-term approach.

- Charlie

[Erik Engbrecht]

What about working it into the compiler?

I think as a general rule, something that can effectively be done in a library and/or compiler, should be done in a library and/or compiler, rather than in the JVM itself.  No one from the EPFL has commented as this so far on the public Scala lists, but I could see a Scala compiler plugin or enhancement that does these transformations for the Scala actors library based on type information encoded in the language and (maybe) some special base traits or annotations.

Given a working demonstration like that maybe it could be merged into something more standard in Java land, but as a standard for way of constructing "actor" class files.  I think the fact that they built this on top of the JVM threading model says a lot.

Anyway, just my two cents.  I'm neither a compiler nor a VM expert.

--
http://erikengbrecht.blogspot.com/

[Charles Oliver Nutter]

Erik Engbrecht wrote:
> What about working it into the compiler?
>
> I think as a general rule, something that can effectively be done in a
> library and/or compiler, should be done in a library and/or compiler,
> rather than in the JVM itself. No one from the EPFL has commented as
> this so far on the public Scala lists, but I could see a Scala compiler
> plugin or enhancement that does these transformations for the Scala
> actors library based on type information encoded in the language and
> (maybe) some special base traits or annotations.
>
> Given a working demonstration like that maybe it could be merged into
> something more standard in Java land, but as a standard for way of
> constructing "actor" class files. I think the fact that they built this
> on top of the JVM threading model says a lot.

Well, my thinking here is that what we as JVM language developers would
like to just generate Plain Old JVM Bytecode and not have to think about
the threading of that code at execution time. So if it actually ends up
mapping N JVM threads to 1 kernel thread, so be it.

So what I want is to be able to answer all the Erlang folks with their
tens of thousands of processes by being able to spin up tens of
thousands of threads. Of course I understand the complexity of this,
given that e.g. hotspot wants to be able to inline a bunch of code down
to a single piece of native code...wants to be able to overload the C
stack to avoid allocating its own stack primitives...and so on. So this
isn't something that would happen tomorrow, obviously, but it certainly
deserves some consideration, yeah?

- Charlie

[Erik Engbrecht]

Hmmm, yes, I see your point.  Especially from the language implementer's point of view.  Pushing it down into the JVM buys you less work and ensures consistency across JVM languages, which is good for interoperability.

However, I wouldn't want to lose the ability to create a kernel thread.  Most of the time I don't care, but sometimes I don't want to rely so much on JVM magic.

So:

  interface Thread { ... }

  class KernelThread implements Thread { ... }

  class GreenThread implements Thread { ... }

...you choose which threading model you want by which implementation class you use.  Of course we'd need different names, because the above would break existing code...

--
http://erikengbrecht.blogspot.com/

[Sriram Srinivasan]

I agree with Charlie about microthreads being baked in to the VM and
the JDK.

I explored the possibility (for Kilim) of making Thread m:n again, but
switching stacks and growing them dynamically is a pain in Hotspot.
The Capriccio project from Berkeley grows the stack at run-time, but
depends on a static analysis to figure out where to put the check to
grow the stack dynamically.

I am now beginning to explore a more interesting alternative (seen in
Kilim), where the user-level thread and the kernel thread schemes
have a loose coupling that is exposed to the programmer. This permits
finer grained control over the mapping of m to n and how the tasks are
scheduled. Maintaining cache affinity is important for some
applications and you don't want to make a thread jump around.

So, in Kilim, a Scheduler manages a thread pool, and you can have many
independent schedulers. A task belongs to a scheduler at any point in
time. (By default, there's one scheduler and one thread pool)

You can of course write your own scheduler. This is good for writing
simulators (JIST-style) that can schedule tasks according to a logical
clock.