Benchmarking for Array.filter
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /// 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