AVL tree implemented in the style of TreeMap for better performance

Doug Lea dl at cs.oswego.edu
Sun Oct 22 22:30:45 UTC 2017


On 10/18/2017 06:35 PM, David McManamon wrote:
> 
> https://github.com/dmcmanam/bbst-showdown
> 
> Although an old topic, it may be worth another look in Java since AVL trees
> do much better in some circumstances.

(And possibly worse in others.) As you note on the above page,
it may be the case that circumstances favoring AVLs are more common
now than back when TreeMap was first introduced.
But it will take some effort to investigate this.
A few microbenchmarks are unlikely to be helpful for a class used in
so many ways across applications.

The best strategy would be to measure across one of the
performance-based program suite corpuses.
A new one (that I don't know much about) is Xcorpus
   https://bitbucket.org/jensdietrich/xcorpus
Others include DaCapo
  http://www.dacapobench.org/

-Doug




More information about the core-libs-dev mailing list