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 and Collectable

• 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 and Collectable

Installation

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

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

Benchmarks

Below is an example of how you might format the benchmark data in Markdown for a README:

---

Benchmark Results

This document summarizes the performance benchmarks 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.

---

Map Delete Operations

Environment

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

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

Environment

(Same as above)

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

Environment

(Same as above)

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

Environment

(Same as above)

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

Environment

(Same as above)

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

Environment

(Same as above)

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

Environment

(Same as above)

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

Environment

(Same as above)

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)

---