latkin/code.fsx

## code.fsx
open System
open System.Collections
open System.Collections.Generic
open System.Diagnostics
open System.Linq

module Algos =
    //
    // non-lazy solutions
    //

    let eager1 (value: string) =
        let result = ResizeArray(value.Length)
        for i in 0 .. value.Length - 1 do
            if not (Char.IsLowSurrogate(value.[i]))
            then result.Add(Char.ConvertToUtf32(value, i))
        result.ToArray()

    let eager2 (value: string) =
        let result = ResizeArray(value.Length)
        for i in 0 .. value.Length - 1 do
            if not (Char.IsLowSurrogate(value.[i]))
            then result.Add(Char.ConvertToUtf32(value, i))
        (result.ToArray()) :> seq<_>

    let eager3 (value: string) =
        let result = ResizeArray(value.Length)
        for i in 0 .. value.Length - 1 do
            if not (Char.IsLowSurrogate(value.[i]))
            then result.Add(Char.ConvertToUtf32(value, i))
        // ToArray() causes another copy to be generated.
        // Avoiding that is a win in large-input scenarios, but at a cost
        // of otherwise slower processing
        (result) :> seq<_>

    //
    // lazy solutions
    //

    let lazy0(value: string) =
        seq {
            let i = ref 0
            while !i < value.Length do
                if not (Char.IsLowSurrogate(value.[!i]))
                then yield Char.ConvertToUtf32(value, !i)
                incr i
        }

    let lazy1(value: string) =
        seq {
            for i = 0 to value.Length - 1 do
                if not (Char.IsLowSurrogate(value.[i]))
                then yield Char.ConvertToUtf32(value, i)
        }

    let lazy2(value: string) =
        value
        |> Seq.mapi (fun i c ->
            if(Char.IsLowSurrogate(c)) then 0
            else Char.ConvertToUtf32(value, i))
        |> Seq.filter (fun x -> x <> 0)

    let lazy3(value: string) =
        let inline mapiAndFilter f g e =
            seq {
                let i = ref 0
                for elem in e do
                    if f elem then yield g !i
                    incr i
            }

        value.AsEnumerable()
        |> mapiAndFilter (not << Char.IsLowSurrogate) (fun i -> Char.ConvertToUtf32 (value, i))

    let lazy4 (value : string) =
        let mapiAndFilter f g (e : seq<'a>) : seq<'b> =
            let i = ref -1
            let e = e.GetEnumerator()

            let inline getEnum() =
                { new IEnumerator<'b> with
                      member __.Current =  g !i
                  interface System.Collections.IEnumerator with
                      member __.Current =  box (g !i)
                      member __.MoveNext() =
                          let rec next() =
                              incr i
                              e.MoveNext() && (f e.Current || next())
                          next()
                      member __.Reset() = failwith "reset"
                  interface IDisposable with
                      member __.Dispose() = e.Dispose() }
            { new IEnumerable<'b> with
                  member __.GetEnumerator() = getEnum()
              interface IEnumerable with
                  member __.GetEnumerator() = getEnum() :> IEnumerator }

        value.AsEnumerable()
        |> mapiAndFilter (not << Char.IsLowSurrogate) (fun i -> Char.ConvertToUtf32(value, i))

    // integrate all logic directly
    // avoids need to use System.String enumerator
    // avoids all recursion
    // very fast!
    let lazy5 (value : string) =
        let inline getEnum() =
            let i = ref -1
            { new IEnumerator<int> with
                  member __.Current = Char.ConvertToUtf32(value, !i)
              interface System.Collections.IEnumerator with
                  member __.Current =  box (Char.ConvertToUtf32(value, !i))
                  member __.MoveNext() =
                          incr i
                          if !i >= value.Length then false else
                          if not (Char.IsLowSurrogate(value.[!i])) then true else
                          incr i
                          !i < value.Length
                  member __.Reset() = failwith "reset"
              interface IDisposable with
                  member __.Dispose() = () }
        { new IEnumerable<int> with
              member __.GetEnumerator() = getEnum()
          interface IEnumerable with
              member __.GetEnumerator() = getEnum() :> IEnumerator }

module Timing =
    let timeit f m =
        GC.Collect()
        GC.WaitForPendingFinalizers()
        Stopwatch.StartNew() |> fun sw -> (f (), sw.Elapsed.TotalSeconds, m)

    let rankTimings fs =
        let results =
            fs
            |> List.map (fun (f, m) -> timeit f m)
            |> List.sortBy (fun (_,t,_) -> t)
        let (_, baseline, _) = results.Head
        results |> List.iter (fun (_, t, m) ->  printfn "%10s  %6f  %6f" m t (t/baseline))

let input = "ab\U0001ABCDcde\U0001ABCEfghi\U0001ABCF"

let run f = for _ in 1 .. 1000000 do f input |> Seq.length |> ignore

printfn "**run**"
Timing.rankTimings [
    (fun _ -> run Algos.eager1), "eager1"
    (fun _ -> run Algos.eager2), "eager2"
    (fun _ -> run Algos.eager3), "eager3"
    (fun _ -> run Algos.lazy0), "lazy0"
    (fun _ -> run Algos.lazy1), "lazy1"
    (fun _ -> run Algos.lazy2), "lazy2"
    (fun _ -> run Algos.lazy3), "lazy3"
    (fun _ -> run Algos.lazy4), "lazy4"
    (fun _ -> run Algos.lazy5), "lazy5"
]

let runmap f = for _ in 1 .. 1000000 do f input |> Seq.map id |> Seq.length |> ignore

printfn "**runmap**"
Timing.rankTimings [
    (fun _ -> runmap Algos.eager1), "eager1"
    (fun _ -> runmap Algos.eager2), "eager2"
    (fun _ -> runmap Algos.eager3), "eager3"
    (fun _ -> runmap Algos.lazy0), "lazy0"
    (fun _ -> runmap Algos.lazy1), "lazy1"
    (fun _ -> runmap Algos.lazy2), "lazy2"
    (fun _ -> runmap Algos.lazy3), "lazy3"
    (fun _ -> runmap Algos.lazy4), "lazy4"
    (fun _ -> runmap Algos.lazy5), "lazy5"
]

let runmapnth f = for _ in 1 .. 1000000 do f input |> Seq.map id |> Seq.nth 6 |> ignore

printfn "**runmapnth**"
Timing.rankTimings [
    (fun _ -> runmapnth Algos.eager1), "eager1"
    (fun _ -> runmapnth Algos.eager2), "eager2"
    (fun _ -> runmapnth Algos.eager3), "eager3"
    (fun _ -> runmapnth Algos.lazy0), "lazy0"
    (fun _ -> runmapnth Algos.lazy1), "lazy1"
    (fun _ -> runmapnth Algos.lazy2), "lazy2"
    (fun _ -> runmapnth Algos.lazy3), "lazy3"
    (fun _ -> runmapnth Algos.lazy4), "lazy4"
    (fun _ -> runmapnth Algos.lazy5), "lazy5"
]

let biginput = String.replicate 262144 input
let runBig f = for _ in 1 .. 100 do f biginput |> Seq.length |> ignore

printfn "**runBig**"
Timing.rankTimings [
    (fun _ -> runBig Algos.eager1), "eager1"
    (fun _ -> runBig Algos.eager2), "eager2"
    (fun _ -> runBig Algos.eager3), "eager3"
    (fun _ -> runBig Algos.lazy0), "lazy0"
    (fun _ -> runBig Algos.lazy1), "lazy1"
    (fun _ -> runBig Algos.lazy2), "lazy2"
    (fun _ -> runBig Algos.lazy3), "lazy3"
    (fun _ -> runBig Algos.lazy4), "lazy4"
    (fun _ -> runBig Algos.lazy5), "lazy5"
]

let runBigNth f = for _ in 1 .. 100 do f biginput |> Seq.map id |> Seq.nth 6 |> ignore

printfn "**runBigNth**"
Timing.rankTimings [
    (fun _ -> runBigNth Algos.eager1), "eager1"
    (fun _ -> runBigNth Algos.eager2), "eager2"
    (fun _ -> runBigNth Algos.eager3), "eager3"
    (fun _ -> runBigNth Algos.lazy0), "lazy0"
    (fun _ -> runBigNth Algos.lazy1), "lazy1"
    (fun _ -> runBigNth Algos.lazy2), "lazy2"
    (fun _ -> runBigNth Algos.lazy3), "lazy3"
    (fun _ -> runBigNth Algos.lazy4), "lazy4"
    (fun _ -> runBigNth Algos.lazy5), "lazy5"
]

## results.md

      
    Raw
  

              results.md
            
          
    run


Algo
time (s)
multiplier


eager0 | 0.184025  | 1.000000
 lazy5 | 0.194004  | 1.054226
eager2 | 0.219321  | 1.191800
eager3 | 0.310223  | 1.685769
 lazy0 | 0.330531  | 1.796125
 lazy4 | 0.376372  | 2.045229
 lazy3 | 0.483981  | 2.629978
 lazy1 | 0.894039  | 4.858259
 lazy2 | 0.921062  | 5.005101

runmap


Algo
time (s)
multiplier


eager1 | 0.579327  | 1.000000
 lazy5 | 0.586707  | 1.012740
eager2 | 0.611499  | 1.055534
 lazy0 | 0.683276  | 1.179431
 lazy4 | 0.742995  | 1.282514
eager3 | 0.785129  | 1.355245
 lazy3 | 0.830547  | 1.433642
 lazy1 | 1.250160  | 2.157954
 lazy2 | 1.523762  | 2.630230

runmapnth


Algo
time (s)
multiplier


 lazy5 | 0.418695  | 1.000000
eager1 | 0.499834  | 1.193789
 lazy0 | 0.507692  | 1.212558
eager2 | 0.524433  | 1.252540
 lazy4 | 0.553255  | 1.321380
 lazy3 | 0.608237  | 1.452697
eager3 | 0.632419  | 1.510452
 lazy1 | 0.873706  | 2.086735
 lazy2 | 1.085998  | 2.593767

runBig


Algo
time (s)
multiplier


 lazy5 | 1.585626  | 1.000000
eager3 | 2.364669  | 1.491316
eager2 | 2.936370  | 1.851868
eager1 | 2.966829  | 1.871077
 lazy0 | 4.594467  | 2.897573
 lazy4 | 4.973711  | 3.136749
 lazy3 | 7.036134  | 4.437449
 lazy2 | 11.858302 |  7.478625
 lazy1 | 14.690765 |  9.264963

runBigNth


Algo
time (s)
multiplier


 lazy4 | 0.000270  | 1.000000
 lazy3 | 0.000296  | 1.099814
 lazy5 | 0.000306  | 1.135065
 lazy2 | 0.000352  | 1.305751
 lazy1 | 0.000453  | 1.679777
 lazy0 | 0.000624  | 2.314286
eager3 | 2.326347  | 8632.086085
eager2 | 2.832068  | 10508.601113
eager1 | 2.938856  | 10904.845640
	open System
	open System.Collections
	open System.Collections.Generic
	open System.Diagnostics
	open System.Linq

	module Algos =
	//
	// non-lazy solutions
	//

	let eager1 (value: string) =
	let result = ResizeArray(value.Length)
	for i in 0 .. value.Length - 1 do
	if not (Char.IsLowSurrogate(value.[i]))
	then result.Add(Char.ConvertToUtf32(value, i))
	result.ToArray()

	let eager2 (value: string) =
	let result = ResizeArray(value.Length)
	for i in 0 .. value.Length - 1 do
	if not (Char.IsLowSurrogate(value.[i]))
	then result.Add(Char.ConvertToUtf32(value, i))
	(result.ToArray()) :> seq<_>

	let eager3 (value: string) =
	let result = ResizeArray(value.Length)
	for i in 0 .. value.Length - 1 do
	if not (Char.IsLowSurrogate(value.[i]))
	then result.Add(Char.ConvertToUtf32(value, i))
	// ToArray() causes another copy to be generated.
	// Avoiding that is a win in large-input scenarios, but at a cost
	// of otherwise slower processing
	(result) :> seq<_>

	//
	// lazy solutions
	//

	let lazy0(value: string) =
	seq {
	let i = ref 0
	while !i < value.Length do
	if not (Char.IsLowSurrogate(value.[!i]))
	then yield Char.ConvertToUtf32(value, !i)
	incr i
	}

	let lazy1(value: string) =
	seq {
	for i = 0 to value.Length - 1 do
	if not (Char.IsLowSurrogate(value.[i]))
	then yield Char.ConvertToUtf32(value, i)
	}

	let lazy2(value: string) =
	value
	\|> Seq.mapi (fun i c ->
	if(Char.IsLowSurrogate(c)) then 0
	else Char.ConvertToUtf32(value, i))
	\|> Seq.filter (fun x -> x <> 0)

	let lazy3(value: string) =
	let inline mapiAndFilter f g e =
	seq {
	let i = ref 0
	for elem in e do
	if f elem then yield g !i
	incr i
	}

	value.AsEnumerable()
	\|> mapiAndFilter (not << Char.IsLowSurrogate) (fun i -> Char.ConvertToUtf32 (value, i))

	let lazy4 (value : string) =
	let mapiAndFilter f g (e : seq<'a>) : seq<'b> =
	let i = ref -1
	let e = e.GetEnumerator()

	let inline getEnum() =
	{ new IEnumerator<'b> with
	member __.Current = g !i
	interface System.Collections.IEnumerator with
	member __.Current = box (g !i)
	member __.MoveNext() =
	let rec next() =
	incr i
	e.MoveNext() && (f e.Current \|\| next())
	next()
	member __.Reset() = failwith "reset"
	interface IDisposable with
	member __.Dispose() = e.Dispose() }
	{ new IEnumerable<'b> with
	member __.GetEnumerator() = getEnum()
	interface IEnumerable with
	member __.GetEnumerator() = getEnum() :> IEnumerator }

	value.AsEnumerable()
	\|> mapiAndFilter (not << Char.IsLowSurrogate) (fun i -> Char.ConvertToUtf32(value, i))

	// integrate all logic directly
	// avoids need to use System.String enumerator
	// avoids all recursion
	// very fast!
	let lazy5 (value : string) =
	let inline getEnum() =
	let i = ref -1
	{ new IEnumerator<int> with
	member __.Current = Char.ConvertToUtf32(value, !i)
	interface System.Collections.IEnumerator with
	member __.Current = box (Char.ConvertToUtf32(value, !i))
	member __.MoveNext() =
	incr i
	if !i >= value.Length then false else
	if not (Char.IsLowSurrogate(value.[!i])) then true else
	incr i
	!i < value.Length
	member __.Reset() = failwith "reset"
	interface IDisposable with
	member __.Dispose() = () }
	{ new IEnumerable<int> with
	member __.GetEnumerator() = getEnum()
	interface IEnumerable with
	member __.GetEnumerator() = getEnum() :> IEnumerator }

	module Timing =
	let timeit f m =
	GC.Collect()
	GC.WaitForPendingFinalizers()
	Stopwatch.StartNew() \|> fun sw -> (f (), sw.Elapsed.TotalSeconds, m)

	let rankTimings fs =
	let results =
	fs
	\|> List.map (fun (f, m) -> timeit f m)
	\|> List.sortBy (fun (_,t,_) -> t)
	let (_, baseline, _) = results.Head
	results \|> List.iter (fun (_, t, m) -> printfn "%10s %6f %6f" m t (t/baseline))

	let input = "ab\U0001ABCDcde\U0001ABCEfghi\U0001ABCF"

	let run f = for _ in 1 .. 1000000 do f input \|> Seq.length \|> ignore

	printfn "run"
	Timing.rankTimings [
	(fun _ -> run Algos.eager1), "eager1"
	(fun _ -> run Algos.eager2), "eager2"
	(fun _ -> run Algos.eager3), "eager3"
	(fun _ -> run Algos.lazy0), "lazy0"
	(fun _ -> run Algos.lazy1), "lazy1"
	(fun _ -> run Algos.lazy2), "lazy2"
	(fun _ -> run Algos.lazy3), "lazy3"
	(fun _ -> run Algos.lazy4), "lazy4"
	(fun _ -> run Algos.lazy5), "lazy5"
	]

	let runmap f = for _ in 1 .. 1000000 do f input \|> Seq.map id \|> Seq.length \|> ignore

	printfn "runmap"
	Timing.rankTimings [
	(fun _ -> runmap Algos.eager1), "eager1"
	(fun _ -> runmap Algos.eager2), "eager2"
	(fun _ -> runmap Algos.eager3), "eager3"
	(fun _ -> runmap Algos.lazy0), "lazy0"
	(fun _ -> runmap Algos.lazy1), "lazy1"
	(fun _ -> runmap Algos.lazy2), "lazy2"
	(fun _ -> runmap Algos.lazy3), "lazy3"
	(fun _ -> runmap Algos.lazy4), "lazy4"
	(fun _ -> runmap Algos.lazy5), "lazy5"
	]

	let runmapnth f = for _ in 1 .. 1000000 do f input \|> Seq.map id \|> Seq.nth 6 \|> ignore

	printfn "runmapnth"
	Timing.rankTimings [
	(fun _ -> runmapnth Algos.eager1), "eager1"
	(fun _ -> runmapnth Algos.eager2), "eager2"
	(fun _ -> runmapnth Algos.eager3), "eager3"
	(fun _ -> runmapnth Algos.lazy0), "lazy0"
	(fun _ -> runmapnth Algos.lazy1), "lazy1"
	(fun _ -> runmapnth Algos.lazy2), "lazy2"
	(fun _ -> runmapnth Algos.lazy3), "lazy3"
	(fun _ -> runmapnth Algos.lazy4), "lazy4"
	(fun _ -> runmapnth Algos.lazy5), "lazy5"
	]

	let biginput = String.replicate 262144 input
	let runBig f = for _ in 1 .. 100 do f biginput \|> Seq.length \|> ignore

	printfn "runBig"
	Timing.rankTimings [
	(fun _ -> runBig Algos.eager1), "eager1"
	(fun _ -> runBig Algos.eager2), "eager2"
	(fun _ -> runBig Algos.eager3), "eager3"
	(fun _ -> runBig Algos.lazy0), "lazy0"
	(fun _ -> runBig Algos.lazy1), "lazy1"
	(fun _ -> runBig Algos.lazy2), "lazy2"
	(fun _ -> runBig Algos.lazy3), "lazy3"
	(fun _ -> runBig Algos.lazy4), "lazy4"
	(fun _ -> runBig Algos.lazy5), "lazy5"
	]

	let runBigNth f = for _ in 1 .. 100 do f biginput \|> Seq.map id \|> Seq.nth 6 \|> ignore

	printfn "runBigNth"
	Timing.rankTimings [
	(fun _ -> runBigNth Algos.eager1), "eager1"
	(fun _ -> runBigNth Algos.eager2), "eager2"
	(fun _ -> runBigNth Algos.eager3), "eager3"
	(fun _ -> runBigNth Algos.lazy0), "lazy0"
	(fun _ -> runBigNth Algos.lazy1), "lazy1"
	(fun _ -> runBigNth Algos.lazy2), "lazy2"
	(fun _ -> runBigNth Algos.lazy3), "lazy3"
	(fun _ -> runBigNth Algos.lazy4), "lazy4"
	(fun _ -> runBigNth Algos.lazy5), "lazy5"
	]