Skip to content

Instantly share code, notes, and snippets.

@mattwarren
Forked from xoofx/BenchLinearVsBinary.cs
Created November 2, 2016 10:55
Show Gist options
  • Save mattwarren/cc8a72a6ced72e81f71293fe2db79e58 to your computer and use it in GitHub Desktop.
Save mattwarren/cc8a72a6ced72e81f71293fe2db79e58 to your computer and use it in GitHub Desktop.
Performance between a linear and binary search on a small ordered set
/*
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>();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment