Elixir: SortedSet and SortedMap

[0b01]

Proposal

Code.

Hi guys, I have been working on the underlying data structure for SortedSet and SortedMap.

The idea is that Elixir does not have ordered set or ordered map and this is an effort to support log time ordinal index access(nth or range(tree, a..b)) The functionalities are implemented correctly. For the past few days, I've been optimizing it. It should be plenty fast for day to day operations :email: . It is as performant :fast_forward: as rvirding/rb.

That said, as you can see from the benchmark results below, it is no match against :gb_sets or :gb_trees. The reason is these erlang libs use AA trees, which should be similar in performance (src) but I have yet to find a test case for this claim to be held.

In the beginning of this project, I have briefly considered AA tree but decided against it because they are never consistent, meaning access by ordinal indices is impossible.

At this point, should we proceed with this rbtree library and make wrapper modules SortedMap and SortedSet? Or should we optimize the performance first?

Any help with optimization would be appreciated :100:.

benchmark name             iterations   average time 

Tree: get size               10000000   0.01 µs/op
gbsets: get size             10000000   0.01 µs/op
gb_trees: get size           10000000   0.02 µs/op
rbdict: get size                10000   17.85 µs/op

rbdict: is_element           10000000   0.06 µs/op
gbtrees: is_defined          10000000   0.07 µs/op
gbsets: is_element           10000000   0.07 µs/op
Tree: is_element              1000000   0.12 µs/op

gbtrees: delete               1000000   0.28 µs/op
rbdict: delete                 100000   1.30 µs/op
Tree: delete                   100000   1.37 µs/op

gbsets: to_list                 10000   12.08 µs/op
Tree: to_list                   10000   19.17 µs/op
gbtrees: to_list                 5000   31.94 µs/op
rbdict: to_list                  5000   32.04 µs/op

gbtrees: lookup                  2000   96.47 µs/op
rbdict: lookup                   1000   115.38 µs/op
Tree: lookup                     1000   196.22 µs/op

gb_trees: new from_list          5000   58.64 µs/op
gb_sets: new from_list           5000   66.36 µs/op
rbdict: new from_list             500   482.26 µs/op
Tree: new from_list               200   954.50 µs/op

gb_trees: words from_list         500   304.65 µs/op
gb_sets: words from_list          500   559.94 µs/op
rbdict: words from_list            50   6051.94 µs/op
Tree: words from_orddict           20   8953.30 µs/op

Tree: range    10000000         0.03 µs/op
Tree: nth       1000000         0.96 µs/op

[josevalim]

Thanks for the numbers! I have replied in the mailing list, lets please continue the discussion there.

[indera]

google group discussion link: https://groups.google.com/forum/#!topic/elixir-lang-core/hjIW1FC-xBw