Thank you @Asd! Map is generally faster at mutations and lookups - potentially much faster as collection size grows. Trees are useful when it’s a requirement to have the data sorted at all times with scalable performance.

Regarding benchmarks, I did use Benchee for a long time but struggled to get stable performance curves covering a wide range of collection sizes (0 to 15k) for the same test (the graphs on the report), or getting consistent results across runs without very long warm up times (and even then).

I solved this with a custom benchmarking framework that maximizes CPU cache pressure while keeping testing conditions overall uniform for all the cases, and that runs repeatedly until some semblance of stability has been achieved instead of running for a fixed amount of time. To be honest, a lot of the work in this project went into benchmarking alone.

IMG_5670750×1334 46.3 KB

Wow, very good library. I did some benchmarks against maps and found that xb5 is slower than maps for put, but slightly faster for get and many times faster for conversion to ordered list

However, I find separate repo for benchmarks a little overengineered, given that I was able to reproduce your results with Benchee in like 10 minutes or so.

I think that you should add GitHub - discord/sorted_set_nif: Elixir SortedSet backed by a Rust-based NIF · GitHub to your benchmarks. I assume that NIF will be just a little bit faster, which is a huge win for you

Again, congratulations on the initial release. Very solid work. I am definitely going to use it in my projects!