Repository navigation
Rust 1.25.0 regressed the performance of encoding_rs's UTF-8 validation on i686 #49873
Description
When Firefox switched from Rust 1.24.0 to Rust 1.25.0, the win32 performance of encoding_rs's UTF-8 validation function dropped 12.5% when used on ASCII input. encoding_rs's UTF-8 validation function is a fork of the Rust standard library validation function that replaces the ASCII acceleration ALU trick that autovectorizes on x86_64 but not on i686 and works only in the aligned case with explicit SIMD code that deals with both the aligned and unaligned cases.
When the input is all ASCII, the function should stay in either the aligned-case or the unaligned-case inner loop that loads 16 bytes using movdqa or movdqu, respectively, performs pmovmskb on the xmm register and compares the result to zero jumping back to the start of the loop if it is zero.
When compiled for i686 Linux with opt level 2 (which Firefox uses) using Rust 1.24.0, the result is exactly as expected.
Unaligned:
.LBB12_3:
movdqu (%edx,%eax), %xmm0
pmovmskb %xmm0, %ebp
testl %ebp, %ebp
jne .LBB12_9
addl $16, %eax
cmpl %ebx, %eax
jbe .LBB12_3
jmp .LBB12_5
.p2align 4, 0x90Aligned:
.LBB12_7:
movdqa (%edx,%eax), %xmm0
pmovmskb %xmm0, %ebp
testl %ebp, %ebp
jne .LBB12_9
addl $16, %eax
cmpl %ebx, %eax
jbe .LBB12_7
.p2align 4, 0x90(Windows wouldn't let me see the asm due to LLVM deeming the IR invalid with --emit asm.)
When compiled with Rust 1.25.0, the result is more complicated:
- There are two instances of
movdqaand two instances ofmovdqusuggesting that the first trip through the loop has been unrolled to be a separate copy from the loop proper. - In the actual loop, ALU instructions have been moved around including placing one between the SSE2 instructions.
Both of these transformations look like plausible optimizations, but considering the performance result from Firefox CI, it seems these transformations made performance worse.
.LBB16_1:
movl %edx, %ebp
leal (%ecx,%edi), %ebx
movl $0, %esi
subl %edi, %ebp
cmpl $16, %ebp
jb .LBB16_22
leal -16(%ebp), %eax
testb $15, %bl
movl %eax, 20(%esp)
je .LBB16_9
movdqu (%ebx), %xmm0
movl %edx, 12(%esp)
xorl %eax, %eax
pmovmskb %xmm0, %edx
testl %edx, %edx
jne .LBB16_7
movl 24(%esp), %eax
xorl %esi, %esi
leal (%eax,%edi), %ecx
.p2align 4, 0x90
.LBB16_5:
leal 16(%esi), %eax
cmpl 20(%esp), %eax
ja .LBB16_20
movdqu (%ecx,%esi), %xmm0
movl %eax, %esi
pmovmskb %xmm0, %edx
testl %edx, %edx
je .LBB16_5
.LBB16_7:
testl %edx, %edx
je .LBB16_12
bsfl %edx, %esi
jmp .LBB16_13
.LBB16_9:
movdqa (%ebx), %xmm0
xorl %ecx, %ecx
pmovmskb %xmm0, %eax
testl %eax, %eax
je .LBB16_15
testl %eax, %eax
je .LBB16_19
.LBB16_11:
bsfl %eax, %esi
addl %ecx, %esi
jmp .LBB16_14
.LBB16_12:
movl $32, %esi
.LBB16_13:
movl 12(%esp), %edx
addl %eax, %esi
.LBB16_14:
movb (%ebx,%esi), %al
jmp .LBB16_24
.LBB16_15:
movl $16, %esi
.p2align 4, 0x90
.LBB16_16:
cmpl 20(%esp), %esi
ja .LBB16_22
movdqa (%ebx,%esi), %xmm0
addl $16, %esi
pmovmskb %xmm0, %eax
testl %eax, %eax
je .LBB16_16
addl $-16, %esi
movl %esi, %ecx
testl %eax, %eax
jne .LBB16_11The asm was obtained by compiling encoding_rs (Firefox uses 0.7.2) using RUSTC_BOOTSTRAP=1 RUSTFLAGS='-C opt-level=2 --emit asm' cargo build --target i686-unknown-linux-gnu --release --features simd-accel and searching for utf8_valid_up_to in the .s file.
Activity
glandium commentedon Apr 11, 2018
Note that I observed something similar on x86-64 (and Firefox has seen a regression on x86-64 too).
hsivonen commentedon Apr 11, 2018
The loop is inlined from
validate_ascii.hsivonen commentedon Apr 11, 2018
The presumed unrolling of the first loop trip happens before LLVM, but the inner loop (which has to be what's slow to get the 12.5% drop in perf) looks the same on the IR level, so this is probably an LLVM 4.0 vs. LLVM 6.0 thing.
IR from 1.24.0:
IR from 1.25.0:
hsivonen commentedon Apr 11, 2018
Code generated by the current nightly looks like the code generated by 1.25.0.
hsivonen commentedon Apr 11, 2018
opt-level=3does not fix this.michaelwoerister commentedon Apr 11, 2018
cc @rust-lang/wg-codegen
hsivonen commentedon Apr 12, 2018
What instruction scheduling model does rustc use by default?
The change looks like it's a result of instruction scheduling trickery, and the LLVM 6.0 release notes say: "Added instruction scheduling information for Intel Sandy Bridge, Ivy Bridge, Haswell, Broadwell, and Skylake CPUs."
Notably, when running
cargo benchon Haswell outside the Gecko context (but withopt-level=2), I was unable to reproduce the performance degradation on the x86_64 Linux target.How can I choose an instruction scheduling model without also enabling the instruction set extensions of the named microarchitecture?
nagisa commentedon Apr 12, 2018
hsivonen commentedon Apr 19, 2018
As far as I can tell, Gecko doesn't set
target-cpuortarget-featureusing the-Cflag.LLVM seems to have microarchitecture-specific sceduling models from Sandy Bridge upwards, and between LLVM 4.0 and 6.0 Intel engineers landed major rewrites of the Sandy Bridge and Haswell scheduling models citing information obtained from the architects of these microarchitectures.
It's unclear to me where the default x86 and x86_64 scheduling models reside in the LLVM source.
hsivonen commentedon Apr 19, 2018
The code generated for x86_64 for the unrolled innermost loop looks closer to expected, though. Aligned case:
hsivonen commentedon Apr 19, 2018
It seems that for the
i686targets, the base CPU ispentium4. Changing it topentium-mdoes not help. However, changing it tox86-64, which is the base CPU for thex86_64targets results in similar instruction scheduling as when actually targeting 64-bit code. (Changing it tohaswellwithout also changingtarget-featureresults in different instruction selection.)16 remaining items
hsivonen commentedon May 21, 2018
Thank you! I verified that the performance of the test case improved with the latest nightly.
Is this kind of LLVM cherrypick eligible to be nominated for cherrypicking into Rust beta? How does one nominate beta backports?
alexcrichton commentedon May 21, 2018
I've added the beta-nominated tag to #50827 which is how we process backports (the compiler team is also tagged to come up during triage)
Update LLVM to 56c931901cfb85cd6f7ed44c7d7520a8de1edf97
nikomatsakis commentedon Jun 7, 2018
The backport seems to be causing issues on beta that don't occur on nightly -- the origins of this are not known, perhaps some other fixes that landed in the meantime? (The failing test is myriad-closures, and it fails only on 32-bit windows, afaik -- it may be a memory usage issue?)
@hsivonen how much do you care that this is backported? We're trying to decide how many resources to devote to tracking this down vs fixing other things.
SimonSapin commentedon Jun 7, 2018
Firefox is not updating its compiler from 1.24 (https://bugzilla.mozilla.org/show_bug.cgi?id=1447116) in part because of this. (@glandium can say more about the other blocker.)
eddyb commentedon Jun 7, 2018
@nikomatsakis
myriad-closuresis indeed a stress test, and memory usage changes make sense.glandium commentedon Jun 7, 2018
Firefox is going to stay on 1.24 until it can jump to 1.28. So, for Firefox, it doesn't matter at all that this makes it to beta.
djc commentedon Jun 8, 2018
@glandium where's the discussion/rationale on that? I searched Bugzilla but couldn't find it.
glandium commentedon Jun 8, 2018
@djc beta is 1.27, and 1.27 doesn't allow to get the allocation size on oom, and that's important to us. 1.28 does.
hsivonen commentedon Jun 8, 2018
@nikomatsakis , given what @glandium said about jumping to 1.28 anyway, I no longer care about a backport.