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:

1. Ensure your dependencies are up-to-date by running: mix deps.get

2. Compile the project: mix compile

3. 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

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

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

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

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

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

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

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

Comparison

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