Time complexity measure of JDK class methods

Question

Is there an established way of measuring (or getting an existing measure) a JDK class method complexity? Is javap representative of time complexity and to what degree. In particular, I am interested in the complexity of Arrays.sort() but also some other collections manipulation methods.

E.g. I am trying to compare two implementations for performance, one is using Arrays.sort() and one doesn't. The javap disassembly for that doesn't returns a lot more steps (twice as many) but I am not sure if the one that does excludes the Arrays.sort() steps. IOW, does javap of one method include a recursive measure of the methods invoked within or just for that method?

Also, is there a way, without modifying and recompiling the Java code itself, to find how many loop iterations were done when a certain base Java method was invoked on specific parameters? E.g. measure the number of iterations of Arrays.sort('A', 'r', 'T', 'f')?

Answer 1

I would not expect javap to be even a little bit representative of actual speed.

The Javadoc specifies the algorithmic complexity, but if you care about constant factors there is absolutely no way to realistically compare constant factors except with actual benchmarks.

You can't get any information on what was done when Arrays.sort is called on a primitive array, but by passing a custom Comparator that counts the number of calls, you can count the number of comparisons made when sorting an object array. (That said, object arrays are sorted with a different sorting algorithm -- specifically a stable one -- and primitive arrays are sorted with a Quicksort variant.)

Answer 2

you can use the output from javap to determine where loops occur you want to find the goto instruction. This post gives a comprehensive explanation of that identification.

From the post:

Before considering any loop start/exit instrumentation, you should look into the definitions of what entry, exit and successors are. Although a loop will only have one entry point, it may have multiple exit points and/or multiple successors, typically caused by break statements (sometimes with labels), return statements and/or exceptions (explicitly caught or not). While you haven't given details regarding the kind of instrumentations you're investigating, it's certainly worth considering where you want to insert code (if that's what you want to do). Typically, some instrumentation may have to be done before each exit statement or instead of each successor statement (in which case you'll have to move the original statement).

Answer 3

Arrays.sort() for primitives uses tuned quicksort. For Object uses mergesort (but this is depends on implementation).

From: Arrays

For example, the algorithm used by sort(Object[]) does not have to be a mergesort, but it does have to be stable