Plowing through bytecodes for the ultimate AI code

[Riven]

You guys might have run into this issue, that when writing AI, you want your units behaviour to be coded as simple as possible, preferably with code that seems to single threaded. The problem however is that each unit would need 1 thread, and that’s just bad for performance, due to both context switches and lock contention.

There are a few alternatives:
[] Splitting your code into very small chunks and schedule those tasks in a queue (poor man’s green threads)
[] Using a library that injects continuations in your code (little less poor man’s green threads)
[*] Using a scripting language that is interruptable, with a local stack and program counter. You have to write your code in another/new language, without IDE support, and performance is probably terrible.

I just had the following idea - and feel free to point out the obvious mistakes… if any.

It would be a major advantage to write your AI code as if it were single-threaded, writen in Java, in your favourite IDE, generating a standard Java ClassFile. Now the idea is not to load it in the JVM, but to interpretate it yourself. It might sound slow, and reinventing the wheel, and what-not, here’s the catch: when you stumble upon the invoke_ family of bytecodes, or getfield/putfield bytecodes, you’d simply use Java Reflection to let the JVM run it at full speed. Suddenly you have this class in which you can step through the bytecodes (with custom program counter, stack) making it possible to put the execution on hold or interleaving thousands of units ‘green threads’, while you’d still be able to call into all your other classes, at full speed.

The interpreter might be 50x (or more) slower than execution by the JVM, but in the end you’re probably doing all the hard stuff in ‘external’ code (JIT compiled classes) anyway, so you might not even notice the performance degradation. It might even be faster (both in coding time as in execution time), as you won’t have to split up your tasks into dozens of Runnables – and we all know interfaces with many implementations end up as massive switch-tables which slows down invoke_special (more or less).

Implementing a Java Bytecode Interpreter that delegates the ‘hard stuff’ to the JVM itself, shouldn’t be too hard, right? The only non-trivial thing is throwing and catching exceptions.

So… what are your thoughts? Best of boths worlds, or did I miss something obvious.

[Demonpants]

I’ve always used the JVM and just thrown the execute call to my class file within my main game loop, just like any other operation. I don’t know if this automatically creates another thread or not, but I’m certainly not doing it personally. Basically each AI or Level script is placed within a class that has a static void main class in it, and it passed a reference to the World so it can do whatever it wants with it.

I haven’t spent much time at all learning about byte code and the JVM’s under-the-hood workings, but the above has never appeared to choke or anything. The only issues I’ve ever had is dealing with classpath.

[jezek2]

@Riven

So… what are your thoughts? Best of boths worlds, or did I miss something obvious.

I don’t see any advantage over continuation library. It would be slower and you have to code the interpreter, with continuations library you have all work already done

[pjt33]

@Riven

It would be a major advantage to write your AI code as if it were single-threaded, writen in Java, in your favourite IDE, generating a standard Java ClassFile. Now the idea is not to load it in the JVM, but to interpretate it yourself. It might sound slow, and reinventing the wheel, and what-not, here’s the catch: when you stumble upon the invoke_ family of bytecodes, or getfield/putfield bytecodes, you’d simply use Java Reflection to let the JVM run it at full speed.

If I’m understanding you correctly (and I’m not at all sure about that), wouldn’t this mean that you couldn’t use methods for any expensive stuff? So you wouldn’t be able to refactor out things like pathfinding.

[Abuse]

@jezek2

I don’t see any advantage over continuation library. It would be slower and you have to code the interpreter, with continuations library you have all work already done

Regarding the referenced continuations library, it doesn’t mention in the pro’s or con’s as to whether source-level debugging is still possible (either when performing the instrumentation as an offline process, or at runtime)

My experience with various instrumentation processes would lead me to believe it isn’t; which I would personally rank as the most serious con of any process that relies upon instrumentation.

[Riven]

@jezek2

I don’t see any advantage over continuation library. It would be slower and you have to code the interpreter, with continuations library you have all work already done

I don’t know whether Abuse’s argument is valid here, as I never worked with Continuation libraries. I’m always a bit weary with code that transforms my code - especially when I don’t know how far the required ‘save stack / restore stack’ propagates through my code.

Further I don’t really like to declare SuspendException everywhere, an annotation that instructs the bytecode transformer to insert it, would have been better - although I’d prefer it to be not in my code at all - but that introduces all kinds of technical problems, as you’d probably have to transform every class then with serious overhead.

This is what I have in mind:

GameUnit unit = new GameUnit();

Interpreter stepper = new Interpreter(unit);
// grabs bytecodes of GameUnit from ClassLoader.getResourceAsStream


stepper.invoke("initiate"); // gotta start somewhere...
while(stepper.step())
   continue;

putfield/getfield on ‘self’ are redirected to passed ‘unit’ instance
all other external calls/field manipulation is done via Reflection.

If nothing else, I expect it to be a good learning experience.

With a fancy ‘AI IDE’ it might even spark more any interest!

The classfile parser is already done, so the first 0.1% wasn’t that hard at all…

[jezek2]

@Abuse

Regarding the referenced continuations library, it doesn’t mention in the pro’s or con’s as to whether source-level debugging is still possible (either when performing the instrumentation as an offline process, or at runtime)

My experience with various instrumentation processes would lead me to believe it isn’t; which I would personally rank as the most serious con of any process that relies upon instrumentation.

This depends on whether that transformation preserves line number mapping or not. In the case of the linked continuation library it seems it preserves it correctly. I didn’t test debugging because my NB and/or Java is somewhat borked from some time and doesn’t allow me to debug (or run jconsole correctly), don’t know why.

@Riven

I don’t know whether Abuse’s argument is valid here, as I never worked with Continuation libraries. I’m always a bit weary with code that transforms my code - especially when I don’t know how far the required ‘save stack / restore stack’ propagates through my code.

Further I don’t really like to declare SuspendException everywhere, an annotation that instructs the bytecode transformer to insert it, would have been better - although I’d prefer it to be not in my code at all - but that introduces all kinds of technical problems, as you’d probably have to transform every class then with serious overhead.

With Matthias Mann’s continuations library it’s simple. Only methods that have SuspendExecution declared are transformed. The checked exception type is there to ensure that any method that could be suspended (directly or just being on stack trace when suspended) will be processed. And it’s logical to mark suspendable methods like this, as it changes flow very similarly like throwables, but to mark it differently (it’s not Exception), it’s actually called SuspendExecution.

Your code flow seems very same to mine handling of game code, practically many methods are not processed as they don’t suspend themselves (nor methods they call). These are usually the ones that actually compute something, and they run at full speed (they’re not transformed). So you have some methods processed and some not in the same class.