src/test/bench/shootout-reverse-complement.rs

   1 // The Computer Language Benchmarks Game
   2 // http://benchmarksgame.alioth.debian.org/
   3 //
   4 // contributed by the Rust Project Developers
   5
   6 // Copyright (c) 2013-2014 The Rust Project Developers
   7 //
   8 // All rights reserved.
   9 //
  10 // Redistribution and use in source and binary forms, with or without
  11 // modification, are permitted provided that the following conditions
  12 // are met:
  13 //
  14 // - Redistributions of source code must retain the above copyright
  15 //   notice, this list of conditions and the following disclaimer.
  16 //
  17 // - Redistributions in binary form must reproduce the above copyright
  18 //   notice, this list of conditions and the following disclaimer in
  19 //   the documentation and/or other materials provided with the
  20 //   distribution.
  21 //
  22 // - Neither the name of "The Computer Language Benchmarks Game" nor
  23 //   the name of "The Computer Language Shootout Benchmarks" nor the
  24 //   names of its contributors may be used to endorse or promote
  25 //   products derived from this software without specific prior
  26 //   written permission.
  27 //
  28 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  31 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  32 // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  33 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  34 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  35 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  36 // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  37 // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  38 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  39 // OF THE POSSIBILITY OF SUCH DAMAGE.
  40
  41 // ignore-android see #10393 #13206
  42
  43 #![feature(slicing_syntax, unboxed_closures)]
  44
  45 extern crate libc;
  46
  47 use std::io::stdio::{stdin_raw, stdout_raw};
  48 use std::io::{IoResult, EndOfFile};
  49 use std::num::{div_rem};
  50 use std::ptr::{copy_memory, Unique};
  51 use std::thread::Thread;
  52
  53 struct Tables {
  54     table8: [u8;1 << 8],
  55     table16: [u16;1 << 16]
  56 }
  57
  58 impl Tables {
  59     fn new() -> Tables {
  60         let mut table8 = [0;1 << 8];
  61         for (i, v) in table8.iter_mut().enumerate() {
  62             *v = Tables::computed_cpl8(i as u8);
  63         }
  64         let mut table16 = [0;1 << 16];
  65         for (i, v) in table16.iter_mut().enumerate() {
  66             *v = (table8[i & 255] as u16) << 8 |
  67                  table8[i >> 8]  as u16;
  68         }
  69         Tables { table8: table8, table16: table16 }
  70     }
  71
  72     fn computed_cpl8(c: u8) -> u8 {
  73         match c {
  74             b'A' | b'a' => b'T',
  75             b'C' | b'c' => b'G',
  76             b'G' | b'g' => b'C',
  77             b'T' | b't' => b'A',
  78             b'U' | b'u' => b'A',
  79             b'M' | b'm' => b'K',
  80             b'R' | b'r' => b'Y',
  81             b'W' | b'w' => b'W',
  82             b'S' | b's' => b'S',
  83             b'Y' | b'y' => b'R',
  84             b'K' | b'k' => b'M',
  85             b'V' | b'v' => b'B',
  86             b'H' | b'h' => b'D',
  87             b'D' | b'd' => b'H',
  88             b'B' | b'b' => b'V',
  89             b'N' | b'n' => b'N',
  90             i => i,
  91         }
  92     }
  93
  94     /// Retreives the complement for `i`.
  95     fn cpl8(&self, i: u8) -> u8 {
  96         self.table8[i as uint]
  97     }
  98
  99     /// Retreives the complement for `i`.
 100     fn cpl16(&self, i: u16) -> u16 {
 101         self.table16[i as uint]
 102     }
 103 }
 104
 105 /// Reads all remaining bytes from the stream.
 106 fn read_to_end<R: Reader>(r: &mut R) -> IoResult<Vec<u8>> {
 107     // As reading the input stream in memory is a bottleneck, we tune
 108     // Reader::read_to_end() with a fast growing policy to limit
 109     // recopies.  If MREMAP_RETAIN is implemented in the linux kernel
 110     // and jemalloc use it, this trick will become useless.
 111     const CHUNK: uint = 64 * 1024;
 112
 113     let mut vec = Vec::with_capacity(CHUNK);
 114     loop {
 115         // workaround: very fast growing
 116         let len = vec.len();
 117         if vec.capacity() - len < CHUNK {
 118             let cap = vec.capacity();
 119             let mult = if cap < 256 * 1024 * 1024 {
 120                 16
 121             } else {
 122                 2
 123             };
 124             vec.reserve_exact(mult * cap - len);
 125         }
 126         match r.push_at_least(1, CHUNK, &mut vec) {
 127             Ok(_) => {}
 128             Err(ref e) if e.kind == EndOfFile => break,
 129             Err(e) => return Err(e)
 130         }
 131     }
 132     Ok(vec)
 133 }
 134
 135 /// Finds the first position at which `b` occurs in `s`.
 136 fn memchr(h: &[u8], n: u8) -> Option<uint> {
 137     use libc::{c_void, c_int, size_t};
 138     let res = unsafe {
 139         libc::memchr(h.as_ptr() as *const c_void, n as c_int, h.len() as size_t)
 140     };
 141     if res.is_null() {
 142         None
 143     } else {
 144         Some(res as uint - h.as_ptr() as uint)
 145     }
 146 }
 147
 148 /// A mutable iterator over DNA sequences
 149 struct MutDnaSeqs<'a> { s: &'a mut [u8] }
 150 fn mut_dna_seqs<'a>(s: &'a mut [u8]) -> MutDnaSeqs<'a> {
 151     MutDnaSeqs { s: s }
 152 }
 153 impl<'a> Iterator for MutDnaSeqs<'a> {
 154     type Item = &'a mut [u8];
 155
 156     fn next(&mut self) -> Option<&'a mut [u8]> {
 157         let tmp = std::mem::replace(&mut self.s, &mut []);
 158         let tmp = match memchr(tmp, b'\n') {
 159             Some(i) => tmp.slice_from_mut(i + 1),
 160             None => return None,
 161         };
 162         let (seq, tmp) = match memchr(tmp, b'>') {
 163             Some(i) => tmp.split_at_mut(i),
 164             None => {
 165                 let len = tmp.len();
 166                 tmp.split_at_mut(len)
 167             }
 168         };
 169         self.s = tmp;
 170         Some(seq)
 171     }
 172 }
 173
 174 /// Length of a normal line without the terminating \n.
 175 const LINE_LEN: uint = 60;
 176
 177 /// Compute the reverse complement.
 178 fn reverse_complement(seq: &mut [u8], tables: &Tables) {
 179     let seq = seq.init_mut();// Drop the last newline
 180     let len = seq.len();
 181     let off = LINE_LEN - len % (LINE_LEN + 1);
 182     let mut i = LINE_LEN;
 183     while i < len {
 184         unsafe {
 185             copy_memory(seq.as_mut_ptr().offset((i - off + 1) as int),
 186                         seq.as_ptr().offset((i - off) as int), off);
 187             *seq.get_unchecked_mut(i - off) = b'\n';
 188         }
 189         i += LINE_LEN + 1;
 190     }
 191
 192     let (div, rem) = div_rem(len, 4);
 193     unsafe {
 194         let mut left = seq.as_mut_ptr() as *mut u16;
 195         // This is slow if len % 2 != 0 but still faster than bytewise operations.
 196         let mut right = seq.as_mut_ptr().offset(len as int - 2) as *mut u16;
 197         let end = left.offset(div as int);
 198         while left != end {
 199             let tmp = tables.cpl16(*left);
 200             *left = tables.cpl16(*right);
 201             *right = tmp;
 202             left = left.offset(1);
 203             right = right.offset(-1);
 204         }
 205
 206         let end = end as *mut u8;
 207         match rem {
 208             1 => *end = tables.cpl8(*end),
 209             2 => {
 210                 let tmp = tables.cpl8(*end);
 211                 *end = tables.cpl8(*end.offset(1));
 212                 *end.offset(1) = tmp;
 213             },
 214             3 => {
 215                 *end.offset(1) = tables.cpl8(*end.offset(1));
 216                 let tmp = tables.cpl8(*end);
 217                 *end = tables.cpl8(*end.offset(2));
 218                 *end.offset(2) = tmp;
 219             },
 220             _ => { },
 221         }
 222     }
 223 }
 224
 225
 226 struct Racy<T>(T);
 227
 228 unsafe impl<T: 'static> Send for Racy<T> {}
 229
 230 /// Executes a closure in parallel over the given iterator over mutable slice.
 231 /// The closure `f` is run in parallel with an element of `iter`.
 232 fn parallel<'a, I, T, F>(mut iter: I, f: F)
 233         where T: 'a+Send + Sync,
 234               I: Iterator<Item=&'a mut [T]>,
 235               F: Fn(&mut [T]) + Sync {
 236     use std::mem;
 237     use std::raw::Repr;
 238
 239     iter.map(|chunk| {
 240         // Need to convert `f` and `chunk` to something that can cross the task
 241         // boundary.
 242         let f = Racy(&f as *const F as *const uint);
 243         let raw = Racy(chunk.repr());
 244         Thread::spawn(move|| {
 245             let f = f.0 as *const F;
 246             unsafe { (*f)(mem::transmute(raw.0)) }
 247         })
 248     }).collect::<Vec<_>>();
 249 }
 250
 251 fn main() {
 252     let mut data = read_to_end(&mut stdin_raw()).unwrap();
 253     let tables = &Tables::new();
 254     parallel(mut_dna_seqs(data.as_mut_slice()), |&: seq| reverse_complement(seq, tables));
 255     stdout_raw().write(data.as_mut_slice()).unwrap();
 256 }