src/libcore/benches/ascii_case.rs

   1 // See comments in `u8::to_ascii_uppercase` in `src/libcore/num/mod.rs`.
   2 fn branchless_to_ascii_upper_case(byte: u8) -> u8 {
   3     byte &
   4     !(
   5         (
   6             byte.wrapping_add(0x1f) &
   7             !byte.wrapping_add(0x05) &
   8             0x80
   9         ) >> 2
  10     )
  11 }
  12
  13
  14 macro_rules! benches {
  15     ($( fn $name: ident($arg: ident: &mut [u8]) $body: block )+) => {
  16         benches!(mod short SHORT $($name $arg $body)+);
  17         benches!(mod medium MEDIUM $($name $arg $body)+);
  18         benches!(mod long LONG $($name $arg $body)+);
  19     };
  20
  21     (mod $mod_name: ident $input: ident $($name: ident $arg: ident $body: block)+) => {
  22         mod $mod_name {
  23             use super::*;
  24
  25             $(
  26                 #[bench]
  27                 fn $name(bencher: &mut Bencher) {
  28                     bencher.bytes = $input.len() as u64;
  29                     bencher.iter(|| {
  30                         let mut vec = $input.as_bytes().to_vec();
  31                         {
  32                             let $arg = &mut vec[..];
  33                             $body
  34                         }
  35                         vec
  36                     })
  37                 }
  38             )+
  39         }
  40     }
  41 }
  42
  43 use test::black_box;
  44 use test::Bencher;
  45
  46 benches! {
  47     fn bench00_alloc_only(_bytes: &mut [u8]) {}
  48
  49     fn bench01_black_box_read_each_byte(bytes: &mut [u8]) {
  50         for byte in bytes {
  51             black_box(*byte);
  52         }
  53     }
  54
  55     fn bench02_lookup(bytes: &mut [u8]) {
  56         for byte in bytes {
  57             *byte = ASCII_UPPERCASE_MAP[*byte as usize]
  58         }
  59     }
  60
  61     fn bench03_branch_and_subtract(bytes: &mut [u8]) {
  62         for byte in bytes {
  63             *byte = if b'a' <= *byte && *byte <= b'z' {
  64                 *byte - b'a' + b'A'
  65             } else {
  66                 *byte
  67             }
  68         }
  69     }
  70
  71     fn bench04_branch_and_mask(bytes: &mut [u8]) {
  72         for byte in bytes {
  73             *byte = if b'a' <= *byte && *byte <= b'z' {
  74                 *byte & !0x20
  75             } else {
  76                 *byte
  77             }
  78         }
  79     }
  80
  81     fn bench05_branchless(bytes: &mut [u8]) {
  82         for byte in bytes {
  83             *byte = branchless_to_ascii_upper_case(*byte)
  84         }
  85     }
  86
  87     fn bench06_libcore(bytes: &mut [u8]) {
  88         bytes.make_ascii_uppercase()
  89     }
  90
  91     fn bench07_fake_simd_u32(bytes: &mut [u8]) {
  92         let (before, aligned, after) = unsafe {
  93             bytes.align_to_mut::<u32>()
  94         };
  95         for byte in before {
  96             *byte = branchless_to_ascii_upper_case(*byte)
  97         }
  98         for word in aligned {
  99             // FIXME: this is incorrect for some byte values:
 100             // addition within a byte can carry/overflow into the next byte.
 101             // Test case: b"\xFFz  "
 102             *word &= !(
 103                 (
 104                     word.wrapping_add(0x1f1f1f1f) &
 105                     !word.wrapping_add(0x05050505) &
 106                     0x80808080
 107                 ) >> 2
 108             )
 109         }
 110         for byte in after {
 111             *byte = branchless_to_ascii_upper_case(*byte)
 112         }
 113     }
 114
 115     fn bench08_fake_simd_u64(bytes: &mut [u8]) {
 116         let (before, aligned, after) = unsafe {
 117             bytes.align_to_mut::<u64>()
 118         };
 119         for byte in before {
 120             *byte = branchless_to_ascii_upper_case(*byte)
 121         }
 122         for word in aligned {
 123             // FIXME: like above, this is incorrect for some byte values.
 124             *word &= !(
 125                 (
 126                     word.wrapping_add(0x1f1f1f1f_1f1f1f1f) &
 127                     !word.wrapping_add(0x05050505_05050505) &
 128                     0x80808080_80808080
 129                 ) >> 2
 130             )
 131         }
 132         for byte in after {
 133             *byte = branchless_to_ascii_upper_case(*byte)
 134         }
 135     }
 136 }
 137
 138 macro_rules! repeat {
 139     ($s: expr) => { concat!($s, $s, $s, $s, $s, $s, $s, $s, $s, $s) }
 140 }
 141
 142 const SHORT: &'static str = "Alice's";
 143 const MEDIUM: &'static str = "Alice's Adventures in Wonderland";
 144 const LONG: &'static str = repeat!(r#"
 145     La Guida di Bragia, a Ballad Opera for the Marionette Theatre (around 1850)
 146     Alice's Adventures in Wonderland (1865)
 147     Phantasmagoria and Other Poems (1869)
 148     Through the Looking-Glass, and What Alice Found There (includes "Jabberwocky" and "The Walrus and the Carpenter") (1871)
 149     The Hunting of the Snark (1876)
 150     Rhyme? And Reason? (1883) – shares some contents with the 1869 collection, including the long poem "Phantasmagoria"
 151     A Tangled Tale (1885)
 152     Sylvie and Bruno (1889)
 153     Sylvie and Bruno Concluded (1893)
 154     Pillow Problems (1893)
 155     What the Tortoise Said to Achilles (1895)
 156     Three Sunsets and Other Poems (1898)
 157     The Manlet (1903)[106]
 158 "#);
 159
 160 const ASCII_UPPERCASE_MAP: [u8; 256] = [
 161     0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
 162     0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
 163     0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
 164     0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
 165     b' ', b'!', b'"', b'#', b'$', b'%', b'&', b'\'',
 166     b'(', b')', b'*', b'+', b',', b'-', b'.', b'/',
 167     b'0', b'1', b'2', b'3', b'4', b'5', b'6', b'7',
 168     b'8', b'9', b':', b';', b'<', b'=', b'>', b'?',
 169     b'@', b'A', b'B', b'C', b'D', b'E', b'F', b'G',
 170     b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O',
 171     b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W',
 172     b'X', b'Y', b'Z', b'[', b'\\', b']', b'^', b'_',
 173     b'`',
 174
 175           b'A', b'B', b'C', b'D', b'E', b'F', b'G',
 176     b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O',
 177     b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W',
 178     b'X', b'Y', b'Z',
 179
 180                       b'{', b'|', b'}', b'~', 0x7f,
 181     0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
 182     0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
 183     0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
 184     0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
 185     0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
 186     0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
 187     0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
 188     0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
 189     0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
 190     0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
 191     0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
 192     0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
 193     0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
 194     0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
 195     0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
 196     0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
 197 ];
 198