Proposal for improving performance of TreeMap and others

[charlie hunt]

It's likely what you are observing in #2 & #3 and possibly in #1 also is 
an artifact of inlining and possibly other JIT (dynamic) compiler 
optimizations.

You might consider re-running your experiment with inlining disabled, 
-XX:-Inlining.

Or, alternatively try running your experiment (with inlining enabled) 
with Sun Studio Collector / Analyzer.  Then, when viewing the results in 
the Analyzer, filter (View > Filter Data), the samples so that you are 
looking at a portion of samples after the code is warmed up.  And, also 
look at the results in machine view mode (View > Set Data Presentation > 
Formats > View Mode > Machine).   NOTE: In machine mode you can also 
view the generated assembly code for each method.  So, you can really 
get down to the specifics of what's being executed.

Fwiw, I did a comparison run of a TreeMap with your suggested changes 
including removing "if (comparator == null)" checks with one of our 
favorite SPEC benchmarks which does a pretty good job at exercising 
TreeMap.compare().  Even with 18 degrees of freedom I found the changes 
to have no significant improvement. I didn't look at, or compare the 
generated assembly code for both versions TreeMap.compare().  Though 
that might be kind of interesting.

So, from a performance perspective, it appears this SPEC benchmark shows 
no change in performance.

hths,

charlie ...

cowwoc wrote:
> Something very weird is going on. I tried profiling a minimal testcase and
> there is a considerable amount of "missing time". I am using a dev build of
> Netbeans 6.1 and it says:
>
> MyComparator.compare(Object, Object) 19670ms
> \-> MyComparator.compare(Integer, Integer) 10229ms
>   \-> Self Time 3001ms
>   \-> Integer.compareTo(Integer) 1575ms
> \-> Self Time 3788ms
>
> I spot at least three problems:
>
> 1) The individual item times do not add up to the total (but they do for
> other stack-traces).
> 2) Comparator.compare() self-time consumes more CPU than Integer.compareTo()
> even though it only invokes a method while the latter does actual
> computation.
> 3) Why is extra time consumed moving from MyComparator.compare(Object,
> Object) to (Integer, Integer)? It looks like Generics is doing something at
> runtime which consumes a large amount of cpu.
>
> Gili
>
>
> Clemens Eisserer wrote:
>   
>> Hi cowwoc,
>>
>>     
>>> I guess you're right. It is probably as likely that the JIT will optimize
>>> away the null check as it is that it will optimize away the
>>> NullPointerException check. One exception, though, is when production
>>> systems run using -Xverify:none. In such a case, wouldn't my approach run
>>> faster?
>>>       
>> I don't think it will optimize the null-check away, however it is so
>> cheap that it most likely will not weight at all, compared to all the
>> other operations happening there. Its maybe 5 instructions compared to
>> thousands or even more.
>> -Xverify:none only disables bytecode verification at class-loading
>> time and has no influence (as far as I know) on the performance of the
>> generated code.
>>
>>     
>>> I still think that my proposed code is somehow more consistent/cleaner on
>>> a
>>> design-level but I guess that's just me :)
>>>       
>> I also like it more, its cleaner in my opinion :)
>>
>>     
>>> As an aside, are there standard benchmarks for testing the impact of this
>>> change? I'd love to know whether it actually produces any performance
>>> difference in practice.
>>>       
>> >From my experience i would rather guess that you won't notice the
>> change, noise will be higher.
>>
>> lg Clemens
>>
>>
>>     
>
>