<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" <[email protected]> > À: "David McManamon" <[email protected]> > Cc: "core-libs-dev" <[email protected]> > 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 <[email protected]> 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
