Arithmetic Nonmax

The arithmetic-nonmax crate provides NonMax* types for integer types that are guaranteed to never be their maximum value (MAX). Using these types enables Rust's "niche optimization," where Option<NonMax*> has the same size as the underlying integer type.

Additionally, arithmetic operations can be written intuitively. For example, in shortest path algorithms, using the Option<NonMax*> type allows you to leverage the type system while optimizing the memory layout. See Benchmarks for more details.

use arithmetic_nonmax::{NonMax, NonMaxU32, non_max};

let a: NonMaxU32 = NonMaxU32::new(5).unwrap();

let b = non_max!(10); // Conveniently create values with the non_max! macro
let c = b - a; // Arithmetic operations between NonMax types
assert_eq!(a, c);

let d = a * 5; // Arithmetic operations with primitive integers
assert!(a < d);
assert_eq!(d.to_string(), "25"); // Can be converted to string

let array = [non_max!(1), non_max!(4), non_max!(5)];
let e = array[non_max!(2)]; // Support indexing
let f = array.iter().sum::<NonMax<_>>();
assert_eq!(f / 2, e);

Benchmarks

The following values are measured using iai and divan. NonMax achieves the same memory savings as the sentinel method (the fastest) while enabling more efficient operations and reduced instruction counts compared to the standard Option.

Instruction-based Benchmarks (benches/iai_comparison.rs)

We measured the number of instructions for operations on each type using iai. Here, we extract results for i32 (default integer type) and usize (indexing type), which are commonly used (other integer types show similar trends).

i32 (Default integer type)

usize (Index type)

Note: Values are measured with iai (x86_64 environment). Comparisons (cmp) measure the cost of infinity-aware comparisons (curr.is_none() || Some(next) < curr vs next < curr). For a full report, see bench_result_iai.txt.

Execution Time and Memory Usage Benchmarks (benches/comparison.rs)

We measured performance in practical algorithms and large-scale data operations using divan. Reducing the memory size by half (8 bytes → 4 bytes) improves cache efficiency, delivering faster execution speeds than the standard Option for large data.

Algorithms

Large-scale Data Operations (N=1,000,000)

Note: Values are measured with divan (x86_64 environment, median). For a full report, see bench_result.txt.

Bundling for Competitive Programming

When submitting to online judges, you can bundle the library into a single file using the following command:

(echo "pub mod arithmetic_nonmax {"; sed -e 's/#!\[no_std\]//' -e '/#\[cfg(test)\]/,$d' -e 's/\$crate/crate::arithmetic_nonmax/g' -e 's|//.*||' -e '/^[[:space:]]*$/d' src/lib.rs; echo "}") > bundled.rs

Examples

You can find programs that solve Aizu Online Judge problems using this library in the examples/ directory. Note that you need to bundle the library into a single file when submitting to an online judge.

• GRL_1_A: Single Source Shortest Path: Uses Option<NonMax<u32>> for distances, representing unreachable nodes as None.
• GRL_1_C: All Pairs Shortest Path: Uses Option<NonMax<i32>> for distances, representing unreachable nodes as None.
• DSL_1_A: Disjoint Set: Manages parent indices in a Union-Find data structure using Option<NonMaxUsize>.
• DPL_1_A: Coin Changing Problem: Solves the coin change problem using DP with Option<NonMax<u32>>.

Similar Libraries

• nonmax
• nonany

License

CC0 1.0 Universal