Introduction
Continuations can be used to implement Green Threads which are basically virtual threads that run on real (native) threads, like java.lang.Thread
. The difference is that we can run thousands, if not millions of green threads on a single thread.
Use case
This enables us to (for example) write AI code with your usual java control-flow, without suffering from the issue of thread overhead and multithreading related complexity (locks, race conditions, etc).
For example, we could write an AI like this, and run it on it’s own green thread
public void run() {
// this is the AI of the unit, it will go on forever
while(true) {
Vec2 originalLocation = new Vec2(this.position);
Water water = this.findWater();
this.moveTo(water.position);
this.drink(water);
this.moveTo(originalLocation); // walk back
}
}
public void drink(Water water) {
while(!this.isFull() && !water.isEmpty()) {
water.level--;
this.water++;
@@ sleep(1500); // drinking takes a while
}
}
public void moveTo(Vec2 dst) {
Vec2 src = new Vec2(this.position);
float distance = Vec2.distance(src, dst);
float duration = distance / this.speed;
for(float traveled = 0.0f; traveled <= duration; traveled += speed) {
float ratio = Math.min(traveled / distance, 1.0f);
this.position.x = src.x + ratio * (dst.x - src.x);
this.position.y = src.y + ratio * (dst.y - src.y);
@@ yield(); // wake up *here* in the next game tick
}
}
Implementation
My continuations library is written on top of Matthias Mann’s continuations library. It provides the concept of ‘yield return’, as found in C# and other languages, and builds Green Threads on top of it. It works by rewriting bytecode, to be able to store and restore the Java stack.
There are two options to rewrite the bytecode;
- Ahead of time: an Ant task will discover your class files and rewrite them
- At runtime: a java-agent will intercept classloading, and rewrite each class, supporting hot-swapping of code
With either option, you still have full debugging functionality in your IDE: step into/over/out and breakpoints work just fine.
Download files
- http://indiespot.net/files/projects/continuationslib/
- http://indiespot.net/files/projects/continuationslib/continuations-all-files.zip
- https://github.com/riven8192/LibContinuations
Matthias Mann’s continuations library (see blog post, mercurial repository)
import java.util.Iterator;
import de.matthiasmann.continuations.CoIterator;
import de.matthiasmann.continuations.SuspendExecution;
public class ContinuationsTestCoIterator {
static class YieldReturn extends CoIterator<String> {
@Override
protected void run() throws SuspendExecution {
this.produce("a");
this.produce("b");
for (int i = 0; i < 4; i++) {
this.produce("c" + i);
}
this.produce("d");
this.produce("e");
}
}
public static void main(String[] args) {
Iterator<String> iterator = new YieldReturn();
for (String str : asIterable(iterator)) {
System.out.println("got: " + str);
}
}
private static final <E> Iterable<E> asIterable(final Iterator<E> iterator) {
return new Iterable<E>() {
@Override
public Iterator<E> iterator() {
return iterator;
}
};
}
}
Output:
got: a
got: b
got: c0
got: c1
got: c2
got: c3
got: d
got: e
Bare bones example of the highlevel continuations library:
import static net.indiespot.continuations.VirtualThread.*;
import net.indiespot.continuations.*;
import de.matthiasmann.continuations.SuspendExecution;
public class VirtualThreadTestSchedule {
public static void main(String[] args) {
final VirtualProcessor processor = new VirtualProcessor();
// create virtual threads (or green threads, if you will)
final long started = now();
final long finalWake = now() + 5000;
new VirtualThread(new VirtualRunnable() {
@Override
public void run() throws SuspendExecution {
System.out.println("thread 1: a (" + (now() - started) + "ms)");
sleep(1000);
System.out.println("thread 1: b (" + (now() - started) + "ms)");
sleep(1000);
System.out.println("thread 1: c (" + (now() - started) + "ms)");
sleep(1000);
System.out.println("thread 1: d (" + (now() - started) + "ms)");
yield();
System.out.println("thread 1: e (" + (now() - started) + "ms)");
wakeupAt(finalWake);
System.out.println("thread 1: f (" + (now() - started) + "ms)");
}
}).start();
new VirtualThread(new VirtualRunnable() {
@Override
public void run() throws SuspendExecution {
sleep(500);
System.out.println("thread 2: a (" + (now() - started) + "ms)");
sleep(2000);
System.out.println("thread 2: b (" + (now() - started) + "ms)");
}
}).start();
new VirtualThread(new VirtualRunnable() {
@Override
public void run() throws SuspendExecution {
sleep(1500);
System.out.println("thread 3: a (" + (now() - started) + "ms)");
sleep(100);
System.out.println("thread 3: b (" + (now() - started) + "ms)");
sleep(100);
System.out.println("thread 3: c (" + (now() - started) + "ms)");
sleep(100);
System.out.println("thread 3: d (" + (now() - started) + "ms)");
}
}).start();
// game loop
do {
processor.tick(now());
try {
Thread.sleep(1);
} catch (InterruptedException exc) {
// ignore
}
} while (processor.hasPendingTasks());
}
static long now() {
return System.nanoTime() / 1_000_000L;
}
}
Output: (the entire program runs on 1 thread!)
thread 1: a (27ms)
thread 2: a (527ms)
thread 1: b (1027ms)
thread 3: a (1527ms)
thread 3: b (1627ms)
thread 3: c (1727ms)
thread 3: d (1827ms)
thread 1: c (2027ms)
thread 2: b (2527ms)
thread 1: d (3027ms)
thread 1: e (3028ms)
thread 1: f (5000ms)
The overhead of continuations is next to zero, you have have at least tens of thousands of units with each having a few green-threads for their AI, ticking at 60Hz.