X

Vaibhav's Blog Space

  • Java
    July 25, 2008

SubType Check Optimization in Java !

Guest Author

Lots of our friends keep on asking, why to use Java SE 5.0 or Java SE 6. And most of the time you need to reply something impressive, then only they will start using it and can understand more benefits.  I was reading the gradual performance improvement in JDK versions which is quite interesting. Java has spotted all its reason to being slow (very nice article, which speaks why Java is slow than C++) and optimized those on max level. One of the reasons mentioned in this article was Lots of Casts. And that's true, a good, big project code goes about millions of cast checking in Java and off course need attention for optimization. JDK 5 and onwards has done a fast subtype checking in Hotspot VM. This blog is dedicated on a small talk on the same, for detail read this article written by John and Cliff.

Prior to 5, Every Subtype has cached with its SuperType(casting of which is correct). The cache strength is 2 and if results return negative then its goes for a VM call which resolves this problem and caches if VM resolves it as positive. So anytime unavailability in cache is a costly operation where we need to make a call for VM. And in the worst scenario mentioned in SpecJBB we can have 3 rotating elements with 2 cache.

So, [A B] in cache <---- C found by VM and get cached, A is out now.

[B,C] in cache <-------- A negative test, VM call(+), get cached, B out.

[C,A] in cache <-------- B negative test, VM call(+), get cached, C out !

So, in basic term we can't trust on complexity(calls happen at runtime). And hence it better to move on a better algorithm. The new algorithm pass the code through an optimizer which checks more specification at compile time. Like if Base class and Derived class is known at compile time only. It try to understand lot of code at compile time only. It put the entire code inline and there is no requirement of VM calls. Complexity is quite consistent and it takes one load for most of the object or object array.

This also divide the subtype checks into primary and secondary checks. For Class, Array of Classes and for array of primitive value, primary check has been done whereas interface and array of interface are handled by secondary check. Finally a smart algorithm combines them.

In primary subtype check:

Aim to Check: Is S a subtype of T ? Calculate the depth of S and T. Depth mean to say all the parent. Though it is done in some base level or assemble level, I am writing a code in Java to find out the depth.  Here is the code using reflection API's:

package findparent;
public class Main {
    public static void main(String[] args) throws Exception {
        String[] display = new String[10];
        int i = 1;
        FifthClass tc = new FifthClass();
        Class classname = tc.getClass();
        display[0] = classname.getName();
        Class parent = classname.getSuperclass();
        while (!(parent.getName().equals("java.lang.Object"))) {
            display[i] = parent.getName();
            classname = parent.newInstance().getClass();
            parent = classname.getSuperclass();
            i++;
        }
        display[i] = "java.lang.Object";
        for (int j = 0; j <= i; j++) {
            System.out.println(display[j]);
        }
        System.out.println("Depth of tc is " + i);
    }
}
class FirstClass {
}
class SecondClass extends FirstClass {
}
class ThridClass extends SecondClass {
}
class ForthClass extends ThridClass {
}
class FifthClass extends ForthClass {
}

Now the algo. says:

S.is_subtype_of(T) :=
return (T.depth <= S.depth) ? (T==S.display[T.depth]) : false;

And further a lot of optimization. Which we will check in next blog :-). I will also try to cover how the secondary Subtype check is being done and also how to combine both the checks.

Till now, make a big inheritance tree and try to see the difference between older JDK and JDK5 onwards.

Join the discussion

Comments ( 3 )
Please enter your name.Please provide a valid email address.Please enter a comment.CAPTCHA challenge response provided was incorrect. Please try again.Captcha