Generics performance demystified

by Amir Shevat


My team and I are developing open source infrastructure solutions such as MantaRay, our open source JMS provider (yes, we are getting paid to write open source). One of my ongoing tasks is performance improvements. When you develop infrastructure you really need to think performance at all times.



Lately I was wondering if utilizing the new features of java 5.0 (AKA java 1.5) such as generics would improve my code's performance. Generics looks like a type-safe solution, the theory behind it being that with generics you have an ArrayList that holds Integers or Strings and not an array of objects that needs to be cast to the specific concrete class. If you have the type information of the Object you are working with, then you do not need type checking, virtual method calls or and other operations that are required when using abstract objects.



Using java 1.4.2 I started to check this theory. I created two arrays, one consisting of Objects and the other of MyTestObject objects. I filled the two arrays with MyTestObject objects and then called the toString method on every element in the array. In order to make this clear, here is a small piece of the code:



// use object array
Object[] objectArray = new Object[1000];

for (int i = 0; i < objectArray.length; i++) {
objectArray[i] = new MyTestObject(i);
}

for (int i = 0; i < objectArray.length; i++) {
String result = objectArray[i].toString();
}

// use MyTestObject array
MyTestObject[] objectArray = new MyTestObject[1000];

for (int i = 0; i < objectArray.length; i++) {
objectArray[i] = new MyTestObject(i);
}

for (int i = 0; i < objectArray.length; i++) {
String result = objectArray[i].toString();
}




There was a 10% improvement in performance using the MyTestObject-specific array. 10% improvement is a lot for me, so I verified the result by running the test thousands of times and got the same results. If generics are all they are cut to be then they will yield the same performance improvements.




Well, actually that is not the case; I have compiled this simple piece of code in java 5.0:



LinkedList<MyTestObject> list =
new LinkedList<MyTestObject>();

list.add(new MyTestObject());
MyTestObject result = list.get(0);


Then I decompiled the code and got these results:



LinkedList list = new LinkedList();
list.add(new MyTestObject());
MyTestObject result =
(MyTestObject)list.get(0);


A mystery! All of the type information has vanished. Later I found the answer on SUN's site:
"Generics are implemented by type erasure: generic type information is present only at compile time, after which it is erased by the compiler..."




To make sure, I implemented my own LinkedList based on java 1.4.2 LinkedList; I just modified the internals to work with MyTestObject instead of object. My linked list showed better performance then java 5.0 LinkedList, although it was less then 10% it was still better, and I only provided runtime type information.



My conclusion is that the new generics feature is a step in the right direction, it looks like the template of C++ and provides type checking at compile time, it might even be more readable and easier to understand, but it fails to follow through and provide the type information needed at runtime to improve performance. The guys at Sun say that type erasure is needed to ensure backward compatibility. While backward compatibility is an important thing; improving the runtime performance is important too. I guess we need to find some way both can coexist.




Are Generics only syntactical sugaring?


10 Comments

SeanReilly
2005-10-18 10:04:40
Combining both performance and type safety
One way to combine performance and type safety is to generate a List implementation:



public class FooList implements List
{
public boolean add(Foo o) { }
/// etc...
}


//somewhere else:
List f = new FooList();


This method will allow you to write (or generate) tuned classes that use runtime type information (as well as any additional performance improvements you can come up with), while still interacting with the traditional collections api, and preserving easy safety.

kgeis
2005-10-18 12:06:20
factoring out Hotspot
Did you make sure to "prime the pump" before running the 1.4.2 microbenchmark? You really should do a loop before timing to make sure that Hotspot has compiled MyTestObject.toString(). I'd like to know that the 10% performance increase didn't come from Hotspot kicking in.
ashevat
2005-10-18 12:55:49
factoring out Hotspot
Yes, I did wait for the Hotspot to kick in. As I said I run the test thousands of times. After the Hotspot kicked in there was an improvement in the absolute time of both loops but the structure that had type information was still 10% faster.
matt111
2005-10-18 19:29:50
Flawed results
I ran it and there is no difference in run time between the two array scenarios. The first one is the slow one because it ran first while the VM was priming. Switch them and the other will be slower. I get no difference.
It makes sense too since the String result of the toString is never read inside the loop the hotspot can mostly optimize that operation away.
ashevat
2005-10-19 02:24:06
Flawed results
Well, I went on a quest to re-verify my results, I tried my code again and again and I got the same result.


Then I tried my code on another machine and the results were a little ambiguous, but when I raised the number of iterations in the loops the results became unambiguous and I got the same improvement ratio again.


Here is the full code; I tried on four different machines with these VM arguments -Xmx512m -Xms512m:



public class MyTest {


public static void main(String[] args){
int iterations = 100;
long dur = 0;
for(int count = 0 ; count < iterations; count++){
// you can switch between the order of the next two lines
long result = withoutTypeInfoTest();
long result2 = withTypeInfoTest();
System.out.println("}} Time difference "+(result-result2));
}

}


public static long withoutTypeInfoTest(){

long startTime = System.currentTimeMillis();
Object[] objectArray = new Object[10000000];
for (int i = 0; i < objectArray.length; i++) {
objectArray[i] = new MyTestObject();
}
for (int i = 0; i < objectArray.length; i++) {
String result = objectArray[i].toString();
}
long endTime = System.currentTimeMillis();
long duration = (endTime -startTime);
System.out.println("time spent in test (no type info) ="+duration);
return duration;
}

public static long withTypeInfoTest(){
long startTime = System.currentTimeMillis();
MyTestObject[] objectArray = new MyTestObject[10000000];
for (int i = 0; i < objectArray.length; i++) {
objectArray[i] = new MyTestObject();
}

for (int i = 0; i < objectArray.length; i++) {
String result = objectArray[i].toString();
}
long endTime = System.currentTimeMillis();
long duration = (endTime -startTime);
System.out.println("time spent in test (with type info) ="+duration);
return duration;
}

}


And MyTestObject code is:



public class MyTestObject {

public String toString(){
// return the meaning of life :)
return "42";
}

}


If you run it please ignore the first iteration in the test, this iteration is before the hotspot kicks in.


If you think that millions of iterations are too much remember that the results are a relative ratio of improved performance, the large number of iterations just makes other process interference go away.


Amir Shevat

nilskp
2005-10-19 07:47:57
Erasure
Since generics are erased at compile time and leaves no trace in the bytecode, I don't see how there can possibly be any difference.
ashevat
2005-10-19 08:25:19
Erasure
Thatís exactly my point.
Because generics are erased in compile time, a new generic LinkedList<MyTestObject>() will yield the same performance as the old java 1.4.2 LinkedList() will yield (and I am not talking about VM performance, I know 5.0 is faster then 1.4.2).
On the other hand a LinkedList that holds the type information at runtime will yield better result.


Amir

TomHawtin(tackline)
2005-10-19 15:36:07
Flawed results

My results show a 10% difference on 1.5.0 with the client VM. If performance is really important to you, use -server which evens things up. 1.6.0 produces closer results too.

If you were doing something less trivial instead, the performance gap would narrow further. This kind of optimisation is completely insignificant, IMO.

matt111
2005-10-19 15:50:17
Flawed results
Ok with your code I do get your results but one simple change, and it's quite the level playing field.

public class MyTestObject {
public MyTestObject() { }


public String toString() {
return super.toString();
}
}


It makes me wonder what exactly accounts for the differing findings, and confirms my suspicion in benchmarking trivial examples with a JIT VM.

ashevat
2005-10-20 01:41:00
Flawed results
matt111,


When you changed the code of toString() to super.toString() the method calls the Object toString():

public String toString() {
return getClass().getName() + "@" + Integer.toHexString(hashCode());
}


As you can see this is heavier implementation and probably takes more time then just returning 42. By making the test trivial we distil the problem at hand.


TomHawtin,


Thanks for the -server and 1.6.0 inputs, this is good and helpful news.
As for the insignificance of the problem, think of how much time we spend optimizing a commonly accessed SQL statement, then think of how commonly we use lists and maps. Shaving off milliseconds can really make an improvement, especially when we talk about Java which is the infrastructure of all of our programs.

I love Java and would really be disappointed if we would be talking about a performance issue in the magnitude of seconds.


Amir