[Perf -30%] System.Memory.Span<Byte>.BinarySearch

[DrewScoggins]

Run Information

Architecture	x64
OS	Windows 10.0.18362
Changes	diff

Regressions in System.Memory.Span

Benchmark	Baseline	Test	Test/Base	Modality	Baseline Outlier
BinarySearch	14.86 ns	19.26 ns	1.30	Bimodal	True

Related Issue on x86 Windows

[Perf -25%] System.Memory.Span.IndexOfAnyThreeValues

Historical Data in Reporting System

Repro

git clone https://github.com/dotnet/performance.git
py .\performance\scripts\benchmarks_ci.py -f netcoreapp5.0 --filter 'System.Memory.Span<Byte>*';

Histogram

System.Memory.Span.BinarySearch(Size: 512)

[13.136 ; 14.227) | @@@@@@@@
[14.227 ; 14.616) | 
[14.616 ; 15.707) | @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[15.707 ; 16.840) | @@@@
[16.840 ; 17.931) | 
[17.931 ; 18.355) | 
[18.355 ; 19.446) | @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

Docs

Profiling workflow for dotnet/runtime repository
Benchmarking workflow for dotnet/runtime repository

[kunalspathak]

I pulled out latest graph and if I compared it with the graph in this issue, it looks like we see regression once in a while, although in latest graph below, the regression continues.

On my local machine, I came up with standalone test to verify it.

Stopwatch st = new Stopwatch();
st.Start();
BinarySearchTest<char> test = new BinarySearchTest<char>();
for (int i = 0; i < 6 * 1000 * 1000 * 200; i++)
{
  test.BinarySearch();
}
st.Stop();
Console.WriteLine("Time: " + st.ElapsedMilliseconds + " msec.");

Base: 16725 msec.
Test: 19845 msec.

Base = 4f703e6
Test = 4c18fb2

I can clearly see the regression on my local machine as well, but I couldn't see why it regressed. The JIT code produced during entire run is identical. The JIT throughput itself was better in test compared to base as seen below:

(left is base and right is test).

Drilling down further doesn't tell much. The time is just spent in executing the assembly code of BinarySearch.

Perhaps, one of @GrabYourPitchforks or @adamsitnik should investigate further.

[adamsitnik]

The JIT code produced during entire run is identical.

Have you used the latest 5.0 bits? I've seen the same assembly code and no regression when using .NET Core SDK=5.0.100-preview.8.20362.3 but when I use the python script to download the latest SDK (RC1) the there is a diff and a regression.

https://www.diffchecker.com/OfXOVRte

git clone https://github.com/dotnet/performance.git
py .\performance\scripts\benchmarks_ci.py -f netcoreapp3.1 netcoreapp5.0 --filter 'System.Memory.Span<Byte>.BinarySearch' --bdn-arguments "--disasm true"

3.1

BenchmarkDotNet=v0.12.1.1405-nightly, OS=Windows 10.0.18363.959 (1909/November2019Update/19H2)
Intel Xeon CPU E5-1650 v4 3.60GHz, 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=5.0.100-rc.1.20411.10
[Host] : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT
Job-IUPLXQ : .NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT

PowerPlanMode=00000000-0000-0000-0000-000000000000 Runtime=.NET Core 3.1 Arguments=/p:DebugType=portable
Toolchain=netcoreapp3.1 IterationTime=250.0000 ms MaxIterationCount=20
MinIterationCount=15 WarmupCount=1

Method	Size	Mean	Error	StdDev	Median	Min	Max	Gen 0	Gen 1	Gen 2	Allocated	Code Size
BinarySearch	512	11.87 ns	0.119 ns	0.105 ns	11.84 ns	11.68 ns	12.01 ns	-	-	-	-	116 B

.NET Core 3.1.6 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.31603), X64 RyuJIT

; System.Memory.Span`1[[System.Byte, System.Private.CoreLib]].BinarySearch()
       sub       rsp,28
       mov       rdx,[rcx+18]
       test      rdx,rdx
       jne       short M00_L00
       xor       r8d,r8d
       xor       edx,edx
       jmp       short M00_L01
M00_L00:
       lea       r8,[rdx+10]
       mov       edx,[rdx+8]
M00_L01:
       movzx     eax,byte ptr [rcx+2C]
       mov       rcx,r8
       mov       r8d,eax
       call      System.SpanHelpers.BinarySearch[[System.Byte, System.Private.CoreLib],[System.Byte, System.Private.CoreLib]](Byte ByRef, Int32, Byte)
       nop
       add       rsp,28
       ret
; Total bytes of code 48

; System.SpanHelpers.BinarySearch[[System.Byte, System.Private.CoreLib],[System.Byte, System.Private.CoreLib]](Byte ByRef, Int32, Byte)
       mov       [rsp+18],r8d
       xor       eax,eax
       dec       edx
       test      edx,edx
       jl        short M01_L03
M01_L00:
       lea       r8d,[rdx+rax]
       shr       r8d,1
       movsxd    r9,r8d
       movzx     r9d,byte ptr [rcx+r9]
       movzx     r10d,byte ptr [rsp+18]
       sub       r10d,r9d
       test      r10d,r10d
       je        short M01_L04
       test      r10d,r10d
       jle       short M01_L01
       lea       eax,[r8+1]
       jmp       short M01_L02
M01_L01:
       lea       edx,[r8+0FFFF]
M01_L02:
       cmp       eax,edx
       jle       short M01_L00
M01_L03:
       not       eax
       ret
M01_L04:
       mov       eax,r8d
       ret
; Total bytes of code 68

5.0

BenchmarkDotNet=v0.12.1.1405-nightly, OS=Windows 10.0.18363.959 (1909/November2019Update/19H2)
Intel Xeon CPU E5-1650 v4 3.60GHz, 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=5.0.100-rc.1.20411.10
[Host] : .NET Core 5.0.0 (CoreCLR 5.0.20.40416, CoreFX 5.0.20.40416), X64 RyuJIT
Job-PXLKUC : .NET Core 5.0.0 (CoreCLR 5.0.20.40416, CoreFX 5.0.20.40416), X64 RyuJIT

PowerPlanMode=00000000-0000-0000-0000-000000000000 Runtime=.NET Core 5.0 Arguments=/p:DebugType=portable
Toolchain=netcoreapp5.0 IterationTime=250.0000 ms MaxIterationCount=20
MinIterationCount=15 WarmupCount=1

Method	Size	Mean	Error	StdDev	Median	Min	Max	Gen 0	Gen 1	Gen 2	Allocated	Code Size
BinarySearch	512	16.56 ns	0.089 ns	0.075 ns	16.57 ns	16.42 ns	16.68 ns	-	-	-	-	113 B

.NET Core 5.0.0 (CoreCLR 5.0.20.40416, CoreFX 5.0.20.40416), X64 RyuJIT

; System.Memory.Span`1[[System.Byte, System.Private.CoreLib]].BinarySearch()
       sub       rsp,28
       mov       rdx,[rcx+18]
       test      rdx,rdx
       jne       short M00_L00
       xor       r8d,r8d
       xor       edx,edx
       jmp       short M00_L01
M00_L00:
       lea       r8,[rdx+10]
       mov       edx,[rdx+8]
M00_L01:
       movzx     eax,byte ptr [rcx+2C]
       mov       rcx,r8
       mov       r8d,eax
       call      System.SpanHelpers.BinarySearch[[System.Byte, System.Private.CoreLib],[System.Byte, System.Private.CoreLib]](Byte ByRef, Int32, Byte)
       nop
       add       rsp,28
       ret
; Total bytes of code 48

; System.SpanHelpers.BinarySearch[[System.Byte, System.Private.CoreLib],[System.Byte, System.Private.CoreLib]](Byte ByRef, Int32, Byte)
       mov       [rsp+18],r8d
       xor       eax,eax
       dec       edx
       test      edx,edx
       jl        short M01_L03
M01_L00:
       lea       r8d,[rdx+rax]
       shr       r8d,1
       movsxd    r9,r8d
       movzx     r9d,byte ptr [rcx+r9]
       movzx     r10d,byte ptr [rsp+18]
       sub       r10d,r9d
       je        short M01_L04
       test      r10d,r10d
       jle       short M01_L01
       lea       eax,[r8+1]
       jmp       short M01_L02
M01_L01:
       lea       edx,[r8+0FFFF]
M01_L02:
       cmp       eax,edx
       jle       short M01_L00
M01_L03:
       not       eax
       ret
M01_L04:
       mov       eax,r8d
       ret
; Total bytes of code 65