Improving Comparable compareTo performance

Question

I profiled my code and found out that my class, which implements Comparable<T>, spends 8x more cpu time in

compareTo(Object)

than in

compareTo(T)

I assume that the slowdown is because of virtual table lookup for this method.

Is there a way to force static invocation of the function? (like in non virtual C++ methods)

I still want to use the Comparable<T> interface since I use TreeSet with this object and I'd like not to rewrite this code.

EDIT: No, I didn't implement the compareTo(Object) - this was automatically generated and reported by the profiler

And the two compareTo's are exactly the same other than casting? — Michael Myers, Mar 10 '09 at 16:40
There will typically be a bridging method where compareTo(Object) calls compareTo(ThisConcreteType). Presumably the latter does almost nothing. -server might help inline things. — Tom Hawtin - tackline, Mar 10 '09 at 16:44
The bridging method should be automatically generated by the compiler, as implementing Comparable only requires you to write the compareTo(T) method. — Powerlord, Mar 10 '09 at 17:12
Yes, but the bridging method still gets executed and appears in the profiler. — Tom Hawtin - tackline, Mar 10 '09 at 17:25
How you found a way to improve performance? I am having the same problem. — killy971, Aug 12 '09 at 21:43

score 4 · Answer 1 · answered Mar 10 '09 at 16:51

4

the reason you are seeing compareTo(Object) is because of Type Erasure. it just means that at runtime the type information is no longer needed for comparing the values. most likely the reason for your slowdown is 1) very, very big TreeSet with lots of elements 2) - more likely - your compareTo method does something expensive. because it is called very often (n*ln(n) times typically ), it should be implemented efficiently

answered Mar 10 '09 at 16:51

Andreas Petersson

16,248
11
59
91

I do use a large TreeSet intentionally, and that's why I tried to make it as fast as possible - it has one dereferencing and two comparisons only. – Dani Mar 10 '09 at 17:36
1

use treeSet only when neccesary. if you need your set sorted only at certain times, consiser using HashSet and sort it when you need it sorted, not all the time. – Andreas Petersson Mar 11 '09 at 10:49

erickson · Answer 2 · 2009-03-10T17:38:45.180

2

No, you can't force static invocation in this case.

An instance method can be invoked "non-virtually" by the invokespecial instruction. This instruction is used when the target is known at compile time, like a constructor or a private method. In other cases—even when the target method is final—the invokevirtual or invokeinterface instructions are used.

edited Mar 10 '09 at 17:38

answered Mar 10 '09 at 17:04

erickson

265,237
58
395
493

Point of pedantry: Or more likely in this case, invokeinterface, as Comparable is an interface. – Tom Hawtin - tackline Mar 10 '09 at 17:27

score 1 · Answer 3 · edited May 23 '17 at 11:43

1

Since java does not preserve generic types at runtime, ideally both of them should behave the same. Probably, there is something else which is causing the problem.

edited May 23 '17 at 11:43

Community

1
1

answered Mar 10 '09 at 16:42

amit

10,612
11
61
60

score 0 · Answer 4 · answered Mar 10 '09 at 17:10

I assume that the slowdown is because of virtual table lookup for this method.

You shouldn't have to guess if this is true. Just pause it a few times, and you will catch it in the act. Display the call stack in its entirety, including calls into library routines.

My guess (which could be wrong) is that it's going through nine-yards of OLE-style invocation hoo-haw.

Improving Comparable compareTo performance

4 Answers4