AVL tree implemented in the style of TreeMap for better performance

Remi Forax forax at univ-mlv.fr
Mon Oct 23 06:22:03 UTC 2017

<shameless plug>

You can play with value types now !
in the valhalla repository, there is a mvt branch (for minimum value type) that add the support of value type in the VM
then you can use the valuetypifier [1] that takes a 1.8 compatible bytecode and transform every usages of the classes annotated with the annotation jdk.incubator.mvt.ValueCapableClass to make it act as a value type.

Here is an example of hastable using value types


[1] https://github.com/forax/valuetypify

----- Mail original -----
> De: "Martin Buchholz" <martinrb at google.com>
> À: "David McManamon" <dmcmanam at gmail.com>
> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>
> Envoyé: Lundi 23 Octobre 2017 02:38:14
> Objet: Re: AVL tree implemented in the style of TreeMap for better performance

> Another thing to keep in mind is that someday Java might have value types,
> which will make "inline objects" possible, which will make us reconsider
> all the data structure implementations.
> On Wed, Oct 18, 2017 at 3:35 PM, David McManamon <dmcmanam at gmail.com> wrote:
>> If the BBST performance numbers from Ben Pfaff's c language research in
>> 2004
>> https://benpfaff.org/papers/libavl.pdf
>> are correct then it seems the red-black tree implementations that are so
>> popular in the JDK might be worth another look.  However, when I surveyed
>> the AVL implementations in the Java world I didn't find the variety I was
>> looking for - specifically an implementation similar to that of the
>> red-black TreeMap (parent pointers, no recursion), so I wrote insert &
>> delete in TreeMapAVL here:
>> 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.
>> Next week I'll write a WAVL implementation and expand the performance
>> testing comparison which so far looks like this:
>> Results for inserting 262143 random integers (height 18 for a complete BST)
>> -
>>   Mean insertion time: 171ms and 169ms, runs to converge:2. AVL tree of
>> size: 262126, height: 21, rotations 183194
>>   Mean insertion time: 165ms and 169ms, runs to converge:2. Red-black tree
>> of size: 262126, height: 22, rotations 152622
>>   Mean insertion time: 170ms and 167ms, runs to converge:1. BST          of
>> size: 262126, height: 46, rotations 0
>>   Time to copy a red-black tree (sorted insertion via recursion): 44ms.
>> Red-black tree of size: 262126, height: 18, rotations 0
>> Results for inserting integer clusters in sequences of 12 and total size:
>> 262143 -
>>   Mean insertion time: 63ms and 62ms, runs to converge:3. AVL tree of size:
>> 262125, height: 21, rotations 325176
>>   Mean insertion time: 70ms and 72ms, runs to converge:2. Red-black tree of
>> size: 262125, height: 24, rotations 320990
>> --David

More information about the core-libs-dev mailing list