sorted_set_nif

I looked at that library and I found https://github.com/discord/sorted_set_nif/issues/30 which made me think it doesn't work on recent Erlang versions and is therefore not used anymore.

Yep, I think you'd be hard-pressed to find the actual Elixir code to be the bottleneck in a real-life application. But if you do encounter that, you can use something like Rustler[0] for the CPU-intensive bottleneck, as Discord did[1] while working on a data structure they needed. Slow DB queries are something else to look out for. edit: Didn't see Rustler was already mentioned in a sibling thread, but hopefully the Discord tidbit will be interesting to others. [0] https://github.com/rusterlium/rustler [1] https://github.com/discord/sorted_set_nif

Articles SortedSet[0] is basically a pseudo-BTree with fixed depth = 2 and fixed max_size of leafs. This gives O(log n) search and O(sqrt n) inserts [1]. It would mean that insertion at beginning is worst case scenario (split + need to move all buckets), but timing of insert is actually dominated by adding size of the buckets to calculate final index. Spending a little bit of time on research, finding https://en.wikipedia.org/wiki/Order_statistic_tree and just using G++ implementation would probably yield better result and less code to support. G++ has __gnu_pbds which add O(log n) "find_by_order" and "order_of_key" to trees, e.g. [2]. [0] https://github.com/discord/sorted_set_nif/blob/master/native... [1] Technically O(n/max_size + max_size) but we can assume that max_size is selected to be ~sqrt n [2] https://www.ideone.com/8mzxGR