Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
open System.Diagnostics
open System.Reflection
open Microsoft.FSharp.Core
open Microsoft.FSharp.Core.Operators
open Microsoft.FSharp.Core.LanguagePrimitives
open Microsoft.FSharp.Core.LanguagePrimitives.IntrinsicOperators
open Microsoft.FSharp.Collections
open Microsoft.FSharp.Primitives.Basics
open System.Collections.Generic
let inline countByImpl (comparer:IEqualityComparer<'SafeKey>) (projection:'T->'SafeKey) (getKey:'SafeKey->'Key) (list:'T list) =
let dict = Dictionary comparer
let rec loop srcList =
match srcList with
| [] -> ()
| h::t ->
let safeKey = projection h
let mutable prev = 0
if dict.TryGetValue(safeKey, &prev) then dict.[safeKey] <- prev + 1 else dict.[safeKey] <- 1
loop t
loop list
let mutable result = []
for group in dict do
result <- (getKey group.Key, group.Value) :: result
result |> List.rev
// We avoid wrapping a StructBox, because under 64 JIT we get some "hard" tailcalls which affect performance
let countByValueType (projection:'T->'Key) (list:'T list) = countByImpl HashIdentity.Structural<'Key> projection id list
let countBy (projection:'T->'Key) (list:'T list) =
countByValueType projection list
let run (f : 'a -> 'b) l =
let res = f l
for i in 2..500 do
f l |> ignore
res
let count = 5000000
let listOfInts = [1..count]
let listOfInts1 = List.concat [[1..count]; [1..10000]; [1..10000]]
#time "on"
run List.countBy id listOfInts //Real: 00:00:01.859, CPU: 00:00:02.015, GC gen0: 27, gen1: 26, gen2: 1
#time "off"
#time "on"
run countBy id listOfInts //Real: 00:00:01.935, CPU: 00:00:01.859, GC gen0: 38, gen1: 38, gen2: 0
#time "off"
#time "on"
run List.countBy (fun i -> if i % 2 = 0 then 0 else 1) listOfInts //Real: 00:00:00.190, CPU: 00:00:00.187, GC gen0: 0, gen1: 0, gen2: 0
#time "off"
#time "on"
run countBy (fun i -> if i % 2 = 0 then 0 else 1) listOfInts //Real: 00:00:00.217, CPU: 00:00:00.218, GC gen0: 0, gen1: 0, gen2: 0
#time "off"
#time "on"
run List.countBy id listOfInts1 //Real: 00:00:02.340, CPU: 00:00:02.265, GC gen0: 26, gen1: 25, gen2: 1
#time "off"
#time "on"
run countBy id listOfInts1 //Real: 00:00:06.138, CPU: 00:00:05.953, GC gen0: 41, gen1: 38, gen2: 2
#time "off"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment