Testing the speed of the instanceof instruction

Some people claim that this instruction is quite slow to execute, this is wrong, according to the testing I have done, checking the type of an object take almost the same time as comparing two long numbers. I believe that this is because both entity have almost the same size, the object type seem to be contained in the reference, what I think is something logic.

Measuring the time taken to perform the operation

Execution time measurement could be done in two ways :

Measure quite short execution time
Measure very long execution time, with a CPU occupation of 100 %

The first methode could give some quite random values, because their are interuption of the operating system that make switch the CPU to another task, or at least to check if their is another that have to do something. This will take time, and will make measured time random, the other way of doing is to measure a much longer time, in this case this source of randomness will be avoided, but their will be an error caused by the CPU usage of the other programs including the operating system, that may be something arround 1%. So first I used the former method, it work quite well and show us an order of magnitude, it take something less than 30 ns and on average 24 ns for each usage of instanceof, this is to compare to addition of an arrray of integer that take on average 7 ns per addition, with some peaks bellow 20 ns. To perform the measurement it's quite easy, we save the time in nanosecond in a variable start, with the instruction System.nanoTime() and then compare to the time after executing a loop that make one million iterations. The same procedure with long numbers ( ie coded on 64 bits ) will take 10 ns for each operations.

Testing with bigger arrays

Using bigger array we avoid imprecision caused by the Scheduling done by the operating system, but their is some precaution to take using larger amount of memory, the first one is to use bigger not swap, because when swaping, memory acces get very slow, and the time used by each operation will be modified due to access to the very slow access to the hard disk. The size best compromis, for very simple operations like addition of long is to simply use 32 millions of elements, this will use 256 mb of memory that is acceptable on a nowaday computer. Going below this size we will get some imprecision because of random fluctuations caused by the scheduling process of the operating system. Note also that large memory allocation is required, this is possible by runing the virtual machine with the flag -Xmx256mb that will allow to allocate much more memory. For an int array the result is a time arround 5 ns, for long it's arround 5.5 ns, it's quite surprising that both of them are almost equal. But return to our goal instanceof this operation is slower than the others it take arround 11 ns to execute. But it not that's slow. By the way we also add an addition, but in this case this addition concern an limited set of elements, so they could be stored in the CPU, avoiding plenty transfert between memory and CPU.

Testing by yourself

I wrote two program to check how much time the operation take :

time that take each addition on an array of long : SpeedTest.java
time that take each instanceof on an array of String/Integer/Double mix TestInstanceof.java

Futher questions

What would also be intersting to answer is checking the size of a specific kind of array, what's about private class that could no more be extended, they don't need to store the type of the object at each references, this should allow to save some space

Conclusion

In our first model both data type, and reference to the object are stored in the same location, we should have had a time that would have been approximatively the same as the one required to access once to memory and make a simple operation. It's seems that we have to do two access. In our cases access might be very optimal because elements are well ordered in memory, but anyway the instanceof instruction is not very costful because it's like doing an access to a variable contained in an object and compare it to a value. In the case of a more simple organization : reference and type are stored in a unique entity, such longer access in comparaison to the simple operation required time is quite hard to explain.

References

http://www.javaworld.com/javaworld/javaqa/2003-12/02-qa-1226-sizeof.html