Crate small_range

Expand description

§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:

Type	Size	vs `Range<T>`	Max Start	Max Length
`SmallRange<u16>`	2 bytes	vs 4 bytes (50%)	254	254
`SmallRange<u32>`	4 bytes	vs 8 bytes (50%)	65,534	65,534
`SmallRange<u64>`	8 bytes	vs 16 bytes (50%)	~4.29B	~4.29B
`SmallRange<usize>`	8 bytes	vs 16 bytes (50%)	~4.29B	~4.29B

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

Method	Description
`SmallRange::new(start, end)`	Create from start and end values
`SmallRange::default()`	Empty range (0, 0)

§Accessors

Method	Returns	Description
`start()`	`T`	Start bound (inclusive)
`end()`	`T`	End bound (exclusive)
`len()`	`usize`	Number of elements
`is_empty()`	`bool`	True if start == end
`to_range()`	`Range<T>`	Convert to std Range

§Iteration

Method	Yields	Description
`for x in range`	`T`	Consuming iteration
`for x in &range`	`T`	Borrowing iteration

§Traits

Trait	Notes
`Clone`, `Copy`	Zero-cost copy
`PartialEq`, `Eq`	Bitwise comparison
`Hash`	Based on packed bits
`Default`	Empty range (0, 0)
`Debug`	Shows start and end
`IntoIterator`	For both owned and borrowed

§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

§Quick Start

use small_range::SmallRange;

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

assert_eq!(range.start(), 10u64);
assert_eq!(range.end(), 20u64);
assert_eq!(range.len(), 10);

// Convert to a standard Range
assert_eq!(range.to_range(), 10u64..20u64);

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

§Storage Type Support

SmallRange supports u16, u32, u64, and usize storage types. Each stores start and length in half the bits, achieving 50% space savings:

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

// SmallRange<u16>: 2 bytes (vs 4 bytes for Range<u16>)
let r16 = SmallRange::<u16>::new(0, 100);
assert_eq!(size_of::<SmallRange<u16>>(), 2);

// SmallRange<u32>: 4 bytes (vs 8 bytes for Range<u32>)
let r32 = SmallRange::<u32>::new(0, 1000);
assert_eq!(size_of::<SmallRange<u32>>(), 4);

// SmallRange<u64>: 8 bytes (vs 16 bytes for Range<u64>) - default
let r64 = SmallRange::<u64>::new(0, 1_000_000);
assert_eq!(size_of::<SmallRange<u64>>(), 8);

// SmallRange<usize>: convenient for indexing
let r_usize = SmallRange::<usize>::new(0, 100);

§Memory Efficiency

SmallRange uses niche optimization, so Option<SmallRange<T>> is the same size as SmallRange<T> itself.

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

assert_eq!(size_of::<SmallRange<u64>>(), size_of::<Option<SmallRange<u64>>>());
assert_eq!(size_of::<SmallRange<u32>>(), size_of::<Option<SmallRange<u32>>>());
assert_eq!(size_of::<SmallRange<u16>>(), size_of::<Option<SmallRange<u16>>>());

Structs§

SmallRange: A compact range that packs start and length into a single storage value.

Traits§

SmallRangeStorage: Trait for types that can be used as storage in a SmallRange.