small_range

A compact range type: 50% smaller than Range with zero-cost Option.

Imagine you need to store Option<Range<usize>> millions of times. That's 192 bits per instance. With this library you can shrink that to just 64 bits (see tradeoffs).

Motivation

Standard Range<T> stores start and end as separate fields, requiring 2 * size_of::<T>() bytes. For applications managing millions of ranges (spatial indexing, text processing, interval trees), this overhead adds up.

SmallRange<T> packs start and length into a single value of type T:

Plus: Option<SmallRange<T>> is the same size as SmallRange<T> due to niche optimization.

use small_range::SmallRange;
use core::mem::size_of;

// 50% space savings
assert_eq!(size_of::<SmallRange<u64>>(), 8);      // vs Range<u64> = 16 bytes
assert_eq!(size_of::<SmallRange<usize>>(), 8);    // vs Range<usize> = 16 bytes

// Option adds no overhead (niche optimization)
assert_eq!(size_of::<SmallRange<u64>>(), size_of::<Option<SmallRange<u64>>>());

Use Cases

Half the memory footprint means better cache locality. Ideal for:

• HFT / Low-latency systems: Order book ranges, tick intervals, buffer slices
• Game engines: Entity ID ranges, spatial partitions, collision bounds
• Compilers & IDEs: Source spans, token ranges, AST extents
• Databases: Index ranges, row bounds, interval trees

API Overview

use small_range::SmallRange;

// Create a range (defaults to u64 storage)
let range = SmallRange::new(10u64, 20u64);

// Access bounds
assert_eq!(range.start(), 10u64);
assert_eq!(range.end(), 20u64);   // exclusive, like std Range
assert_eq!(range.len(), 10);
assert!(!range.is_empty());

// Iterate
for i in &range {
    println!("{}", i);
}

// Convert to standard Range
let std_range: core::ops::Range<u64> = range.to_range();

Storage Types

use small_range::SmallRange;
use core::mem::size_of;

// SmallRange<u16>: 2 bytes, values 0-254
let r16 = SmallRange::<u16>::new(0, 100);
assert_eq!(size_of::<SmallRange<u16>>(), 2);

// SmallRange<u32>: 4 bytes, values 0-65,534
let r32 = SmallRange::<u32>::new(0, 1000);
assert_eq!(size_of::<SmallRange<u32>>(), 4);

// SmallRange<u64>: 8 bytes, values 0-4,294,967,294 (default)
let r64 = SmallRange::<u64>::new(0, 1_000_000);
assert_eq!(size_of::<SmallRange<u64>>(), 8);

// SmallRange<usize>: convenient for slice indexing
let r_usize = SmallRange::<usize>::new(0, 100);
let data = vec![0; 200];
let slice = &data[r_usize.start()..r_usize.end()];

Limitations

Value Constraints

Start and length must each fit in half the storage width minus 1:

• SmallRange<u16>: max start = 254, max length = 254
• SmallRange<u32>: max start = 65,534, max length = 65,534
• SmallRange<u64>: max start = 4,294,967,294, max length = 4,294,967,294

use small_range::SmallRange;

// This will panic in debug mode (start exceeds capacity)
let invalid = SmallRange::<u16>::new(255, 256);

No RangeBounds Implementation

SmallRange does not implement RangeBounds<T> because the trait requires returning references (Bound<&T>), but our values are computed from packed bits -- there's no stored T to reference.

Workaround: Use .to_range() which returns Range<T>, and Range<T> implements RangeBounds<T>:

use small_range::SmallRange;
use core::ops::RangeBounds;

let small = SmallRange::new(10u64, 20u64);

// to_range() gives full RangeBounds support
let range = small.to_range();
assert!(range.contains(&15));
assert!(!range.contains(&25));

Sealed Trait

The SmallRangeStorage trait is sealed -- only u16, u32, u64, and usize are supported.

Implementation Details

Encoding Scheme

Values are packed as (start+1, length+1) where start is in the high bits and length is in the low bits:

SmallRange<u32> in 4 bytes:
+----------------+----------------+
|   start + 1    |  length + 1    |  -> NonZero<u32>
|   (16 bits)    |   (16 bits)    |
+----------------+----------------+

SmallRange<u64> in 8 bytes:
+--------------------------------+--------------------------------+
|           start + 1            |          length + 1            |  -> NonZero<u64>
|           (32 bits)            |           (32 bits)            |
+--------------------------------+--------------------------------+

By adding 1 to both start and length:

• Both halves are always >= 1, so the packed value is never zero
• Zero is reserved for Option::None (niche optimization)
• len() is a simple mask + subtract operation

Performance

All operations are #[inline] and compile to minimal assembly:

• new(): Subtract, two adds, shift, OR
• start(): Shift, mask, subtract
• end(): Shift, mask, subtract, add
• len(): Mask, subtract

No heap allocation, no branches, no function calls.

See full benchmark results comparing Option<SmallRange> vs Option<Range> with 100 million entries:

• 2.4x faster sequential scans (better cache utilization)
• 2.3x faster creation
• 3x less memory (800 MB vs 2.4 GB)

Memory Layout

use small_range::SmallRange;
use core::mem::{size_of, align_of};

// Transparent wrapper around NonZero<T>
assert_eq!(size_of::<SmallRange<u64>>(), 8);
assert_eq!(align_of::<SmallRange<u64>>(), 8);

// Niche optimization works
assert_eq!(size_of::<Option<SmallRange<u64>>>(), 8);

Quick Reference

Construction

Accessors

Iteration

Traits

When to Use SmallRange

Good fit:

• Storing many ranges where memory matters (50% savings)
• Need Option<Range> with zero discriminant overhead
• Indices that fit in half the storage width (e.g., u32 indices in u64 storage)
• no_std environments (only depends on num-traits)

Poor fit:

• Need RangeBounds trait directly (use .to_range() as workaround)
• Values exceed half-width capacity
• Single ranges where memory isn't a concern (just use Range<T>)

License

MIT