An interesting implementation for sorted structures (map, sets, etc)

[Attila-Mihaly Balazs]

Grant Jenks - Python Sorted Collections - PyCon 2016: https://youtu.be/7z2Ki44Vs4E?t=16m18s

(yes, it's python but could be adopted to Java and I wager it would have a better performance than the RBTree / AVLTree / etc implemetnations since it uses contiguous memory locations - AKA arrays :-))

Cheers,
Attila

[Vincent Sonnier]

There was a time when I searched B+tree-like structures in literature to implement in HPPC-RT. Finally I didn't have time to do it, but I would have done it in a fixed-height B-tree structure. 

This idea is not especially new, for instance is described in the paper Modularizing B+Trees: ThreeLevel B+Trees Work Fine.

Indeed Python Sorted Collections implements the concept with a 2-level B+tree if I understand correctly, together with smart indexing methods. If I had time, I would port it in Java to HPPC-RT, but my interests have shifted elsewhere. Maybe a job for an internship :)

Regards,

Vincent

[Sebastiano Vigna]

Hey, would it be complicated for you to run your tests against the version currently in the repository?

Ciao,

seba

[Vincent Sonnier]

Hello Sebastiano,

Do you mean running my HPPC-RT benchmark suite with the fastutil master? 

It only tests certain maps combinations between different  libraries, though.

Regards,

Vincent