Micro-benchmark of three implementation strategies for https://github.com/mozilla/rust/pull/8231 i7-3520M CPU @ 2.90GHz A lookup table is pretty much always faster.

ascii_case_bench.rs

extern mod extra;

pub use std::{str, ptr};
pub use std::str::{from_char, OwnedStr};
pub use extra::test::BenchHarness;


macro_rules! benchmarks(() => { mod benchmarks {
    use super::*;

    #[bench]
    fn bench_to_upper__lower(bh: &mut BenchHarness) {
        let string = "supercalifragilisticexpialidocious".repeat(100);
        do bh.iter {
            to_ascii_upper(string);
        }
    }

    #[bench]
    fn bench_to_upper__upper(bh: &mut BenchHarness) {
        let string = "SUPERCALIFRAGILISTICEXPIALIDOCIOUS".repeat(100);
        do bh.iter {
            to_ascii_upper(string);
        }
    }

    #[bench]
    fn bench_to_upper__title(bh: &mut BenchHarness) {
        let string = "Supercalifragilisticexpialidocious".repeat(100);
        do bh.iter {
            to_ascii_upper(string);
        }
    }

    #[bench]
    fn bench_to_upper__mixed(bh: &mut BenchHarness) {
        let string = "supercaLIfragIlistiCEXpIAlIdociOUs".repeat(100);
        do bh.iter {
            to_ascii_upper(string);
        }
    }


    #[bench]
    fn bench_to_lower__lower(bh: &mut BenchHarness) {
        let string = "supercalifragilisticexpialidocious".repeat(100);
        do bh.iter {
            to_ascii_lower(string);
        }
    }

    #[bench]
    fn bench_to_lower__upper(bh: &mut BenchHarness) {
        let string = "SUPERCALIFRAGILISTICEXPIALIDOCIOUS".repeat(100);
        do bh.iter {
            to_ascii_lower(string);
        }
    }

    #[bench]
    fn bench_to_lower__title(bh: &mut BenchHarness) {
        let string = "Supercalifragilisticexpialidocious".repeat(100);
        do bh.iter {
            to_ascii_lower(string);
        }
    }

    #[bench]
    fn bench_to_lower__mixed(bh: &mut BenchHarness) {
        let string = "supercaLIfragIlistiCEXpIAlIdociOUs".repeat(100);
        do bh.iter {
            to_ascii_lower(string);
        }
    }


    #[bench]
    fn bench_eq_lower__lower(bh: &mut BenchHarness) {
        let string = "supercalifragilisticexpialidocious".repeat(100);
        let reference = "supercalifragilisticexpialidocious".repeat(100);
        do bh.iter {
            eq_ascii_lower(string, reference);
        }
    }

    #[bench]
    fn bench_eq_lower__upper(bh: &mut BenchHarness) {
        let string = "SUPERCALIFRAGILISTICEXPIALIDOCIOUS".repeat(100);
        let reference = "supercalifragilisticexpialidocious".repeat(100);
        do bh.iter {
            eq_ascii_lower(string, reference);
        }
    }

    #[bench]
    fn bench_eq_lower__title(bh: &mut BenchHarness) {
        let string = "Supercalifragilisticexpialidocious".repeat(100);
        let reference = "supercalifragilisticexpialidocious".repeat(100);
        do bh.iter {
            eq_ascii_lower(string, reference);
        }
    }

    #[bench]
    fn bench_eq_lower__mixed(bh: &mut BenchHarness) {
        let string = "supercaLIfragIlistiCEXpIAlIdociOUs".repeat(100);
        let reference = "supercalifragilisticexpialidocious".repeat(100);
        do bh.iter {
            eq_ascii_lower(string, reference);
        }
    }
}};)

macro_rules! tests(() => { mod tests {
    use super::*;

    #[test]
    fn test_to_ascii_upper() {
        assert_eq!(to_ascii_upper("url()URL()uRl()ürl"), ~"URL()URL()URL()üRL");
        assert_eq!(to_ascii_upper("hıKß"), ~"HıKß");

        let mut i = 0;
        while i <= 500 {
            let c = i as char;
            let upper = if 'a' <= c && c <= 'z' { c + 'A' - 'a' } else { c };
            assert_eq!(to_ascii_upper(from_char(i as char)), from_char(upper))
            i += 1;
        }
    }

    #[test]
    fn test_to_ascii_lower() {
        assert_eq!(to_ascii_lower("url()URL()uRl()Ürl"), ~"url()url()url()Ürl");
        // Dotted capital I, Kelvin sign, Sharp S.
        assert_eq!(to_ascii_lower("HİKß"), ~"hİKß");

        let mut i = 0;
        while i <= 500 {
            let c = i as char;
            let lower = if 'A' <= c && c <= 'Z' { c + 'a' - 'A' } else { c };
            assert_eq!(to_ascii_lower(from_char(i as char)), from_char(lower))
            i += 1;
        }
    }


    #[test]
    fn test_eq_ascii_lower() {
        assert!(eq_ascii_lower("url()URL()uRl()Ürl", "url()url()url()Ürl"));
        // Dotted capital I, Kelvin sign, Sharp S.
        assert!(eq_ascii_lower("HİKß", "hİKß"));

        let mut i = 0;
        while i <= 500 {
            let c = i as char;
            let lower = if 'A' <= c && c <= 'Z' { c + 'a' - 'A' } else { c };
            assert!(eq_ascii_lower(from_char(i as char), from_char(lower)));
            i += 1;
        }
    }
}};)


macro_rules! map_bytes(
    ($string: expr, $new_c: expr) => {{
        let len = string.len();
        let mut result = str::with_capacity(len);
        unsafe {
            do result.as_mut_buf |mut buf, _| {
                foreach c in string.as_bytes().iter() {
                    let c = *c;
                    *buf = $new_c;
                    buf = ptr::mut_offset(buf, 1)
                }
            }
            str::raw::set_len(&mut result, len);
        }
        result
    }};
)


macro_rules! all_bytes(
    ($string: expr, $reference: expr, $test: expr) => {
        string.len() == reference.len()
        && do string.as_bytes().iter().zip(reference.as_bytes().iter()).all
              |(s_byte, r_byte)| { let s_byte = *s_byte; let r_byte = *r_byte; $test }
    };
)


mod c_comp {
    pub use super::*;

    tests!()
    benchmarks!()

    #[inline]
    pub fn to_ascii_upper(string: &str) -> ~str {
        map_bytes!(string, {
            if c >= 97 && c <= 122 { c & !0x20 } else { c }
        })
    }

    #[inline]
    pub fn to_ascii_lower(string: &str) -> ~str {
        map_bytes!(string, {
            if c >= 65 && c <= 90 { c | 0x20 } else { c }
        })
    }

    #[inline]
    pub fn eq_ascii_lower(string: &str, reference: &str) -> bool {
        all_bytes!(string, reference, {
            r_byte == if s_byte >= 65 && s_byte <= 90 { s_byte | 0x20 }
                      else { s_byte }
        })
    }
}


mod b_match {
    pub use super::*;

    tests!()
    benchmarks!()

    #[inline]
    pub fn to_ascii_upper(string: &str) -> ~str {
        map_bytes!(string, {
            match c {
                97 .. 122 => c & !0x20,
                _ => c
            }
        })
    }

    #[inline]
    pub fn to_ascii_lower(string: &str) -> ~str {
        map_bytes!(string, {
            match c {
                65 .. 90 => c | 0x20,
                _ => c
            }
        })
    }

    #[inline]
    pub fn eq_ascii_lower(string: &str, reference: &str) -> bool {
        all_bytes!(string, reference, {
            r_byte == match s_byte {
                65 .. 90 => s_byte | 0x20,
                _ => s_byte
            }
        })
    }
}


mod a_lookup {
    pub use super::*;

    tests!()
    benchmarks!()

    /// Convert the string to ASCII upper case:
    /// ASCII letters 'a' to 'z' are mapped to 'A' to 'Z',
    /// but non-ASCII letters are unchanged.
    #[inline]
    pub fn to_ascii_upper(string: &str) -> ~str {
        map_bytes!(string, ASCII_UPPER_MAP[c])
    }

    /// Convert the string to ASCII lower case:
    /// ASCII letters 'A' to 'Z' are mapped to 'a' to 'z',
    /// but non-ASCII letters are unchanged.
    #[inline]
    pub fn to_ascii_lower(string: &str) -> ~str {
        map_bytes!(string, ASCII_LOWER_MAP[c])
    }

    /// Check that `string` is an ASCII case-insensitive mach for `reference`,
    /// which is assumed to be in ASCII lower-case.
    /// Same as `to_ascii_lower(string) == reference`,
    /// but without allocating a new string.
    #[inline]
    pub fn eq_ascii_lower(string: &str, reference: &str) -> bool {
        // TODO: do this in debug/testing mode only?
        // assert!(string.as_bytes().iter().all(|b| ASCII_LOWER_MAP[*b] == *b))
        all_bytes!(string, reference, {
            ASCII_LOWER_MAP[s_byte] == r_byte
        })
    }

    static ASCII_LOWER_MAP: &'static [u8] = &[
        0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
        0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
        0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
        0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
        0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
        0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
        0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
        0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
        0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
        0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
        0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
        0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
        0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
        0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
        0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
        0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
        0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
        0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
        0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
        0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
        0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
        0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
        0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
        0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
        0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
        0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
        0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
        0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
        0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
        0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
        0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
        0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
    ];

    static ASCII_UPPER_MAP: &'static [u8] = &[
        0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
        0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
        0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
        0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
        0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
        0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
        0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
        0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
        0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47,
        0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f,
        0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
        0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
        0x60, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47,
        0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f,
        0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
        0x58, 0x59, 0x5a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
        0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
        0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
        0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
        0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
        0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
        0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
        0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
        0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
        0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
        0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
        0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
        0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
        0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
        0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
        0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
        0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
    ];
}

format.py

from __future__ import print_function, division
import re
import sys

impls = []
tests = []
results = []

for line in sys.stdin:
    match = re.match(
        'test (\w+)::benchmarks::bench_(\w+) ... bench: (\d+) ns/iter', line)
    if match:
        impl, test, result = match.groups()
        impls.append(impl)
        tests.append(test.replace('__', ' '))
        results.append(int(result))

N_impls = 3
assert len(results) % N_impls == 0
N = int(len(results) / N_impls)

for i in range(1, N):
    assert impls[i::N] == impls[::N]

for i in range(1, N_impls):
    assert tests[i*N:(i+1)*N] == tests[:N]

codes = []
for impl in impls[::N]:
    code, _, impl = impl.partition('_')
    print(code, ':', impl)
    codes.append(code)

print('', '', *codes + ['%s/%s' % (c, codes[0]) for c in codes[1:]], sep='\t')
for i in range(N):
    result = results[i::N]
    relative = ['%.2f' % (r / result[0]) for r in result[1:]]
    print(tests[i], *result + relative, sep='\t')

Output

# Output of 'ascii_case_bench --test --bench',
# Built with 'rustc ascii_case_bench.rs -O'
# rustc 0.8-pre (fc57182 2013-08-02 09:13:53 -0700)

running 45 tests
test a_lookup::tests::test_eq_ascii_lower ... ok
test a_lookup::tests::test_to_ascii_lower ... ok
test c_comparisons::tests::test_eq_ascii_lower ... ok
test b_match::tests::test_eq_ascii_lower ... ok
test b_match::tests::test_to_ascii_lower ... ok
test c_comparisons::tests::test_to_ascii_upper ... ok
test c_comparisons::tests::test_to_ascii_lower ... ok
test a_lookup::tests::test_to_ascii_upper ... ok
test b_match::tests::test_to_ascii_upper ... ok
test a_lookup::benchmarks::bench_eq_lower__lower ... bench: 4769 ns/iter (+/- 293)
test a_lookup::benchmarks::bench_eq_lower__mixed ... bench: 4769 ns/iter (+/- 58)
test a_lookup::benchmarks::bench_eq_lower__title ... bench: 4772 ns/iter (+/- 98)
test a_lookup::benchmarks::bench_eq_lower__upper ... bench: 4770 ns/iter (+/- 74)
test a_lookup::benchmarks::bench_to_lower__lower ... bench: 2345 ns/iter (+/- 40)
test a_lookup::benchmarks::bench_to_lower__mixed ... bench: 2355 ns/iter (+/- 1548)
test a_lookup::benchmarks::bench_to_lower__title ... bench: 2353 ns/iter (+/- 43)
test a_lookup::benchmarks::bench_to_lower__upper ... bench: 2355 ns/iter (+/- 84)
test a_lookup::benchmarks::bench_to_upper__lower ... bench: 2338 ns/iter (+/- 33)
test a_lookup::benchmarks::bench_to_upper__mixed ... bench: 2349 ns/iter (+/- 215)
test a_lookup::benchmarks::bench_to_upper__title ... bench: 2351 ns/iter (+/- 155)
test a_lookup::benchmarks::bench_to_upper__upper ... bench: 2356 ns/iter (+/- 245)
test b_match::benchmarks::bench_eq_lower__lower ... bench: 5721 ns/iter (+/- 334)
test b_match::benchmarks::bench_eq_lower__mixed ... bench: 5729 ns/iter (+/- 428)
test b_match::benchmarks::bench_eq_lower__title ... bench: 6279 ns/iter (+/- 394)
test b_match::benchmarks::bench_eq_lower__upper ... bench: 5722 ns/iter (+/- 297)
test b_match::benchmarks::bench_to_lower__lower ... bench: 3353 ns/iter (+/- 138)
test b_match::benchmarks::bench_to_lower__mixed ... bench: 4356 ns/iter (+/- 247)
test b_match::benchmarks::bench_to_lower__title ... bench: 4857 ns/iter (+/- 264)
test b_match::benchmarks::bench_to_lower__upper ... bench: 3606 ns/iter (+/- 93)
test b_match::benchmarks::bench_to_upper__lower ... bench: 3609 ns/iter (+/- 252)
test b_match::benchmarks::bench_to_upper__mixed ... bench: 3474 ns/iter (+/- 212)
test b_match::benchmarks::bench_to_upper__title ... bench: 4212 ns/iter (+/- 105)
test b_match::benchmarks::bench_to_upper__upper ... bench: 3312 ns/iter (+/- 195)
test c_comparisons::benchmarks::bench_eq_lower__lower ... bench: 6685 ns/iter (+/- 1053)
test c_comparisons::benchmarks::bench_eq_lower__mixed ... bench: 6676 ns/iter (+/- 312)
test c_comparisons::benchmarks::bench_eq_lower__title ... bench: 7321 ns/iter (+/- 272)
test c_comparisons::benchmarks::bench_eq_lower__upper ... bench: 6680 ns/iter (+/- 254)
test c_comparisons::benchmarks::bench_to_lower__lower ... bench: 4292 ns/iter (+/- 304)
test c_comparisons::benchmarks::bench_to_lower__mixed ... bench: 4506 ns/iter (+/- 268)
test c_comparisons::benchmarks::bench_to_lower__title ... bench: 5303 ns/iter (+/- 219)
test c_comparisons::benchmarks::bench_to_lower__upper ... bench: 4669 ns/iter (+/- 271)
test c_comparisons::benchmarks::bench_to_upper__lower ... bench: 4671 ns/iter (+/- 211)
test c_comparisons::benchmarks::bench_to_upper__mixed ... bench: 4397 ns/iter (+/- 157)
test c_comparisons::benchmarks::bench_to_upper__title ... bench: 4782 ns/iter (+/- 241)
test c_comparisons::benchmarks::bench_to_upper__upper ... bench: 4023 ns/iter (+/- 168)

test result: ok. 9 passed; 0 failed; 0 ignored; 36 measured

Summary

# Result of piping the output below through 'python format.py'

a : lookup
b : match
c : comparisons
                a       b       c       b/a     c/a
eq_lower lower  4769    5721    6685    1.20    1.40
eq_lower mixed  4769    5729    6676    1.20    1.40
eq_lower title  4772    6279    7321    1.32    1.53
eq_lower upper  4770    5722    6680    1.20    1.40
to_lower lower  2345    3353    4292    1.43    1.83
to_lower mixed  2355    4356    4506    1.85    1.91
to_lower title  2353    4857    5303    2.06    2.25
to_lower upper  2355    3606    4669    1.53    1.98
to_upper lower  2338    3609    4671    1.54    2.00
to_upper mixed  2349    3474    4397    1.48    1.87
to_upper title  2351    4212    4782    1.79    2.03
to_upper upper  2356    3312    4023    1.41    1.71