Just In Time (JIT) Compilation in JVM

The Just In Time (JIT) compilation in Java is essentially a process that improves the performance of Java applications at run time. JIT compiler is a component of Java Runtime Environment (JRE) and is enabled by default. JIT is a type of dynamic compilation whereas javac is static compilation. With static compilers, the input code is interpreted once. Unless you make changes to your original source code and recompile the code, the output would result in the same outcome. A dynamic compiler, on the other hand, translates one language to another dynamically, meaning that it happens while program is being executed. Dynamic compilers can do a lot of optimizations at run time which can't be done by a static compiler.

Java source files are compiled by the Java compiler into platform independent bytecode or Java class files. When we start a Java application, the JVM loads the compiled class files at run time and executes the program via Java interpreter which reads the byte code in the loaded class files. Due to this interpretation, Java application performs slowly than a native application. The JIT compiler helps improve the performance of Java applications by compiling byte codes into native machine code at run time. The JIT compiler analyses the application method calls and compiles the byte code into native, more efficient machine code.

In practice, the methods are not compiled the first time they are called. For each method, JVM maintains a call count, which is incremented every time a method is called. JVM would keep on interpreting a method until its call count exceeds a JIT compilation threshold. Therefore, methods which are used often are compiled soon after the JVM is started, and less used methods are compiled much later or not at all. After a method is compiled, the JMV resets its call count to zero. Subsequent method calls keep on incrementing the call count. If it reaches JIT compilation threshold for the second time, the JIT compiler compiles the method for a second time, but this time it applies much more optimizations. This process is repeated until maximum optimization threshold is reached. This is the reason, why Java applications are warmed up before benchmarking. This also explains why Java application have long start up time.

Here are some of the optimizations done by JIT in Hotspot JVM :

1. Instead of calling methods on an instance of an object, it copies the method to the caller code. This is called inlining. The hot methods (methods used more often) should be located as close to the caller as possible to prevent any overhead.
2. Delay memory writes for non-volatile variables.
3. Replace interface with direct method calls for method implemented only once to eliminate calling of virtual function overhead.
4. Eliminate dead code. Dead code is a code in the source code which is executed, but whose result is never used in any other computation.
5. Rearrange the code. JIT analyzes the flow of control within a method and rearrange code paths to improve the efficiency.

The HotSpot JVM currently supports two JIT compilers : Client and Server. The HotSpot VM's Client JIT compiler targets applications desiring rapid startup time and quick compilation so as not to introduce jitter in responsiveness such as client GUI applications. The HotSpot VM Server JIT compiler targets peak performance and high throughput for Java applications, so its design tends to focus on using the most powerful optimizations it can. This often means that compiles can require much more space or time than an equivalent compile by the Client JIT complier. It tends to aggressively inline as well, which often leads to large methods, and larger methods take longer to compile. It also has an extensive set of optimizations covering a large number of corner cases, which is needed to generate optimal code for any bytecodes it might see.

Largest Rectangular Area in a Histogram

Problem :

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. All bars have same width and the width is 1 unit.

For example, consider the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 2, 6}. The largest possible rectangle possible is 12 (see the below figure, the max area rectangle is highlighted in red)

Solution:

A straightforward answer is to go for each bar in the histogram and find the maximum possible area in histogram for it. Finally find the maximum of these values. This will require O(n^2) time. We would solve this problem in O(n) time complexity.

There are a few invariants that we can use for this problem :

1. If we include bar i, maximum possible height of rectangle including that bar will be h(i), height of that bar.
2. If we include bar i, maximum possible width of rectangle including that bar will be L + R + 1, where :
1. L is the number of adjacent bars to the left of ith bar and height greater than or equal to h(i)
2. R is the number of adjacent bars to the right of ith bar and height greater than or equal to h(i)

Now our task remains as follows:
1) Get Li
2) Get Ri
3) Get area of rectangle for bar i : A(i) = h(i) * (Li + Ri + 1)
4) Fid maximum value of A(i)

Here is the Java code :

Fail-Safe Vs Fail-Fast iterators in Java

Fail-Fast iterators :

Fail-fast iterators fail as soon as they realize that the structure of the collection has changed since the iteration has begun. By changing the structure of the collection, we mean adding, removing or updating an element in the collection. It is implemented by keeping a modification count and if the iterating thread realizes the change in modification count, it throws ConcurrentModificationException. Most of the collections in Java are fail-fast. This is not a guaranteed behavior. So, we should not rely on this behavior.

We can get ConcurrentModificationException if one thread is iterating over a collection and at the same time that collection is modified by some other thread. Please note that we can get ConcurrentModificationException even in single threaded applications. The following code snippet would throw ConcurrentModificationException :
Whereas, the following code snippet won't throw ConcurrentModificationException :

So, if we use Iterator's remove method, we won't get ConcurrentModificationException. To understand why the second approach doesn't throw ConcurrentModificationException, we need to understand how fail-fast iterators are implemented in Java. The fail-fast iterators are typically implemented using a volatile counter on the list object. When the list is updated, the counter is updated. When an iterator is created, the current value of the counter is embedded in the Iterator object. When an iterator operation is performed, the iterator method compares the list counter with the Iterator counter, and throws ConcurrentModificationException if they differ. That explains why the first code snippet above throws ConcurentModificationException. On the contrary, if we use Iterator's remove method (second code snippet above), the Iterator counter is also decremented. So, in the next iteration, the counter check succeeds. Hence, the second code snippet above doesn't throw ConcurrentModificationException.

Fail-Safe iterators :

Contrary to fail-fast iterators, fail safe iterators don't throw ConcurrentModificationException. This is because they work on clone of collection rather than the original collection. Fail-safe iterators typically operate over a snapshot and allow concurrent modification. But the fail fast iterators may not reflect the updates on collection after the iterator was created. What this implies is that Fail-Fast iterator is guaranteed to list elements as they existed upon iterator construction, and may reflect any modification subsequent to construction of the iterator(without guarantee).  Iterator of CopyOnWriteArrayList and iterators of java.util.concurrent package was fail-fast iterators. Since fail-safe iterators work on cloned objects, they have extra memory overhead.

Java 8 : Difference between List.sort and Collections.sort

One of the most anticipated programming language updates in many years is here. Java 8 would be officially released on March 18, 2014. It offers a lot of new features which are worth exploring. One of them that we would be discussing here is List.sort. The addition of List.sort(Comparator) in Java 8 is fantastic. List.sort unsurprisingly allows you to sort a list, but the neat thing about List.sort is that for most of the common list implementations (such as ArrayList), it would sort much more quickly than Collections.sort. To understand this, first we need to know how Collections.sort works internally.

Collections.sort is a stable sort which means that equal elements won't be reordered after sorting. So, quicksort and heapsort are out of question since they are not stable. The most efficient stable sorting algorithm is merge sort. So, Java internally uses a modified version of merge sort. The exact algorithm was derived from Tim Sort which was developed by Tim Peter for Python. Tim sort is a combination of insertion sort and merge sort. If the number of elements is less than a certain value, insertion sort is used. This is because in case of smaller lists, the overhead of making recursive calls in case of merge sort is greater than the performance benefit obtained by using merge sort. Hence, it makes sense to use insertion sort for smaller lists.

Collections.sort implementation first dumps the specified list into a primitive array. Then it sorts this primitive array and puts back the sorted array elements back into the list in sorted order. Now the question is why do we need to copy the list into a new primitive array ? This is because Collections can be backed up by a primitive array (as in ArrayList) or can be backed up by a linked list (as in LinkedList). Copying into a new primitive array is done to avoid n^2 * log(n) performance that would result if we try to sort linked list in place.

But if we see carefully, this copying into a new primitive array is not required in case of ArrayList and some other list implementations since these list implementations are already backed up by a primitive array. This is exactly what List.sort takes advantage of. The default implementation of List.sort still does what Collections.sort does, but concrete implementing classes are free to optimize. For example, ArrayList.sort invokes Arrays.sort on the ArrayList's internal array. Hence the overhead of allocating and deallocating a new primitive array is gone. Also overhead of copying back the sorted elements from the array is gone. This is a big performance gain. Needless to say, we are saving space as well since we are not allocating space for a new primitive array.

Performance isn't the only potential gain from these new methods. Sorting a Collections.synchronizedList is an atomic operation using List.sort. You can iterate over all the elements of a List as an atomic operation using List.forEach. This was not possible in Java 7.

Bonds

A bond is a fixed income security i.e. the return from a bond is known when it is issued. The essential difference between a bond and a stock can be summed up in one phrase : "Debt Vs Equity". That is, bonds represent debt and stocks represent equity ownership. This difference brings us to the first main advantage of bonds : In general, investing in bonds is safer than investing in stocks. The reason for this is because of the priority that debt holders have over share holders. But not all bonds are safe. There are also very risky bonds which are known as junk bonds. If a company goes bankrupt, debt holders are ahead of shareholders in the line to be paid.

Bond Issuance :

Bonds are issued by public authorities, credit institutions, governments and companies in the primary market. The bonds are mostly issued through a process called underwriting. On the other hand, government bonds are mostly issued in an auction. After the issue, the bonds can be traded in the secondary market just like other instruments.

Important Bond terms:

Principal value or Par value or face value :

This is the amount on which the issuer pays the interest. In most of the bonds, this amount has to be paid at the maturity of the bond. In some bonds, the amount which is paid at maturity is different from the principal amount.

Maturity :

This the date on which the bond expires. The issuer of the bond has to pay back the nominal amount to the holder of the bond on this date. Most of the bonds have term upto 10 to 30 years. But there are bonds with terms upto 100 years. And there are bonds with terms upto 1 year.

Coupon :

This is the interest rate that the issuer of the bond pays to the holder of the bond. Usually it is fixed, but it can also be variable.

Yield:

Yield is the rate of interest received from investing in the bond. It is one of the most important factors that investors care about while investing in bonds. We would talk more about it later.

Credit Rating:

This is the rating given by an agency which tells us the probability that the bond issuer would pay back the promised amount at maturity.

Some major types of bonds:

1) Fixed rate bonds : As the name suggests the coupon rate of these bonds is fixed.
2) Floating rate bonds :  The coupon rate of these bonds is not fixed.
3) Zero coupon bonds : These bonds don't pay any coupon.
4) High yield bonds :  These are also known as junk bonds. These bonds are usually start up companies which need capital to expand but don't have good credit rating. So, to lure the investors these companies issue high-yield bonds which have very high coupon rate. But this comes at the cost of risk associated with these bonds.
5) Convertible bonds : These types of bonds allows the owner of a bond to exchange it for some specific number of shares.

Bond Valuation:

Bond valuation refers to valuing the present value of a bond. The fundamental principle of bond valuation is that the bond's value is equal to the present value of its expected (future) cash flows. While valuing bonds, we consider time value of money concepts. Let's see how to calculate the price of a bond. First we need to compute the present value (PV) of the bond's future cash flows.The PV is the amount that would have to be invested today to generate that future cash flow. To find the value or the price of a bond, the PV of each individual cash flow should be added.

PV at time T = (Expected cash flow in period T) /( (1 + I) to the power T)
where I is the discount rate.

Value of bond = PV @ T1 + PV @ T2 +.........+ PV @ Tn

How does the value of a bond change:

As we can see, discount rate is the only variable factor in bond price. Rest everything is fixed.

• As the rate increases of decreases, the discount rate that is used also changes. Higher the discount rate, the lower the value of a bond; the lower the discount rate, the higher the value of the bond. 
• If the discount rate is higher than the coupon rate, the PV will be less than par. If the discount rate is lower than the coupon rate, the PV will be higher than par value.
• As the bond moves closer to its maturity, it's price will closer to par. At par, market price is equal to par value and yield to maturity is equal to the coupon rate. This is clear since the expected rate of return in this case would be equal to the coupon rate. When a bond is selling at a discount, it's market price is less than the par value. So, it's yield to maturity is greater than the coupon rate. On the other hand, if a bond is selling at a premium, it's market price is greater than it's par value. So, it's yield to maturity is less than the coupon rate.
• If a bond's market prices increases, then it's yield must increase; conversely if a bond's market price decreases, then it's yield must increase.
• If a bond's yield does not change over it's life, then the size of it's discount or premium will decrease at an increasing rate as it's life gets shorter.

Mutex in Java : Explained using Producer Consumer Problem

A mutex is a kernel resource that provides synchronization services. Intrinsic locks or monitors in Java act as mutexes, which means that only one thread can own the lock at one time. When thread A attempts to acquire a lock held by the thread B, thread A has to wait till thread B releases the lock.

 Every Java object can intrinsically act as a lock for purposes of synchronization. These build in locks are called intrinsic locks or monitor locks. The lock is automatically acquired by the executing thread before entering the synchronized block or method and is automatically released when the control exits the synchronized block, by the normal control flow or by throwing an exception out of the synchronized block. One important point to note is that Java locks are reentrant. When a thread attempts to acquire a lock held by another thread, it has to wait, but if a thread attempts to acquire a lock held by itself, it succeeds.

As noted above, that each object in Java can act as a lock, we need to careful while guarding a shared resource using a lock. For each shared resource, that may be accessed by multiple threads, all accesses to that resource must be performed with the same lock held. There is no relation between an object's state and it's intrinsic lock. The state of an object need not be guarded by the intrinsic lock.

Let's move to Producer Consumer problem to demonstrate the use of intrinsic locks in Java. Since intrinsic locks serve as mutexes, this example demonstrates the use of mutexes as well.

Problem:
Consider two threads : Producer thread and Consumer thread. The producer's job is to generate a piece of data and put it into a buffer shared with the consumer. The consumer's job is to consume the data from the buffer . The problem is to make sure that the producer won't try to add into the buffer if it's full and that the consumer won't try to remove data from an empty buffer.

For demonstration purpose, we have used just a count variable instead of a buffer. The producer would produce only if the count is 0 and increment count to 1. Consumer would only consume if the count is 1 and set count to 0.

Here's the code:


Here are few important points that we must note :

1. Note that wait() and notify() are called from a synchronized block. This is because of race condition. We may lose a notify signal if these methods are not called from a synchronized block.
2. wait() and notify() methods are defined in the Object class. This is because every Java object has a monitor associated with it.
3. Why are we waiting in a loop in both produce() and consume() methods ? This is because of spurious wakeups. It is possible for threads to wake up even if notify() or notifyAll() has not been called. This while loop is also a nice solution if you have multipe threads waiting, which are all awakened using notifyAll(), but only one of them lets the lock. The others should continue waiting.
4. wait() method releases the acquired lock/monitor. Otherwise the above code could easily go into a deadlock.

Java result bearing tasks : Callable and Future

Whenever we think of creating threads in Java, Runnable interface comes to mind. If we implement Runnable interface, we need to implement run method which takes no arguments and has no return type. But if we expect a value to be returned after completion of a thread, we need to look for something else. Also Runnable can't throw a checked exception.

That something else is Callable. Callable is an interface introduced in Java 5 to meet this requirement. Callable is similar to Runnable, but it returns a value. The call() method is the entry method into a Callable object and it's return type is the type parameter set in the Callable object. Please note that the call() method in Callable object throws a Checked Exception unlike run() method in Runnable which does not throw any exception.

A Future represents the result of an asynchronous computation. The result can be retrieved using get() method when the computation has completed. The call to get() method blocks until the result is computed. Runnable and Callable represent abstract computational tasks. Future represents the life cycle of a task and provides methods to test whether the task has been completed or been cancelled. It can be used to retrieve the result of a task and also cancel the task. If you want to use Future for the sake of cancellability but not provide a usable result, you declare types of the form Future<?> and return null as the result of the underlying task. FutureTask provides a base implementation of Future. You can refer to online Java documentations to know more about Callable, Future and FutureTask.

I have demonstrated the usage of Callable and Future through the following programs :

RandomStringGenerator class :


RandomStringGeneratorTest class :

LazySet Operations in Java

LazySet is a method offered by Atomic classes in Java. The lazySet method offers significantly cheaper volatile writes for single writers. Let's first find out how lazySet method achieves this performance gain. To find out this, we need to go into the Java Memory Model (JMM). Suppose a primitive variable is shared among different CPU cores. Each core has a local cache where it can store the variable for faster access so that it doesn't have to go to the main memory every time it has to access the variable. If one thread makes a change to this variable, it won't be reflected to the other core since it has a different cache. To mitigate this problem, the Java memory model offers volatile keyword. The reads and writes on a volatile variable would by-pass the cache and go to the main memory. But this comes at a latency cost and lazySet can be used to mitigate this cost. Please note that the cache is not really bypassed, but a memory barrier is used.

The Java Atomic variables have get() and set() methods that work as reads and writes on volatile variables with the additional feature of semi-volatile write. When you change the value of an Atomic variable through the lazySet method, the value is updated in the cache but is not pushed to the main memory. It can take indefinite amount of time of the change to be pushed to the maim memory so that other threads can see the new value. Since in case of lazySet, value is not pushed to the main memory every time, writes are significantly faster. The most important use case lazySet operation is to implement asynchronous logging.