Erlang: The New Scalable ETS Ordered_set

gautamcgoel 5 years ago |

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.

eternalban 5 years 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

diggan 5 years 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.

macintux 5 years ago | | |

Clojure's first release was 2007, or are you referring to a feature released in 2013?

diggan 5 years ago | | |

Yeah, referring to the initial release of core.async (Clojure implementation of CSP) which seems to have been in late 2013 (https://github.com/clojure/core.async). Clojure usually ships new features as libraries rather than changing the core language, so both a feature and a library I guess.

muxator 5 years 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/

tracker1 5 years 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.

saurik 5 years ago |

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

dnautics 5 years ago | |

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