mywheel-rs

API Design Rationale

This document explains the design decisions behind the data structures in mywheel-rs, providing context for understanding when and why to use each implementation.

Table of Contents

Design Philosophy

The mywheel-rs project follows specific design principles:

Educational Focus

Non-Ownership Model

API Design Principles

Dllist Design

Core Concepts

The doubly linked list implementation is designed around non-owning nodes and sentinel-based design.

Non-Ownership Benefits

// Nodes can be shared between multiple data structures
let mut shared_node = Dllink::new("shared_data");
list1.append(&mut shared_node);
list2.append(&mut shared_node); // Same node in two lists

This approach enables:

Sentinel Node Design

pub struct Dllist<T> {
    pub head: Dllink<T>, // Sentinel node with specific data
}

impl<T> Dllist<T> {
    pub fn clear(&mut self) {
        self.head.clear(); // Creates self-referential loop
    }
}

Benefits:

Unsafe Usage Rationale

Raw pointers are used strategically:

// Safe: self.head.next points to valid node (self or other list nodes)
unsafe {
    (*self.head.prev).next = new_node; // Known valid pointer
}

Safety guarantees:

BPQueue Design

Bounded Priority Queue Concept

BPQueue implements a bucket-based priority queue optimized for small integer ranges.

Range-Based Optimization

let mut bpq = BPQueue::<i32>::new(-5, 5); // Range: -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5

Design advantages:

Sentinel Bucket Management

// Extra bucket at index 0 always empty for boundary management
let mut bpq = BPQueue::<i32>::new(-6, 6); // One extra bucket
bpq.bucket[0].append(&mut sentinel); // Boundary checking elimination

Benefits:

FM Algorithm Integration

BPQueue is specifically designed for Fiduccia-Mattheyses partitioning algorithms:

// Nodes maintain (gain, data) tuples for FM operations
bpq.modify_key(&mut node, new_gain); // O(log k) priority update

Design alignment:

Array Structures Design

RepeatArray: Zero-Allocation Abstraction

pub struct RepeatArray<T: Copy> {
    value: T,
    size: usize,
}

impl<T: Copy> Index<usize> for RepeatArray<T> {
    fn index(&self, _index: usize) -> &Self::Output {
        &self.value // Always returns same reference
    }
}

Memory efficiency:

ShiftArray: Offset-Based Indexing

pub struct ShiftArray<T> {
    start: usize,
    lst: Vec<T>,
}

impl<T> Index<usize> for ShiftArray<T> {
    fn index(&self, key: usize) -> &Self::Output {
        &self.lst[key - self.start] // O(1) translation
    }
}

Use cases:

MapAdapter Design

Vector-Like API Compatibility

impl<T> Index<usize> for MapAdapter<T> {
    fn index(&self, key: usize) -> &Self::Output {
        &self.lst[key] // Direct Vec access
    }
}

Design advantages:

Sparse Data Optimization

pub fn contains(&self, key: usize) -> bool {
    key < self.lst.len() // O(1) check
}

Memory patterns:

Robin Design

Round-Robin Scheduling Algorithm

pub struct Robin {
    cycle: Vec<u8>, // Pre-computed cycle
}

impl<'a> Iterator for Robin<'a> {
    fn next(&mut self) -> Option<Self::Item> {
        // O(1) iteration with state machine
    }
}

Design characteristics:

Limitations and Extensions

Current limitations:

Potential extensions:

Performance Considerations

Cache Optimization Strategies

L1 Cache Considerations

Cache-Avoiding Patterns

// Avoid: Pointer chasing in linked lists
for node in list.iter() {
    // Cache-inefficient: random memory access pattern
}

// Prefer: Array-based iteration
for i in 0..array.len() {
    // Cache-friendly: sequential memory access
    process(array[i]);
}

Memory Access Patterns

Optimal Patterns

  1. Sequential access - Best for cache prefetching
  2. Strided access - Regular stride patterns (matrix operations)
  3. Blocked access - Process contiguous chunks
  4. Access locality - Group related operations spatially

Suboptimal Patterns

  1. Pointer chasing - Linked list random access
  2. Random access - Poor cache hit rates
  3. False sharing - Multiple threads writing same cache lines

Algorithmic Complexity Trade-offs

Time vs Space Complexity

| Operation | Custom Implementation | Standard Library | When to Prefer Custom | |————|——————-|—————–|——————-|———————–| | Access | O(1) | O(1) | Custom when cache-critical | | Insert | O(1) | O(log n) | Custom for bounded ranges | | Search | O(k) | O(log n) | Custom for specialized structures | | Delete | O(1) | O(1) | Custom when non-owning needed |

Memory Usage Patterns

| Structure | Memory Per Element | Total Memory | Use Cases | |———–|——————|————|———–|—————| | Vec | 24 + sizeof(T) | 24n + n*sizeof(T) | General purpose | | Dllist | 24 (sentinel) + 1n | 24 + 24n | Shared nodes | | BPQueue | 24 + k + n | 24 + k*n | Bounded keys | | RepeatArray | 24 + sizeof(T) | 24 + sizeof(T) | Constant data | | ShiftArray | 24 + sizeof(T) | 24 + n*sizeof(T) | Offset addressing |

Trade-offs and Decisions

Binary Heap vs BPQueue

std::collections::BinaryHeap advantages:

BPQueue advantages:

Raw Pointers vs Safe Abstractions

Raw pointers (Dllist):

Safe abstractions (Vec):

Evolution Strategy

The mywheel-rs project demonstrates a progressive enhancement approach:

  1. Foundation - Basic, safe implementations of fundamental algorithms
  2. Performance layering - Add specialized, optimized versions alongside general ones
  3. Educational layering - Rich examples and documentation for each design choice
  4. Integration patterns - Demonstrate how different structures work together

This design philosophy ensures that each data structure serves both educational purposes and practical performance needs, with clear documentation of when each approach is optimal.

This site is open source. Improve this page.