Performance degradation of memcmp(size=24) after commit 308322

[ZviRackover]

Bugzilla Link	33914
Resolution	FIXED
Resolved on	Aug 02, 2017 05:23
Version	trunk
OS	Windows NT
Blocks	#33196
CC	@topperc,@zmodem,@RKSimon,@rnk,@rotateright

Extended Description

We observed a 13% degradation in an internal benchmark after commit 308322.

The minimal reproducer:

define i32 @​foo(i8* %A, i8* %B) {
%res = call i32 @​memcmp(i8* %A, i8* %B, i64 24)
ret i32 %res
}
declare i32 @​memcmp(i8* nocapture, i8* nocapture, i64) local_unnamed_addr #​5

Before the commit the call to memcmp was lowered to a call to glibc's memcmp which was dispatched to __memcmp_sse4_1. The hot code in __memcmp_sse4_1 was doing 1-XMM-load pair+ptest+jcc+8-byte-load-pair+cmp+jcc:

...
│ movdqu -0x18(%rdi),%xmm2
│ movdqu -0x18(%rsi),%xmm1
11.11 │ pxor %xmm1,%xmm2
7.41 │ ptest %xmm2,%xmm0
14.81 │ ↓ jae 15e8
14.81 │ mov -0x8(%rsi),%rcx
│ mov -0x8(%rdi),%rax
│ cmp %rax,%rcx
│ ↓ jne 1603
│ xor %eax,%eax
11.11 │ ← retq
...

After the commit the memcmp is expanded inline to three 8-byte-load-pairs+cmp+jcc's:

...

# BB#0: # %loadbb

    movbeq  (%rdi), %rcx
    movbeq  (%rsi), %rdx
    cmpq    %rdx, %rcx
    jne     .LBB0_1

BB#2: # %loadbb1

    movbeq  8(%rdi), %rcx
    movbeq  8(%rsi), %rdx
    cmpq    %rdx, %rcx
    jne     .LBB0_1

BB#3: # %loadbb2

    movbeq  16(%rdi), %rcx
    movbeq  16(%rsi), %rdx
    xorl    %eax, %eax
    cmpq    %rdx, %rcx
    jne     .LBB0_1

BB#4: # %endblock

    retq

.LBB0_1: # %res_block
cmpq %rdx, %rcx
movl $-1, %ecx
movl $1, %eax
cmovbl %ecx, %eax
retq
...

Options for fixing:

1. Improve the inline expansion to generate a similar sequence to glibc's: 1 16-byte pair load + ptest + jcc + 8-byte load + cmp + jmp

2. call libc's memcmp

I would like to request this commit be reverted until we get this issue fixed. Thanks.

[RKSimon]

Options for fixing:

1. Improve the inline expansion to generate a similar sequence to glibc's: 1
   16-byte pair load + ptest + jcc + 8-byte load + cmp + jmp

2. call libc's memcmp

I would like to request this commit be reverted until we get this issue
fixed. Thanks.

(1) should be possible, but a quick initial fix would be to limit memcmp to 2 splits (compared to the current 4) like it is for -Os. I'll create a patch for review.

[rnk]

+1 for the 2 element limit

[RKSimon]

https://reviews.llvm.org/D35830

If accepted I'd like to merge this into the 5.0.0 release branch as well.

[RKSimon]

trunk - rL308986

[RKSimon]

Hans - I'd like to merge this into the 5.0.0 branch please

[zmodem]

Hans - I'd like to merge this into the 5.0.0 branch please

Please let it sit in the tree for a day first, then go ahead and merge. Thanks.

[rotateright]

We did look at both vectorization and larger scalar chunking options in bug 33329, and we can enable/implement those, but I think we need to understand why the 8-byte chunk version is poor on this benchmark.

The overhead of making the libcall seems to be more than overcome by the loss from an extra branch in the implementation. Is dynamic branch prediction defeated by this benchmark?

There's a patch to eliminate the trailing cmov codegen at https://reviews.llvm.org/D34904 . Could that be the problem?

It would be great to know if the poor benchmark results are on publicly available hardware, so we can experiment more. Memcmp perf is always going to fluctuate with hardware and workload, so we just have to try to maximize the benefit of the inlined code.

[ZviRackover]

The regression was observed on a Skylake (6th generation client) processor in EMBC/networking/qos, Red-Hat 7.1 64-bit.

I agree it would be interesting to analyze this regression more in-depth. I can't say for sure what was the root cause of the slow-down. The cmov, branch mispredictions are valid suspects.

I am not yet up-to-speed with the PRs and patches mentioned above, but may i suggest that when measuring inline expansion options we should also compare performance to a libc implementation we intend to replace (and this may have been done. I did not go over all the experiment reports in detail yet).

[zmodem]

Hans - I'd like to merge this into the 5.0.0 branch please

Please let it sit in the tree for a day first, then go ahead and merge.
Thanks.

Merged together with r308963 in r309127.

[rotateright]

The regression was observed on a Skylake (6th generation client) processor
in EMBC/networking/qos, Red-Hat 7.1 64-bit.

I agree it would be interesting to analyze this regression more in-depth. I
can't say for sure what was the root cause of the slow-down. The cmov,
branch mispredictions are valid suspects.

I am not yet up-to-speed with the PRs and patches mentioned above, but may i
suggest that when measuring inline expansion options we should also compare
performance to a libc implementation we intend to replace (and this may have
been done. I did not go over all the experiment reports in detail yet).

Yes, definitely. The test program in the related bug includes a call to libc as one of the data points. In the last iteration of the tester, however, the compiler was smart enough to zap the entire loop that called memcmp() because it knows that's a readonly call. I'll have to try harder to defeat LLVM. :)

The good news is that you have identified a standard benchmark and platform with a strong memcmp() dependence. We should be able to beat any current perf score by inlining the memcmp code.