Performance between a linear and binary search on a small ordered set

BenchLinearVsBinary.cs

/*
Q: At which size is it preferrable to use binary search over a simple linear search for a small ordered set?

R: Under 5 elements, linear search is slightly faster (from 200% to 10% faster)
But in practice, not sure a switch case to select the best method is really worth it
Unless main usecase is having most of the time only 1-2 elements (so it could be optimized manually without a loop and switch to binary otherwise)
At 3-4 elements, linear is only 10-5% faster

Relative performance between linear and binary search:
size   x86     x64
1     x2.21   x1.42
2     x1.21   x1.39
3     x1.05   x1.14
4     x1.16   x1.06
5     x0.91   x0.87
7     x0.81   x0.87
10    x0.81   x0.80
12    x0.69   x0.69
15    x0.53   x0.44


// * Summary *

Host Process Environment Information:
BenchmarkDotNet.Core=v0.9.9.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i5-6600K CPU 3.50GHz, ProcessorCount=4
Frequency=3421876 ticks, Resolution=292.2374 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1586.0

Type=Program  Mode=Throughput  LaunchCount=2

       Method | Platform |    Jit | Size |     Median |    StdDev |
------------- |--------- |------- |----- |----------- |---------- |
 LinearSearch |      X64 | RyuJit |    1 |  3.7918 ns | 0.0660 ns |
 BinarySearch |      X64 | RyuJit |    1 |  5.3974 ns | 0.0980 ns |
 LinearSearch |      X86 |   Host |    1 |  4.2171 ns | 0.0916 ns |
 BinarySearch |      X86 |   Host |    1 |  9.3073 ns | 0.1453 ns |
 LinearSearch |      X64 | RyuJit |    2 |  6.2138 ns | 0.0621 ns |
 BinarySearch |      X64 | RyuJit |    2 |  8.6610 ns | 0.1128 ns |
 LinearSearch |      X86 |   Host |    2 |  9.2964 ns | 0.1072 ns |
 BinarySearch |      X86 |   Host |    2 | 11.2322 ns | 0.1508 ns |
 LinearSearch |      X64 | RyuJit |    3 |  7.7123 ns | 0.0996 ns |
 BinarySearch |      X64 | RyuJit |    3 |  8.7631 ns | 0.1973 ns |
 LinearSearch |      X86 |   Host |    3 | 10.6464 ns | 0.1705 ns |
 BinarySearch |      X86 |   Host |    3 | 11.1315 ns | 0.1072 ns |
 LinearSearch |      X64 | RyuJit |    4 | 10.1063 ns | 0.1183 ns |
 BinarySearch |      X64 | RyuJit |    4 | 10.7465 ns | 0.1473 ns |
 LinearSearch |      X86 |   Host |    4 | 13.1234 ns | 0.4123 ns |
 BinarySearch |      X86 |   Host |    4 | 15.1706 ns | 0.9016 ns |
 LinearSearch |      X64 | RyuJit |    5 | 11.3418 ns | 0.1654 ns |
 BinarySearch |      X64 | RyuJit |    5 |  9.8712 ns | 0.1687 ns |
 LinearSearch |      X86 |   Host |    5 | 13.9416 ns | 0.2365 ns |
 BinarySearch |      X86 |   Host |    5 | 12.6655 ns | 0.2102 ns |
 LinearSearch |      X64 | RyuJit |    7 | 14.3160 ns | 0.1605 ns |
 BinarySearch |      X64 | RyuJit |    7 | 12.5245 ns | 0.0852 ns |
 LinearSearch |      X86 |   Host |    7 | 17.5668 ns | 0.2574 ns |
 BinarySearch |      X86 |   Host |    7 | 14.2466 ns | 0.2864 ns |
 LinearSearch |      X64 | RyuJit |   10 | 19.7330 ns | 0.2001 ns |
 BinarySearch |      X64 | RyuJit |   10 | 15.8517 ns | 0.2610 ns |
 LinearSearch |      X86 |   Host |   10 | 23.7432 ns | 0.3223 ns |
 BinarySearch |      X86 |   Host |   10 | 19.2047 ns | 0.1379 ns |
 LinearSearch |      X64 | RyuJit |   12 | 23.0494 ns | 0.2310 ns |
 BinarySearch |      X64 | RyuJit |   12 | 15.7903 ns | 0.2585 ns |
 LinearSearch |      X86 |   Host |   12 | 27.7983 ns | 0.4011 ns |
 BinarySearch |      X86 |   Host |   12 | 19.2106 ns | 0.2223 ns |
 LinearSearch |      X64 | RyuJit |   15 | 32.0775 ns | 1.9523 ns |
 BinarySearch |      X64 | RyuJit |   15 | 14.1464 ns | 0.1689 ns |
 LinearSearch |      X86 |   Host |   15 | 32.7228 ns | 0.4728 ns |
 BinarySearch |      X86 |   Host |   15 | 17.3869 ns | 0.2655 ns |

// ***** BenchmarkRunner: End *****
*/
using System.Diagnostics;
using System.Runtime.InteropServices;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Attributes.Exporters;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Exporters;
using BenchmarkDotNet.Jobs;

namespace BenchLinearVsBinary
{
    [Config(typeof(Config))]
    [MarkdownExporter]
    public class Program
    {
        private const int MaxCount = 50;
        private readonly Data[][] dataSet;
        private Data[] currentSet;
        private int currentMid;
        private int currentMax;

        public Program()
        {
            dataSet = new Data[MaxCount][];
            for (int i = 0; i < MaxCount; i++)
            {
                var datas = new Data[i];
                for (int j = 0; j < datas.Length; j++)
                {
                    datas[j].Key = j;
                }
                dataSet[i] = datas;

                int max = datas.Length - 1;
                int mid = datas.Length/2;

                Debug.Assert(BinarySearch(datas, 1) == LinearSearch(datas, 1) &&
                             BinarySearch(datas, mid) == LinearSearch(datas, mid) &&
                             BinarySearch(datas, max) == LinearSearch(datas, max));
            }
        }


        [StructLayout(LayoutKind.Sequential, Size = 16)]
        struct Data
        {
            public int Key;
        }

        [Params(1, 2, 3, 4, 5, 7, 10, 12, 15)]
        public int Size
        {
            set
            {
                currentSet = dataSet[value];
                currentMax = value - 1;
                currentMid = value/2;
            }
        }

        [Benchmark]
        public int LinearSearch()
        {
            int x = 0;
            x += LinearSearch(currentSet, 0);
            x += LinearSearch(currentSet, currentMax);
            x += LinearSearch(currentSet, currentMid);
            return x;
        }

        [Benchmark]
        public int BinarySearch()
        {
            int x = 0;
            x += BinarySearch(currentSet, 0);
            x += BinarySearch(currentSet, currentMax);
            x += BinarySearch(currentSet, currentMid);
            return x;
        }

        private static int LinearSearch(Data[] set, int key)
        {
            for (int i = 0; i < set.Length; i++)
            {
                var c = set[i].Key - key;
                if (c == 0)
                {
                    return i;
                }
                if (c > 0)
                {
                    return ~i;
                }
            }
            return ~set.Length;
        }

        private static int BinarySearch(Data[] set, int key)
        {
            int i = 0;
            int up = set.Length - 1;
            while (i <= up)
            {
                int mid = (up - i) / 2 + i;
                int c = set[mid].Key - key;
                if (c == 0)
                {
                    return mid;
                }
                if (c < 0)
                {
                    i = mid + 1;
                }
                else
                {
                    up = mid - 1;
                }
            }
            return ~i;
        }


        public class Config : ManualConfig
        {
            public Config()
            {
                Add(Job.Default.With(Platform.X86).WithLaunchCount(2));
                Add(Job.Default.With(Platform.X64).With(Jit.RyuJit).WithLaunchCount(2));
                Add(CsvMeasurementsExporter.Default);
                Add(RPlotExporter.Default);
            }
        }

        static void Main(string[] args)
        {
            BenchmarkDotNet.Running.BenchmarkRunner.Run<Program>();
        }
    }
}