Memory Issues using Java ThreadPoolExecutors

Java ThreadPoolExecutors are a very conventient way to make your applications as concurrent. We recently began a drive to refactor most of our code so that we make use of these ThreadPools. We had a particular process where we read XML files from filesystem and did some transformations on the XML and write the transformed XML into the DB. When we started testing the initial code, we ran into serious OutOfMemoryErrors for even a few hundred XML files.

This was a serious drawback. I looked at our code and found we had set our pool size as 15 and had a blocking input of 500 which meant only 515 xml files are meant to be in memory at any given point in time. This was puzzling since this ideally should not max out memory in a 1.5 GB heap.

Roughly our process was like

XML File --> Callable --> Thread Pool (insert into Db) --> Return boolean success

The pool took a Callable that held a reference to xml and wrote it into DB.

On further analysing the code the only thing that was suspicious was an innocuous looking ArrayList. This List held all the future objects so that we could iterate thru this list and wait for all the inputs to be processed before terminating the process. Why would a List of Future objects cause issues?

To identify the root cause I looked into the JDK ThreadPoolExecutor implementation and found the following

1) When we create a Callable task and submit it to the ThreadPoolExecutor using any of the submit methods, a FutureTask object containing the callable is created. This is returned as return value of the submit method.

2) This FutureTask Object is a concrete class implementing both Future and Runnable. This object is the one that is submitted into the ThreadPoolExecutor. The ThreadPoolExecutor never takes a Callable task directly.

3) The ThreadPoolExecutor when its ready to execute a new task picks up the task (a FutureObject or a Runnable) and calls the run method on it.

4) The FutureTask object has stored the callable object as its instance variable. The run method calls the call method and the result returned is set into an instance variable on the FutureTask. At this point both the Callable object and the returned value from the Callable object are both instance variables in the Future object.

5) The Callable and its results are never set to null in the Future.

So since all the Callable objects were in memory, and each callable maintained a reference to DOM object we maxed out on memory ! So we came up with a set of rules when using Callable to make life simpler.

Rules when using Callables and Futures :

A) Never maintain a huge state in Callable. The state variables will not be explicitly GC'ed as long as a reference to the Future is held.
B) If you need to have a lot of state in Callable, ensure that you clean them up at the end of the call method.
C) Never hang on to the Future indiscriminately. This will prevent the Callable and its Return value from being GC'ed.

I dont understand why FutureTask needs to hold on to Callable forever. Why can't the executing thread on completion set a variable called result in Future and nullify the reference to callable ? I dont have an answer yet but this sounds logical to me. Can someone please educate me?

Subscribe to comments for this post

Future of Java Synchronization - Escape Analysis, Lock Coarsening & FastPath

The future releases of Java has a few important synchronization related changes. The new features are

1. Fast Path

Ok..to understand what FastPath means, let us look at how synchronization works in Java. Each Object in java should support synchronization but only a tiny fraction of the objects we use would ever be used for synchronizing. So the overhead (of memory) to implement sync'ing should be very minimal. Hence all the information needed during synchronization are stored in a separate class and objects of this class would be referenced when the object is being sync'ed on.

The class that holds sync info has various fields some of which are a counter holding the number of threads blocked/waiting on this object, an OS specific semaphore object (very heavyweight object) and a counter to track nested syncing on same object by same thread.

When a thread attemps to sync on an object for the first time, the JVM sees that the object has either no sync info instance associated or that the sync info instance has counter of threads waiting as 0. Both of these mean there is no contention on this object yet. So the sync call proceeds into a fast path execution. It either creates a sync info instance and updates the address of this instance into the object(the one we're sync'ing on) using a CAS (compare and swap) instruction or updates the owner field in sync info instance to refer to the new thread.

If the sync info instance has a non-zero instance (yeah we're screwed !) the JVM blocks the thread on the OS specific semaphore. This operation is heavyweight and is called slow path. I dont know why this is heavy and i can just speculate on why its so. So let me not get into that without having more info.

There are two ways of implementing this blocking...using either a infinite loop checking if the object is freed (spin locking) or using the bad OS semaphore to do the work. The first one is CPU intensive and can only be used if the locks are held for very short durations and second can be used anytime. Apparently the JVM will either do an infinte loop for short sync operations. Also the Compare and Swap instruction itself is being replaced by something more efficient. Dunno what though.

All these things help making the fast path locking go thru even faster and attempt to implement spinning to ensure that semaphores are used as minimally as possible ensuring the sync operation itself becomes fast.

2. Escape Analysis to help Lock elision

If an object being locked by a thread can never be accessed by another thread it means each of the synchronizations will always occur on a new object. In such cases we can eliminate the synchronization itself leading to the code being faster since the memory will not have be flushed, the lock will not have to be checked and created. This helps in faster execution times.

3. Lock Coarsening

Consider the following code

private String getMessag()
{
StringBuffer sb = new StringBuffer();
sb.append("line one");
sb.append("line two");
sb.append("line three");
}

Each of the StringBuffer.append instructions would involve locking on the string buffer itself. But we can see three calls to this method meaning we would do the following operations thrice

1. Flush of memory to main memory
2. Acquire Lock on String Buffer
3. Flush of memory to main memory

Since the above function can be re-interpreted as

private String getMessag()
{
StringBuffer sb = new StringBuffer();
synchronized(sb)
{
sb.append("line one");
sb.append("line two");
sb.append("line three");
}
}

we can cut down the number of sync calls to only one. This is called lock coarsening since we effectively coarsen the lock.

Some of these 3 features are in Mustang (Java 6) while most are in Dolphin (Java 7). The mustang already does some escape analysis but apparently the info is not used to do lock elisions and only some simple coarsenings are supported currently. So expect to wait longer till ur code can run fast. To know more on this u can refer to Davids blog entry.

Subscribe to comments for this post

Why a ConcurrentHashMap is so fast

We all know a ConcurrentHashMap is nearly as fast as a HashMap plus provided concurrency like a Hashtable. Some very ingenious coding has made this possible. To understand the hows and whys the key is the structure of the ConcurrentHashMap itself.

A ConcurrentHashMap contains a final array of Segment objects. Each segment extends ReentrantLock, and contains a transient volatile array of HashEntry objects. Each HashEntry object is made of final key, hash and next variables and a volatile content variable.

Every get/put/remove/add operation involves creating an index from the hashkey that maps to one of the available segment objects. The call is then delegated to the obtained segment instance.

Let take put call. The segment first locks itself (since extends from ReentrantLock). Then proceeds to check if the hashkey already exists, if it does, it updates the value of the volatile value field in the HashEntry object. Since it is a volatile variable, the new value is guaranteed to be seen by other threads in the jvm without any explicit need for synchronization. Voila ! Now if the key is not present then a new HashEntry object is created and added to the head of the existing list. Since there are an array of Segments, the writes can be spread and not all threads might lock on the same segment leading to more concurrent writes.

Consider a get call. Get the first HashEntry and iterator till the end and if found return the value. No locking at all. Same as a HashMap but unlike a Hashtable. So all reads work at nearly same speed as HashMap.

There are 2 things that make this possible

1) The new JMM guarantees that Volatile reads are not re-ordered with volatile writes and all reads after a write will get the updated contents without synchronization. Variable that holds value reference in HashEntry is volatile. Plus the whole HashEntry array in each segment is volatile. So any changes to value or every newly added HashEntry object(or key-value pair) is visible to all threads after they are assigned without any syncronization.


2) Final fields initialization safety, all threads will see the values for its final fields that were set in its constructor.Further, any variables that can be reached through a final field of a properly constructed object, such as fields of an object referenced by a final field, are also guaranteed to be visible to other threads as well. So if a new key-value pair is added and is instantly accessed by another thread the key, hashkey and next pointer will have proper values and never null.


These ensure that any add in any thread instantly reflects in other threads, without any flushing of memory. Does this mean no locking at all ? None in the java code but the jvm implementation will have to do some locking to ensure that volatile variable reads return latest written values. Since its a very lower level it should be more faster.

Never seen an API that uses the features of the JMM to this extent. Hats off to Doug Lea who made this all possible.

Subscribe to comments for this post

Time based UUID Generation Algorithm

We had a requirement recently that we should map files to UUIDs. This gives us the flexibility to refer to a file without using a name thereby enabling us to rename it. So we dug a lil bit on UUIDs. java.util.UUID is the UUID implementation in java and this is the RFC its linked to.

So basically a UUID (java.util.UUID) represents a 128-bit value. These bits are split as

32 bits time_low
16 bits time_mid
16 bits time_hi_and_version
16 bits clock sequence
48 bits node

Timestamp is a 60 bit value of the UTC as a count of 100-nanosecond intervals since 00:00:00.00, 15 October 1582.

Clock Sequence is used to help avoid duplicates that could arise when the clock is set backwards in time or if the node ID changes.The clock sequence MUST be originally (i.e., once in the lifetime of a system) initialized to a random number to minimize the correlation across systems. If the previous value of the clock sequence is known, it can just be incremented; otherwise it should be set to a random or high-quality pseudo-random value.

Node For UUID version 1, the node field consists of an IEEE 802 MAC address, usually the host address.For UUID version 3 or 5, the node field is a 48-bit value constructed from a name. For UUID version 4, the node field is a randomly or pseudo-randomly generated 48-bit value.

There are four different basic types of UUIDs: time-based, DCE security, name-based, and randomly generated UUIDs. These types have a version value of 1, 2, 3 and 4, respectively. Lets look at the time based UUID generation algo.

Time based UUID creation Algorithm

These are the steps as present in the RFC. All italics are my comments..

1) Obtain a system-wide global lock - How ? Simple use a java.nio.channels.FileLock ! This is what the java.util.logging framework uses to ensure log entries are not overwritten when used from multiple JVMs.
2) From a system-wide shared stable store (e.g., a file), read the UUID generator state: the values of the timestamp, clock sequence, and node ID used to generate the last UUID.
3) Get the current time as a 60-bit count of 100-nanosecond intervals since 00:00:00.00, 15 October 1582.
4) Get the current node ID.
5) If the state was unavailable (e.g., non-existent or corrupted), or the saved node ID is different than the current node ID, generate a random clock sequence value - If someone deletes the state store file, then since we start off with a random number we can still get a unique UUID.
6) If the state was available, but the saved timestamp is later than the current timestamp, increment the clock sequence value. - Ingenious !! This means if u revert back ur clock the UUID will still remain unique.
7) Save the state (current timestamp, clock sequence, and node ID) back to the stable store.
8) Release the global lock.
9) Format a UUID from the current timestamp, clock sequence, and node ID values.

The algorithm looks very simple and elegant, and though there are other ways of getting UUIDs this is the one that is easy to understand.

Subscribe to comments for this post

Reference Objects and hashcode

In my previous post, i had brought up the observation that Reference objects cannot be used as reliable keys in Maps/Sets. Intutively I had expected the Reference objects to delegate the equals/hashCode methods to its referrant object.But it was not so. It left me thinking why was it designed not to delegate.

The top reason that comes to my mind is that if the referent object that the Reference points to is GC'ed, then if we are delegating, then equals/hashCode would have to be handled by Reference.Typically it would have do something like

public int hashCode(){
  if(get() == null) return 0 or -1;
  return get().hashCode();
}

This means that in a map, where keys are references, all the keys(references) whose referents have been GC'ed, would end up having the same hashCode. This would cause weird runtime issues when the map is being resized and we would have no clue why ! Same hold true when we try to add ReferenceObjects to a Set.

We might also wonder why not then store the hashCode of the referent in a separate variable when creating the reference. Well hashCode can change over the lifetime of an object, meaning we will never know if the stored value is still valid. If it does not change, it will work.

Geez, i've been breaking my head trying to create something like a ConcurrentWeakHashMap and nothing seems to work. So I just made a call and decided my keys have to be objects whose hashCode will not change with data. Makes life more simpler. If at all I need a true ConcurrentWeakHashMap i've decided to use the less performant method of creating a WeakHashmap and doing a Collections.synchronizedMap() !

Subscribe to comments for this post

Reference Objects as Keys in Maps

WeakReference nor its parent Reference implement the hashCode or Equals method. The default implementation of the Object.equals is to check reference equality. So theoretically if i have an object objInstance and i create two WeakReferences out of it and add it to a hashmap it should not overwrite but add it. And it did.

String str1 = "oioioi";
HashMap map = new HashMap();
map.put(new WeakReference(str1),"one");
map.put(new WeakReference(str1),"two");

Map size at end of the above is 2.

Now comes the million $ question...how the heck does a WeakHashMap work properly then if all keys are indeed WeakReferences as the doc specifies?

To unravel the mystery, lets dig a bit into the src of WeakHashMap.

All entries in a Map are made up of Entry objects.

class Entry<k, v> extends WeakReference<k> implements Map.Entry<k, v>

whereas the same in a HashMap looks like

class Entry<k, v> implements Map.Entry<k, v>

The Entry class in both maps implements equals and hashCode methods.

The keys in WeakHashMap (which are strong references) are objects that implement hashcode methods. Internally when storing the keys, they are stored as weak references since Entry extends WeakReference. And when we call equals/hashcode on these WeakReference Entry objects, the subclass Entry has overidden these methods to delegate the call to the actual key object.

Thus the mystery is solved. So essentially it means subclass WeakReference if you want to use it in a Map.

Subscribe to comments for this post

Classloading in Appservers

Anyone creating a web-application in an application server, might have wondered, how the servlet engine did not muddle up classes from different web-apps. Take the case of a jsp index.jsp or com.xxx.Controller which might be present in nearly all web-apps. When we deploy 2 webapps having these two classes, how is the server using the correct index.jsp/Controller, when a request comes in.

The point to note is that since a class is loaded only once by a classloader, Controller if loaded once will stay on in the memory and same copy will be reused. If the application server used only one class loader to load all classes then we would show only one version of index.jsp for all webapps.

To solve this, it becomes clear each web-app needs its own classloader. Good. Now knowing this, I thot if i compile Controller & put it some where on the class path, then each web-app class loader will still refuse to pick up the Controller in its deployed location. Why ? Because the class loader documentation says all classloaders typically delegate the request to the parent before attempting to resolve it itself. The classloader hierarchy looks like this ...

Bootstrap classloader
        |
Extension classloader (loads extension classes...new version of jaxp.jar..)
        |
System classloader (loads classes from classpath)
        |
EAR Classloader
        |
WAR Classloade

So if the system class loader loads Controller from classpath it prevents all the WAR classloaders from loading Controller ever. The only way out is to prevent system classloader from loading Controller from classpath. How? By using our own implementation of the classloader. This lead me to my next question..how do i swap the default system class loader with my own implementation ?

The answer is quite simple. All we need to do is set the propery java.system.class.loader to the desired system classloader. Say we do java -Djava.system.class.loader=my.test.SimpleClassLoader then the class loader hierarchy now becomes ..

Bootstrap classloader
        |
Extension classloader (loads extension classes...new version of jaxp.jar..)
        |
Default System classloader (can load classes from classpath)
        |
System classloader (my.test.SimpleClassLoader)
        |
EAR Classloader
        |
WAR Classloader

Then i found out that the system classloaders in most app servers is designed to load only those package names that fit some predefine rules like javax.ejb.* etc and load classes only from those selected packages. They also delegate loading core java classes to the boostrap loader. These classloaders in addition do not delegate to parent for other requests. This solves most of the questions raised !

Quite a long post, makes me remember the stories we wrote in our history exams ! Ok, more details on how default system class loaders work and how class sharing between select web-apps can be done in the future.

For knowing more on classloaders read this article

Subscribe to comments for this post

Type Checking Verifier in Java6

In my previous post I talked about different steps involved in loading a class.

The verification process that happens during linking is a very important part of the java sandbox security model.

The verification process does the following

* Checks that every instruction has a valid operation code;
* Checks every branch instruction branches to the start of some other instruction,rather than into the middle of an instruction;
* Checks every method is provided with a structurally correct signature;
* Checks every instruction obeys the type discipline of the Java virtual machine language.
* Checks accesses to objects are always as what they are (for example, InputStream objects are always used as InputStreams and never as anything else).
* Access restrictions are not violated
* Plus a lot of other things as specified in the JVM specs.

As you can guess this process would be very time intensive. Java 6 has reportedly come with a new 'Type Checking Verifier' that promises to dramatically reduce the run-time computational requirements of the bytecode verifier on Java SE.

How does it manage to do it?

It turns out that much of the program analysis that the verifier performs at run-time may not be necessary, because the type information can also be obtained at compile-time when the class file is generated. The compiler includes type information needed by the verifier in the class file, the job of the verifier at run-time is made much simpler and less memory intensive. The verifier is handed a table of expected program states encoded in the class file, and can validate that those expected states actually occur, and result in safe execution.

More details on it, once i get a chance to read the updated JVM specs for this feature.

Subscribe to comments for this post

Java Program Execution

The favourite interview question one of my friends used to ask was what happens when a java program is run. The answer to this question would set our expectations from the guy in front of us immediately. Most did not even get close.

So what is the answer?

Three important steps happen before main is invoked - loading, linking and initialization.

Loading

• Loads the class byte codes and create a Class object.

Linking

• verification - binary representation of a class or interface is structurally correct
• preparation - creating the static fields for a class or interface and initializing such fields to the default values
• resolution -symbolic references to other classes and interfaces and their fields, methods, and constructors is checked to be correct and, typically, replaced with a direct reference that can be more efficiently processed if the reference is used repeatedly

Initialization

• Initialization of a class consists of executing its static initializers and the initializers for static fields
• Initialization of an interface consists of executing the initializers for fields (constants) declared
• Synchronize on the Class object that represents the class or interface to be initialized since other threads may be attempting to init the same class.

As simple as that ! Then once the class is loaded into memory, the JVM will call the main with the parameters passed in .

Subscribe to comments for this post

JMM

Whats the new JMM (JSR-133) all about?

Apparently the rules that govern the java memory these days have been changed. A brief list of the new rules:

1. Volatile read/write instructions cannot be reordered with other instructions
2. Synchronized blocks cannot be executed out of sequence with each other
   
3. Writes that initialize final fields will not be reordered with operations following the freeze
   
4. Every entry into a synchronised blocks trigger a flush of working memory so that all subsequent calls goto main memory
   
5. Every exit out of synchronised blocks trigger a write of working memory to main memory
6. All actions in a thread t1 should happen before any other thread (t2 say), successfully returns from a Thread.join() on thread t1.

Wonder how much of these were in the older JMM. I do know 1, 3 were not in the old specs, not sure abt the rest though.

Subscribe to comments for this post