library/core/benches/ascii.rs

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