Skip to content

Instantly share code, notes, and snippets.

@jimfleming
Last active August 29, 2015 14:03
Show Gist options
  • Save jimfleming/d7e8960693e393f8efcf to your computer and use it in GitHub Desktop.
Save jimfleming/d7e8960693e393f8efcf to your computer and use it in GitHub Desktop.
extern crate test;
use test::Bencher;
use std::fmt::{Show, Formatter, Result};
use std::iter::AdditiveIterator;
enum Node<T> {
Cons(T, Box<Node<T>>),
Nil
}
impl<T> Node<T> {
fn new() -> Node<T> {
Nil
}
fn prepend(self, elem: T) -> Node<T> {
Cons(elem, box self)
}
fn len(&self) -> uint {
match *self {
Cons(_, ref tail) => tail.len() + 1,
Nil => 0
}
}
}
impl<T: Show> Show for Node<T> {
fn fmt(&self, f: &mut Formatter) -> Result {
match *self {
Cons(ref head, ref tail) => {
write!(f, "{}, [ ] -> {}", head, tail)
},
Nil => {
write!(f, "Nil")
},
}
}
}
impl<T: PartialEq> PartialEq for Node<T> {
fn eq(&self, ys: &Node<T>) -> bool {
match (self, ys) {
(&Nil, &Nil) => true,
(&Cons(ref x, box ref next_xs), &Cons(ref y, box ref next_ys))
if x == y => next_xs == next_ys,
_ => false
}
}
}
// Simple hashed wheel timer with bounded interval
// See http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf
struct WheelTimer<T> {
maxInterval: uint,
currentTick: uint,
ring: Vec<Node<T>>
}
impl<T> WheelTimer<T> {
// Returns the number of items currently scheduled
fn size(&self) -> uint {
return self.ring.iter().map(|node| node.len()).sum()
}
// Creates a new timer with the specified max interval
fn new(maxInterval: uint) -> WheelTimer<T> {
// Initialize the ring with Nil values
let mut ring = Vec::with_capacity(maxInterval);
for _ in range(0u, maxInterval) {
ring.push(Nil)
}
return WheelTimer{
maxInterval: maxInterval,
currentTick: 0,
ring: ring
}
}
// Schedules a new value, available after `ticks`
fn schedule(&mut self, ticks: uint, value: T) {
// Compute the scheduled position in the wheel
let index = (self.currentTick + ticks) % self.maxInterval;
// Get the current node at `index` in the wheel
let node = std::mem::replace(self.ring.get_mut(index), Nil);
// Set the position in the wheel with the appended node
*self.ring.get_mut(index) = node.prepend(value);
}
// Tick the timer, returning the list of nodes at the spot
fn tick(&mut self) -> Node<T> {
// Get the node at the current tick in the wheel
let node = std::mem::replace(self.ring.get_mut(self.currentTick), Nil);
// Increment the timer
self.currentTick = (self.currentTick + 1) % self.maxInterval;
// Return the node that was in that spot
return node
}
}
fn main() {
// LinkedList example
// Create an empty linked list
let mut list = Node::<uint>::new();
// Append some elements
list = list.prepend(1);
list = list.prepend(2);
list = list.prepend(3);
// Show the final state of the list
println!("linked list has length: {}", list.len());
println!("{}", list);
// WheelTimer example
// Create a new timer
let mut timer = WheelTimer::<uint>::new(3);
// Schedule some things
timer.schedule(1, 1);
timer.schedule(2, 2);
timer.schedule(3, 3);
// Print the timer size
println!("size: {}", timer.size());
// Tick! Tick! Tick!
println!("{}", timer.tick());
println!("{}", timer.tick());
println!("{}", timer.tick());
}
#[test]
fn wheel_timer_new_test() {
let timer = WheelTimer::<uint>::new(3);
assert!(timer.maxInterval == 3);
assert!(timer.ring.capacity() == 3);
assert!(timer.ring.len() == 3);
}
#[test]
fn wheel_timer_schedule_test() {
let mut timer = WheelTimer::<&'static str>::new(10);
timer.schedule(3, "tick");
timer.tick();
timer.tick();
timer.tick();
let node = timer.tick();
assert!(node != Nil);
let val = match node {
Cons(val, _) => val,
Nil => ""
};
assert!(val == "tick");
}
#[test]
fn wheel_timer_tick_test() {
let mut timer = WheelTimer::<uint>::new(10);
for i in range(0, 10) {
println!("schedule: {}", i);
timer.schedule(i, i)
}
for i in range(0, 10) {
let node = timer.tick();
assert!(node != Nil);
let val = match node {
Cons(val, _) => val,
Nil => -1
};
println!("{} == {}?", val, i);
assert!(val == i);
}
}
#[bench]
fn bench_wheel_timer_drain(b: &mut Bencher) {
let maxInterval = 20;
let mut timer = WheelTimer::<uint>::new(maxInterval);
b.iter(|| {
// Fill
for j in range(0u, 100u) {
timer.schedule(j%maxInterval, j%maxInterval);
}
// Drain
for _ in range(0u, 100u) {
timer.tick();
}
});
}
#[bench]
fn bench_wheel_timer_fill(b: &mut Bencher) {
let maxInterval = 20;
let mut timer = WheelTimer::<uint>::new(maxInterval);
let mut i = 0;
b.iter(|| {
timer.schedule(i%maxInterval, i%maxInterval);
i = i + 1;
});
}
#[bench]
fn bench_wheel_timer_fast(b: &mut Bencher) {
let maxInterval = 2;
let mut timer = WheelTimer::<uint>::new(maxInterval);
let mut i = 0;
b.iter(|| {
timer.schedule(i%maxInterval, i%maxInterval);
timer.tick();
i = i + 1;
});
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment