sorted_set_nif: an ordered set for Elixir with a Rust core

A set that remembers where everything sits

Discord.SortedSet is described as a fast and efficient data structure that provides certain guarantees and functionality, and the README states two guarantees plainly. Terms in the set are sorted according to the Elixir sorting rules, and the set is a set, so any item appears zero or one times.

Those two together are ordinary. What makes this structure different is stated a few paragraphs later as special functionality beyond sortedness and uniqueness: the set has a defined ordering, unlike a pure mathematical set, and because of that ordering it can report the index at which an item was added or removed, and it can provide random access of items and slices.

Reporting the index of an insertion is the capability that is hard to get elsewhere. A Map gives you membership and deletion, but not the position of a key in an order. Here the position is a fact the structure knows, because the structure is ordered and the position is derived from it.

The library lives in the Discord namespace, and the README says why: to prevent symbol collision. It is used with the full module name or through an alias, and the library is published on Hex as sorted_set_nif, with the API documentation hosted on hexdocs.

A vector of vectors, searched like a skip list

The implementation detail section explains the whole design. Internally the Elixir terms stored in the set are converted to Rust equivalents and stored in a Vector of Vectors, and the structure is described as similar to a skip list. Almost every operation performs a linear scan through the buckets to find the bucket that owns the term, and then a binary search within that bucket completes the operation.

So an operation is a scan plus a binary search, and the scan is over buckets rather than over elements. That is what keeps the cost tied to the number of buckets rather than the number of terms, provided the buckets are sized sensibly.

The design question was why not just a Vector of Terms. The README says that was explored, and that when the vector needed to grow beyond its capacity, copying terms over to the new larger vector proved to be a performance bottleneck. Using a vector of vectors, the bucket pointers can be copied quickly when more capacity is required. The strategy is described as a reasonable trade-off between performance and implementation complexity, which is a fair description of the choice.

Bucket size is tunable by the caller, with a default of 500 chosen because it performs well for most use cases, and new/2 takes the tuning details. A workload with many small collections would want smaller buckets, and one with a few large collections would want the opposite, so the default is a starting point rather than a constant.

Adding a dependency and generating the docs

Installation is the standard Mix flow. The dependency is added to the deps list and then fetched and compiled:

def deps do
  [
    {:sorted_set_nif, "~> 1.0.0"}
  ]
end

The README says to add SortedSet to your dependencies and then install with mix do deps.get, deps.compile, and the version requirement is a ~> 1.0.0 match, so the library is expected to be used within the 1.x line.

Documentation is hosted on hexdocs, and a local copy can be generated from the source because the mix.exs file is already set up for it:

$ mix deps.get
$ mix docs

There are two test suites, and the README explains what each one covers. The ExUnit suite tests the correctness of the implementation from a black box point of view, and runs with mix test in the root of the library. The Rust code carries its own tests, which run with cargo test in the native/sorted_set_nif directory. Both halves of the library are therefore testable on their own, which is the arrangement you want in a project where the boundary between Elixir and Rust is where the bugs live.

The caveats are about types and about cost

The README lists two caveats, and the first is the one that catches people out.

SortedSets do not support some Elixir term types, specifically reference, pid, port, function and float. Attempting to store any of those, or an allowed composite type containing one of them, results in the error {:error,:unsupported_type}. The reason follows from the implementation: these terms are converted to Rust equivalents, and the structure does not accept them. A float is the surprising one, since a float is perfectly comparable in Erlang, so an application that puts floats in a set and meets the error at runtime will be caught out.

The second caveat is about performance rather than types. Because of the implementation, some operations that are constant time in a set have different performance characteristics here, and the README says these are noted on the operations themselves. That points to the API documentation as the place to look before assuming an operation is cheap, and it is the main reason to read the docs before choosing this structure.

Using it, and the namespace convention

The basic usage example builds a set through the pipe, and the module is referenced with its full name:

defmodule ExampleModule do
  def get_example_sorted_set() do
    Discord.SortedSet.new()
    |> Discord.SortedSet.add(1)
    |> Discord.SortedSet.add(:atom),
    |> Discord.SortedSet.add("hi there!")
  end
end

The README then points out that you can always add an alias to make the code less verbose, and shows the same function written against an aliased Discord.SortedSet. That is ordinary Elixir practice, and the reason the README bothers is that the namespace itself is a design decision worth copying: the library sits under Discord so that it does not collide with other modules, and using the full path in a small codebase is a reasonable trade for clarity.

The README also notes that the full API documentation is available, and that there is a full test suite with examples of how the library can be used, which is the practical answer to the question of what else the structure can do.

Where a Rust-backed sorted set is the wrong tool

The first wrong-tool case is ordinary set membership. If all you need is to know whether a key is present and to delete it, the standard Elixir Map does it in constant time, and this structure turns both into a bucket scan plus a binary search. The README's own caveat about operations that are constant time in sets covers this, and it is the reason to check the per-operation notes before swapping a Map out for a SortedSet on the assumption of a win.

The second is a set that has to hold the awkward types. A process identifier, a reference, a port, a function or a float is exactly what many Elixir systems use as identifiers, and all five are rejected here. If your data model leans on pids or references, this library is not a candidate regardless of how well the ordering suits you.

The third is a team that does not want a native dependency. A NIF means Rust in the build chain, a compiled artefact per platform, and the operational question of how that artefact gets built and shipped in your release pipeline. The library is developed on Travis according to the .travis.yml file at the root, and a project that releases precompiled binaries or targets platforms its CI does not cover will need to solve that problem for itself.

MIT, no releases, and a benchmark that needs a special flag

The library is MIT licensed, with the LICENSE file at the repository root, and it is published on Hex as sorted_set_nif with a version badge. The repository is not archived, and the last push was on 2026-05-13. There are no GitHub releases, so the Hex package version and the commit history are the version record.

The benchmark instructions contain the detail worth knowing. The README warns that during development the NIF is built unoptimized, and that an optimized version has to be rebuilt before running benchmarks. The benchmarks live in the bench folder, are written with Benchee, and run with:

$ OPTIMIZE_NIF=true mix run bench/{benchmark}.exs

The environment variable is what forces the run against the fully optimized NIF. Skipping it gives you numbers for a debug build, which is the kind of mistake that makes a fast library look slow and a slow one look unusable.

The repository layout is conventional for a mixed Elixir and Rust project: lib/ for the Elixir side, native/sorted_set_nif for the Rust source, bench/ for the Benchee scripts, test/ for the ExUnit suite, plus config/, mix.exs and mix.lock, a .formatter.exs and a .travis.yml.

Editorial conclusion

Adopt sorted_set_nif when your Elixir code needs a set with a stable order, and you need the index an element was inserted at, the index it was removed from, random access by position, or slices of a set, and you can work within the type restrictions that exclude references, pids, ports, functions and floats. Do not adopt it as a drop-in replacement for a plain Elixir Map or for the standard MapSet, because membership and insertion are no longer constant time and unsupported term types return {:error,:unsupported_type}. Before you commit, read the notes on the individual operations, since the README states that the performance characteristics differ from set semantics, and run the benchmarks with OPTIMIZE_NIF=true, because a development build is unoptimized and will mislead you.

Frequently asked questions

Official sources

1. discord/sorted_set_nif on GitHub
2. Issues
3. License: MIT
4. README