Repository navigation
str::starts_with('x') (literal char) is slower than str::starts_with("x") (literal string). #41993
Description
(Discovered when reviewing #41957)
This piece of code:
pub fn check(a: &str) -> bool {
a.starts_with('/')
}generates an extremely complicated assembly. The generated function will try to decode the input string a, obtain the first code point, and then compare with '/' (47).
Compare with
pub fn check(a: &str) -> bool {
a.starts_with("/")
}which basically just checks if the first byte of the string is '/' (after an unnecessary (?) is_char_boundary check introduced in #26771 and another unnecessary pointer-equality check)
Most of the time the character as a pattern is a compile-time constant, so it should be more efficient by encoding the char into UTF-8, and then memcmp with the input string.
(Rust uses the "decoding" approach so that char share the same implementation with &[char] and FnMut(char) -> bool via the CharEq trait.)
This problem is particularly bad for Clippy users, since there is a single_char_pattern lint which suggested changing all .starts_with("x") by .starts_with('x') with the assumption that the latter is faster, which as of Rust 1.19 it is the reverse.
$ rustc -vV
rustc 1.19.0-nightly (826d8f385 2017-05-13)
binary: rustc
commit-hash: 826d8f3850b37a23481dfcf4a899b5dfc82d22e3
commit-date: 2017-05-13
host: x86_64-apple-darwin
release: 1.19.0-nightly
LLVM version: 4.0x86_64 ASM
Build with:
$ rustc --crate-type=dylib -Copt-level=3 --emit=asm 2.rs
$ cat 2.sFirst function (.starts_with('/')):
.section __TEXT,__text,regular,pure_instructions
.globl __ZN2_25check17hfe0a879e8d0ee56bE
.p2align 4, 0x90
__ZN2_25check17hfe0a879e8d0ee56bE:
.cfi_startproc
pushq %rbp
Lcfi0:
.cfi_def_cfa_offset 16
Lcfi1:
.cfi_offset %rbp, -16
movq %rsp, %rbp
Lcfi2:
.cfi_def_cfa_register %rbp
testq %rsi, %rsi
je LBB0_1
movzbl (%rdi), %edx
testb %dl, %dl
jns LBB0_17
leaq (%rdi,%rsi), %r8
xorl %eax, %eax
cmpq $1, %rsi
movq %r8, %rsi
je LBB0_5
movzbl 1(%rdi), %eax
addq $2, %rdi
andl $63, %eax
movq %rdi, %rsi
LBB0_5:
movl %edx, %ecx
andl $31, %ecx
cmpb $-32, %dl
jb LBB0_6
cmpq %r8, %rsi
je LBB0_8
movzbl (%rsi), %edi
incq %rsi
andl $63, %edi
jmp LBB0_10
LBB0_1:
xorl %eax, %eax
jmp LBB0_18
LBB0_6:
shll $6, %ecx
jmp LBB0_16
LBB0_8:
xorl %edi, %edi
movq %r8, %rsi
LBB0_10:
shll $6, %eax
orl %edi, %eax
cmpb $-16, %dl
jb LBB0_11
cmpq %r8, %rsi
je LBB0_13
movzbl (%rsi), %edx
andl $63, %edx
jmp LBB0_15
LBB0_11:
shll $12, %ecx
jmp LBB0_16
LBB0_13:
xorl %edx, %edx
LBB0_15:
andl $7, %ecx
shll $18, %ecx
shll $6, %eax
orl %edx, %eax
LBB0_16:
orl %ecx, %eax
movl %eax, %edx
LBB0_17:
cmpl $47, %edx
sete %al
LBB0_18:
popq %rbp
retq
.cfi_endproc
.subsections_via_symbolsSecond function (.starts_with("/")):
.section __TEXT,__text,regular,pure_instructions
.globl __ZN2_25check17hfe0a879e8d0ee56bE
.p2align 4, 0x90
__ZN2_25check17hfe0a879e8d0ee56bE:
.cfi_startproc
pushq %rbp
Lcfi0:
.cfi_def_cfa_offset 16
Lcfi1:
.cfi_offset %rbp, -16
movq %rsp, %rbp
Lcfi2:
.cfi_def_cfa_register %rbp
testq %rsi, %rsi
je LBB0_3
cmpq $1, %rsi
je LBB0_4
cmpb $-65, 1(%rdi)
jle LBB0_3
LBB0_4:
movb $1, %al
leaq _str.0(%rip), %rcx
cmpq %rcx, %rdi
je LBB0_6
cmpb $47, (%rdi)
je LBB0_6
LBB0_3:
xorl %eax, %eax
LBB0_6:
popq %rbp
retq
.cfi_endproc
.section __TEXT,__const
_str.0:
.byte 47
.subsections_via_symbols
Activity
nagisa commentedon May 15, 2017
Single char cannot be possibly faster than a string, because it will have to encode the character to utf-8 (or decode the string bytes into utf-32, which is what seems to be done here), in general case.
It does not seem to me that this issue is actionable in any way. We could change our implementation strategy, but it would only end up redistributing the costs.I guess the ascii_only optimisation could be implemented, actually. The infrastructure is there, only need to adjust the impl of the matcher.
kennytm commentedon May 15, 2017
@nagisa The performance of starts_with constant char and constant string should at least be the same. I'm pretty sure the LLVM optimizer is able to encode the character at compile time to reduce the whole
is_prefix_oftohaystack.as_bytes()[0] == b'/'plus length check.The problem is not really about the unused function
only_ascii, but that the expensive operation (decoding) is done on the haystack which is only known at runtime, rather than (encoding) done on the pattern which can be evaluated at compile time.Yes there wouldn't be improvement for a runtime char, but it should be a pretty rare case.
nagisa commentedon May 15, 2017
So, I’ve “optimised” the
charPattern to the point where doingtext.starts_with('k')is as simple as:The benchmark for 1024 iterations of such call is
1000nsvs1140nsoriginally. It also regresses patterns such astext.contains('k')4 times (or I’m benchmarking it wrong): from 44µs to 175µs, despite not doing the UTF-8 decoding.Here’s the interesting parts of the code in question:
Feels like it was complete waste of my time to look into this.
kennytm commentedon May 15, 2017
@nagisa Thanks for the test! Could you share the benchmarking code? I'll take a look later.
My benchmark looks like this https://gist.github.com/kennytm/2b6264fdf67651db78cb37095b037fae, with a 100% speed up (4.5 ns → 2.2 ns) rather than the bland 1.1 ns → 1.0 ns change. (For sure this really doesn't matter unless you do run
.starts_with()million times.)(Note: OK this shows
strandcharactually may have similar performance, although this also shows that both can be improved.)nagisa commentedon May 15, 2017
is quite literally what I used.
Assembly was generated by compiling
nagisa commentedon May 15, 2017
master...nagisa:charpat is the diff against libcore
nagisa commentedon May 16, 2017
So I tried multiple implementation strategies, and none of them really yielded any substantial benefit for
starts_withoverall.In the table below,
Two Wayis the Searcher based on the same algorithm as the string searcher,Smart Jumpingis a greatly improved variant of the idea above,This Patchis a simple patch that does not change the searcher at all, only applies a few small tweaks around, mostly adding inline hints.All of these do end up in
text.starts_with(constant)being optimised to the desired short assembly, even for non-ASCII case. Despite all that, some of the benchmarks run around 2 times as slow, when compared to original code.I will submit a patch for the other improvements, but I don’t think there’s too much to be done for
starts_with(char)case specifically.This is my benchmark results table:
kennytm commentedon Jul 23, 2018
Minor update:
.starts_with('x')is still slower than.starts_with("x")even with LLVM 7 + RFC 2500. See #52646 (comment) for the microbenchmarksteveklabnik commentedon Oct 7, 2019
Triage: I tried to reproduce the microbenchmark, but:
Both of these are not insurmountable, but I don't have the time right now to do that work. For simplicity's sake, https://gist.github.com/kennytm/2b6264fdf67651db78cb37095b037fae is the benchmark referenced above.
mati865 commentedon Oct 7, 2019
Assembly of literal char version still looks worse: https://godbolt.org/z/oZb-_I
Mark-Simulacrum commentedon Dec 9, 2019
Yes, that assembly is worse -- it looks like that's mostly down to the
chars()iterator of str rather than the direct prefix -- thecheckcharfunction here looks pretty good (and comparable with the string version).I think the problem comes down to trying to re-encode the UTF-8 str input to a char isn't something that we can constant fold away, as it's from the unknown input, and LLVM isn't good enough to see that for the
'/'charit seems like we can just care about the first byte of the encoded str (which is altogether unsurprising, to be honest, since we are comparing essentially u32 with u32, and LLVM has no knowledge that the first byte is all that matters since it doesn't know the encoding here).I wonder if we could get some wins by replacing the Pattern impl for char to not use the chars iterator but rather the proposal I gave above (re-encoding the char as UTF-8 and then checking if it's a prefix).
I don't have time to run benchmarks right now but thought I'd leave it here at least.
spunit262 commentedon Dec 11, 2019
I think the actual issue is that nothing is telling LLVM that Overlong encodings are forbidden. With them there are 4 different ways to encode
'/'. Adding a fewunreachable_uncheckedtoChars::nextmight help.ranma42 commentedon Dec 11, 2019
Since UTF8 has good slicing properties, we could actually compare the
.as_bytes()slices whenever we are testing for string vs substring equality (and skip the char boundary check).This seems to improve the assembly for
str.starts_with(str).encode_utf8combined with this seems to generate the desired assembly:https://godbolt.org/z/myTjHj
I will try something along these lines in the core library ASAP
Prefer encoding the char when checking for string prefix/suffix
Rollup merge of rust-lang#67249 - ranma42:improve-starts-with-literal…
Rollup merge of rust-lang#67249 - ranma42:improve-starts-with-literal…
Prefer encoding the char when checking for string prefix/suffix