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