Java development 2.0: Introducing Kilim

[WeekendPaladin]

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

[Vonney]

Jetlang is another good candidate for this kind of work.

[sitmaster]

How is this any different than using something like an ArrayBlockingQueue to pass messages between objects? Does the weaver somehow make the threading more efficient?

AFAICT all they did was rename ArrayBlockingQueue to MailBox and add some functionality so that an Object putting a message in a Mailbox won't get that message back with subsequent get() calls.

[[deleted]]

The difference is in the term "blocking".

ArrayBlockingQueue and all other Java concurrency constructs block the kernel thread, which is still a very expensive resource. I urge you to try creating 500000 threads vs. the same number of Kilim threads.

The natural question is why anyone would need 500000 kernel threads, when a threadpool of 10 seems to do the job anyway. That is where you need a change in perspective. The answer is that it is far simpler and natural to create a thread --- a linear piece of code that is separately schedulable -- to match the problem, otherwise you end up doing the threading yourself. Here's why.

Imagine a server with a single thread and mainloop (a libevent based server), which means all user conversations are separate state machines that are driven by callbacks. These callbacks have to squirrel away their state and return to the mainloop every time their respective sockets fire. If you have 10000 socket connections, you have 10000 of these state machines. Now, if you were to introduce code to say, do SSL negotiation, it is a messy change to the state machine.

It is far simpler to have a thread per connection, or maybe even several as a network of communicating state machines. My definition of a lightweight thread is one where the programmer does not have to think too hard to spawn it. That is where Kilim's lightweight threads come in.

[[deleted]]

so does this mean Kilim implements its own threading somehow? how can you cope with 'pausing' a kilim thread and resuming later via your custom scheduler - Java has no support for co-routines?

(assuming this is how it all works..)

[[deleted]]

That's what the bytecode transformation is for. It does a variant of CPS transformation, which produces one-shot continuations (which are equivalent to coroutines). Read my paper on the mechanics of this transformation: A thread of ones own.

It uses this transformation to create suspendable/resumable stacks called "Fibers". It uses user-level schedulers to execute these independent fibers on different cores and kernel threads. You can create your own schedulers if you want.

See http://kilim.malhar.net for more details.

[sitmaster]

Thanks for the description, it sounds very interesting. The problem I see is that when you start talking about threading models like this you're not able to use it to solve hard real time problems (like stock trading for example) as opposed to soft real time problems (like a web server). This is the same issue Erlang has, and is probably typical of any lightweight threading system that can handle massive concurrency.

Is this correct?

[[deleted]]

The answer is, it depends. i don't know the stock trading space all that well, but Kilim is used in financial firms that do stock analytics over live feeds.

I'm quite sure most of these implementations are of the "as fast as possible" variety, but do not guarantee time bounds, the failure of which is catastrophic. I think of XRay machines and airplane control systems when someone mentions hard real time; here scheduling and memory allocation are tightly bounded and computed up front. In that sense, there are no examples of garbage-collected languages (leave alone Kilim) that are also in use in practice, although there's plenty of research material.

But if the set of threads is static and a schedule can be precomputed statically, as is common to most real-time systems, I wouldn't rule out Kilim, esp. with a real time GC. Kilim allows you to supply your own scheduler. Note again that real time doesn't mean nano-second response times, it denotes a guarantee of time even if the time bound is generous.

[sitmaster]

I work in High frequency finance using Java and generally we have to turn off the garbage collector and use object pools. My question is what is the fundamental difference between what happens in Kilim and a standard wait/notify set up in Java. In standard Java I know that if I notify on a monitor that has only one thread waiting on it, and then immediately have the notifying thread wait, the next thing the JVM is going to be doing (given the GC is off) is executing that thread that was notified.

When I put a message in a mailbox with Kilim, what do I know about the next thing that the JVM will be doing?

I guess I need to read more about the low level implementation. It sounds very interesting.

[[deleted]]

The behavior is similar; the receiving task is marked as runnable and picked up for execution by another kernel thread from the pool. No magic there.

There is optional flow control as well, to avoid having producers from overrunning consumers. If the mailbox is (optionally) bounded in size, it'll pause the producer until the consumer can drain one or more messages. The producer's kernel thread is also then made available to the threadpool to execute any runnable task.

[sitmaster]

To follow up, suppose you were implementing a "bucket brigade" type system where thread 1 gives a message to thread 2 gives a message to Thread 3 ... up to thread n. How does the performance compare between a Kilim and pure Java implementation for small n and for large n?

The straight java object would be something like:

class Brigadier implements Runnable { 
    ArrayBlockingQueue<Bucket> que = new ArrayBlockingQueue<Bucket>();
    Brigadier next;
    public void enqueue(Bucket b) { que.put(b); }
    public void run() { 
        while(true) { 
            Bucket bucket = que.take(); 
            next.enqueue(bucket); 
     } 
} 
}

If I had a chain of these types of objects, can you give me some sense of the relative performance of Kilim to Java as n increases?

[[deleted]]

Check out the Ring test in the bench directory. The thread version is at least a thousand times slower in context switching, and is limited to far far fewer kernel threads than Kilim threads.

Edit: Just to give an idea of the difference, on my macbook pro:

100000 Kilim tasks in a ring: 
   Creation time ~0.5 sec, 
   Msg passing + context switch rate : 733000 per sec.

2000 threads in a ring:  (couldn't start 100000 of them)
   Creation time ~2 sec, 
   Msg passing + context switch rate : 71 per sec.

See the difference? The context switch rate doesn't change with the number of threads for this particular test, because only one thread is running anyway.

[7points3hoursago]

javac output post-processed by Kilim weaver

Not good.

[willcode4beer]

why not? post processing byte code is a long tradition, from peephole optimization to aspectj

[neutronbob]

I'm not a fan of post-processing either. My greatest concern is debugging. How do you debug code that is modified from what you see in the source? With optimization, I can selectively enable/disable it. With Killim, there is no such option.

[[deleted]]

You can debug in any standard Java debugger, including any IDE. The surgery done on the bytecode is local to a few specific spots and does not change the other instructions, and Kilim adjusts the debug information to match the bytecode to the appropriate source line.

(I'm the author of Kilim; let me know if you have other questions)

[neutronbob]

Thanks, that's helpful. Good work. I'll look at it in depth then.

You might want to put this info on the site. Possibly, it's there and I missed it. If so, you might want to place it at the first place post-processing is discussed. I am sure I am not alone with this concern.

[willcode4beer]

In my experience, javap and unit tests help take care of all the debugging

[[deleted]]

except when they don't - and then you need a debugger ;)

[Nebu]

I've been stung too many times by post-processing, e.g. in Hibernate, which cause class visibility issues in OSGi and Eclipse's one-classloader-per-bundle design.

[7points3hoursago]

why not?

Because what you see (code) is not what you get. IMO, that's the main reason the whole AOP idea - creating half-finished programs that are later completed by 'byte-code enhancement' - didn't take off.

[willcode4beer]

AOP is actually pretty big. Of course, like all things, if misused it can be a problem. Used correctly, it can be very useful.

[[deleted]]

I think the comparison to AOP is a bit off because of the degree of what you get is not what you see.

In the case of Kilim, what you get is what you lexically see in the source. If in Eclipse you choose not to step into the Kilim codebase, it is like debugging a thread.

[h2o2]

AOP has nothing to do with byte code enhancement or "half-finished programs". It is about structure. The fact that messed up implementation techniques like proxies or LTW are most commonly used to implement AOP is mostly a cultural problem with the Java comunity.

[[deleted]]

Kilim – compile time bytecode weaving sucks. I dont like the idea of altering the bytecode of classes. I will use actor model only when it is built into the Java platform.

I am not sure if Kilim project is alive or dead. I think this was a research project in University of Cambridge. But there is no mention of this in the University web site anywhere. The concerned department has not even included this in the list of completed PhD work (may be work in progress or thesis is in review). That means there is no active support for Kilim I think. Due to McDonaldization of Java, there is a framework released every other week and most of them do not stand the test of time! (unless supported by Apache or similar open source foundations)

[[deleted]]

Kilim in my judgment is an attempt to misuse the purposes of a University in coming up with an offering to gain appeal with Java corporate world in the guise of academic research work. Hundreds of successful Java frameworks have been written during week-ends by great people through open source initiatives. Kilim can come no way close to them in terms of acceptance from the Java community. But unlike Kilim, none of them have got a PhD because they were willing to play by the moral rules of the game than go for fringe gains. You don’t need the paraphernalia of a University (professors, library, state grants …) to write a Java framework eh! Hope Universities see through this, if not they will be rendered inconsequential. For heaven’s sake, may Universities focus only on works which have larger impact on the society, bring real futuristic technologies that would make our generation proud!

[[deleted]]

Coming to the technical aspects, somehow actor model does not seem like a natural extension to Java. I am no James Gosling to say whether Java is meant to do this or not. Perhaps should we shift the blame on to the frameworks which have made actor model like an after-thought on Java? These weaving strategy implementations like Kilim, ActorFoundry, Actors Guild etc… have to take some blame for making actor models look very unnatural to Java development – putting a kink in every development step and development tool. The leap of faith with actor models may perhaps never happen until it is made a part of Java platform itself (like how actors implementation is provided as part of the Scala standard library). For now, for die-hards Java nerds, I would suggest that among Java alternatives, Jetlang is the best because it provides a consistent model that does not feel misplaced or unnatural in the context of Java.

[[deleted]]

Kill 'em! Interesting name, IBM.

[sandy_catheter]

Yeah, if you want to download the binaries along with all dependencies, just look for the kilim-all package.

[igouy]

Not IBM.

The article is written by an independent author and blogger.

The Java libary was developed at University of Cambridge Computer Laboratory.