121How Deep is Your Hierarchy?

Author: Dr. Heinz M. KabutzDate: 2006-02-14Java Version: 5Category: Language

Abstract: Someone asked me yesterday what the maximum inheritance depth is in Java. I guessed a value of 65535, but for practical purposes, not more than 5. When I asked performance guru Kirk Pepperdine to estimate, he shot back with 63. In this newsletter, we look at the limitations in the JVM and examine some existing classes.

Welcome to the 121st edition of The Java(tm) Specialists' Newsletter, sent to you all the way from Cape Town, South Africa. I am back home again, enjoying the warmth and sunshine. The lions and elephants are kindof quiet tonight ;-) Our excellent finance minister Trevor Manuel is delivering the budget speech tomorrow, and we are hoping that our high taxes will be reduced. I was surprised to read the other day that out of a pool of 50 million South African residents, over 10 million are beneficiaries of various social security grants (that's over 20% of our population depending on welfare). So whilst I am hoping for a reduction in my tax rate, I will not be holding my breath that the savings will be significant ...

In my last newsletter I mentioned that "I wrote" the Java Programmer exam. This caused some confusion amongst readers, since it sounded like "I authored". Instead, I should have said "I took" or "I sat". The subtle differences between South African English and US/UK/etc can be confusing. If you ask directions in South Africa, don't be surprised if you are told: "turn right at the robots" - down here, traffic lights are called "robots".

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

How Deep is Your Hierarchy?

Someone asked me yesterday what the maximum inheritance depth is in Java. I guessed a value of 65535, but for practical purposes, not more than 5. In this newsletter, we look at the limitations in the JVM and examine some existing classes.

To test the limitations, I wrote a little program that generates Java source files.

import java.io.*;

/**
 * This class generates a deep class hierarchy, with # levels
 * specified by the first command line parameter.
 */
public class MakeClasses {
  public static void main(String[] args) throws IOException {
    File temp = new File("temp");
    temp.mkdir();
    int levels = Integer.parseInt(args[0]);
    for (int i = 0; i < levels; i++) {
      PrintStream out = new PrintStream("temp/Test" + i + ".java");
      String superClass = i == 0 ? "Object" : ("Test" + (i - 1));
      String className = "Test" + i;
      out.println("public class " + className +
          " extends " + superClass + " {}");
      out.close();
    }
    PrintStream out = new PrintStream("temp/Test.java");
    out.println("public class Test {");
    out.println("  public static void main(String[] args) {");
    out.println("    Test" + (levels - 1) + " t = " +
       "new Test" + (levels - 1) + "();");
    out.println("    System.out.println(t);");
    out.println("  }");
    out.println("}");
  }
}

When running this code, I managed to compile and run up to 60 levels deep below Object. No one would ever want to do that in practice, but it is interesting that it fails so soon. At 61 levels I get a StackOverflowError when trying to print the class.

Another interesting fact is that I could only compile up to 1000 levels below Object. Here is the output if I compile 1001 levels below Object:

    The system is out of resources.
    Consult the following stack trace for details.
    java.lang.StackOverflowError

I tried generating 100,000 classes in one long inheritance chain, but javac just laughed at me when I tried to compile them.

How closely are depth of hierarchy related to complexity? We all know the rule of "favour composition over inheritance". I must put that in my will: "Dear son, you will have to be composed, I left you out of my inheritance."

To try this out, I wrote another small class that examines how deep the hierarchies go. It examines all the jar and zip files in the classpath, loads all the classes and checks how their depth. It only works for a few thousand classes, after that it crashes mysteriously.

You can run this against your own libraries by simply putting them into the classpath.

public class ClassInfo implements Comparable<ClassInfo>{
  private final String className;
  private final int depth;
  public ClassInfo(String className, int depth) {
    this.className = className;
    this.depth = depth;
  }

  public int compareTo(ClassInfo o) {
    if (depth < o.depth) return -1;
    if (depth > o.depth) return 1;
    return className.compareTo(o.className);
  }

  public String toString() {
    return depth + "\t" + className;
  }
}


import java.io.File;
import java.util.*;
import java.util.jar.*;

public class DeepestClassSearch {
  public static void main(String[] args) throws Exception {
    String java_class_path = System.getProperty(
        "java.class.path");
    String separator = System.getProperty("path.separator");
    String[] jars = java_class_path.split(separator);

    Collection<ClassInfo> result = new TreeSet<ClassInfo>();
    for (String jarFileName : jars) {
      if (jarFileName.endsWith(".jar") ||
          jarFileName.endsWith(".zip")) {
        File jarFile = new File(jarFileName);
        if (jarFile.exists()) {
          System.out.println("Scanning: " + jarFile);
          extractClasses(jarFile, result);
        }
      }
    }
    for (ClassInfo info : result) {
      System.out.println(info);
    }
  }
  private static void extractClasses(File file,
          Collection<ClassInfo> result)
      throws Exception {
    Enumeration<JarEntry> en = new JarFile(file).entries();
    while (en.hasMoreElements()) {
      JarEntry je = en.nextElement();
      String className = je.getName();
      if (className.endsWith(".class")) {
        className = className.replaceAll("\\.class", "");
        className = className.replaceAll("/", ".");
        try {
          Class clazz = Class.forName(className, false,
              ClassLoader.getSystemClassLoader());
          int depth = checkDepth(clazz);
          result.add(new ClassInfo(className, depth));
        } catch (Throwable er) {
          System.err.println(className + ": " + er);
        }
      }
    }
  }

  public static int checkDepth(Class clazz) {
    int level = 0;
    while (clazz != null) {
      level++;
      clazz = clazz.getSuperclass();
    }
    return level;
  }
}

Run it with rt.jar file like this:

java -classpath .;%JAVA_HOME%\jre\lib\rt.jar DeepestClassSearch

The worst offenders had an inheritance depth of 9 classes. Look for example at the inner class DoubleRenderer within JTable. One interesting thing to notice there is that the inner class UIResource extends the outer class! Here is the inheritance hierarchy:

1 javax.swing.JTable$DoubleRenderer
    extends
2 javax.swing.JTable$NumberRenderer
    extends
3 javax.swing.table.DefaultTableCellRenderer$UIResource
    extends
4 javax.swing.table.DefaultTableCellRenderer
    extends
5 javax.swing.JLabel
    extends
6 javax.swing.JComponent
    extends
7 java.awt.Container
    extends
8 java.awt.Component
    extends
9 java.lang.Object

Inheritance Depth Record

Perhaps we should start a Guiness Book of Geek Records, then we could document the deepest inheritance hierarchy found on any project.

I ran this code over some jar files that I worked with many years ago. In the one, I discovered a hierarchy depth of 10. This was the most difficult code that I have ever had the displeasure of working with. (The guilty programmer, you probably know who you are, I'll buy you some cheap beer in Cape Town one day ;-)

So here is the start of a new hobby: Geek Records - have a look at our webpage . Two categories, open source and proprietary. To win fame for discovering a deep open-source hierarchy, you have to reveal the project and the class that exceeds 9 levels. You may post anonymous submissions for the proprietary records. We will take your word for it.

• Open Source: Click here if you have found an open source inheritance depth bigger than 9.
• Proprietary: Click here if you have found a proprietary inheritance depth bigger than 10.

In this newsletter, I looked at how deep some class hierarchies get. I recommend limiting them to 5 or less. I did not look at how many interfaces you could implement. The Java Virtual Machine Specification limits this to 65535 per class, but I did not feel like trying this out.

Inheritance is an essential technique of building Object Oriented systems. Design Patterns show us how to apply inheritance correctly in practice. The more I study these patterns, the clearer the relationship between composition and inheritance becomes.

For some reason I woke up at 4:00 this morning. I think it was a guilty conscience for not doing enough exercise. I spent an hour contemplating whether to cycle or run. Eventually I settled for a short jog / walk, much to the delight of our little black Dachshund.

Kind regards

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive