Erlang: The New Scalable ETS Ordered_set (opens in new tab)

(blog.erlang.org)

102 pointscodeadict5y ago9 comments

9 comments

This is really neat! I'm always excited when academics propose a new data structure or algorithm and it ends up being deployed in the field. In this case, it looks like the main idea underlying the data structure is beautiful and simple.

eternalban5y ago

http://www.it.uu.se/research/group/languages/software/ca_tre...

Looks like this data structure was out in the late 90s (author is co-author of 2017 OP):

[1]: Faster Concurrent Range Queries with Contention Adapting Search Trees Using Immutable Data, Kjell Winblad, 1998

diggan5y ago

I guess relative to other examples of academia -> deployed in field, that's relatively quick!

Using CSP (Communicating sequential processes) as an example of sometimes how long time it can take before academic ideas are actually developed: Initially CSP was described in 1978, but it wasn't until Golang (2009) and Clojure (2013) came around implementing it that the idea actually became popular.

1 more reply

muxator5y ago

Moderators: could the link to this story be upgraded to https?

My (ugly) mobile ISP does DNS hijacking on clear text connections.

The https version [0] works OK.

[0] https://blog.erlang.org/the-new-scalable-ets-ordered_set/

tracker15y ago

Semi-OT, but man are the windows version downloads for Erlang unreasonably slow... I really wish they'd just publish Windows binary releases in Github.

saurik5y ago

And with this (finally) dies one of the few remaining serious usages of an AVL tree.

dnautics5y ago

according to the diagram, past a few nodes, it appears that the ETS set still uses AVL trees.

j / k navigate · click thread line to collapse