Engineering Chronon

All the technical and design details on Chronon - The DVR for Java

Morning with Control Flow Graphs

Please dont write methods that result in Control Flow Graphs (CFGs) like this (takes 5 seconds to load full image on windows image viewer on my 12 core machine with the latest SSD):



Filed under  //     

Hidden evils of Java's boolean array (boolean[])

Consider this piece of code which allocates a boolean array of 100,00:

boolean[] array = new boolean[100000];

What should the size of this array be?

Considering that a boolean can just be either true or false, every element in the array only needs a single bit of space each. Thus, the size of our boolean array in bytes should be:

100,000/8 + (overhead of array object) = 12,500 bytes + (overhead of array object)

But there lies the hidden evil....

The Evil Inside

As it turns out, when you allocate a boolean array, Java uses an entire byte for each element in the boolean array!

Thus the size of the boolean array is in fact:

100,000 bytes + (overhead of array object)


So is there any way not to use the 7 extra bytes when you only need the 1 bit? Its here that the java.util.BitSet class comes to rescue.

The BitSet class does indeed use a single bit to represent a true/false boolean value. Its implementation uses an array of 'long' values, where each bit of the long value can be individually manipulated to set any position in the entire BitSet to true or false.

The BitSet implementation does add a bit of cpu overhead since it has to shift and or bits together to set the value of the bit in the correct position. Thus you need to weigh the cost of memory savings versus the extra cpu overhead when using this class.


As an example, here is a screenshot from the YourKit profiler, showing the memory used by a boolean array and a bitset object, both 100000 element long:


As can be be seen:

The boolean array takes:
100,000 + 16 (array overhead) = 100,016 bytes

The BitSet object only takes : 

100,000 / 64 (size of long) = 1562.5 = 1563 long values after rounding
1563*8 + 16 (array overhead) = 12, 520 bytes

A few extra bytes are added for the BitSet object itself and the extra 2 fields that it contains.

To put things in perspective, here is a graph showing the space occupied by both for 100,000 elements:



As can be seen from the graph above, using the BitSet instead of a boolean[] can save you tons of memory at the cost of just a few extra cpu cycles

Filed under  //   

Hidden evils of Java's String.split() and replace()

If you code in Java, you have inevitably used the String.split() and String.replace() (including replaceFirst() and replaceAll()) functions.

And why wouldn't you? They are much more convenient than using the Java Regular Expressions API where you need to create a 'Pattern' object, and possibly a 'Matcher', and then call methods on those.

However, all convenience comes at a price!

The Evil Inside

In this case, the String.split() and String.replace*() methods (with the sole exception of String.replace(char, char) ) internally use the regular expression apis themselves, which can result in performance issues for your application.

Here is the String.split() method:

Notice that each call to String.split() creates and compiles a new Pattern object. The same is true for the String.replace() methods. This compiling of a pattern each time can cause performance issues in your program if you call the split() or replace() functions in a tight loop.


I tried a very simple test case to see how much the performance is affected. 

The first case used String.split() a million times: 

In the second case, I just changed the loop to use a precompiled Pattern object:

Benchmark Results

Here are the average results of 6 test runs:

Time taken with String.split() : 1600ms
Time taken with precompiled Pattern object: 1195 ms



Note that I used an extremely simple regular expression here which consists of just a single 'space' character and it resulted in > 25% decrease in performance.

A longer more complex expression would take longer to compile and thus make the loop containing the split() method even slower compared to its counterpart.

Lesson learned: It is good to know the internals of the APIs you use. Sometimes the convenience comes at the price of a hidden evil which may come to bite you when you are not looking.


Filed under  //   

Java Bytecode manipulation : Tools of the trade

Since the Chronon recorder uses bytecode instrumentation to record your java applications, I thought I would list some of the tools we use to help us with it:

ASM framework

The de-facto Java framework for bytecode manipulation. The ASM framework is the fastest, most flexible and well known framework around for doing bytecode manipulation.  At the time of writing its the only framework that supports the Java 7 class file format. If you are trying to choose a framwork for bytecode manipulation, stop, just learn and use ASM.

Bytecode Outline plugin

This eclipse plugin can automatically show you the bytecode for java file open in your editor. It can also show the corresponding ASM code that would be needed to generate the said bytecode. It will help you understand both bytecodes and the ASM framework better.

jClassLib Bytecode Viewer

This free tool, made by the same guys who make JProfiler, is the most comprehensive way to view your generated .class files. It can show you the bytecodes individually for a method along with things like the local variable table, exceptions table, constant pool, etc.  Its a must have, in my opinion, if you are fiddling around with Java byetcodes in any way.

Chronon Time Travelling Debugger

This may sound like self promotion, but I remember the time before Chronon was born and each time we would run into issues with the generated bytecode, (which btw you will at some point too, no matter how hard you try not to), it would take hours trying to use the standard debugger or littering our code with println() statements everywhere before we found the root cause. Now if we find any error in the generated bytecode, we just look at the Chronon recording of the executed code in the Time Travelling Debugger and can find root cause in minutes.



Filed under  //   

JVM 5 is the new IE 6

Note that I mentioned JVM 5, not Java 5.

Since Chronon requires running on JVM 6, we do get people time to time asking "Does that mean Java 5 is not supported?".

Backward Compatibility

It seems some people still don't understand that you can run Java 5 code on JVM 6. The JVMs are, and have always been, fully backward compatible.

This also means, that you can still write your code as Java 5 and even use JVM 5 to compile and build your  application, but during deployment you can choose JVM 6 instead of JVM 5 and gain all the advantages of using a more recent JVM while making sure your code still can, if really needed, run on JVM 5.

Disadvantages of JVM 5

The JVM 5 is over 7 years old. It was even End Of Life'd over 2 years ago.  That means it won't be receiving any more updates, so if you run into a jvm bug, tough luck... On Macs, its not even possible to install JVM 5 unless you use some hacks.

Frankly, why anyone would use a a 7 year old technology which won't receive any new updates, when a perfectly good alternative is available, is beyond me!

Advantages of JVM 6

The JVM 6 has been with us for > 5 years now and is still very much under active development. It has had 29 updates so far and is used by millions. It has much better performance than JVM 5 and the vast number of updates have ensured it is pretty damn stable.


At this point it baffles me that enterprises are sticking with a 7 year old, discontinued technology which has a perfectly good replacement which performs better and gets active updates. JVM 5 is the new IE 6 and like IE 6, it would be good for everyone if it was completely eradicated from this world.


Filed under  //   

-Xmx is hurting the usability of Java

How would it feel if every time you opened a program or a website it asked you how much memory it could use?

Or even worse it by itself decided some maximum memory value for you which is far lower than the amount of ram on your system. How would you then feel if that said program or website threw an error in your face complaining about memory, all this while you had more than enough ram on your system for it to use?

What Java does

Apparently that is exactly how Java programs behave or rather the JVM implementations compel java programs to behave. 

  1. Either you specify an -Xmx value and try to guess memory usage before hand, or 
  2. Depending on the vendor, version or implementation the JVM will choose its own maximum heap size (which is almost always lower than the total ram on your machine).

What it should Do

Now I am sure there are good technical reasons why this is the case. However I will cite the age old programming quote:

First make it correct, then make it fast.

In this case going Out Of Memory on a system which does have enough memory is plain incorrect. Any program on a system can due to unforeseen circumstances might temporarily require more memory than its user thought it would. It could be that disk IO became slow or there were suddenly a traffic spike for a few minutes, etc. Operating Systems found a way around this a long time ago using virtual memory and disk swapping. Sure swapping causes your program to go slow but it doesn't outright crash it.

I have 24gb of ram on my machine (since ram is super cheap nowdays). I should never see an OutOfMemoryException. Yet time and again I see it pop up in Java programs, even when they were using a mere fraction of my 24 gigs of ram.

Real World Experience

We have so many cases of people using Chronon on 64 bit machines and getting Out Of Memory Exceptions.  We keep getting queries like "but my machine has 4 gigs of ram" and we always have to say "but did you allow the jvm to use it? whats your -Xmx value?". 

Since the performance of Chronon is greatly impacted by memory, with our Time Traveling Debugger Eclipse plugin, during installation we bump up the -Xmx value of Eclipse. Although all this does is allow Eclipse to use the extra memory if needed, due to the common misconception out there, people think just by setting a higher -Xmx value Eclipse is magically using more memory than before.


All said and done, I think the need to specify a max heap or randomly choosing a heap size less than the system memory highly impacts the usability of Java programs in a 64 bit world, and leads to confusion with people who get Out Of Memory errors even though they have plenty of memory. The performance gains are not worth the errors and confusion.



Filed under  //   

Method Size Limit in Java

Most people don’t know this, but you cannot have methods of unlimited size in Java.

Java has a 64k limit on the size of methods.

What happens if I run into this limit?

If you run into this limit, the Java compiler will complain with a message which says something like "Code too large to compile".

You can also run into this limit at runtime if you had an already large method, just below the 64k limit and some tool or library does bytecode instrumentation on that method, adding to the size of the method and thus making it go beyond the 64k limit. In this case you will get a java.lang.VerifyError at runtime.

This is an issue we ran into with the Chronon recorder where most large programs would have atleast a few large methods, and adding instrumentation to them would cause them to blow past the 64k limit, thus causing a runtime error in the program.

Before we look into how we went about solving this problem for Chronon, lets look at under what circumstances people write such large methods in the first place.

Where do these large methods come from?

·         Code generators
As it turns out, most humans don’t infact write such gigantic methods. We found that most of these large methods were the result of some code generators, eg the ANTLR parser generator generates some very large methods.

·         Initialization Methods
Initialization methods, especially gui initialization methods, where all the layout and attaching listeners, etc to every component in some in one large chunk of code is a common practise and results in a single large method.

·         Array initializers
If you have a large array initialized in your code, eg:
static final byte largeArray[] = {10, 20, 30, 40, 50, 60, 70, 80, …};
that is translated by the compiler into a method which uses load/store instructions to initialize the array. Thus an array too large can cause this error too, which may seem very mysterious to those who don’t know about this limit.

·         Long jsp pages
Since most JSP compilers put all the jsp code in one method, large jsp pages can make you run into these errors too.

Of course, these are only a few common cases, there can be a lot of other reasons why your method size is too large.

How do we get around this issue?

If you get this error at compile time, it is usually trivial to split your code into multiple methods. It may be a bit hairy when the method limit is reached due to some automated code generation like ANTLR or JSPs, but usually even these tools have provisions to allow you to split the code into chunks, eg : jsp:include in the case of JSPs.

Where things get hairy is the second case I talked about earlier, which is when bytecode instrumentation causes the size of your methods to go beyond the 64k limit, which results in a runtime error. Of course you can still look at the method which is causing the issue, and go back and split it. However, this may not be possible if the method is inside a third party library.

Thus, for the Chronon recorder at least, the way we fixed it was to instrument the method, and then check the method's size after instrumentation. If the size is above the 64k limit, we go back and 'deinstrument' the method, thus essentially excluding it from recording. Since both our Recorder and  Time Travelling Debugger are already built from the groud up to deal  with excluded code, it wasn’t an issue while recording or debugging the rest of the code.

That said, the method size limit of 64k is too small and not needed in a world of 64 bit machines. I would urge everyone reading this to go vote on this JVM bug so that this issue can be resolved in some future version of the JVM.

Filed under  //   

Misconceptions regarding Java heap size arguments

There seem to be some misconceptions regarding the Java Heap size arguments.

For those who don't know, Java is peculiar in the sense that you have to specify the amount of memory you want your program to use, before you run your program. If you fail to do so then depending on the version and implementation of the JVM, your program will only be allowed to use a fraction of your computer's total RAM. This is the reason why you might get an OutOfMemoryError even if your machine has 24gb of ram and you know your Java program needs way below that amount of memory.

The way to mitigate this is to set the -Xms and -Xmx parameters when launching your Java program to explicitly set the initial and maximum amount of memory your Java program is allowed to use.

Note the use of the word 'allowed' in my previous statement. This is the misconception I am talking about.  Let's say you start Eclipse with a setting of -Xmx6g. This does not mean that magically eclipse will start allocating more memory. All this means is that you have allowed eclipse to use 6gb of memory and that if a situation does occur that eclipse maybe for a short time needs that extra amount of memory, it will be able to use it and wont crash by giving you an OutOfMemoryError.

The need to pre define the amount of memory usage allowed was a big problem with Chronon , since Chronon does make good use of the memory on your system and gets a huge performance boost the more memory you give it. However since eclipse by default only sets a -Xmx value of 384m, we would get a lot of complaints from people saying 'I have 4 gigs of ram on my machine, why is Chronon still running dog slow'. And it would always involve setting the -Xmx and -Xms to a higher value.

So we decided to use some of the functionalities of Eclipse p2 and now when you install the Chronon Time Travelling Debugger eclipse plugin, we automatically increase the -Xms and -Xmx to a much higher value in your eclipse.ini file. This has obviously put an end to all the performance complaints and I bet has solved a lot of non Chronon related performance problems for some eclipse users who are now actually able to use their machines to their full potential when running eclipse.

Of course, this has angered some people who when they see the heap size in their eclipse status bar set to a high value tend to freak out. "What, my eclipse is suddenly taking more memory!". Thus, the point of this post is to make it clear that Eclipse is not magically using more memory when you install Chronon, you are only allowing it to use all the memory of your system which you paid with your hard earned cash.

Filed under  //