Skip to content

Instantly share code, notes, and snippets.

@manofstick
Created August 22, 2016 03:06
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save manofstick/229384a1bd0bdb26caf9a780b952d9b8 to your computer and use it in GitHub Desktop.
Benchmarking for Array.filter
/// BenchmarkDotNet Notes:
/// Docs/Github: https://github.com/PerfDotNet/BenchmarkDotNet#getting-started
///
/// This benchmarking suite will perform JIT warmups, collect system environment data
/// run multiple trials, and produce convenient reports.
/// You will find csv, markdown, and and html versions of the reports in .\BenchmarkDotNet.Artifacts\results
/// after running the tests.
///
/// Be sure to run tests in Release mode, optimizations on, etc.
module Program
open System
open System.Threading.Tasks
/// BenchmarkDotNet on Nuget at:
/// https://www.nuget.org/packages/BenchmarkDotNet/
/// https://www.nuget.org/packages/BenchmarkDotNet.Diagnostics.Windows/
open BenchmarkDotNet.Attributes
open BenchmarkDotNet.Running
open BenchmarkDotNet.Configs
open BenchmarkDotNet.Jobs
#if MONO
#else
open BenchmarkDotNet.Diagnostics.Windows
#endif
/// When pulling functions out of the complete fsharp solution to test
/// Some things are not easily available, such as Array.zeroCreateUnchecked
/// We mock these here using their checked variations
module Array =
let inline zeroCreateUnchecked (count:int) =
Array.zeroCreate count
let inline subUnchecked startIndex count (array : 'T[]) =
Array.sub array startIndex count
// Almost every array function calls this, so mock it with
// the exact same code
let inline checkNonNull argName arg =
match box arg with
| null -> nullArg argName
| _ -> ()
[<CompiledName("Empty")>]
let empty<'T> : 'T [] = [| |]
[<CompiledName("Filter")>]
let filter f (array: _[]) =
checkNonNull "array" array
let mutable i = 0
while i < array.Length && not (f array.[i]) do
i <- i + 1
if i <> array.Length then
let mutable element = array.[i]
let chunk1 : 'T[] = Array.zeroCreateUnchecked (((array.Length-i) >>> 2) + 1)
let mutable count = 1
chunk1.[0] <- element
i <- i + 1
while count < chunk1.Length && i < array.Length do
element <- array.[i]
if f element then
chunk1.[count] <- element
count <- count + 1
i <- i + 1
if i < array.Length then
let chunk2 = Array.zeroCreateUnchecked (array.Length-i)
count <- 0
while i < array.Length do
element <- array.[i]
if f element then
chunk2.[count] <- element
count <- count + 1
i <- i + 1
let res : 'T[] = Array.zeroCreateUnchecked (chunk1.Length + count)
Array.Copy(chunk1,res,chunk1.Length)
Array.Copy(chunk2,0,res,chunk1.Length,count)
res
else
Array.subUnchecked 0 count chunk1
else empty
let philter32 f (source: 'T[]) =
checkNonNull "" source
let thirtytooth = source.Length/32
let filterMaskMap = Array.zeroCreate<uint32> (thirtytooth+1)
let mutable filteredCount = 0
let sourceBatchEnd = thirtytooth * 32
let mutable sourceIdx = 0
while sourceIdx < sourceBatchEnd do
let mutable filterMask = 0u
if f source.[sourceIdx+0x00] then filterMask <- filterMask + 0x00000001u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x01] then filterMask <- filterMask + 0x00000002u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x02] then filterMask <- filterMask + 0x00000004u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x03] then filterMask <- filterMask + 0x00000008u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x04] then filterMask <- filterMask + 0x00000010u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x05] then filterMask <- filterMask + 0x00000020u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x06] then filterMask <- filterMask + 0x00000040u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x07] then filterMask <- filterMask + 0x00000080u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x08] then filterMask <- filterMask + 0x00000100u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x09] then filterMask <- filterMask + 0x00000200u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x0A] then filterMask <- filterMask + 0x00000400u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x0B] then filterMask <- filterMask + 0x00000800u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x0C] then filterMask <- filterMask + 0x00001000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x0D] then filterMask <- filterMask + 0x00002000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x0E] then filterMask <- filterMask + 0x00004000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x0F] then filterMask <- filterMask + 0x00008000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x10] then filterMask <- filterMask + 0x00010000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x11] then filterMask <- filterMask + 0x00020000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x12] then filterMask <- filterMask + 0x00040000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x13] then filterMask <- filterMask + 0x00080000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x14] then filterMask <- filterMask + 0x00100000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x15] then filterMask <- filterMask + 0x00200000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x16] then filterMask <- filterMask + 0x00400000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x17] then filterMask <- filterMask + 0x00800000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x18] then filterMask <- filterMask + 0x01000000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x19] then filterMask <- filterMask + 0x02000000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x1A] then filterMask <- filterMask + 0x04000000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x1B] then filterMask <- filterMask + 0x08000000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x1C] then filterMask <- filterMask + 0x10000000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x1D] then filterMask <- filterMask + 0x20000000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x1E] then filterMask <- filterMask + 0x40000000u; filteredCount <- filteredCount + 1
if f source.[sourceIdx+0x1F] then filterMask <- filterMask + 0x80000000u; filteredCount <- filteredCount + 1
filterMaskMap.[sourceIdx / 32] <- filterMask
sourceIdx <- sourceIdx + 32
if sourceIdx < source.Length then
let mutable filterMask = 0u
let mutable elementMask = 1u
while sourceIdx < source.Length do
if f source.[sourceIdx] then filterMask <- filterMask ||| elementMask; filteredCount <- filteredCount + 1
elementMask <- elementMask <<< 1
sourceIdx <- sourceIdx + 1
filterMaskMap.[filterMaskMap.Length-1] <- filterMask
if filteredCount = 0 then [||]
else
let res = Array.zeroCreate filteredCount
if source.Length = res.Length
then System.Array.Copy (source, res, filteredCount)
else
let mutable resIdx = 0
sourceIdx <- 0
for filterMask in filterMaskMap do
if filterMask <> 0u then
if filterMask &&& 0x00000001u <> 0u then res.[resIdx] <- source.[sourceIdx+0x00]; resIdx <- resIdx + 1
if filterMask &&& 0x00000002u <> 0u then res.[resIdx] <- source.[sourceIdx+0x01]; resIdx <- resIdx + 1
if filterMask &&& 0x00000004u <> 0u then res.[resIdx] <- source.[sourceIdx+0x02]; resIdx <- resIdx + 1
if filterMask &&& 0x00000008u <> 0u then res.[resIdx] <- source.[sourceIdx+0x03]; resIdx <- resIdx + 1
if filterMask &&& 0x00000010u <> 0u then res.[resIdx] <- source.[sourceIdx+0x04]; resIdx <- resIdx + 1
if filterMask &&& 0x00000020u <> 0u then res.[resIdx] <- source.[sourceIdx+0x05]; resIdx <- resIdx + 1
if filterMask &&& 0x00000040u <> 0u then res.[resIdx] <- source.[sourceIdx+0x06]; resIdx <- resIdx + 1
if filterMask &&& 0x00000080u <> 0u then res.[resIdx] <- source.[sourceIdx+0x07]; resIdx <- resIdx + 1
if filterMask &&& 0x00000100u <> 0u then res.[resIdx] <- source.[sourceIdx+0x08]; resIdx <- resIdx + 1
if filterMask &&& 0x00000200u <> 0u then res.[resIdx] <- source.[sourceIdx+0x09]; resIdx <- resIdx + 1
if filterMask &&& 0x00000400u <> 0u then res.[resIdx] <- source.[sourceIdx+0x0A]; resIdx <- resIdx + 1
if filterMask &&& 0x00000800u <> 0u then res.[resIdx] <- source.[sourceIdx+0x0B]; resIdx <- resIdx + 1
if filterMask &&& 0x00001000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x0C]; resIdx <- resIdx + 1
if filterMask &&& 0x00002000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x0D]; resIdx <- resIdx + 1
if filterMask &&& 0x00004000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x0E]; resIdx <- resIdx + 1
if filterMask &&& 0x00008000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x0F]; resIdx <- resIdx + 1
if filterMask &&& 0x00010000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x10]; resIdx <- resIdx + 1
if filterMask &&& 0x00020000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x11]; resIdx <- resIdx + 1
if filterMask &&& 0x00040000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x12]; resIdx <- resIdx + 1
if filterMask &&& 0x00080000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x13]; resIdx <- resIdx + 1
if filterMask &&& 0x00100000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x14]; resIdx <- resIdx + 1
if filterMask &&& 0x00200000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x15]; resIdx <- resIdx + 1
if filterMask &&& 0x00400000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x16]; resIdx <- resIdx + 1
if filterMask &&& 0x00800000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x17]; resIdx <- resIdx + 1
if filterMask &&& 0x01000000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x18]; resIdx <- resIdx + 1
if filterMask &&& 0x02000000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x19]; resIdx <- resIdx + 1
if filterMask &&& 0x04000000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x1A]; resIdx <- resIdx + 1
if filterMask &&& 0x08000000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x1B]; resIdx <- resIdx + 1
if filterMask &&& 0x10000000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x1C]; resIdx <- resIdx + 1
if filterMask &&& 0x20000000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x1D]; resIdx <- resIdx + 1
if filterMask &&& 0x40000000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x1E]; resIdx <- resIdx + 1
if filterMask &&& 0x80000000u <> 0u then res.[resIdx] <- source.[sourceIdx+0x1F]; resIdx <- resIdx + 1
sourceIdx <- sourceIdx + 32
res
/// Configuration for a given benchmark
type ArrayPerfConfig () =
inherit ManualConfig()
do
base.Add Job.RyuJitX64
//base.Add Job.LegacyJitX86 // If you want to also test 32bit. It will run tests on both if both of these are here.
#if MONO
#else
base.Add(new MemoryDiagnoser()) // To get GC and allocation data
#endif
[<Config (typeof<ArrayPerfConfig>)>]
type ArrayBenchmark () =
let mutable array = [||]
[<Params (1000, 10000000)>] //[<Params (10,100,10000,1000000,10000000)>]
member val public Length = Unchecked.defaultof<int> with get, set
[<Params (1, 100)>] // [<Params (1, 10, 100, 100)>]
member val public MaxRunLengthBeforeValueChange = Unchecked.defaultof<int> with get, set
[<Params (1, 10, 50, 90, 99)>]// [<Params (0, 1, 10, 50, 90, 100)>]
member val public PercentOfDataInFilter = Unchecked.defaultof<int> with get, set
[<Setup>]
member self.SetupData () =
let getRandomInt =
let r = Random ()
fun n -> r.Next (0, n)
let getDataValue () = getRandomInt 1000
let getRunLength () = getRandomInt self.MaxRunLengthBeforeValueChange
array <- Array.zeroCreate self.Length
let mutable randomValue = getDataValue ()
let mutable countUntilChangeValue = getRunLength ()
for i = 0 to array.Length-1 do
array.[i] <- randomValue
countUntilChangeValue <- countUntilChangeValue - 1
if countUntilChangeValue <= 0 then
randomValue <- getDataValue ()
countUntilChangeValue <- getRunLength ()
member private self.filterFunction valueFromArray =
(valueFromArray % 100) < self.PercentOfDataInFilter
[<Benchmark(Baseline=true)>]
member self.Filter1456 () = array |> filter self.filterFunction
[<Benchmark>]
member self.Philter32 () = array |> philter32 self.filterFunction
[<EntryPoint>]
let main argv =
let switch =
BenchmarkSwitcher [| typeof<ArrayBenchmark> |]
switch.Run argv |> ignore
0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment