`bstr::ByteSlice::chars` is significantly slower than `str::from_utf8` + `str::chars`

[01mf02]

I have byte slices of which I would like to obtain the number of characters, as given by bstr::ByteSlice's chars().
I have noted that when the byte slice is a valid UTF-8 string, it is about 8x faster to convert the byte slice to UTF-8 and then call str::chars() instead:

fn len(b: &[u8]) -> usize {
    use bstr::ByteSlice;
    // 1. only use `bstr`
    //b.chars().count()
    // 2. use `bstr` only as fallback if the bytes cannot be converted to UTF-8
    core::str::from_utf8(b).map_or_else(|_| b.chars().count(), |s| s.chars().count()) 
}

fn main() {
    let mut s = String::new();
    use bstr::ByteSlice;
    while len(&s.as_bytes()) < 10000 {
        s.push('a');
    }
}

(I also performed this experiment in a real-world program to exclude that the Rust compiler does some nifty optimizations here that dilute the results, but I still got roughly the same factor of performance difference.)

$ hyperfine -M 5 -L v only,fallback "target/release/bstr-{v}"
Benchmark 1: target/release/bstr-only
  Time (mean ± σ):      2.505 s ±  0.016 s    [User: 2.495 s, System: 0.001 s]
  Range (min … max):    2.487 s …  2.522 s    5 runs
 
Benchmark 2: target/release/bstr-fallback
  Time (mean ± σ):     313.8 ms ±   0.2 ms    [User: 311.7 ms, System: 0.9 ms]
  Range (min … max):   313.5 ms … 314.0 ms    5 runs
 
Summary
  target/release/bstr-fallback ran
    7.98 ± 0.05 times faster than target/release/bstr-only

This came very unexpected for me, to the point that I think it should either be pointed out in the documentation or, even better, be sped up in the implementation.
I have looked at bstr's chars(), but I have not seen obvious ways to speed it up. The question is: Why is str::from_utf8 + str::chars so fast that their combination can walk through the whole bytes twice in 1/8 of the time that bstr walks through once? Is this some dark SIMD magic?
The source of from_utf8 uses run_utf8_validation, do you think it would be worthwhile to adapt bstr's chars() to use something more akin to that? I would be motivated to try that, but first, I would like to hear your opinion on this.

[BurntSushi]

From this repository's bench directory, I ran:

cargo bench -- '(bstr|std)/chars/' --save-baseline chars

And then critcmp can compare:

$ critcmp chars -g '[^/]+/(.*)'
group                   chars/bstr/                            chars/std/
-----                   -----------                            ----------
chars/en-huge-ascii     2.00    197.4±0.52µs     2.4 GB/sec    1.00     98.7±0.43µs     4.8 GB/sec
chars/en-small-ascii    1.98    394.2±1.90ns     2.4 GB/sec    1.00    199.4±1.03ns     4.7 GB/sec
chars/en-tiny-ascii     2.62     23.6±0.49ns  1619.6 MB/sec    1.00      9.0±0.03ns     4.1 GB/sec
chars/ru-huge-utf8      1.66   913.6±13.39µs   534.4 MB/sec    1.00    550.2±6.81µs   887.5 MB/sec
chars/ru-small-utf8     3.23   1115.2±9.21ns   855.1 MB/sec    1.00   345.3±17.15ns     2.7 GB/sec
chars/ru-tiny-utf8      3.19     45.4±0.30ns   840.3 MB/sec    1.00     14.2±0.67ns     2.6 GB/sec
chars/zh-huge-utf8      2.09    657.8±3.32µs   742.3 MB/sec    1.00    314.2±1.17µs  1554.3 MB/sec
chars/zh-small-utf8     3.66   975.6±13.00ns   903.3 MB/sec    1.00    266.4±5.05ns     3.2 GB/sec
chars/zh-tiny-utf8      3.29     40.4±0.70ns   943.8 MB/sec    1.00     12.3±0.40ns     3.0 GB/sec

That was on x86-64. For aarch64 I get:

$ critcmp chars -g '[^/]+/(.*)'
group                   chars/bstr/                            chars/std/
-----                   -----------                            ----------
chars/en-huge-ascii     1.57    439.3±1.35µs  1111.4 MB/sec    1.00    279.3±0.51µs  1748.2 MB/sec
chars/en-small-ascii    1.58    864.5±4.53ns  1103.1 MB/sec    1.00    548.1±2.62ns  1740.0 MB/sec
chars/en-tiny-ascii     2.45     34.6±0.15ns  1101.8 MB/sec    1.00     14.1±0.07ns     2.6 GB/sec
chars/ru-huge-utf8      1.75    910.2±2.23µs   536.4 MB/sec    1.00    518.7±2.03µs   941.4 MB/sec
chars/ru-small-utf8     2.35   1148.9±5.78ns   830.1 MB/sec    1.00    489.5±2.32ns  1948.3 MB/sec
chars/ru-tiny-utf8      2.33     46.3±0.23ns   823.2 MB/sec    1.00     19.9±0.18ns  1920.2 MB/sec
chars/zh-huge-utf8      2.12    696.2±1.63µs   701.3 MB/sec    1.00    328.1±0.96µs  1488.1 MB/sec
chars/zh-small-utf8     3.02   1019.7±5.35ns   864.2 MB/sec    1.00    337.5±5.15ns     2.5 GB/sec
chars/zh-tiny-utf8      2.92     41.3±0.21ns   922.8 MB/sec    1.00     14.2±0.07ns     2.6 GB/sec

bstr's implementation is slower, but not anywhere close to 8x slower according to these measurements. To be clear, I do generally expect bstr to be slower here on principle by the simple fact that UTF-8 decoding when you know the string is valid UTF-8 can take advantage of assumptions that you cannot make when the string is not valid UTF-8.

Why is str::from_utf8 + str::chars so fast that their combination can walk through the whole bytes twice in 1/8 of the time that bstr walks through once? Is this some dark SIMD magic?

str::from_utf8 is a throughput optimized routine and looks to me like it is indeed using SIMD. bstr's own is_utf8 does too. (For the ASCII case.) So overall, it's likely to be quite fast, much faster than just stepping through one codepoint at a time like str::chars or bstr's ByteSlice::chars.

Now, as for why ByteSlice::chars is slower than str::chars, I'm not entirely sure. I looked very briefly at a profile and nothing stood out to me. bstr does use a very different technique for UTF-8 validation than what std does. I think if I were to do a full investigation here, I'd first start by trying std's approach (but slightly different because, again, we can't do the unwrap_uncheckeds when we don't know that we have valid UTF-8). In particular, I'm interested to better understand why the ASCII case is so much different. Both implementations have an early check to bail out. Adding this simple patch results in a 25% speed-up:

diff --git a/src/utf8.rs b/src/utf8.rs
index 054740c..931d3ea 100644
--- a/src/utf8.rs
+++ b/src/utf8.rs
@@ -113,6 +113,12 @@ impl<'a> Iterator for Chars<'a> {
 
     #[inline]
     fn next(&mut self) -> Option<char> {
+        if let Some(&first) = self.bs.first() {
+            if first.is_ascii() {
+                self.bs = &self.bs[1..];
+                return Some(first as char);
+            }
+        }
         let (ch, size) = decode_lossy(self.bs);
         if size == 0 {
             return None;

So I think to me, there is likely something sub-optimal in how the UTF-8 validation is arranged.

Now... as for why you're seeing an 8x difference... That I do not know. Looking at the program you've provided, your timings don't make sense to me. When I run your program as provided, it completes instantly in about 4ms.

OK, let's try for a complete reproduction here instead of me needing to guess. Here's my Cargo.toml:

[package]
publish = false
name = "bstr-chars"
version = "0.1.0"
edition = "2024"

[dependencies]
bstr = "1.12.1"

[[bin]]
name = "bstr-chars"
path = "main.rs"

[profile.release]
debug = true

Here's my main.rs (notice that I've bumped up the number of iterators by a factor of 10):

fn len_std(b: &[u8]) -> usize {
    use bstr::ByteSlice;
    core::str::from_utf8(b)
        .map_or_else(|_| b.chars().count(), |s| s.chars().count())
}

fn len_bstr(b: &[u8]) -> usize {
    use bstr::ByteSlice;
    b.chars().count()
}

fn main() {
    const ITERS: usize = 100_000;
    let mut s = String::new();
    if std::env::args_os().nth(1).is_some_and(|arg| arg == "bstr") {
        while len_bstr(&s.as_bytes()) < ITERS {
            s.push('a');
        }
    } else {
        while len_std(&s.as_bytes()) < ITERS {
            s.push('a');
        }
    }
}

Here's how I compile:

cargo b -r

And benchmark:

$ hyperfine './target/release/bstr-chars std' './target/release/bstr-chars bstr'
Benchmark 1: ./target/release/bstr-chars std
  Time (mean ± σ):     230.9 ms ±   3.8 ms    [User: 230.4 ms, System: 0.3 ms]
  Range (min … max):   223.7 ms … 234.7 ms    13 runs

Benchmark 2: ./target/release/bstr-chars bstr
  Time (mean ± σ):      1.454 s ±  0.007 s    [User: 1.452 s, System: 0.001 s]
  Range (min … max):    1.447 s …  1.470 s    10 runs

Summary
  ./target/release/bstr-chars std ran
    6.30 ± 0.11 times faster than ./target/release/bstr-chars bstr

OK! Now we're getting somewhere. This is much closer to what you report. And now the answer is immediately clear to me. std has a fast path for Iter::count:

https://github.com/rust-lang/rust/blob/f21b4c0888ca6a388fcf9365fc0044fa0642ab98/library/core/src/str/iter.rs#L48-L45

And:

https://github.com/rust-lang/rust/blob/f21b4c0888ca6a388fcf9365fc0044fa0642ab98/library/core/src/str/count.rs#L26-L37

And:

https://github.com/rust-lang/rust/blob/f21b4c0888ca6a388fcf9365fc0044fa0642ab98/library/core/src/str/count.rs#L108-L39

bstr doesn't have any fast path for that. So it's just going to go through the slower iterate-one-codepoint-at-a-time, where as std isn't going to do any decoding. And std's implementation can indeed be faster than bstr's ever could be, because bstr does still need to do some kind of validation. Although, surely, bstr can do a lot better in this case than it does today. An "easy" first pass at this would be to target the ASCII case by modifying or copying validate:

bstr/src/utf8.rs

Line 464 in f0ebd3a

pub fn validate(slice: &[u8]) -> Result<(), Utf8Error> {

Specifically, if we know we have a big chunk of ASCII, then we can "count" it by just taking its length. And then fall back to a decoding loop for the non-ASCII case.

So I think the more precise statement is not about str::chars(), but rather, str::chars().count().

[01mf02]

Hi @BurntSushi, thanks so much for your extremely detailed writeup!

Sorry for the confusion regarding my reproduction example. I had commented out one of the two code paths and thought that it was clear enough how to evaluate that. But your way with args is of course much nicer to use. :)

To verify your hypothesis, I went ahead and avoided count():

use bstr::ByteSlice;

fn len_bstr(b: &[u8]) -> usize {
    let v: Vec<_> = b.chars().collect();
    v.len()
}

fn len_std(b: &[u8]) -> usize {
    let v: Vec<_> = core::str::from_utf8(b).map_or_else(|_| b.chars().collect(), |s| s.chars().collect());
    v.len()
}

fn main() {
    const ITERS: usize = 100_000;
    let mut s = String::new();
    if std::env::args_os().nth(1).is_some_and(|arg| arg == "bstr") {
        while len_bstr(&s.as_bytes()) < ITERS {
            s.push('a');
        }
    } else {
        while len_std(&s.as_bytes()) < ITERS {
            s.push('a');
        }
    }
}

Results:

$ hyperfine -M 5 -L v bstr,std "target/release/bstr-perf {v}"
Benchmark 1: target/release/bstr-perf bstr
  Time (mean ± σ):      5.059 s ±  0.012 s    [User: 5.032 s, System: 0.003 s]
  Range (min … max):    5.039 s …  5.068 s    5 runs
 
Benchmark 2: target/release/bstr-perf std
  Time (mean ± σ):      3.576 s ±  0.014 s    [User: 2.718 s, System: 0.840 s]
  Range (min … max):    3.566 s …  3.600 s    5 runs
 
Summary
  target/release/bstr-perf std ran
    1.41 ± 0.01 times faster than target/release/bstr-perf bstr

Indeed, the difference is now much smaller. So you're right, it's the optimised count() from core::str. The implementation is slightly ... intimidating, but probably not impossible to adapt to bstr. Would you be up to include such a special code path for count() in bstr? I could try to write it once I have a bit of spare time on my hands.

[BurntSushi]

Yes, that sounds fine.

I would prefer a first pass being what I described above, instead of trying to copy std right out of the gate. I'll be able to review and merge my suggestion much more quickly than a PR that tries to copy std.

[01mf02]

I would prefer a first pass being what I described above, instead of trying to copy std right out of the gate. I'll be able to review and merge my suggestion much more quickly than a PR that tries to copy std.

I understand. Thanks for clarifying this!