Proposal for improving performance of TreeMap and others

[cowwoc]

	That's good news, I guess ;) because in my minimal testcase that had 
nothing to do with TreeMap it looked like using a Comparator to wrap 
natural ordering degraded performance by an order of magnitude... which 
is really bad :)

	If the same isn't true for the actual TreeMap this change might be 
worth considering for its code-cleanup potential.

Gili

charlie hunt wrote:
> 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
>>>
>>>
>>>     
>>
>>