Announcing my next F/OSS project

And it is gonna be written in Java.

Please if you are interested either in Heroes 2 or Java, please follow updates into this new F/OSS project I've started to contribute to.

Don't trust (VM) benchmarks and how to spot bad benchmarks

Introduction

Around year 2000 the computing was changed drastically, even more with the launching of multi-core era around year 2005 and after. Right now, we are in another "revolution" using "computing". And every time you will see new benchmarks where a generation is 25% faster (like A8 is faster than A7) or 100% (like A7 is "up-to" 100% faster than A6), and so on!

But as there are many whereabouts in real life, benchmarks are critical to show if you can have a good experience for users:
- you want your image effect to finish fast. Even more when there is a movie to be processed and a movie as is a huge collection of photos, you care about the language is used and the time your animation is finished
- you want all cores to be used especially when 4 cores look to be the norm today or at least 2 cores with hyperthreading, so you want that all your hardware to be used
- you want to save battery for your mobile devices
- and many other reasons where when things go fast, you will feel happier than if things go slow

What you should care about

But when you as an user may want all these, sometimes you miss the mark. I simply mean that when you do your tasks, you may look in the wrong direction:
- the disk is many many times slower than memory. So let's say you have to make as fast as possible  a picture you've just received on Skype from a friend and he/she asks you to use Sepia tones. Starting Photoshop (or Gimp) can take literally many seconds if not a full minute (if you have more plugins on startup). So using Paint.Net will start the picture editing program faster, you can select faster to Sepia tone and you can send eventually faster the picture back faster. This is not to say that theoretically Photoshop if you would have 100 pictures to load it may not finish them faster (or any other program on that matter), but is often when starting a smaller program makes your task to finish faster
- on a similar note: do you have enough RAM (system memory)? When your system feels slow, is very often that is one of the two factors: you have few memory on your system (and memory is really one of the most disproportionately cheap component) or your CPU is really outdated (like let's say you want to process big pictures with a Pentium 4 1.7 GHz from 2001). But even the 2nd case is what's make your system slow, is still likely that adding memory will make it faster and usable even 10 years later!
- if your application doesn't care much about RAM and disk, is (very) probably a game, so the next question is: do you have the best video card is in your budget? It can be an integrated video card, but to be the fastest you can afford. Very few games are CPU limited, and even the CPU is to slow, and you have just 30 frames per second (so you can "feel" gaming lag), you can increase game detail and you will lose very little performance (if you have a to fast video card), and all will decrease to 28 FPS. So nothing to lose here!

What Internet says

Ok, being said that, I noticed some very bad benchmarks lately over the Internet, and they are made basically to put shocking numbers. like Android L will run basically slower than Android 4.4, or the reverse (these are Google numbers) in the attached picture, or the latest of them, a bit old, but with a big surprise.


What is funny in these 3 sources, are basically these conclusions:

From source (1) you will "understand" that performance will decrease slightly between Android K and L, but criticism is basically that is a Javascript code, the source (2) states that is not true, but Android L will run a bit faster than Android K, and the source (3) states that JavaScript is in fact the fastest, even faster than Java.

So why this mess? As a (somewhat) compiler writer, I understand the following: all compilers have tradeoffs and sometimes (like the preview builds) you enable debug information to get better information. Also, when you compare, you have to make sure you compare the same thing. The last item that matter.

Investigating the claims

So, is it JavaScript faster or slower than Java? For people following this blog, I can say that CR is faster than .Net, but I can have to make some qualifiers:
- CR doesn't handle exceptions at all, including bounds checking, NPE, so if you have a lot of iterations, you can get really awesome generated code, but it compares a minimalist "C-like" code with .Net's full code
- CR anyway uses C++ allocator which is roughly an order of magnitude slower than the .Net's GC, so if you allocate a lot of objects .Net ca be faster even .Net has exceptions (the same story is with Mono). CR has optimizations to help on this (mostly escape analysis, but users have to write code in a compiler friendly way).

Similarly: JavaScript as of today is not faster than Java, excluding you write Asm.JS (in which I would expect that Asm.JS to be slightly faster in very few cases with the same abstraction level as Java), but overall you should expect that C/C++ code will run with at least 50% faster than JavaScript with ASM.JS and even faster than without (like 2-3x times faster). This happen on a desktop class CPU only, on tablets/phones, the difference is wider, because the CPUs are weaker so the VMs there will do fewer optimizations. Here is the source I am using which is known for its impartiality.

Java most of the time (in low level math) with hot loops receives like 90% of C++ performance. In my experience, CodeRefractor was a bit faster (11%) in a very tight loop with no special hand-tune of code (but still tunning as much the compiler flags) so I can confirm as a consistent experience

How can it happen still that Java is slower in the 3rd source than JavaScript? Simple: Dalvik is not Java VM (in the strict sense) as CodeRefractor is not .Net (or Mono). Meaning that Dalvik has many designs choices which are strange in the JVM space: they are using a register based VM (like CodeRefractor) which means that their interpreter is faster (even with no compilation you should expect around 60% faster interpretation, there are scientific papers which found that interpreters on stack VMs work faster, the Google team claimed that they are around 2x faster than the JVM, which is consistent even a bit on the high side with scientific papers) and they are using a JIT (dynamic compilation) just for small subsections of the program. I would expect that they get 2x times faster because Google documented that they will preoptimize the bytecode: so the interpreter will run not your bytecode you gave to clients, but a slightly simplified Dalvik bytecode.

JavaScript VM is using a different technique on Android: is using V8 JavaScript virtual machine which uses a "direct to native" quick JIT and after that they are using a more advanced compiler for the hot code. This makes that all JS code (even JS is intrinsically slower) to be compiled.

For the sake of correctness, V8 was not all the time faster than the JIT of the Dalvik, the Android's "Java" implementation, but Dalvik was not improved from 2010 JIT wise, but most of improvements were GC related, and that Android applications will use GPU so they will use much less CPU to draw the screen, making applications to feel faster without Dalvik to become more CPU efficient. Do you remember how I've started the post: when applications need to feel faster, the best way to improve is to improve the components, not CPU only: this is what Google teams did, and I think it was the most sensible thing to do.

As a conclusion, Android L also introduces ART an AOT technique of compilation ("similar" with CR) meaning that (most of) compilation will happen on install time, making at least compilation to be program wide and I would expect as the Google team will improve the ART runtime, will make it very likely faster (if is not already) than V8.

So, how to spot bad benchmarks?
Every benchmarks which are not made for the domain of the user (typically your application), you should state upfront is a bad benchmark. Even more when is comparing "runtimes" or VMs in different class.

This is not to say that are not useful benchmarks, but you can get so easily tricked (and even experts can make mistakes, like this amazing talk of Gil Tene about GC latency and "almost"!) asking your compiler vendor (or JS vendor) to optimize for SunSpider, instead optimizing for your (web) application (like FaceBook, GMail, or what you really use from the web).

Soon I will likely announce my next (not CR related) FOSS project, and will be in the world of Java. The reason is that I understood why Java can give so much performance if written properly and the multitude of tools, but this is for another post. Also, I want to make clear that CR will likely not be updated for a time (excluding someone is interested on some feature and needs assistance). 

Sources:
1. http://www.reddit.com/r/Android/comments/2987ny/just_finished_doing_444_dalvik_444_art_and_l/
2.  http://www.cnet.de/88132773/android-l-und-android-4-4-4-im-benchmark-test/
3. http://www.stefankrause.net/wp/?p=144

Some future plans

Few great contributions were arriving to CR, mostly that the compiler works with more string operations (the single limitation is that they ignore the CultureInfo part), but other than this, it is done.

Also, it is feature wise even it is buggy the most complete CR version ever. You have supported cases of virtual methods, a much clean defined architecture that is incremental, optimizations are using various scopes, from block level, to multi-function dead-code elimination.

So what I would expect in future to be done:
- expect no future improvements than bug fixes excluding someone has time to maintain the project
- I will refactor it slowly to support another runtimes (an old wish of mine), in special cases if CR can work with simple use-cases for your random use-case. Let's say you want to write a runtime so CR can work with embedded C++ compilers, or you want to define a new class special for your use-case
- I will support people which want to contribute and I want with this occasion to than to the people who contributed already: Ronald Adonyo and Bogdan Mustiata, two great developers. Ronald made it much easier and transparent the testing of the compiler and he made fixes all around the runtime; Bogdan added support for most string operations.

Why you cannot beat the compiler...

In the last weeks there was a big rewrite inside CodeRefractor. The main change is basically that we do in a multiple pass algorithm the building of code tree that can be built from the Main method. The changes we propagated from the frontend to the deep of the virtual methods backend (where the code is generated) and simplified.

using System;
class A
{
    public void F() { Console.WriteLine("A.F"); }
    public virtual void G() { Console.WriteLine("A.G"); }
}
class B : A
{
    public void F() { Console.WriteLine("B.F"); }
    public override void G() { Console.WriteLine("B.G"); }
}
class Test
{
    static void Main()
    {
        B b = new B();
        A a = b;
        a.F();
        a.G();
        b.G();
    }
}

Let's start with this code. Which is CR's output for Main method (C++ code)?

System_Void _Test_Main()
{

_B_F();
_B_G();
_B_G();
return;
}
 
CR doesn't have full inlining (yet!) but it has analysis steps that check if variables are used over the method boundaries and the most important part: it does it safely!

Many people may say that this code is contrived and unrealistic and I have to agree, also it has to be a "lucky case" that many things to happen:
- methods to devirtualize correctly
- the members of the method calls are not used
- the instance of B has no members  that are used, so the compiler can remove it safely

But on the other hand, this is also the strength of the compilers today: one month ago CR would not be able to write this code, but today it cans, so all you have to do to get a bit better performance is just update the compiler (or wait for the next release) and voila, you're good to go. Even more, every time when in future the compiler is able to devirtualize, it will devirtualize, over all program, and the most important bit: with no work from your side!

So, every time when you write code that targets a compiler (any compiler, not only CR), if the compiler project is improving, all you have to do is to wait, or to report bugs if the compiler doesn't compile your code, or update minimally your code to avoid the compiler issues and the code will improve itself.

Some String support

A simple program as this one:

 static void Main()
 {
        var s1 = "Hello";
        var s2 = " world";
        var s3 = s1 + s2;
        Console.Write(s3);
 }

 would not work and even seems to be a simple program, in fact is a bit harder because CR didn't have a nice way to map types and to implement a mix of the CR's internal string and the real string, so there was the need to duplicate the entire code of string and make it work.

Right now it works as the following:

[ExtensionsImplementation(typeof (string))]
    public static class StringImpl
    {
        [MapMethod]
        public static string Substring(string _this, int startIndex)
        {(...)}
        [MapMethod(IsStatic = true)]
        public static string Concat(string s1, string s2)
        {(...)}
        [MapMethod]
        public static char[] ToCharArray(CrString _this)
        {(...)}
 }
By adding implementation of mapped CrString for the System.String type makes possible to make implementations natural and as the library will grow (please spend very little time to support a simplified version of any class you think you can implement in .Net) many programs which were missing just the part of displaying some combined strings, right now is all possible.

Improving debugging experience by improving internal structures

CodeRefractor has some clean advantages over other static compilers that target LLVM by targetting C++ but also some disadvantages.

One great advantage is that it is written in .Net and it bootstraps everything needed for output, and the output is somewhat human readable result. This also allows simple optimizations to be done as CR rewrites everything into an intermediate representation (IR) and this representation is simplified with many high level optimization steps.

So this instruction was in the past setup as a list of pairs of values: instruction kind and the instruction data and many casts were made based on this instruction. This is good design, but right now the code is represented as a specific instruction class. So if in the past for storing a label, you would have something like: pair of (Label, 23) where 23 was the label's name, right now is a class Label where it stores: JumpTo property which is set to value 23.

Similarly, more changes are to debug methods, in the past there was a similar pair of the method kind and a MethodInterpreter, and sadly the MethodInterpreter type will store based on the kind of method various fields which some of them were redundant, some of them unused, and changes of this kind. As the code right now is split, the experience in debugging CR is better also.

At last, but not at least, even is not yet fully implemented, it is important to say that the types right now are resolved using a construction named ClosureEntities, and there are steps (similar with optimization steps) that they find the unused types. This also will likely improve in future the definition of types and make possible to define easier the runtime methods. This new algorithm has one problem as for now: it doesn't solve the abstract/virtual methods and the fixing of them will be necessary in future.

Let's get Visual

About a month ago, Ciprian asked for developers to join CR, and I thought since I love the .Net ecosystem, I should be able to help a little here and there.After I looked at the code, having never really understood compilers or transpilers in this case, I needed an easier way to visualize what was going on behind the hood, so I could get up to speed with CR.

I then decided to mock up a "Visual Compiler" to both test CR and to get a simple call graph.
The Visual Compiler (VCR), once setup enables seamless development and testing of CR, alot of improvements can be made, such as full debugging support or clicking errors to take you to the line of code, but for now its a pretty useful tool. With this I have been able to catch up quite a bit and add/fix a few runtime features such as virtual methods and interfaces to CR.

VCR has the following features;
 - opening files
 -  enabling /  disabling specific optimizations
 - running the C# / CPP code and viewing output
 -  and testing the output of C# vs that of CPP.
 - multiple compiler support (although there is no gui to set that, yet)

With the knowledge gained, I am hoping to complete a Pet Project (C# Editor, Compiler and Interpreter for iOS), that has been in the Attic for about 2 years now.

I am currently writing a few more tests and looking into delegates to have CR almost feature complete with the C# language.

Ofcourse even with this tool, I needed alot of guidance, which Ciprian has been kind enough to provide. I am pretty optimistic of where this project is heading :)

Oops, Almost forgot, this is what VCR looks like;

VCR Running on Windows Server 2012 R2

My next blog post will be on the architecture of CR itself, stay tuned.


Enjoy CR,
Ronald Adonyo.