Feeling Grumpy?

Grumpy, might have been mentioned a few times here and there already, but what is it? 

It is a little project for Groovy we are currently working on and the project title is for now Grumpy. Grumpy is no final name, we use it really just until we found a final and more serious name.

The goal of Grumpy is to have a static type checker for Groovy driven by an annotation. This will be optional and not cause any changes to normal Groovy. We see this as part of the Java migration story, in which people may not want the dynamic type system of Groovy everywhere. Grumpy is also no static compiler, it will be normal Groovy under the hood. I will not exclude a future static compiler based on Grumpy, but that is not the primary purpose of Grumpy. also we don't want to compete with Scala here. For my taste their type system is too complex. We may go beyond Java's system though, if we think it makes sense.

Basically there is a static type checker with Groovy++ (and a static compiler), but integrating that into Groovy just for type checking will mean either to integrate huge parallel structures, that no one but the Groovy++ people do understand. Or it means to invest a lot of time to transfer everything over, probably more than it takes to write the type checker new. Thus we decided to make a new type checker and try to involve the community as much as possible on every step.


How will it work?
So far you will be able to annotate methods or classes and an AST transform will then perform some type checking on that code. We don't want any new syntax constructs for Grumpy. This means only a subset of Groovy will be accepted by Grumpy.

Can I mix dynamic typed code and Grumpy?
Yes you can. If you use the per method level annotations you can just use a different method for the dynamic or grumpy code. So far we have no annotation that will turn dynamic typing on again for the case you used the class level annotation, but that may follow in the future.

When will it be available?
Grumpy will be part of Groovy 1.9, the next beta will already include a pretty advanced Grumpy.

What will Grumpy do about the GDK?
For those, that don't know... the GDK is a set of methods we use to enhance standard Java classes. For example we have an "each" method on Collections, to iterate over the list using a Groovy Closure. Grumpy will support all GDK methods, but to enable type checking in those Closure blocks, there will have to be much more work.

Much more work?
In for example "int i=1; [1,2].each {i += it}" you want to ensure nothing is added to i, that is not compatible with int. Since we cannot possible let the compiler know about how each of those GDK methods is working by code, we will have to find a way to do that more automatically. The Java type system with generics is not really able to express our needs here. For example if you iterate a Map using each, you have one variant, that takes a Map.Entry, another one, that takes key and value. If you just declare everything as Object, you won't gain all that much in terms of type checking. most probably we will have a second annotation for this kind of thing, in which we will store a String with extra type information. The goal here is to let the compiler add this annotation on its own for Groovy code, but for predefined Java code we will of course have to depend on the user doing that, or not having the type information.

Anyway, I am sure Grumpy will be an interesting project. Feel free to suggest names

About primtive optimizations - Come into being

New idea?
The idea to those kind of optimizations is by far not new in Groovy. In very early days the compiler had two modes of operation, where one was doing a more or less direct compilation as static language. But this compiler mode was not paid attention to for years and then finally removed by me. The normal compiler evolved far beyond that one and the language itself had a long history of semantic and syntactic changes back then already. As some may remember, it took Groovy 5 years to get to an 1.0 version.

Even if we ignore those first failed attempts, my optimizations are still not really new. Many other languages know the concept of slow and fast paths, ways of switching between them and so on. Going to the JVM language summit for several years is going to influence you.

So what is the idea?
The idea is to have some kind of guard, which decides if we want to do a fast path or a slow path. Of course we prefer the fast path, but it is not doable if for example we want to do a 1+1 and the integer meta class defines a new add method, making your fast path resulting in a wrong value compared with the slow path.

Synchronization is bad
The first big problem was thus to find a way to recognize meta class changes and react to them. This guard has to be as simple as possible. If we compare ourselves here with Java for example, then every little extra does cost you badly. The classic way, as call site caching does it, is far from ideal. to ensure no category is active we have to test - in the end - a volatile int. That may not be much you think, but this volatile int represents a big barrier for inlining and internal compilation by hotspot. Volatiles are something we have to avoid.

But if our guard is not using volatiles and not using any kind of synchronization, lock or even fence, then this means meta class changes done in one thread may not be seen in another thread. It is not that they would be invisible, there are normally enough synchronization mechanisms involved during execution to give a piggyback ride (see piggybacking on synchronization from Java Concurrency in Practice). If the user wants better controlled synchronization the user would then have to add synchronization code of his own, that enforces such happens-before-relationship... for example waiting with a BarrierLock in the Thread that is supposed to see the change and do the change in the other Thread, to later then reactivate the waiting thread. the change will become visible to the other Thread, even though we didn't synchronize the guard directly. In most cases though I dare to say this is not really needed.

Simple boolean flags
The next problem with checking, if a meta class is unchanged is to actually get the meta class. Since we are talking about for example int here, we would have to go the ugly way and request the current meta class from the registry. This again involves a lot of synchronization and many many method calls on top of that. If our guard should be as cheap as possible, then this is bad. Maybe even so bad, your guard is eating up all the performance gain of the fast path. I decided for a different way then.

I plug a listener into the MetaClassRegistry, which reacts to set meta classes for Integer and then set a boolean according to that. The default of the flag indicates, no custom meta class has been set and since MetaClassImpl does not allow for modification later on, we are safe in our assumptions for the fast path. The first guard is therefore a boolean flag in DefaultMetaClassInfo and some easy method calls to see on this flag. I implemented a logic that allows to enable the flag again, after a custom meta class was used. Another way for custom meta classes is the meta class creation handle. Setting that one will thus also disable all the fast paths. For this I use a different boolean. This boolean then represents: no active category && no meta class creation handle set. This normally means a globally enabled ExpandoMetaClass will not allow for the fast path changes to play out.

My branch point for slow and fast path for int+int is then guarded by two boolean checks, one for the standard meta class usage in general, the other for Integer specifically.

Piggybacking
For the reader this solution may look easy and simple, but I must confess coming up with that one took quite some time on my side. I was facing the volatile problem and looked into fences for a while before I found it is nothing for Groovy. Only then I started wondering what may happen if I don't synchronize at all and stumbled upon piggybacking, which fits my needs well enough.

Now that we know when to take the fast path, it is time to actually implement one. The theory is that int+int in Java is quite fast compared to Integer+Integer, because the JVM has special instructions for operations on primitives. That means we need to use the IADD operation.

Object operands
People knowing internals of Groovy may realize at this point, Groovy has primitives in the fields, in method signatures, but not for local variables. Even worse, every primitive gets boxed right away. This has partially historical reasons, but in the end it boils down to having less trouble with emitting bytecode. Not only comes there a big amount of additional instructions for primitives, some of them take also 2 slots (long and double), making basic operations like swapping the last two operands on the stack a little problematic. Of course, if I want to benefit from the fast operations on primitives  I have to have them primitive. Of course without losing the ability to handle them as objects if needed.

So I had to rewrite the compiler to trace the operand stack in a way that allows me to see if I need to do boxing or not. From the first tests to actually having that for Groovy 1.8.0 this took a big part of my time. I used the opportunity to refactor the gigantic AsmClassGenerator into many smaller parts and establish some logic, allowing everything to be visited twice (one time slow path, one time fast path), with some more abstraction what to use here and there.

Type extraction
Another problem to be faced was: When do I actually have an int? If I have a local variable or field declared as int, then well, then I know I have. If it is an int constant, I know I have, but beyond that? My first tests also showed another problem: If I check the guards for each expression, then checking the guards consumes too much time.

So he decision was to guard statements, or if possible blocks of statements. For the statement there are then two versions, the fast and the slow version, where each expression in the fast version, may be handled as part of the fast path. If I have now i = a+b+c+d+e, I still have only one int guard - assuming i,a,b,c,d,e are all ints.

In this there is yet another part we have to look at. Is int+int an int? Only then we can guard using an int and safely do a+b+c. Luckily Groovy does not have type promotion, so there is no danger of a+b giving a long as result. a+b will stay int, even in the overflow case. Staying in the same group are also minus and multiplication, devision not, because int/int results in a BigDecimal. Other allowed operators are the shifts of course, the binary operations and modulo. The last mathematical operation is not allowed, the power operator ** has type promotion, so I cannot safely assume it working on int.

Stupid Fibonacci
A typical test I used, that concentrates on not too many operations, is a Fibonacci function:

int fib(int n){

  if (n<2) return 1

  return fib(n-1)+fib(n-2)
}

But if I am going to only implement n-1 and n-1 as fast path elements, I will not gain pretty much performance. The function is dominated by one compare, 2 minus operations, 1 plus and two method calls. The two minus operations are therefore only a small part in this. To also optimize the plus I need to know the return types of the fib method calls. In ordinary Groovy I will not know the return types.

This led me to want to optimize the method call in this case as well. In general this is a problem not really easily solvable in Groovy, but if I limit the optimization to only calls on "this", then I have a chance, because then I need to check only the meta class of the current class and since the current class is a Groovy class I have some freedom. I implemented another flag, that indicates, the current class is using the default meta class.

The result was that I now could emit optimized code for fib(n-1)+fib(n-2) guarded by thee guards now. Testing the result was not encouraging though. I gained maybe a third in performance. Compared to Java this was by far too slow.

Groovy standard compare is slow
By using a profiler I found that a lot of time is actually burned in the compare. The n<2 branches of into a gigantic internal function for all kinds of cases. I imagine hotspot simply going on strike for this one. That means I have to emit specialized code for the compare as well. Actually the principle is the same as before. int+int normally results into int.plus(int), and n<2 in n.compareTo(2). Of course I don't want to call the compareTo, just the same as I didn't want to call the plus. There are special VM instructions for this kind of thing and I should use them. And I did. I also did a small optimization in this code. Since now the first statements is guarded by 2 flags and the second statement by 3,  of which 2 are identical I made all 3 flags be checked for both statements. In the AST they are in a BlockStatement, so I kind of guarded that one instead of the single statements. That the BlockStatement has nor representation in the bytecode should not bother us. in the end it is some checks and some jumps only. The shortened bytecode looks then like this:

  public fib(I)I

   L0

    INVOKESTATIC test.$getCallSiteArray ()[Lorg/codehaus/groovy/runtime/callsite/CallSite;

    ASTORE 2

    INVOKESTATIC org/.../BytecodeInterface8.isOrigInt ()Z

    IFEQ L1

    GETSTATIC test.__$stMC : Z

    IFNE L1

    INVOKESTATIC org/.../BytecodeInterface8.disabledStandardMetaClass ()Z

    IFNE L1

    GOTO L2

   L1

    /* slow path ... */

   L2

    /* fast path ... */

    ILOAD 1

    LDC 2

    IF_ICMPGE L5

    ICONST_1

    GOTO L6

   L5

    ICONST_0

   L6

    IFEQ L7

    LDC 1

    IRETURN

    GOTO L7

   L7

    ALOAD 0

    ILOAD 1

    LDC 1

    ISUB

    INVOKEVIRTUAL test.fib (I)I

    ALOAD 0

    ILOAD 1

    LDC 2

    ISUB

    INVOKEVIRTUAL test.fib (I)I

    IADD

    IRETURN

Quite visible the BytecodeInterface8 calls for the check for categories and the original int meta class, as well as __$stMC, the guard for the default meta class. Compared to normal Javac code:

   public fib(I)I

   L0

    ILOAD 1

    ICONST_2

    IF_ICMPGE L1

    ICONST_1

    IRETURN

   L1

    ALOAD 0

    ILOAD 1

    ICONST_1

    ISUB

    INVOKEVIRTUAL X.fib (I)I

    ALOAD 0

    ILOAD 1

    ICONST_2

    ISUB

    INVOKEVIRTUAL X.fib (I)I

    IADD

    IRETURN

We can see that those two version are not all that different. The compare looks a bit different, some LDC should be ICONST, but all in all, quite similar. The result for fib(38) on my machine is 940ms in the groovy version and 350ms in the java version. In Groovy 1.7 we would have had something over 14s and most probably a stack overflow. And I think that is a pretty good result. If I would have only one guard, I would be almost at Java speed.

Invokedynamic and others
I mentioned earlier this technique is not really new, but I have actually never seen it being used in this way. Normally you have some kind of interpreter, representing the slow path. At runtime you find the parameters for the path and then emit a specialized fast path for these. You have to check the parameters after of course, but it is similar to what I do with the guards. Only in the interpreter you are working with actual runtime information and you can go far beyond what I did. I optimized for example method calls on "this". I have this limitation because I know of no good way to check the metaclass of the receiver in general. In the interpreter this is most probably no problem to care about so much and you get that call optimized as well. But Groovy has no interpreter that could be used for this, so that was no option. And while this approach here avoids the generation of classes at runtime it also bloats the bytecode quite a bit. Which means methods can now contain less Groovy code, a drawback I have not yet encountered in real life, but it probably is one.

The of course a word on invokedynamic here. This work was done for JVMs of the pre Java7 era. Java 5+6 will be around for at least another 2 years I imagine and thus we wanted to have something for those cases. Also the problems with the guards is one for invokedynamic as well, so I thought back then. Now I know that in the cases I would normally guard, I will simply invalidate all call site on demand and be done with it. What stays is the static code analysis for the types. If I know I will get only ints then I don't have to check for other types. If I have for example a+b and now nothing more of a and b, then they might be Integer in one case and String in another. If I make a callsite target for the Integer I will have to check a and b for each invocation to ensure they really are Integer. If it then turns out they are suddenly Strings, I will have to make a new callsite target and check for Strings.

Conferences I am going to this year

I decided I could at least my update my blog with the conferences I am planing to attend this year.

So first is JAX 2011 May 2 till May 6 2011 in Mainz. The JAX is a pretty big German conference about Java and other things, including Groovy. I will speak on May 3 11:45.

Following tightly is GR8Conf Europe 2011 May 18 to May 19 2011 in Copenhagen. This conference is surely not as big as the JAX, but in exchange it is about all the great (gr+8) technologies around Groovy. I am especially looking forward to the Hackergarten there again. I will speak there on May 19 12:10. My third time for this conference.

Next and last that I am planing to attend is the JVM Language Summit. Well, at the moment the link still leads to the 2010 page, a final date is not up yet. I strongly hope there will be another one and that I can visit it the third... or was it forth? time. This conference was for me as language implementer on the JVM always extremely interesting. Also being able to bug the different JVM engineers about the dark corners of the JVM is just plain fun.

Besides that I did not yet plan anything more, but who knows ;)

git again

For a while now I am using git locally and I am starting to like it a little. Coming from CVS and SVN many things just behave not right and it takes quite some time to make the transition to the new system. Along the way I found some very helpful pointers, that I want to mention here too. There is http://flavio.castelli.name/howto_use_git_with_svn giving a good overview of how to use git and SVN together. But the most helpful had been the documentation at kernel.org. There I discovered for example the rebase command, allowing me to reorder, split and edit my local changes. This truly helps keeps you to commit often and always having a backup of your work. With SVN I often did not commit, since my code would break trunk. For some time I had a local SVN repository that I used to save my changes. But the reediting capabilities in git are so much better.

The next step for me would probably be to put my git repository on github.com. Now the question is of course how to do that? How to have a git personal git repository on github, that I can use to commit to Groovy trunk (SVN) and that I can use for my local work. Can I have like two remote branches? I guess for this I will have to look around more.

Next steps with git...

So after doing a checkout of the repository using git-svn for over two hours I started looking for an eclipse plugin for git.

What I found was EGit, which installed fine... but... well none of the git options appeared. Neither can I import from a git repository nor can I use git commands on the ready project. I tried to install about 5 times and failed 5 times. Maybe it is an error with the plugin, or something with eclipse is making a problem - I really don't know. The error log is clean.

So for me the one and only existing Git plugin for eclipse I found is unusable for me atm.... Next minus for git.

In fact I am now wondering about how to use something equal to for example RapidSVN. A diff tool, that allows me to remove different changes is very important to me - doing that only on the command line is not very effective.

Trying out Git

My current work requires a lot of changes and experiments so I thought it might be good to try out git with the subversion back end.

So the first step is to make a local repository and then get the current svn repository... uhm, yes, the complete repository. Well ok, I am chekcing out only for trunk here, but that is the branch with the most traffic. NOw trunk is atm around revision 19250. A lot of those are not relevant for trunk, since it is about making branches or the test system making commits. But even if a third of those are normal revisions, we still talk about over 6000 revision. Revision git will all have to download.

Now after 45 Minutes I am at about revision 2350... 17000 to go... ehm... this will take hours it seems.

Ok, you have to do that part only once, but still... This I take as a minus for git vs. svn

Static Groovy - about calling methods

After a long time I am now here writing something in my blog again. In the past I talked mostly about new features and possibilities like for example http://blackdragsview.blogspot.com/2006/09/groovy-on-speed-fast-mode-for-groovy.html

I want to talk about a static mode for Groovy here, since this is a reoccurring thing on the lists. I get the feeling people don't understand exactly what I mean and I want to try and explain it here a bit more. Of course I have my knowledge and others have their knowledge and maybe I will tell something that is wrong here. Well, if that happens tell me, I am aware of the fact that I know only a small fraction. And maybe one of the readers here knows just the way I was searching for and unable to find.

One basic part in Groovy is the method call. Almost any operator results in a method call and many structures are simulated through method calls. Now Groovy is a language with what I call instance based multi methods. Let me give an example:

class A {
 def foo(Object x){ bar(x) }
 def bar(Object o){1}
}
class B extends A {
 def bar(String s){2}
}
def a = new A()
assert a.bar("x") ==1
assert a.foo("x") ==1
def b = new B()
assert b.bar("x") ==2
assert b.foo("x") ==2

Now looking at that code you might realize, that Java would fail in the last assert for multiple reasons. First foo takes an Object typed parameter and that is never going to call a String based method, because the static type of the parameter is used as type for the argument, which then influences the method preselection process the compiler does. So Java would always select the bar(Object) method. The other aspect is that bar(String) is not declared in A, but in B. If you want another method get called in Java, you have to override one from the parent class, but bar(String) is not overriding in the Java sense of inheritance. So in Java you would in class B write a bar(Object) method, that checks if the given argument has the runtime type String and then dispatch to the String taking method else to super.bar(Object). In Groovy this is not needed. If bar is final, then in Java you cannot do that additional dispatch, for Groovy this makes no difference.

I should maybe also mention that often people talk about dynamic dispatch or dynamic method calls. What some mean is that from a given set of methods of a given class a method is selected using the runtime types of all involved arguments and the receiver. They often don't realize that this is multi methods. Coming from a Java thinking they assume only methods from class A can be taken, since foo is defined in A and so a bar of A must be used. In Java you might add that this is always true unless a subclass is overriding the method, but no new method signatures will be added to the set. Only, that if you use the dynamic type of the receiver anyway (yes, Java does this!) why make methods of it invisible? That was a decision made by the Java people and I am sure they had their reason to do so, but this is no requirement for a static language, especially if the return types cannot differ Before Generics were introduced this was the case for Java. Even for current Java I think it would be possible to ad. And if you take a look at MultiJava for example, you might realize that it does not have to be a dynamic feature either.


Another aspect of Groovy and method calls is the invokeMethod/methodMissing logic. Basically the method is called if the goal method couldn't be found. The parameters for this search are based on the dynamic types and multi methods, but a static language could have a methodMissing as well. But what would that mean?

A static mode for Groovy is something all those people like to have, that either think the compiler should do more checks or that Groovy should have more speed. Let us concentrate on compile time checks here. A common example is the misspelling of a method name or a method name gets changed. Let us take the example Chris Richardson in his Community One East 09 talk gave http://www.slideshare.net/chris.e.richardson/communityoneeast-09-dynamic-languages-the-next-big-thing-for-the-jvm-or-an-evolutionary-dead-end On slide 30 executeRequest got renamed to executeEc2Request and he complains about his test not picking up the problem, where it should have been a job of the compiler anyway.

Now let us imagine a language in which every method call, that does not point to a specific method, the compiler will create a call to method missing. In such a language a change of the signature of one method will most probably not lead to a compilation error. Instead the method call will now call method missing. In other words: One of the most important features, the check of a method call, will not work.

Still it wouldn't be worthless since in refactorings you could still have the method being changed automatically you might say. But this is an IDE-thing and not a compiler thing. As such it is only partially concern of the language and more of the IDE being able to do something in such cases.

class A {
 def bar() {1}
}
def a = new A()
a.bar()

Let us assume this is the code in your IDE and you want to refactor A.bar into A.foo. An IDE could through type inference know that "a" will be of type A and as such know that the call a.bar() would normally have called A.bar and that if I rename that method, the IDE should change a.bar() into a.foo(). Also if the example would have been

class A {
 def bar() {1}
}
def exec(x){x.bar()}
def a = new A()
exec(a)

the IDE would have had a much tougher job. But an IDE knows all the code that is involved, so it could try to identify all types that are used to call exec and then distill a common super type for it. So in the end it could still find out, that exec is called with A and since we refactor A.foo it could still find that it should be changed to A.bar. It is difficult, but not impossible for the IDE to set things right here as we can resolve the issue with just type inference. Let us go even one step further

class A {
 def bar() {1}
}
class B {
 def bar() {2]
}
def exec(x){x.bar()}
def a = new A()
exec(a)
def b = new B()
exec(b)

Here A and B have no common super type that contains the definition of bar, still a name change for A.bar would affect the program. The right thing here to do would be to also change the name of B.bar. If the IDE knows how exec is called and with what types these calls are made, it can find this out. There might be cases in which the IDE won't be able to find the right types, but I am positive that in most cases the IDE will be able to just do that. If such type inference is available, then auto completion for method signatures will work too. So the biggest use cases in an IDE, renaming and completion, can work out just fine in most cases even with Groovy.

So if method missing has no positive affect and multi methods are restricted, then what is left is the normal method call logic Java uses. And the question here is if that is worth it.