Monday, April 30, 2012

Print odd and even numbers using two threads

Once again this is question from one of the java interviewer. We have two threads, one thread prints odd number and another prints even number. Modify code in such a way that output on console will be 1,2,3,4,5,6,...
I solved similar problem on coderach using CyclicBarrier. Earlier problem requires one barrier point but for current problem, we need 2 barriers. Odd Thread prints between one barrier and even thread between another barrier.
public class OddEvenPrintTest {
 public static boolean print = false;
 public static void main(String args[]) throws Exception {
  Thread t;
  int runs = 10000000;  
  CyclicBarrier barrier = new CyclicBarrier(2);

  long time = System.currentTimeMillis();
  t = new Thread(new OddBarrierRunnable(runs, barrier), "OddThread");
  t.start();
  t = new Thread(new EvenCyclicRunnable(runs, barrier), "EvenThread");
  t.start();
  t.join();
  System.out.println("Time using cyclic barrier " + (System.currentTimeMillis() - time)+"ms for runs "+runs);

 }

}

class OddBarrierRunnable implements Runnable {
 CyclicBarrier barrier;
 int runs;

 public OddBarrierRunnable(int runs, CyclicBarrier barrier) {
  this.runs = runs;
  this.barrier = barrier;
 }

 public void run() {
  try {
   for (int i = 1, counter = 0; counter < runs; i += 2, counter++) {
    if (OddEvenPrintTest.print) {
     System.out.println(i);
    }
    barrier.await();
    barrier.await();

   }
  } catch (Exception e) {
   System.out.println("Opps. I was not expecting any exception here");
  }
 }
}

class EvenCyclicRunnable implements Runnable {
 CyclicBarrier barrier;
 int runs;

 public EvenCyclicRunnable(int runs, CyclicBarrier barrier) {
  this.runs = runs;
  this.barrier = barrier;
 }

 public void run() {
  try {
   for (int i = 2, counter = 0; counter < runs; i += 2, counter++) {
    barrier.await();
    if (OddEvenPrintTest.print) {
     System.out.println(i);
    }
    barrier.await();
   }
  } catch (Exception e) {
   System.out.println("Opps. I was not expecting any exception here");
  }
 }
}

and output for different runs
Time using cyclic barrier 3 ms for runs 10
Time using cyclic barrier 31 ms for runs 100
Time using cyclic barrier 45 ms for runs 1000
Time using cyclic barrier 279 ms for runs 10000
Time using cyclic barrier 1423 ms for runs 100000
Time using cyclic barrier 18313 ms for runs 1000000
Problem with above approach is for printing one odd even number pair using 2 threads, Threads will be blocked twice and which will involve thread context switches.

Implementation of java.util.concurrent.ConcurrentLinkedQueue helped me to think this problem as Non Blocking problem. Just to give you background about ConcurrentLinkedQueue implementation, it's not using any of the plain old wait/notify mechanism or java.util.concurrent.Lock which is introduced in Java 5. Both these mechanisms will park your thread if monitor is already acquired by another thread or Lock is acquired by another thread (tryLock() will not block your thread).

Coming back to our ConcurrentLinkedQueue implementation, it internally using java.util.concurrent.atomic.AtomicReferenceFieldUpdater to update head and tail node references. Instead of every thread competing to enter into critical section (which consist of updating head/tail pointer for poll/offer operation) and blocking if lock is acquired by another thread, every thread will try to update head/tail reference from it's current reference to new reference. AtomicReferenceFieldUpdater guarantees that only one thread can succeed and other threads will fail. other failed threads will keep on updating references until they succeed.

Lets get back to our problem. here I am using AtomicInteger and to maintain 4 states and transitions as mentioned below.
State Description Transition to
1 Lock acquired by Odd Thread 2
2 Lock released by Odd Thread 3
3 Lock acquired by Even Thread 0
0 Lock released by Even Thread 1
Odd Thread can acquire lock only when current state is 0. Once it will acquire lock (at line 29), it will update current state to 1 (ie. Odd thread is holding lock). Once odd thread holds lock, it prints odd value and then release lock by setting AtomicInteger value to 2( ie. Lock is released by Odd Thread. at line 34).

While Odd thread is holding lock, even thread also tries to update value from 2 to 3 in infinite loop( at line 52). This operation will succeed only after Odd Thread updates value from 1 to 2(at line 34). Once Even thread done with it's turn, it updates value from 3 to 0 (at line 57).
public class OddEvenPrintTest {
 public static boolean print = false;
 public static void main(String args[]) throws Exception {
  AtomicInteger atomicInt = new AtomicInteger(0);
  Thread t;
  int runs = 10;
  long time = System.currentTimeMillis();
  new Thread(new OddAtomicRunnable(atomicInt, runs)).start();
  t = new Thread(new EvenAtomicRunnable(atomicInt, runs));
  t.start();
  t.join();
  System.out.println("Runs -"+runs);
  System.out.println("Time using Atomic " + (System.currentTimeMillis() - time)+"ms for runs "+runs);
 }
}


class OddAtomicRunnable implements Runnable {
 AtomicInteger atomicInt;
 int runs;

 public OddAtomicRunnable(AtomicInteger atomicInt, int runs) {
  this.atomicInt = atomicInt;
  this.runs = runs;
 }

 public void run() {
  for (int i = 1, counter = 0; counter < runs; i += 2, counter++) {
   while (!atomicInt.compareAndSet(0, 1)) {
   }
   if (OddEvenPrintTest.print) {
    System.out.println(i);
   }
   while (!atomicInt.compareAndSet(1, 2)) {
   }
  }
 }
}


class EvenAtomicRunnable implements Runnable {
 AtomicInteger atomicInt;
 int runs;

 public EvenAtomicRunnable(AtomicInteger atomicInt, int runs) {
  this.atomicInt = atomicInt;
  this.runs = runs;
 }

 public void run() {
  for (int i = 2, counter = 0; counter < runs; i += 2, counter++) {
   while (!atomicInt.compareAndSet(2, 3)) {
   }
   if (OddEvenPrintTest.print) {
    System.out.println(i);
   }
   while (!atomicInt.compareAndSet(3, 0)) {
   }
  }
 }
}

and here is the output for different runs
Time using Atomic 14 ms for runs 10
Time using Atomic 50 ms for runs 100
Time using Atomic 71 ms for runs 1000
Time using Atomic 100 ms for runs 10000
Time using Atomic 121 ms for runs 100000
Time using Atomic 249 ms for runs 1000000
Time required using AtomicInteger is definitely less than time it took using Cyclicbarrier.

Advantage of using AtomicInteger here:
  • This solution can be extended for many threads.
It also has some limitations as mentioned below:
  • make sure critical section needs to be really short. Runs in few CPU cycles. because other threads will be also competing for lock using busy waiting approach.
  • Any blocking operations like I/O, wait/notify should not be executed from Critical section.

Note:Tests conducted on fedora 13 Intel Core2 Duo machine with JDK 1.6.0_12

Sunday, April 1, 2012

Extract system properties from heap dump using Visual VM OQLand JavaScript

VisualVM is one of the great tool but still it's not popular in Java community.

One of the interesting feature of VisualVM is traversing heap dump. VisualVM supports OQL syntax similar to eclipse MAT. But java script support along with OQL sytax make it different.

Do you want to print system properties from heap dump? System Properties are internally maintained as hash Map. It's probably difficult to traverse such hash map using normal OQL syntax. But using VisualVM OQL syntax along with java script it's possible.

Load heap dump in visualVM and copy paste below javascript syntax into VisualVM -> HeapDump -> OQL Console (tab).

function printProp(obj) {
    var ret = '';
        // count is proeprty of java.util.Properties 
        ret = 'Count = '+obj.count+"< br/>";
        // table is property of java.util.Properties which is table of java.util.HashTable.Entry
        tables = toArray(obj.table);

        //Iterate over table and print entries
        for(i = 0;i< tables.length;i++) {
               e = tables[i];
               //Iterate while e is not null
               while(e != null) {
                    if(e.key!= null) {
                        ret +=e.key.toString();
                    }else {
                        ret += 'null';
                    }
                    if(e.value!= null) {
                        ret +=" = "+e.value.toString();
                    }else {
                        ret +=" = null";
                    }
                    ret+="< br/>";
                    e = e.next;
               }
        }
    return ret;
}
// props is static attribute of java.lang.System which holds system Properties.
// pass props to printProp function.
printProp(heap.findClass("java.lang.System").props);

and here is output.

Count = 50
sun.cpu.isalist =
sun.desktop = gnome
sun.io.unicode.encoding = UnicodeLittle
sun.cpu.endian = little
java.vendor.url.bug = http://java.sun.com/cgi-bin/bugreport.cgi
file.separator = /
java.vendor = Sun Microsystems Inc.
sun.boot.class.path = /usr/java/jdk1.6.0_12/jre/lib/resources.jar:/usr/java/jdk1.6.0_12/jre/lib/rt.jar:/usr/java/jdk1.6.0_12/jre/lib/sunrsasign.jar:/usr/java/jdk1.6.0_12/jre/lib/jsse.jar:/usr/java/jdk1.6.0_12/jre/lib/jce.jar:/usr/java/jdk1.6.0_12/jre/lib/charsets.jar:/usr/java/jdk1.6.0_12/jre/classes
java.ext.dirs = /usr/java/jdk1.6.0_12/jre/lib/ext:/usr/java/packages/lib/ext
java.version = 1.6.0_12-ea
java.vm.info = mixed mode
user.language = en
java.specification.vendor = Sun Microsystems Inc.
java.home = /usr/java/jdk1.6.0_12/jre
sun.arch.data.model = 32
java.vm.specification.version = 1.0
java.class.path = /home/rohand/workspace/java5/bin:
user.name = rohand
file.encoding = UTF-8
java.specification.version = 1.6
java.awt.printerjob = sun.print.PSPrinterJob
user.timezone =
user.home = /home/rohand
os.version = 2.6.33.3-85.fc13.i686.PAE
sun.management.compiler = HotSpot Tiered Compilers
java.specification.name = Java Platform API Specification
java.class.version = 50.0
java.library.path = /usr/java/jdk1.6.0_12/jre/lib/i386/server:/usr/java/jdk1.6.0_12/jre/lib/i386:/usr/java/jdk1.6.0_12/jre/../lib/i386:/usr/lib/jvm/java-1.6.0-openjdk-1.6.0.0/jre/lib/i386/client:/usr/lib/jvm/java-1.6.0-openjdk-1.6.0.0/jre/lib/i386:/usr/lib/xulrunner-1.9.2:/usr/lib/xulrunner-1.9.2:/usr/java/packages/lib/i386:/lib:/usr/lib
sun.jnu.encoding = UTF-8
os.name = Linux
java.vm.specification.vendor = Sun Microsystems Inc.
java.io.tmpdir = /tmp
line.separator =

java.endorsed.dirs = /usr/java/jdk1.6.0_12/jre/lib/endorsed
os.arch = i386
java.awt.graphicsenv = sun.awt.X11GraphicsEnvironment
java.runtime.version = 1.6.0_12-ea-b03
java.vm.specification.name = Java Virtual Machine Specification
user.dir = /home/rohand/workspace/java5
sun.java.launcher = SUN_STANDARD
user.country = US
sun.os.patch.level = unknown
java.vm.name = Java HotSpot(TM) Server VM
file.encoding.pkg = sun.io
path.separator = :
java.vm.vendor = Sun Microsystems Inc.
java.vendor.url = http://java.sun.com/
sun.boot.library.path = /usr/java/jdk1.6.0_12/jre/lib/i386
java.vm.version = 11.2-b01
java.runtime.name = Java(TM) SE Runtime Environment

Screenshot of VisualVM OQL Syntax tab

Saturday, March 10, 2012

Call Grand Parent method in Java

This is my very first blog. Help me to make it better.

Last week one of the java interviewer asked my friend whether you can call a grand parent method if method is overridden in parent class ? As like most other java developers know, he replied no, you can’t directly call grand parent method if it’s overridden in child class and I also agreed with him.

I know it’s not a supported feature in java language but I really wanted to see if I can do it anyway.
The only thing that came into my mind was reflection. I tried to retrieve Method instance from Parent Class and passed instance of child class, but Java still invoked overridden method of child class. No way you can do it with reflection.

To execute parent class method you always need to call it as super.method(). So how this super.method() makes difference than normal this.method() ?

public void test() {
 super.test();
 this.test();
}

So lets decompile bytecode for above test method.
public void test();
Code:
0:    aload_0
1:    invokespecial    #15; //Method AI1.test:()V
4:    aload_0
5:    invokevirtual    #17; //Method test:()V
8:    return

Wow, so when I called super.test(), that gets translated into 'invokespecial' bytecode and other method call gets translated into 'invokevirtual' bytecode.

Do you think with this knowledge of bytecodes, you can play any trick to call grand parent method ?

Yes, we can do it with the help of ASM. Using ASM, call test() method of Ancestor class with 'invokespecial'

Now let's see our class hierarchy.

public class AI {
 public void test() {
  System.out.println("test of AI");
 }
}

public class AI1 extends AI{
 public void test() {
  System.out.println("test of AI-1");
 }
}

public class AI2 extends AI1{
 public void test() {
  System.out.println("test of AI-2");
 }
}

Here Class AI2 is extending from AI1 and AI1 is extending from AI. Also method test() is overridden in all classes that means calling test() method on instance of AI2 class will result into executing test() method of AI2 only.

Now it's time to write down my ASM code. Using ASM, you can modify any existing class as well. But for simplicity I am creating here one more class Example, which is extending from AI2 class and also has overridden test() method.

import java.io.FileOutputStream;

import org.objectweb.asm.ClassWriter;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;

public class ASMByteCodeManipulation extends ClassLoader implements Opcodes {

 public static void main(String args[]) throws Exception {
  ClassWriter cw = new ClassWriter(0);
  cw.visit(V1_1, ACC_PUBLIC, "Example", null, "AI2", null);

  // creates a MethodWriter for the (implicit) constructor
  MethodVisitor mw = cw.visitMethod(ACC_PUBLIC, "<init>", "()V", null,null);
  mw.visitVarInsn(ALOAD, 0);
  mw.visitMethodInsn(INVOKESPECIAL, "AI2", "<init>", "()V");
  mw.visitInsn(RETURN);
  mw.visitMaxs(1, 1);
  mw.visitEnd();

  // creates a MethodWriter for the 'test' method
  mw = cw.visitMethod(ACC_PUBLIC, "test", "()V", null, null);
  mw.visitFieldInsn(GETSTATIC, "java/lang/System", "out","Ljava/io/PrintStream;");
  mw.visitLdcInsn("test of AI3");
  mw.visitMethodInsn(INVOKEVIRTUAL, "java/io/PrintStream", "println",
    "(Ljava/lang/String;)V");
  //Call test() of AI
  mw.visitVarInsn(ALOAD, 0);
  mw.visitMethodInsn(INVOKESPECIAL, "AI", "test", "()V");
  //Call test() of AI
  mw.visitVarInsn(ALOAD, 0);
  mw.visitMethodInsn(INVOKESPECIAL, "AI1", "test", "()V");
  //Call test() of AI
  mw.visitVarInsn(ALOAD, 0);
  mw.visitMethodInsn(INVOKESPECIAL, "AI2", "test", "()V");
  mw.visitInsn(RETURN);
  mw.visitMaxs(2, 1);
  mw.visitEnd();

  byte[] code = cw.toByteArray();
  FileOutputStream fos = new FileOutputStream("Example.class");
  fos.write(code);
  fos.close();

  ASMByteCodeManipulation loader = new ASMByteCodeManipulation();
  Class<?> exampleClass = loader.defineClass("Example", code, 0,
    code.length);
  Object obj = exampleClass.newInstance();
  exampleClass.getMethod("test", null).invoke(obj, null);

 }
}

and here is the output of above class
test of AI3
test of AI
test of AI-1
test of AI-2
Lets see now, how we achieved this.
On line 11, we defined new class Example which is extending from AI2 class. We also need to write down constructor. On line 22, our new Example class is overriding test() method where it first prints "test of AI3" and then invokes test() method of AI, AI1 & AI2 class on line 29,32 & 35 respectively. In main method, on line 45 it's creating an instance of Example class and invoking its test method using reflection.

Our new Example class is also written to Example.class file. Let's decode it's test() method
public void test();
Code:
0:    getstatic    #15; //Field java/lang/System.out:Ljava/io/PrintStream;
3:    ldc    #17; //String test of AI3
5:    invokevirtual    #23; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
8:    aload_0
9:    invokespecial    #27; //Method AI.test:()V
12:    aload_0
13:    invokespecial    #30; //Method AI1.test:()V
16:    aload_0
17:    invokespecial    #31; //Method AI2.test:()V
20:    return

yes, on line 7,9 & 11 you can see it's invoking test() method of AI, AI1 & AI2 class respectively.

Above approach has limitations as well. invokespecial can be invoked from child class only. If you will try to use 'invokespecial' from non-child class,JVM runtime will fail to load your class with error message as
Exception in thread "main" java.lang.VerifyError: (class: Example, method: test1 signature: (LAI2;)V) Illegal use of nonvirtual function call

Yes, our job is done. Even though java language specification does not support invoking grand parent method if it is overridden in parent class, with the help of few bytecode manipulation we can always do it.

Note :- Above demonstration is just to show you capabilities of byte code manipulation. This solution is not advised for your day to day development.