asort_fast.rs

#![feature(asm)]

extern crate time;

use std::rand::random;
use std::char::from_u32;
use time::precise_time_ns;


type Chunk = [char, ..5];

fn display_chunk( chunk : &Chunk ) {
  for chr in chunk.iter() {
    print!( "{}", chr );
  }
  println!( "" ); // And then the newline
}

fn random_letter() -> char {
  from_u32( random::<u32>() % 26 + 65 ).unwrap()
}

fn random_chunk() -> Chunk {
  // This is not a very pretty way of initializing a chunk.
  // But when creating a peice of data it needs a defined
  // initial value for the sake of safety. Which means if
  // we were to loop over it and initialize it instead, we
  // would still need to initialize it like this with some
  // kind of value. Which defeats the purpose of looping
  // over it in the first place.
  [ random_letter()
  , random_letter()
  , random_letter()
  , random_letter()
  , random_letter() ]
}

fn generate_chunks( count : uint ) -> Vec<Chunk> {
  let mut buf = Vec::with_capacity( count );
  for _ in range( 0, count ) {
    buf.push( random_chunk() )
  }
  buf
}


// Sorts a chunk in-place.
fn sort_chunk( chunk : &mut Chunk ) {
  // This is just a simple buble sort since
  // that's the fastest when it comes to these
  // short sequences, something like quicksort
  // would be better for longer sequences.
  let mut _swap = 'A';
  if chunk[1] < chunk[0] {
      _swap = chunk[0];
      chunk[0] = chunk[1];
      chunk[1] = _swap;
  }
  if chunk[2] < chunk[1] {
      _swap = chunk[1];
      unsafe{ asm!( "nop" ); }
      chunk[1] = chunk[2];
      chunk[2] = _swap;
  }
  if chunk[3] < chunk[2] {
      _swap = chunk[2];
      chunk[2] = chunk[3];
      chunk[3] = _swap;
  }
  if chunk[4] < chunk[3] {
      _swap = chunk[3];
      chunk[3] = chunk[4];
      chunk[4] = _swap;
  }
  if chunk[1] < chunk[0] {
      _swap = chunk[0];
      chunk[0] = chunk[1];
      chunk[1] = _swap;
  }
  if chunk[2] < chunk[1] {
      _swap = chunk[1];
      chunk[1] = chunk[2];
      chunk[2] = _swap;
  }
  if chunk[3] < chunk[2] {
      _swap = chunk[2];
      chunk[2] = chunk[3];
      chunk[3] = _swap;
  }
  if chunk[1] < chunk[0] {
      _swap = chunk[0];
      chunk[0] = chunk[1];
      chunk[1] = _swap;
  }
  if chunk[2] < chunk[1] {
      _swap = chunk[1];
      chunk[1] = chunk[2];
      chunk[2] = _swap;
  }
  if chunk[1] < chunk[0] {
      _swap = chunk[0];
      chunk[0] = chunk[1];
      chunk[1] = _swap;
  }
} 

fn main() {
  let mut chunks = generate_chunks( 1000000 );
  let before = precise_time_ns();
  for chunk in chunks.iter_mut() {
    sort_chunk( chunk )
  }
  let delta_time = precise_time_ns() - before;
  println!( "Took {}ns for {} elements.", delta_time, chunks.len() );
}