onsdag 10. april 2013 F# Testing Ytelse QuickBencher
I forrige blogpost (Telle ord-forekomster med F#) brukte jeg en funksjon som het benchmark til å måle hvor lang tid det tok å kjøre programet mitt. Nå vil jeg "avsløre" hva som skjuler seg bak denne funksjonen.
Da jeg eksperimenterte med ulike algoritmer i F# for å prosessere større datamengder hadde jeg behov for å enkelt kunne måle og sammenligne kjøretider på ulike funksjoner. Dette behovet har jeg hatt før, og i 2010 førte det til at jeg lagde biblioteket QuickBencher (tilgjengelig på CodePlex). Bibloteket var kraftig inspirert av tilsvarende funksjonalitet som er å finne i Ruby.
Jeg kunne selvfølgelig ha brukt QuickBencher fra F# også. Men det jeg i stedet gjorde var å røske ut den sentrale innmaten fra bibloteket, og kode det om til et par hendige F#-funksjoner. Her følger en gjennomgang av koden.
Først importerer jeg noen navnerom jeg kommer til å bruke mye:
open System open System.Diagnostics
Deretter lager jeg min første datatype, som er en record jeg kaller ProcessorTime. Formålet med denne er å holde på informasjon om forbrukt tid. Disse tidene kommer fra en prosess (System.Diagnostics.Process), og jeg inkluderer en statisk metode på typen min for å opprette en ProcessorTime-instans basert på en prosess. Dette ser slik ut:
type ProcessorTimes =
{ User : TimeSpan
System : TimeSpan
Total : TimeSpan }
static member get (p : Process) =
{ User = p.UserProcessorTime
System = p.PrivilegedProcessorTime
Total = p.TotalProcessorTime }
Videre trenger jeg en liten hjelpefunksjon får å få tak i forskjellen mellom to Timespan (i sekunder):
let getDuration start stop =
let duration : TimeSpan = stop - start
duration.TotalMilliseconds / 1000.0
Og da kan jeg lage min andre datatype, som heter ProcessorDuration. Denne holder tidsinformasjon fra en prosess for to ulike tidspunkt – et starttidspunkt og et stopptidspunkt. Den har også et felt for å holde på forløpt klokketid. ProcessorDuration representerer rett og slett en benchmark-måling.
I tillegg har jeg overstyrt typens ToString-metode til å gi en printbar representasjon av målingen. Tekstformateringen som er brukt er den samme som du finner både i QuickBencher og i Ruby sin benchmark-funksjonalitet.
type ProcessorDuration =
{ Start : ProcessorTimes
Stop : ProcessorTimes
ClockTime : int64 }
override x.ToString () =
sprintf "%f user, %f system, %f total (%f)"
(getDuration x.Start.User x.Stop.User)
(getDuration x.Start.System x.Stop.System)
(getDuration x.Start.Total x.Stop.Total)
(float x.ClockTime / 1000.0)
Funksjonen startBenchmark gjør det du antar at den gjør – den begynner å måle tiden. Men den gjør en ting til: Den oppretter og returnerer en lexical closure (altså en funksjon som har referanser til frie variabler fra det scopet hvor den ble opprettet). Denne closuren skal så brukes til å stoppe målingen, og den vil returnere resultatet i form av en ProcessorDuration-instans.
Slik er funksjonen implementert:
let startBenchmark ()=
let proc = Process.GetCurrentProcess()
let startTimes = ProcessorTimes.get proc
let stopwatch = Stopwatch.StartNew()
(fun () ->
stopwatch.Stop()
{ Start = startTimes
Stop = ProcessorTimes.get proc
ClockTime = stopwatch.ElapsedMilliseconds })
Vi har kommet frem til selve rosinen – benchmark-funksjonen som måler forbrukt tid for en vilkårlig funksjon. Ta først en titt på koden, som ser slik ut:
let benchmark label thunk callback =
let getResult = startBenchmark()
let temp = thunk()
callback label (getResult().ToString())
temp
benchmark har altså tre parametre. Nummer én er en label som skal identifisere akkurat denne målingen. Typen er ikke gitt – det er typisk tenkt at det skal være en streng, men det kan være hva som helst.
Parameter nummer to heter thunk. I funksjonell programmering er thunk enkelt fortalt betegnelsen på en parameterløs closure. Dette er rett og slett funksjonen som skal måles.
Det tredje parameteret er en callback som vil bli evaluert etter at målingen er foretatt. Argumentene til callbacken vil være labelen og resultatet av målingen. Dermed er det altså signaturen til callbacken som avgjør hvilken type label'en må være.
Etter å ha startet en måling, eksekvert thunken, og gitt resultatet til callbacken, vil benchmark returnere resulatet fra thunken. Dette vil gjøre det enklere å snike inn benchmarking uten for mye endringer i eksisterende kode.
I 99% av tilfellene ønsker du sansynligvis bare å printe ut målingen til konsollvinduet, så jeg lagde en enklere versjon av benchmark for akkurat det. Den er selvsagt enkel, men jeg tar den med for kompletthets skyld:
let benchmarkPrintn label thunk =
benchmark label thunk (printfn "%s: %s")
For å vise hvordan benchmark virker vil jeg løse Project Euler-oppgaven nummer 1, en gjenganger på denne bloggen. Jeg skal finne summer av alle multipler av 3 og 5. Men denne gangen inkluderer jeg multipler helt opp til og med 1'000'000 – for det tar såpass lang tid at det blir noe å måle.
Jeg designer fire ulike løsninger på problemet, og er veldig spent på hva målingene vil vise.
let test1 ()=
let mutable result = 0L
for i in 1L..1000000L do
if i % 3L = 0L || i % 5L = 0L
then result <- result + i
printfn "\nResult by for loop and mutation: %s"
(string result)
let test2 ()=
{1L..1000000L}
|> Seq.filter (fun x -> x % 3L = 0L || x % 5L = 0L)
|> Seq.fold (fun acc x -> acc + x) 0L
|> string
|> printfn "\nResult by range, filter and fold: %s"
let test3 ()=
let result = ref 0L
{1L..1000000L}
|> Seq.iter (fun x -> if x % 3L = 0L || x % 5L = 0L
then result := !result + x)
printfn "\nResult by iter and reference cell: %s"
(string !result)
let test4 ()=
let rec inner acc n =
match n with
| 1000001L -> acc
| n when n % 3L = 0L -> inner (acc + n) (n + 1L)
| n when n % 5L = 0L -> inner (acc + n) (n + 1L)
| _ -> inner acc (n + 1L)
printfn "\nResult by recursion: %s"
(string (inner 0L 1L))
Når jeg så benchmarker de fire testene...
do
benchmarkPrintn "For and mutation" test1
benchmarkPrintn "Range, filter, fold" test2
benchmarkPrintn "Iter and referece cell" test3
benchmarkPrintn "Recursion" test4
...får jeg følgende output:
Result by for loop and mutation: 233334166668 For and mutation: 0.249602 user, 0.000000 system, 0.249602 total (0.250000) Result by range, filter and fold: 233334166668 Range, filter, fold: 0.405603 user, 0.000000 system, 0.405603 total (0.417000) Result by iter and reference cell: 233334166668 Iter and referece cell: 0.265202 user, 0.000000 system, 0.265202 total (0.260000) Result by recursion: 233334166668 Recursion: 0.031200 user, 0.000000 system, 0.031200 total (0.033000)
At sekvensoperasjoner som filter og fold (test2) gir svakere kjøretid enn for-løkker og mutering av data (test1 og test3) er skuffende men ikke overraskende i et språk som F#. Men resultatet fra test4 veltet meg nesten av stolen! Rundt 85% reduksjon i kjøretid sammenlignet med forløkke-varianten ved bruk av rekursjon var totalt uventet, og viser at F# er blodtrimmet og optimalisert for algoritmer som bruker halerekursjon.
Hvis ytelse er viktig for deg så er det viktig å faktisk måle hvor lang tid ting tar. Å anta er skummelt, og å endre/optimalisere kode uten å holde track på kjøretid er ikke å anbefale. Da trenger du verktøy som det jeg har laget og vist frem i denne bloggposten, som er enkle å bruke, og som gjør én ting og gjør den godt.