Showing posts with label Java. Show all posts
Showing posts with label Java. Show all posts

Friday, August 9, 2013

Multiplayer-TicTacToe

If you read my previous post and/or looked at my GitHub account, you already know that I'm programming a small game of TicTacToe to demonstrate and debug my state synchronization library, Harmonic. At first, I had two engines, where one actually played the game, and the other simply listened. Both engines were located in the same JVM, so identifying them was easy.

At that time, I didn't even have states yet, so the communication exchanged the actual action. This was a problem, because although both engines executed the same actions, there was no way that the application could really know. Only later, when the communication consisted of states, this could really be called synchronization.

The real fun began when I added a notion of branches. A branch points at a state, and can move to other states as well. An engine can publish changes to a branch, and the receiving engine will then ask for the missing states. Branches also make it possible to delve into alternate histories, for example for AI.

Although states and actions are defined as protobuf messages, nothing I described so far contained any networking or IO code. The BranchManager class contains three methods that do communication, but all they do is call a callback method and leave the actual networking to whatever the implementation of that callback sees fit. I added an implementation using JGroups; the same library I used in my last attempt.

And now, I have a graphical multiplayer Tic Tac Toe. Granted, it does not enforce that every client plays only his own pieces, but that's not the point and would be easy to do; it just requires a more sophisticated new-game negotiation. What does work out of the box is spectating. A newly started client does not yet ask for the current state, but as soon as one of the playing clients performs an action, the spectator is also updated.

Right now, to try it, you have to build Polybuf, Harmonic and TicTacToe yourself, which is not optimal. TicTacToe is meant to help me experiment, find out what's good practice and what needs improvement. When it comes to distribution, applications have different requirements than libraries, and fulfilling these requirements is the next thing on my schedule.

Okay, that's fixed now! I have added a git repository that contains a Maven repository. That means you can reference my libraries (for example, in building TicTacToe), and the dependencies can be downloaded from there, without the need for you to build them yourself.

The repository also contains a TicTacToe-0.1.0-jar-with-dependencies.jar, which... well. It also has a MainClass attribute, so it should be reasonably double-clickable. I have only tested it on one machine, and I don't know how the default JGroups-Stack behaves in LANs and WANs, but fixing issues arising from that is a matter of passing a configuration to a constructor...

Thursday, August 1, 2013

Harmonic: Game replication and git?

So I took some time off of trying to implement game replication. Instead, I did some other stuff (like university), and gathered some experience with git. With time, I realized that git, and distributed version control in general, provides exactly those concepts needed for the model of replication I wanted. Looking back at an earlier post on that topic, I can't really say how I expected it to work out. In the end, it turned out that transmitting "unfinished transactions" was a really bad idea; in the end, the very essence of a transaction is that it executes either as a whole or not at all.

Well, anyway, now I had experience with git, and it contained exactly those concepts I needed for my replication as well:
  • a repository of files (objects) in which changes are tracked
  • a history of commits, where commits have a parent/child relation. The main attribute of that relation is what changes happened between those commits
  • branches which point at specific commits and provide a comfortable way of traversing and manipulating the history
  • definition of remote repositories for synchronization of branches
In contrast to the transaction approach I pursued earlier, where the parent/child relationship is in regard to application logic and does not really add to the synchronization capabilities of the framework, this version control approach is based around a tree of commits, where the parent/child relationship is a temporal one, and essential to the framework. The framework is less cluttered with concepts that are not important to it.

Of course, a few things are different: a git repository manages files, essentially byte sequences, while a replication framework manages objects. While these could be interpreted as byte sequences, it doesn't really add to the usability, because objects are usually manipulated on the level of fields and methods. Furthermore, files are organized in a file system with human-chosen names for every single file. Objects simply reside at some location in memory not even the program can control; some other sort of identification is needed. And finally, for file versioning, a human user can try to resolve conflicts. For replication, this is not possible. Conflicts can't be resolved automatically, and as different object store different data, even manual merging could result in inconsistent state.

Luckily, besides the last problem, these can be solved. And for the last problem, usually it shouldn't be a problem in the first place, at least when talking about Magic. Magic is not a game of reaction time, where all players try to do something at the same time, and in the end someone was the earliest. Magic's system of priority defines very clearly which player may take an action at what point, so the game logic can ensure that conflicts do not arise, simply by obeying the rules.

You can take a look at Harmonic if you want. I'm not happy with the name, but I couldn't come up with anything better. I wanted it to sound like multiple independent systems are in sync, like vibrating at the same frequency, or looking the same; I don't think I succeeded, but that's okay as long as it works.

An Entity compares to a file. Entities are objects managed by Harmonic and are identified by a numeric ID. IDs are created by simply incrementing a counter, so creating IDs in different instances of Harmonic is consistent.

An Engine compares to a repository; it is a store of entities. An Engine also manages the different states (analogous to commits), and its current state: in a repository, the files always reflect one specific commit. In the engine, the entities always reflect one state, and the engine knows how to move between the states. Engines are identified with random IDs; as engines are generated on different machines, there is no way to ensure that engine IDs are always different. So, random IDs are used.

States, as mentioned above, compare to commits. Git uses random commit IDs - at least they look random. In Harmonic, the engine ID is part of the state ID. Assuming the engine IDs are different, it's enough to simply increase the ID for each subsequently created state.

Last but not least, Actions and Modifications correspond to the changes that make up a commit. A modification is a single change that is easily reverted, like setting a variable (or creating a new entity ID). An action is a sequence of modifications, so the action can be reverted by reverting the modifications making it up.

In this model, states, containing actions, are transmitted between engines, but modifications are not. Actions are defined by the application, so they may be as small as needed and as big as possible. The modifications making up the action are only created during execution, so they don't need to be transmitted, making large actions more efficient. For example, instead of transmitting that a card is tapped and mana is added to a mana pool, it's now enough to transmit that a mana ability of a land was played.

I like the direction where this is going. I think distributed source control is an elegant concept, and I don't think I did a bad job at catching its essence, so this should turn out to be pretty usable. In fact, while developing Harmonic, I also wrote a game of Tic Tac Toe that uses it, so I have a proof of concept that Harmonic really works as intended in a turn based game.

Wednesday, July 31, 2013

I'm back(?) and polybuf

I hope I am!

I was just thinking I was in the mood to write something for my blog. And I have things to talk about. I have some new code online at github; Polybuf and Harmonic might be intersting to you.

Mind you that I don't have any Laterna Magica code online there. I'm not sure about LM's future, besides that it will definitely have one! Looking at the history, it seems it was over two years ago when I added the last bit of real functionality. Somewhere in that time frame, I realized that the whole architecture of LM wasn't able to address all the stuff I wanted to get out of it - and that stifled the fun I had with the project.

But LM was always in the back of my head. I tried to figure out what I wanted, what I needed to do so, and what was fun for me to make at that moment. And here I am, writing a new blog entry, because it's fun to me. I hope it will stay fun to me, so I hope I'm back!


Now to make this post not entirely meta, let's talk about protobuf and polybuf.

Protobuf is a protocol library which is apparently widely used inside Google. You specify a protocol using .proto files, and protobuf creates code to read and write that protocol. It's basically a replacement for serialization, and provides code generators for different target languages, so that programs written in different languages can exchange data.

The protobuf code generator supports options that let you control how the code is generated; without losing protocol compatibility, you can code that is more or less optimized for memory footprint, code size, parsing time. Protobuf is only one serialization replacement library of many, and depending on how you run your benchmarks, you probably get different results as for which is the fastest. Anyway, protobuf definitely has the features I need, whether or not it's the "best", and it's supposed to have good documentation. I can't complain so far.


One thing I didn't like about serialization from the beginning is that you throw the Serializable interface right into your code. Exporting and importing state is a very specialized aspect of a software, and it's likely not directly related to the core classes of your software. The thought behind serialization is that adding the implements Serializable clause immediately enables you to serialize your objects - but that's only true if your object really correspond to whatever you would want to transmit over the network or store on this. Any discrepancies mean that you have to work around this central concept of serialization, often making the code further less readable, and further clogging your classes with logic that does not correspond to their original concerns.

And after you're finished with all this, you have a class that has logic for one specific serialization mechanism. If you want to switch that mechanism out, you have to plumb directly in your application logic classes, instead of replacing some auxiliary import/export classes.

And there comes the fact that Serialization semantics are... funny to begin with. Deserialization does not invoke a constructor of the class to deserialize. It creates an empty object without using constructors and then populates the fields manually from the stream. Deserialization can even modify final fields. But, after that, you yourself can't, even using the mechanisms that deserialization provides.


Protobuf (and its likes) kind of work around these problems. You're not serializing your logic objects, but dedicated messages that have well defined serialization properties. On the receiving end, you can restore your object using whatever constructors and methods you seem fit. That seems like more work, but only in the short run; your benefits are familiar semantics (constructors and methods), separation of concerns, easier reaction to changes (through the separation, and the fact that protobuf was created with the explicit goal of compatibility between protocol versions), and of course improved performance through dedicated code instead of reflection.

One thing, by the way, that protobuf does not support, is polymorphism. The reason is simple: there are other patterns in protobuf that enable the same functionality, and polymorphism is a feature handled differently in different languages (Java has no multiple inheritance, and C obviously has no inheritance at all). Making Polymorphism a feature on that level limits the interoperability of protocols.


And that's where polybuf comes into play, and where I'll finally show some example code. Polybuf is essentially a convention on how to format messages that contain polymorphic content, and a collection of classes that facilitate deserializing these messages. At the core is the polybuf.proto file, showing the relevant parts:

message Obj {
  optional uint32 type_id = 1 [default = 0];
  optional uint32 id = 2 [default = 0];
  
  extensions 100 to max;
}

Proto files contain message definitions. The messages declare fields that may be required, optional or repeated. required is actually not recommended, because it makes changing the message slightly harder. This message features only one data type: uint32. Protobuf encodes these as compact as possible; small numbers will take less than four bytes; big numbers may be larger. For values where big values are expected, there are other fixed length encoding types. Every field has a numeric tag that is used instead of encoding the field name. Fields can be removed and added without breaking compatibility, as long as these tags are not reused - at least on the protobuf level. Of course, the application must be able to process messages where some fields are missing; that's what the default values are for. These are not transmitted. The receiver simply fills in the values if the field was not present (very possible for optional fields).

Below these two fields, there is an extension declaration, and now it becomes interesting: 100 to max specifies that all field tags greater than 100 are free to use for extensions. There is an example directly in the file:

//  message Example {
//    extend Obj {
//      optional Example example = 100;
//    }
//    
//    optional string value = 1;
//  }

The Example message declares an extension to Obj, which is simply a set of additional fields, labeled with tags from the extension range. It has nothing to do with and extends clause, and is pretty independent from the Example message; it just happens to be there for logical grouping. The only consequence from the placement is the namespace used by the extension.

The Example message itself declares a field value, plain and simple. Now, where's the benefit? Imagine there's a class Example in your program and you expect it to be subclassed, but want to still support protobuf serialization. This structure allows you to
  • reference an Example by declaring the field as Obj,
  • create an Example by setting type_id to 100 (the extension tag used by Example), and filling the example extension field with an Example message,
  • create an ExampleSub message that uses a different extension tag, and simply fill both the Example and ExampleSub extension fields. From the type_id field, you can see that it's an ExampleSub object, and since you know the ExampleSub class structure, you know that there will be an Example message containing the superclass fields.
  • The same goes for multiple inheritance: If you know that the type_id-referenced class has two superclasses, simply read both superclass extension messages from the Obj.
Of course there's some Java code supporting this message structure to give a more serialization-like experience. Look at it. Input and Output are similar to the streams you're used to; however, they don't convert objects into bytes and vice versa, they convert between objects and Objs. From there, it's only a small step to networking and persistence. Config stores the IO objects that actually translate between objects and the corresponding extension messages. The Config is reused for subsequent Input and Output uses.

The IO interface is the most interesting one. Its three methods specify clearly the semantics that polybuf expects for (de)serialization, making it easy to understand what's going on. It extracts the logic from private methods in the class itself into a place that is actually meant to handle that concern, and gives the programmer full control over what data is (de)serialized, what constructors and methods should be called. And last but not least - these IO classes support inheritance! Deserializing a subclass can be as simple as subclassing the superclass IO, add your own subclass initialization and persistence, and delegate to the superclass IO for fields that belong to it.

Wednesday, June 27, 2012

Properties and relationships - it won't get easier

Okay, now to show you the peak of what I've done using ASM: Look at these classes:

@PropertyFactory("p")
public class Test {
    protected final PropertyChangeSupport s = new PropertyChangeSupport(this);
    protected final Properties p = new BoundProperties(s);
   
    @Property
    private String s;
    
    public void setS(String s) {this.s = s;}
    public String getS() {return s;}
    //add/remove PropertyChangeListener methods
}

//test code
Test t = new Test();
t.addPropertyChangeListener(...); //prints to System.out
t.setS("hello"); //listener fires!

With the right setup (and with setup I don't mean things you have to do every time; it's just either configuring a ClassLoader or transforming the bytecode directly after compilation), it's as simple as that to add property change support, and other things; in fact everything that can be done with a Properties object. (in case you never heard of that creation, look at the code) And there is another thing I have done using properties: bidirectional 1:1, 1:n and m:n relationships, which is pretty nice if it's as simple as this:

@PropertyFactory("p")
public class A {
    protected final Properties p = new BasicProperties();
   
    @OneToOne("a")
    private B b;
    //getters and setters
}

@PropertyFactory("p")
public class B {
    protected final Properties p = new BasicProperties();
   
    @OneToOne("b")
    private A a;
    //getters and setters
}

//test code
A a = new A(); B b = new B();
a.setB(b);
System.out.println(b.getA() == a); //true!

I'm skipping the other cardinalities, and the two examples here were a little modified, but they are functional! It's not simplified beyond what's necessary for the code to actually work as advertised. If you want to take a look at the complete test cases, look here. It also includes a ClassLoader that can do the job, as well as the setup for junit that invokes the test code on the modified class.

Okay, the advertising is over; one or two sentences about the internals:
  • The class loader that is used prints all classes it loads (that is, the test classes) to a directory structure analogous to java's package structure. The printed text is the disassembled bytecode that is actually loaded - so not the same code as the compiled class files, and even some classes that are not present in the sources. If you can read bytecode, that's perfect to see every detail on how a simple this.b = b; comes to setting the private A a; in the newly referenced B instance.
  • The relation annotations create a new attribute, for example OneToOne<A> a$o2o; (with default access). This is essentially the field you would name a if not making your life easier with ASM.
  • That field is accessed by a class like B$$a$o2o_EntityFunction (For the OneToOne field named a in class B). It implements a simple interface and implements only one method, taking the B instance and returning the OneToOne object. Since the class is in the same package as B, the access is allowed, and any classes can be related without exposing any normal-java accessible fields for other classes.
I hope you can get your benefits out of this little gem!

Saturday, June 2, 2012

Under the Hood: Creating a class with ASM

Now, let's get serious! We know how ClassLoaders are responsible for getting the binary class data to load Java classes, and we know how that binary class data actually looks. What's missing is a way to effectively modify that data, without worrying too much about the low-level details of data storage in a class file.
And that's where ASM comes into play. ASM is one library (BCEL is another) for bytecode manipulation, and it seems to be the "tool of choice" out there. That means it's relatively active in development, yet mature and usable. Let's dive straight into a code example for creating (not modifying) a class with ASM:

public class AsmBuilder implements Opcodes {
    public static final byte[] HelloWorld = HelloWorld();
  
    private static byte[] HelloWorld() {
        ClassWriter cw = new ClassWriter(0);
      
        cw.visit(V1_6, ACC_PUBLIC | ACC_SUPER, "net/slightlymagic/asm/test/HelloWorld", null, "java/lang/Object",
                null);
        cw.visitSource("<generated>", null);
      
        HelloWorld_init(cw);
        HelloWorld_main(cw);
        HelloWorld_hello(cw);
      
        return cw.toByteArray();
    }
  
    private static void HelloWorld_init(ClassWriter cw) {
        MethodVisitor mv = cw.visitMethod(ACC_PUBLIC, "<init>", "()V", null, null);
        mv.visitCode();
        mv.visitVarInsn(ALOAD, 0);
        mv.visitMethodInsn(INVOKESPECIAL, "java/lang/Object", "<init>", "()V");
        mv.visitInsn(RETURN);
        mv.visitMaxs(1, 1);
        mv.visitEnd();
    }
  
    private static void HelloWorld_main(ClassWriter cw) {
        MethodVisitor mv = cw.visitMethod(ACC_PUBLIC | ACC_STATIC, "main", "([Ljava/lang/String;)V", null, null);
        mv.visitCode();
        mv.visitTypeInsn(NEW, "net/slightlymagic/asm/test/HelloWorld");
        mv.visitInsn(DUP);
        mv.visitMethodInsn(INVOKESPECIAL, "net/slightlymagic/asm/test/HelloWorld", "<init>", "()V");
        mv.visitMethodInsn(INVOKEVIRTUAL, "net/slightlymagic/asm/test/HelloWorld", "hello", "()V");
        mv.visitInsn(RETURN);
        mv.visitMaxs(2, 1);
        mv.visitEnd();
    }
  
    private static void HelloWorld_hello(ClassWriter cw) {
        MethodVisitor mv = cw.visitMethod(ACC_PUBLIC, "hello", "()V", null, null);
        mv.visitCode();
        mv.visitFieldInsn(GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;");
        mv.visitLdcInsn("Hello, World");
        mv.visitMethodInsn(INVOKEVIRTUAL, "java/io/PrintStream", "println", "(Ljava/lang/String;)V");
        mv.visitInsn(RETURN);
        mv.visitMaxs(2, 1);
        mv.visitEnd();
    }
}

What you see here is a series of visitSomething() calls on a ClassWriter (which implements ClassVisitor) and the MethodVisitors created from it. The Opcodes interface impelemented just gives us easy access to some useful constants. Before elaborating on the Visitor pattern next time, let's go through the calls:

ClassVisitor.visit() gets all data that is necessary once for a class definition; that includes class version, access flags like public, class name, superclass name, signature (for generic classes like List<T>) and an array of implemented interfaces. visitSource() gets one piece of optional information; the source file name, plus a debug string that I know nothing about.

Now to the interesting method instructions: visitMethod() again takes some data that is needed once for each method: access flags, name, method descriptor, signature, and declared exceptions. visitCode() simply indicates that the actual instructions follow, as opposed to the optional annotations.
visitVarInsn(ALOAD, 0) takes an opcode that works with local variables (either LOAD or STORE) of a specific type (a reference in this case; don't ask me why the prefix is A) and takes the index of a local variable; as I said earlier, 0 is the implicit this reference for nonstatic methods. So, in plain words, this instruction pushes this onto the stack.
visitMethodInsn(INVOKESPECIAL, "java/lang/Object", "<init>", "()V") invokes a method. In this case, because it's a constructor (see the name), using the INVOKESPECIAL opcode. There are four other INVOKE opcodes, but we'll only see two others in this example. The next argument is the owner, i.e. the class containing the called method, followed by name and descriptor. If you haven't guessed it, this is a super() call, invoked on this. (Ironically, writing this.super(); in Java is illegal, yet the implicit reference is needed of course)
Last but not least, there's visitInsn(RETURN). Unlike visit*Insn(), visitInsn() takes no additional arguments, because the opcodes supported by this instruction simply don't need any. RETURN is only one of many RETURN opcodes for void methods (including constructors).
Finally, there's visitMaxs(1, 1) and visitEnd(). The maxs are stack and local. stack is 1, because there is at most one entry on the stack, namely this after ALOAD 0. And the sole local variable is, again, this, ammounting for 1 again.

A look at main([Ljava/lang/String;)V: We have a new type of instruction again! visitTypeInsn(NEW, "net/slightlymagic/asm/test/HelloWorld") takes an opcode that needs a class name. In this case, we allocate a new object (of our class) on the heap.
visitInsn(DUP) duplicates the top element on the stack, i.e. the reference.
visitMethodInsn(INVOKESPECIAL, "net/slightlymagic/asm/test/HelloWorld", "<init>", "()V") invokes the constructor on our new object. Think about it: the constructor has an implicit argument that must be on the stack prior to calling, and in the case of additional parameters, these have to come even after the new reference, so there's essentially no way to integrate the constructor call into the NEW opcode. (Well, of course you could, but why complicate the VM by introducing a different order of arguments for constructor calls if you can make it a really regular INVOKESPECIAL call simply by splitting object creating into two opcodes?) And here, you have the reason for the previous DUP: <init> is void, but we want to use the object afterwards, so we have to keep the reference on the stack some other way.
visitMethodInsn(INVOKEVIRTUAL, "net/slightlymagic/asm/test/HelloWorld", "hello", "()V") invokes hello(). INVOKEVIRTUAL is probably the most common INVOKE opcode. It's used for all nonstatic, non-constructor, non-interface methods (and now, if you wonder what the fifth variant, as hinted above, is: it's INVOKEDYNAMIC, which is a new feature targeted at dynamic JVM languages, not Java itself). The big point about virtual method invocation is overriding. The VM searches for an overridden variant of the called method, which is not necessarily that of the owner class given in the instruction.
visitInsn(RETURN); visitMaxs(2, 1); visitEnd(); there were two entries on the stack after DUP, and there is one parameter [Ljava/lang/String; in the main method.

Now hello()V: visitFieldInsn(GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;"), yet another type of instruction. visitFieldInsn() supports the four logically named opcodes GETFIELD, GETSTATIC, PUTFIELD and PUTSTATIC. The nonstatic variants take a reference from the stack for obvious reasons. Then there's an owner, a field name, and a field descriptor. Unlike LOAD and STORE, where there's no descriptor, but different opcodes for different types.
visitLdcInsn("Hello, World"), where LDC stands for "load constant". The argument is of type Object, but must be a primitive wrapper like Integer, or String.
visitMethodInsn(INVOKEVIRTUAL, "java/io/PrintStream", "println", "(Ljava/lang/String;)V") is our first method invocation with real arguments! I hope you can follow what's currently on the stack; there's a PrintStream (System.out) and a String ("Hello, World"), and now we're invoking a nonstatic method of PrintStream, taking a String as an argument. Knowing the order of elements on the stack is important when trying to modify bytecode; obviously, when you insert instructions, you have to leave the stack as you found it to have the following code work correctly (and don't forget to tamper with maxStack afterwards!)
visitInsn(RETURN); visitMaxs(2, 1); visitEnd(); there were two entries on the stack after LDC, and the method is not static.

Now, to make this post longer, and not make you wait on how to invoking your new class, let's look at the classloading part. we have byte[] containing the class and need a Class from it. Take a look at this simple custom ClassLoader:

public class DynamicClassLoader extends ClassLoader {
    private final HashMap<String, byte[]> bytecodes = new HashMap<String, byte[]>();
   
    public DynamicClassLoader() {
        super();
    }
   
    public DynamicClassLoader(ClassLoader parent) {
        super(parent);
    }
   
    public void putClass(String name, byte[] bytecode) {
        bytecodes.put(name, bytecode);
    }
   
    @Override
    protected Class<?> findClass(String name) throws ClassNotFoundException {
        //remove here, because the class won't be loaded another time anyway
        byte[] bytecode = bytecodes.remove(name);
        if(bytecode != null) {
            return defineClass(name, bytecode, 0, bytecode.length);
        } else {
            return super.findClass(name);
        }
    }
}


... and take a look at that simple main method:

public static void main(String[] args) throws Exception {
    DynamicClassLoader l = new DynamicClassLoader();
    l.putClass("net.slightlymagic.asm.test.HelloWorld", AsmBuilder.HelloWorld);
   
    Class<?> HelloWorld = l.loadClass("net.slightlymagic.asm.test.HelloWorld");
    HelloWorld.getMethod("main", String[].class).invoke(null, (Object) args);
}


Of course, we can't plainly reference a class that isn't present at compile time, but we can use reflection to test it. Of course, normally the generated class would implement some interface so we can store it in a variable other than an Object, and make regular method calls through the interface.

Wednesday, May 30, 2012

Under the Hood: Java Bytecode

So, now that we have cleared up how a Java application is executed, I can talk about bytecode manipulation, a technique to modify the compiled classes before execution.
There are two possible times when modification can occur: at build time, modifying the class filers after compilation, or at runtime, using a class loader that modifies the bytes of the class before passing them on and actually defining the class from it. Both have their advantages: Build time simplifies the structure at runtime; your application runs like an ordinary Java application, except that not all of its classes were ordinarily created from Java source code. Runtime gives you the possibility of applying different modifications in different executions, which could be used to, say provide compatibility to different environments. More importantly in my opinion, this allows to create completely new classes based on user input!

Let me give you an example: You make an application that draws the graph of a function the user types into a text field, so basically you take y = f(x) for each coordinate visible in the plot; that's a lot of times and you want to compute your function very quickly. So, instead of parsing the expression, building a tree from it, inserting a new value for x, and then evaluating the function, wouldn't it be nice to parse the expression into a real Java class that is executed on the tested and optimized JVM, with the possibility that your code is even JIT-compiled into machine code for an extra boost?

And guess what - that's not only possible, but even relatively easy, once you've grasped what java byte code looks like, so that's what were going to look at now. It's pretty straight forward that a class consists of fields and methods, and when you think about the fact that inner classes have separate class files, it becomes clear that there must be some information about enclosing class and inner classes, too.

The code of methods is of course where it gets interesting. The JVM is a stack based machine, which means that values are kept in a last-in-first-out data structure, and every operation pops a specific number of values from the stack and pushes its results onto the stack again. Note that this data is not related to local variables or fields; here, we're basically talking about the steps taken in evaluating an expression.
Also, type names have a special form in class files. Where a class name is needed, a string of the form java/lang/Object is used; where it could be a primitive type, too, this is wrapped into L...;, where L somehow was chosen to mean "object type", and ; denotes the end of the type name. As another example, long, which can't use the L, was given J as the identifier, and boolean uses Z; arrays prepend a [ for every dimension. A method, for example int indexOf(char ch) or String substring(int beginIndex, int endIndex) would be described as (C)I or (II)Ljava/lang/String; - note that the name is not part of the signature but stored separately.

And that's all you really need to know, except for the few less than 256 possible commands (opcodes) that the JVM knows. The details of how all the strings are stored in a classfile is hidden from you when you use ASM to generate bytecode.

Now let's look at some bytecode, as this is where it gets interesting. A simple example first:

package Example;
class Example {
    int a;
    void example(int a) {
        this.a = a;
    }
}

...and the bytecode for example():


example(I)V
ALOAD 0
ILOAD 1
PUTFIELD example/Example.a : I
RETURN


MAXSTACK = 2
MAXLOCALS = 2

ALOAD pushes a local variable onto the stack. In this example, there are - surprise - two! Not only is there parameter a, there's also the implicit this of every nonstatic method. When both are on the stack (explaining the MAXSTACK entry above), PUTFIELD can take the second value and store it into the named field of the first reference on the stack, which better be an instance of Example.

Let's take a more complex example:

package Example;
class Example {
    int a;
    Example(int a) {
        this.a = a;
    }
}

...doesn't seem so? Look at the bytecode:

(I)V
ALOAD 0
INVOKESPECIAL java/lang/Object.<init> ()V
ALOAD 0
ILOAD 1
PUTFIELD example/Example.a : I
RETURN

MAXSTACK = 2
MAXLOCALS = 2

First of all, as you see, constructors are internally void methods with special names. The special code here is ironically the one that we didn't write ourselves: the superconstructor invocation.

Okay, that's it for today! Thanks for reading!

Monday, May 28, 2012

Under the Hood: Classloading

I'm kind of a tinkerer... I like exploring new aspects of things I already know, or new things altogether, even if there is no apparent gain in it. And I bet many of you (well, if there were many readers in the first place...) share this trait with me, because it is one of the things that most engineers share.

The "thing" that I explored in the last week is Java itself, and the new aspect is the Java Bytecode, along with a few intricacies of Java that most programmers never have to worry about, namely bytecode manipulation and class loading.

Just in case you are not aware of it, I'll first describe the lifecycle of a HelloWorld program from writing it, up to its execution. It all starts, of course, with a source file. In the standard case, that's HelloWorld.java, but there are other languages, like Groovy, Scala and JRuby, that all run on the JVM.
This leads us directly to our next step, compilation. The JVM is, as the name suggests, a machine, just like any computer (except it's "virtual"), and has an instruction set it can execute. The Java compiler javac translates the more or less human readable source code into a .class file that contains code executable by the JVM, as do other compilers like gcj or scalac, except that in case of scalac, the source is written in a different language of course.

One aside about gcj: there are a few Java compiler vendors around, but by far not as many as for other languages like C. The answer is, again, the JVM: while a C compiler creates code for a specific architecture and OS, and therefore each new platform needs a new compiler (although much logic can be reused, of course), Java targets only a single platform, the JVM. Therefore, there's no inherent need for numerous compilers and Java doesn't have the problem of incompatible dialects. Still, there is some competition; for example, gcj is an open source alternative to javac. More importantly, the part of Java that is platform specific is the JVM. In Java's early days, Microsoft had its own Java implementation, which was kind of crappy compared to Sun's and was thankfully soon discontinued. Additionally, there are VMs implemented in Java, or ones that target platforms where Oracle does not provide support, or ones with smaller memory requirements, etc.

So, now we have a class file consisting of Java bytecode, independent of the language we started with. Using the java command, we can launch the main method of that class, but this involves more steps than are apparent!
Every java application has a system class loader. A ClassLoader is responsible for finding class files, reading them, and loading the classes into memory. In the most basic case, the classloader has a list of URLs (the classpath) that contains locations where classes are found. By default, this classpath contains the JRE classes (plus some more) and those found in the current directory, e.g. HelloWorld.class. Other classloaders delegate to a parent classloader, but may add new search locations or other means of getting the bytes that make up a class.
Now, the classloader loads the main class of the application, and the main thread starts, executing the main method. This method may in turn require other classes which are then loaded by the same classloader that also loaded the current class. This means by extension that normally, all classes are loaded by the same classloader that also loaded the main class. However, it's also possible to create and invoke classloaders directly, creating a class that was loaded by a different classloader than the current class. This is important because of two things. Firstly, as I said, the new classloader can add new ways of loading classes (the main reason for using a separate classloader), and secondly because it can introduce subtle problems when multiple classloaders define classes with the same name: they are not compatible, and you get a ClassCastException when you try to mix them. Don't worry, there's an easy solution: define an interface that is loaded by a common parent classloader, and only cast to the interface.

And finally, our main method can execute. And since this post was already long enough, I'll tell the story about bytecode manipulation with ASM next time ;)

Friday, December 30, 2011

Java 5 compatibility is hard

From the times when I read the bug thread of Forge (about a year ago or so), it seemed to me that a lot of users, especially those on Macs or at work, were still using Java 5. I have no idea how it is now, but I still try to code and compile Java 5 compatible for exactly that reason.

Usually, it works out one way or another, but not today. I wanted to try JGroups (a story for another time, after I actually succeeded in it), but even the releases that are advertised (if you can call it that) as Java 5 compatible seem to be compiled in the Java 6 binary format. Since only part of the featureset I'm trying to implement depends on JGroups, I wanted to at least create compatible class files, even if using these features will fail on a Java 5 runtime.

There are basically two inputs to the compiler: my own Java 5 compatible code, and the already compiled Java 6 compatible bytecode. My output of choice was Java 5 compatible bytecode. After all, this output does not contain anything not Java 5 compatible, so I thought I was good to go. Using a Java 5 compiler will of course fail, because it can't read the necessary classes, but Using a Java 6 compiler with compatibility settings should work...

There are a few features new in Java 5, like generics, annotations, enums and for-each loops. It sounds reasonable that compiling Java 5 source code to Java 1.4 byte code won't work. Java 6 also has a new byte code format. It supports a new verification mechanism, and while the compatibility notes say that the compiler outputs this format only "by default", there is no way (I have found, at least) to change it: The most obvious way of setting the compiler arguments: javac -source 1.6 -target 1.5 gives an errror that source release 1.6 requires target release 1.6 - which exactly contradicts what is said in the compatibility notes.

It turns out that the Java 6 compiler can take Java 6 bytecode input even if the source setting is 1.5. That there's an error for 1.6 + 1.5, even though the Java language hasn't changed, is kind of absurd in my opinion... well, better having an absurd solution than none at all...