AVL tree implemented in the style of TreeMap for better performance

[Remi Forax]

<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
  https://github.com/forax/valuetypify/blob/master/src/test/java/fr/umlv/valuetypify/test/Hash.java

Rémi  

[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