Proposal for improving performance of TreeMap and others
cowwoc at bbs.darktech.org
Tue Jan 8 16:23:50 UTC 2008
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.
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
> You might consider re-running your experiment with inlining disabled,
> 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.
> charlie ...
> cowwoc wrote:
>> Something very weird is going on. I tried profiling a minimal testcase
>> 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
>> even though it only invokes a method while the latter does actual
>> 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.
>> Clemens Eisserer wrote:
>>> Hi cowwoc,
>>>> I guess you're right. It is probably as likely that the JIT will
>>>> 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
>>> 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
>>>> 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
>>>> 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
More information about the core-libs-dev