src/libcore/benches/ascii.rs

   1 // Lower-case ASCII 'a' is the first byte that has its highest bit set
   2 // after wrap-adding 0x1F:
   3 //
   4 //     b'a' + 0x1F == 0x80 == 0b1000_0000
   5 //     b'z' + 0x1F == 0x98 == 0b1001_1000
   6 //
   7 // Lower-case ASCII 'z' is the last byte that has its highest bit unset
   8 // after wrap-adding 0x05:
   9 //
  10 //     b'a' + 0x05 == 0x66 == 0b0110_0110
  11 //     b'z' + 0x05 == 0x7F == 0b0111_1111
  12 //
  13 // … except for 0xFB to 0xFF, but those are in the range of bytes
  14 // that have the highest bit unset again after adding 0x1F.
  15 //
  16 // So `(byte + 0x1f) & !(byte + 5)` has its highest bit set
  17 // iff `byte` is a lower-case ASCII letter.
  18 //
  19 // Lower-case ASCII letters all have the 0x20 bit set.
  20 // (Two positions right of 0x80, the highest bit.)
  21 // Unsetting that bit produces the same letter, in upper-case.
  22 //
  23 // Therefore:
  24 fn branchless_to_ascii_upper_case(byte: u8) -> u8 {
  25     byte & !((byte.wrapping_add(0x1f) & !byte.wrapping_add(0x05) & 0x80) >> 2)
  26 }
  27
  28 macro_rules! benches {
  29     ($( fn $name: ident($arg: ident: &mut [u8]) $body: block )+ @iter $( $is_: ident, )+) => {
  30         benches! {@
  31             $( fn $name($arg: &mut [u8]) $body )+
  32             $( fn $is_(bytes: &mut [u8]) { bytes.iter().all(u8::$is_) } )+
  33         }
  34     };
  35
  36     (@$( fn $name: ident($arg: ident: &mut [u8]) $body: block )+) => {
  37         benches!(mod short SHORT $($name $arg $body)+);
  38         benches!(mod medium MEDIUM $($name $arg $body)+);
  39         benches!(mod long LONG $($name $arg $body)+);
  40     };
  41
  42     (mod $mod_name: ident $input: ident $($name: ident $arg: ident $body: block)+) => {
  43         mod $mod_name {
  44             use super::*;
  45
  46             $(
  47                 #[bench]
  48                 fn $name(bencher: &mut Bencher) {
  49                     bencher.bytes = $input.len() as u64;
  50                     bencher.iter(|| {
  51                         let mut vec = $input.as_bytes().to_vec();
  52                         {
  53                             let $arg = &mut vec[..];
  54                             black_box($body);
  55                         }
  56                         vec
  57                     })
  58                 }
  59             )+
  60         }
  61     }
  62 }
  63
  64 use test::black_box;
  65 use test::Bencher;
  66
  67 benches! {
  68     fn case00_alloc_only(_bytes: &mut [u8]) {}
  69
  70     fn case01_black_box_read_each_byte(bytes: &mut [u8]) {
  71         for byte in bytes {
  72             black_box(*byte);
  73         }
  74     }
  75
  76     fn case02_lookup_table(bytes: &mut [u8]) {
  77         for byte in bytes {
  78             *byte = ASCII_UPPERCASE_MAP[*byte as usize]
  79         }
  80     }
  81
  82     fn case03_branch_and_subtract(bytes: &mut [u8]) {
  83         for byte in bytes {
  84             *byte = if b'a' <= *byte && *byte <= b'z' {
  85                 *byte - b'a' + b'A'
  86             } else {
  87                 *byte
  88             }
  89         }
  90     }
  91
  92     fn case04_branch_and_mask(bytes: &mut [u8]) {
  93         for byte in bytes {
  94             *byte = if b'a' <= *byte && *byte <= b'z' {
  95                 *byte & !0x20
  96             } else {
  97                 *byte
  98             }
  99         }
 100     }
 101
 102     fn case05_branchless(bytes: &mut [u8]) {
 103         for byte in bytes {
 104             *byte = branchless_to_ascii_upper_case(*byte)
 105         }
 106     }
 107
 108     fn case06_libcore(bytes: &mut [u8]) {
 109         bytes.make_ascii_uppercase()
 110     }
 111
 112     fn case07_fake_simd_u32(bytes: &mut [u8]) {
 113         // SAFETY: transmuting a sequence of `u8` to `u32` is always fine
 114         let (before, aligned, after) = unsafe {
 115             bytes.align_to_mut::<u32>()
 116         };
 117         for byte in before {
 118             *byte = branchless_to_ascii_upper_case(*byte)
 119         }
 120         for word in aligned {
 121             // FIXME: this is incorrect for some byte values:
 122             // addition within a byte can carry/overflow into the next byte.
 123             // Test case: b"\xFFz  "
 124             *word &= !(
 125                 (
 126                     word.wrapping_add(0x1f1f1f1f) &
 127                     !word.wrapping_add(0x05050505) &
 128                     0x80808080
 129                 ) >> 2
 130             )
 131         }
 132         for byte in after {
 133             *byte = branchless_to_ascii_upper_case(*byte)
 134         }
 135     }
 136
 137     fn case08_fake_simd_u64(bytes: &mut [u8]) {
 138         // SAFETY: transmuting a sequence of `u8` to `u64` is always fine
 139         let (before, aligned, after) = unsafe {
 140             bytes.align_to_mut::<u64>()
 141         };
 142         for byte in before {
 143             *byte = branchless_to_ascii_upper_case(*byte)
 144         }
 145         for word in aligned {
 146             // FIXME: like above, this is incorrect for some byte values.
 147             *word &= !(
 148                 (
 149                     word.wrapping_add(0x1f1f1f1f_1f1f1f1f) &
 150                     !word.wrapping_add(0x05050505_05050505) &
 151                     0x80808080_80808080
 152                 ) >> 2
 153             )
 154         }
 155         for byte in after {
 156             *byte = branchless_to_ascii_upper_case(*byte)
 157         }
 158     }
 159
 160     fn case09_mask_mult_bool_branchy_lookup_table(bytes: &mut [u8]) {
 161         fn is_ascii_lowercase(b: u8) -> bool {
 162             if b >= 0x80 { return false }
 163             match ASCII_CHARACTER_CLASS[b as usize] {
 164                 L | Lx => true,
 165                 _ => false,
 166             }
 167         }
 168         for byte in bytes {
 169             *byte &= !(0x20 * (is_ascii_lowercase(*byte) as u8))
 170         }
 171     }
 172
 173     fn case10_mask_mult_bool_lookup_table(bytes: &mut [u8]) {
 174         fn is_ascii_lowercase(b: u8) -> bool {
 175             match ASCII_CHARACTER_CLASS[b as usize] {
 176                 L | Lx => true,
 177                 _ => false
 178             }
 179         }
 180         for byte in bytes {
 181             *byte &= !(0x20 * (is_ascii_lowercase(*byte) as u8))
 182         }
 183     }
 184
 185     fn case11_mask_mult_bool_match_range(bytes: &mut [u8]) {
 186         fn is_ascii_lowercase(b: u8) -> bool {
 187             match b {
 188                 b'a'..=b'z' => true,
 189                 _ => false
 190             }
 191         }
 192         for byte in bytes {
 193             *byte &= !(0x20 * (is_ascii_lowercase(*byte) as u8))
 194         }
 195     }
 196
 197     fn case12_mask_shifted_bool_match_range(bytes: &mut [u8]) {
 198         fn is_ascii_lowercase(b: u8) -> bool {
 199             match b {
 200                 b'a'..=b'z' => true,
 201                 _ => false
 202             }
 203         }
 204         for byte in bytes {
 205             *byte &= !((is_ascii_lowercase(*byte) as u8) << 5)
 206         }
 207     }
 208
 209     fn case13_subtract_shifted_bool_match_range(bytes: &mut [u8]) {
 210         fn is_ascii_lowercase(b: u8) -> bool {
 211             match b {
 212                 b'a'..=b'z' => true,
 213                 _ => false
 214             }
 215         }
 216         for byte in bytes {
 217             *byte -= (is_ascii_lowercase(*byte) as u8) << 5
 218         }
 219     }
 220
 221     fn case14_subtract_multiplied_bool_match_range(bytes: &mut [u8]) {
 222         fn is_ascii_lowercase(b: u8) -> bool {
 223             match b {
 224                 b'a'..=b'z' => true,
 225                 _ => false
 226             }
 227         }
 228         for byte in bytes {
 229             *byte -= (b'a' - b'A') * is_ascii_lowercase(*byte) as u8
 230         }
 231     }
 232
 233     @iter
 234
 235     is_ascii,
 236     is_ascii_alphabetic,
 237     is_ascii_uppercase,
 238     is_ascii_lowercase,
 239     is_ascii_alphanumeric,
 240     is_ascii_digit,
 241     is_ascii_hexdigit,
 242     is_ascii_punctuation,
 243     is_ascii_graphic,
 244     is_ascii_whitespace,
 245     is_ascii_control,
 246 }
 247
 248 macro_rules! repeat {
 249     ($s: expr) => {
 250         concat!($s, $s, $s, $s, $s, $s, $s, $s, $s, $s)
 251     };
 252 }
 253
 254 const SHORT: &'static str = "Alice's";
 255 const MEDIUM: &'static str = "Alice's Adventures in Wonderland";
 256 const LONG: &'static str = repeat!(
 257     r#"
 258     La Guida di Bragia, a Ballad Opera for the Marionette Theatre (around 1850)
 259     Alice's Adventures in Wonderland (1865)
 260     Phantasmagoria and Other Poems (1869)
 261     Through the Looking-Glass, and What Alice Found There
 262         (includes "Jabberwocky" and "The Walrus and the Carpenter") (1871)
 263     The Hunting of the Snark (1876)
 264     Rhyme? And Reason? (1883) – shares some contents with the 1869 collection,
 265         including the long poem "Phantasmagoria"
 266     A Tangled Tale (1885)
 267     Sylvie and Bruno (1889)
 268     Sylvie and Bruno Concluded (1893)
 269     Pillow Problems (1893)
 270     What the Tortoise Said to Achilles (1895)
 271     Three Sunsets and Other Poems (1898)
 272     The Manlet (1903)[106]
 273 "#
 274 );
 275
 276 #[rustfmt::skip]
 277 const ASCII_UPPERCASE_MAP: [u8; 256] = [
 278     0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
 279     0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
 280     0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
 281     0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
 282     b' ', b'!', b'"', b'#', b'$', b'%', b'&', b'\'',
 283     b'(', b')', b'*', b'+', b',', b'-', b'.', b'/',
 284     b'0', b'1', b'2', b'3', b'4', b'5', b'6', b'7',
 285     b'8', b'9', b':', b';', b'<', b'=', b'>', b'?',
 286     b'@', b'A', b'B', b'C', b'D', b'E', b'F', b'G',
 287     b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O',
 288     b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W',
 289     b'X', b'Y', b'Z', b'[', b'\\', b']', b'^', b'_',
 290     b'`',
 291
 292           b'A', b'B', b'C', b'D', b'E', b'F', b'G',
 293     b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O',
 294     b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W',
 295     b'X', b'Y', b'Z',
 296
 297                       b'{', b'|', b'}', b'~', 0x7f,
 298     0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
 299     0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
 300     0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
 301     0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
 302     0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
 303     0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
 304     0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
 305     0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
 306     0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
 307     0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
 308     0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
 309     0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
 310     0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
 311     0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
 312     0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
 313     0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
 314 ];
 315
 316 enum AsciiCharacterClass {
 317     C,  // control
 318     Cw, // control whitespace
 319     W,  // whitespace
 320     D,  // digit
 321     L,  // lowercase
 322     Lx, // lowercase hex digit
 323     U,  // uppercase
 324     Ux, // uppercase hex digit
 325     P,  // punctuation
 326     N,  // Non-ASCII
 327 }
 328 use self::AsciiCharacterClass::*;
 329
 330 #[rustfmt::skip]
 331 static ASCII_CHARACTER_CLASS: [AsciiCharacterClass; 256] = [
 332 //  _0 _1 _2 _3 _4 _5 _6 _7 _8 _9 _a _b _c _d _e _f
 333     C, C, C, C, C, C, C, C, C, Cw,Cw,C, Cw,Cw,C, C, // 0_
 334     C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, // 1_
 335     W, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, // 2_
 336     D, D, D, D, D, D, D, D, D, D, P, P, P, P, P, P, // 3_
 337     P, Ux,Ux,Ux,Ux,Ux,Ux,U, U, U, U, U, U, U, U, U, // 4_
 338     U, U, U, U, U, U, U, U, U, U, U, P, P, P, P, P, // 5_
 339     P, Lx,Lx,Lx,Lx,Lx,Lx,L, L, L, L, L, L, L, L, L, // 6_
 340     L, L, L, L, L, L, L, L, L, L, L, P, P, P, P, C, // 7_
 341     N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
 342     N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
 343     N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
 344     N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
 345     N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
 346     N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
 347     N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
 348     N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,
 349 ];