OrderedCollections

For detailed usage see our docs

OrderedCollections is a library for Elixir that provides efficient, sorted data structures:

SortedMap and SortedSet wrap Erlang's :gb_trees and :gb_sets for easy use in Elixir.

Features

SortedMap
- Insert, update, and delete key-value pairs while preserving sorted order.
- Fast lookups using :gb_trees
- Range queries over keys.
- Conversion to standard Elixir Map or list.
- Implements Enum, Collectable, Inspect and the new JSON protocol introduced in Elixir 1.18
SortedSet
- Maintain a set of unique elements in sorted order.
- Fast membership checks using :gb_sets
- Union, intersection, and difference operations.
- Range queries over elements.
- Conversion to a standard Elixir MapSet or list.
- Implements Enum, Collectable, Inspect and the new JSON protocol introduced in Elixir 1.18

Installation

Add ordered_collections to your list of dependencies in mix.exs:

def deps do
  [
    {:ordered_collections, "~> 0.3.2"}
  ]
end

Benchmarks

Running Benchmarks

To run the benchmarks for OrderedCollections, follow these steps:

Ensure your dependencies are up-to-date by running: mix deps.get
Compile the project: mix compile
Execute the benchmark suite: mix run bench/sorted_collections_bench.exs

This command will automatically locate and run all benchmark files under the "bench/sorted_collections/" directory. You can also run individual benchmark files if desired, for example: mix run bench/sorted_collections/<set|map>/bench.exs or mix run bench/sorted_collections/<set|map>/<delete|insert|lookup|range>/bench.exs

Benchmarks are configured using Benchee. Feel free to modify the benchmark settings in the respective files as needed.

Pre-executed Benchmarks

Below are the benchmark results for various map and set operations. Each section details the environment, benchmark configuration, results, and comparisons.

Note: All benchmarks were executed on macOS using an Apple M3 CPU with 8 cores, 16 GB of memory, Elixir 1.18.3, Erlang 27.2.4, and JIT enabled.

Environment

Operating System: macOS
CPU: Apple M3 (8 cores)
Memory: 16 GB
Elixir: 1.18.3
Erlang: 27.2.4
JIT Enabled: true

Map Delete Operations

Benchmark Configuration

Warmup: 2 s
Time: 5 s
Memory Time: 0 ns
Reduction Time: 0 ns
Parallel: 1
Inputs: none specified
Estimated Run Time: 21 s

Results

Test	ips	Average	Deviation	Median	99th %
Delete - gb_trees	1084.28	0.92 ms	±6.34%	0.91 ms	1.10 ms
Delete - SortedMap (Core)	989.02	1.01 ms	±5.58%	1.00 ms	1.23 ms
Delete - SortedMap (Convenience)	986.13	1.01 ms	±4.84%	1.00 ms	1.23 ms

Comparison

Delete - gb_trees: 1084.28 ips
Delete - SortedMap (Core): 989.02 ips (1.10× slower, +0.0888 ms)
Delete - SortedMap (Convenience): 986.13 ips (1.10× slower, +0.0918 ms)

Map Insert Operations

Benchmark Configuration

Warmup: 2 s
Time: 5 s
Memory Time: 0 ns
Reduction Time: 0 ns
Parallel: 1
Inputs: none specified
Estimated Run Time: 21 s

Results

Test	ips	Average	Deviation	Median	99th %
Insert - gb_trees	329.53	3.03 ms	±38.68%	2.94 ms	4.05 ms
Insert - SortedMap (Convenience)	334.44	3.99 ms	±16.76%	3.01 ms	3.75 ms
Insert - SortedMap (Core)	329.17	3.04 ms	±23.13%	3.07 ms	3.91 ms

Comparison

Insert - SortedMap (Convenience): 334.44
Insert - gb_trees: 329.53 - 1.01x slower +0.0445 ms
Insert - SortedMap (Core): 329.17 - 1.02x slower +0.0479 ms

Map Lookup Operations

Benchmark Configuration

Warmup: 2 s
Time: 5 s
Memory Time: 0 ns
Reduction Time: 0 ns
Parallel: 1
Inputs: none specified
Estimated Run Time: 21 s

Results

Test	ips	Average	Deviation	Median	99th %
gb_trees Lookup	2.69K	371.12 μs	±6.40%	367.88 μs	449.14 μs
SortedMap Lookup (Core)	2.28K	437.72 μs	±13.92%	434.04 μs	517.95 μs
SortedMap Lookup (Convenience)	2.11K	474.03 μs	±5.68%	473.25 μs	562.01 μs

Comparison

gb_trees Lookup: 2.69K ips
SortedMap Lookup (Core): 2.28K ips (1.18× slower, +66.60 μs)
SortedMap Lookup (Convenience): 2.11K ips (1.28× slower, +102.91 μs)

Map Range Operations

Benchmark Configuration

Warmup: 2 s
Time: 5 s
Memory Time: 0 ns
Reduction Time: 0 ns
Parallel: 1
Inputs: none specified
Estimated Run Time: 28 s

Results

Test	ips	Average	Deviation	Median	99th %
SortedMap Range (Convenience)	8.89K	112.49 μs	±6.17%	111.58 μs	127.67 μs
SortedMap Range (Core)	8.79K	113.80 μs	±7.02%	112.92 μs	132.33 μs
gb_trees Range	8.42K	118.71 μs	±6.46%	117.83 μs	135.66 μs
Elixir Range	5.43K	184.15 μs	±101.67%	176.79 μs	272.26 μs

Comparison

SortedMap Range (Convenience): 8.89K ips
SortedMap Range (Core): 8.79K ips (1.01× slower, +1.30 μs)
gb_trees Range: 8.42K ips (1.06× slower, +6.22 μs)
Elixir Range: 5.43K ips (1.64× slower, +71.66 μs)

Set Delete Operations

Benchmark Configuration

Warmup: 2 s
Time: 5 s
Memory Time: 0 ns
Reduction Time: 0 ns
Parallel: 1
Inputs: none specified
Estimated Run Time: 21 s

Results

Test	ips	Average	Deviation	Median	99th %
Delete - SortedSet (Core)	686.83	1.46 ms	±4.46%	1.46 ms	1.67 ms
Delete - SortedSet (Convenience)	675.48	1.48 ms	±9.15%	1.47 ms	1.76 ms
Delete - :gb_sets	631.20	1.58 ms	±33.92%	1.47 ms	2.35 ms

Comparison

Delete - SortedSet (Core): 686.83 ips
Delete - SortedSet (Convenience): 675.48 ips (1.02× slower, +0.0245 ms)
Delete - :gb_sets: 631.20 ips (1.09× slower, +0.128 ms)

Set Insert Operations

Benchmark Configuration

Warmup: 2 s
Time: 5 s
Memory Time: 0 ns
Reduction Time: 0 ns
Parallel: 1
Inputs: none specified
Estimated Run Time: 21 s

Results

Test	ips	Average	Deviation	Median	99th %
Insert - :gb_sets	554.73	1.80 ms	±8.50%	1.79 ms	2.26 ms
Insert - SortedSet (Convenience)	383.41	2.61 ms	±6.95%	2.60 ms	3.19 ms
Insert - SortedSet (Core)	381.61	2.62 ms	±6.84%	2.62 ms	3.15 ms

Comparison

Insert - :gb_sets: 554.73 ips
Insert - SortedSet (Convenience): 383.41 ips (1.45× slower, +0.81 ms)
Insert - SortedSet (Core): 381.61 ips (1.45× slower, +0.82 ms)

Set Lookup Operations

Benchmark Configuration

Warmup: 2 s
Time: 5 s
Memory Time: 0 ns
Reduction Time: 0 ns
Parallel: 1
Inputs: none specified
Estimated Run Time: 21 s

Results

Test	ips	Average	Deviation	Median	99th %
:gb_sets Lookup	1.68K	595.51 μs	±15.03%	586.25 μs	716.88 μs
SortedSet Lookup (Core)	1.63K	615.22 μs	±9.16%	605.98 μs	768.99 μs
SortedSet Lookup (Convenience)	1.60K	626.72 μs	±4.67%	627.91 μs	738.40 μs

Comparison

:gb_sets Lookup: 1.68K ips
SortedSet Lookup (Core): 1.63K ips (1.03× slower, +19.70 μs)
SortedSet Lookup (Convenience): 1.60K ips (1.05× slower, +31.21 μs)

Set Range Operations

Benchmark Configuration

Warmup: 2 s
Time: 5 s
Memory Time: 0 ns
Reduction Time: 0 ns
Parallel: 1
Inputs: none specified
Estimated Run Time: 14 s

Results

Test	ips	Average	Deviation	Median	99th %
SortedSet Range (Convenience)	3.28K	305.11 μs	±36.98%	259.12 μs	651.30 μs
SortedSet Range (Core)	2.27K	441.03 μs	±11.94%	430.75 μs	759.20 μs

Comparison

SortedSet Range (Convenience): 3.28K ips
SortedSet Range (Core): 2.27K ips (1.45× slower, +135.92 μs)

Name		Name	Last commit message	Last commit date
.vscode		.vscode
bench		bench
lib		lib
test		test
.cursorrules		.cursorrules
.editorconfig		.editorconfig
.formatter.exs		.formatter.exs
.gitignore		.gitignore
LICENSE		LICENSE
README.md		README.md
mix.exs		mix.exs
mix.lock		mix.lock

Latest commit

History

Folders and files

Repository files navigation

OrderedCollections

Features

Installation

Benchmarks

Running Benchmarks

Pre-executed Benchmarks

Environment

Map Delete Operations

Benchmark Configuration

Results

Comparison

Map Insert Operations

Benchmark Configuration

Results

Comparison

Map Lookup Operations

Benchmark Configuration

Results

Comparison

Map Range Operations

Benchmark Configuration

Results

Comparison

Set Delete Operations

Benchmark Configuration

Results

Comparison

Set Insert Operations

Benchmark Configuration

Results

Comparison

Set Lookup Operations

Benchmark Configuration

Results

Comparison

Set Range Operations

Benchmark Configuration

Results

Comparison

About

Resources

Stars

Watchers

Forks

Releases

Packages

Contributors

Languages