Skip to content

Instantly share code, notes, and snippets.

@BurntPizza
Last active August 27, 2016 04:52
Show Gist options
  • Save BurntPizza/1f233ed700fb26752b05b8803cca93dd to your computer and use it in GitHub Desktop.
Save BurntPizza/1f233ed700fb26752b05b8803cca93dd to your computer and use it in GitHub Desktop.
#![feature(test)]
extern crate rand;
extern crate test;
#[macro_use]
extern crate nom;
use nom::*;
named!(parse_u32 <u32>,
map!(take_while!(is_digit), |digits| {
let mut acc = 0;
for n in digits {
acc = acc * 10 + (n - b'0') as u32;
}
acc
})
);
named!(parse_f32 <f32>,
chain!(
a: parse_u32 ~
char!('.') ~
b_: take_while!(is_digit) ,
|| {
let mut b = 0u64;
for n in b_ {
b = b * 10 + (n - b'0') as u64;
}
(a as f64 + (b as f64 / 10u64.pow(b_.len() as u32) as f64)) as f32
}
)
);
named!(row_parser <(u32, u32, f32)>,
chain!(
origin: parse_u32 ~
tag!(b" - ") ~
des: parse_u32 ~
char!(',') ~
dist: parse_f32 ,
|| { (origin, des, dist) }
)
);
fn parse_row_nom(row: &str) -> (u32, u32, f32) {
row_parser(row.as_bytes()).unwrap().1
}
fn parse_row_naive(row: &str) -> (u32, u32, f32) {
let origin_stop = row.find(" - ");
let des_stop = row.find(',');
let origin: u32 = row[..origin_stop.unwrap()].parse().expect("Failed 3");
let des: u32 = row[origin_stop.unwrap() + 3..des_stop.unwrap()].parse().expect("Failed 4");
let dist: f32 = row[des_stop.unwrap() + 1..].parse().expect("Failed 4");
(origin, des, dist)
}
fn parse_row_unrolled(row: &[u8]) -> (u32, u32, f32) {
// "2224 - 26466,79.2503490704"
let mut origin: u32 = 0;
let mut des: u32 = 0;
let mut dist: f32 = 0.0;
let mut ind = 0;
while (ind < row.len()) && ('0' as u8 <= row[ind]) && (row[ind] <= '9' as u8) {
origin *= 10;
origin += row[ind] as u32 - '0' as u32;
ind += 1;
}
ind += 3;
while (ind < row.len()) && ('0' as u8 <= row[ind]) && (row[ind] <= '9' as u8) {
des *= 10;
des += row[ind] as u32 - '0' as u32;
ind += 1;
}
ind += 1;
while (ind < row.len()) && ('0' as u8 <= row[ind]) && (row[ind] <= '9' as u8) {
dist = dist.mul_add(10.0, row[ind] as f32 - '0' as u8 as f32);
ind += 1;
}
ind += 1;
let mut pow = 1;
let mut temp: f32 = 0.0;
while (ind < row.len()) && ('0' as u8 <= row[ind]) && (row[ind] <= '9' as u8) {
temp = temp.mul_add(10.0, row[ind] as f32 - '0' as u8 as f32);
pow += 1;
ind += 1;
}
dist += (temp) * (10.0f32).powi(-pow + 1);
assert!(ind == row.len());
(origin, des, dist)
}
#[cfg(test)]
mod tests {
use {parse_row_naive, parse_row_nom, parse_row_unrolled};
use test::{black_box, Bencher};
use rand::{Rng, StdRng, SeedableRng};
const N: usize = 1000;
fn gen_data() -> Vec<String> {
let mut data = Vec::with_capacity(N);
let mut rng = StdRng::from_seed(&[23435, 13425, 134426]);
for _ in 0..N {
let src: u32 = rng.gen();
let dst: u32 = rng.gen();
let magnitude: f64 = rng.gen::<f64>() * 10.0 + 25.0;
data.push(format!("{} - {},{}", src, dst, magnitude));
}
data
}
#[test]
fn verify() {
let data = black_box(gen_data());
for line in &*data {
assert_eq!(parse_row_naive(line), parse_row_nom(line));
}
}
#[bench]
fn bench_naive(b: &mut Bencher) {
let data = black_box(gen_data());
b.iter(|| {
for line in &*data {
let row = parse_row_naive(line);
black_box(row);
}
});
}
#[bench]
fn bench_unrolled(b: &mut Bencher) {
let data = black_box(gen_data());
b.iter(|| {
for line in &*data {
let row = parse_row_unrolled(line.as_bytes());
black_box(row);
}
});
}
#[bench]
fn bench_nom(b: &mut Bencher) {
let data = black_box(gen_data());
b.iter(|| {
for line in &*data {
let row = parse_row_nom(line);
black_box(row);
}
});
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment