5 people like it.

Faster .. operator for range generation

The .. operator that is used to generate ranges in F# core is quite slow. This snippet shows an alternative implementation that is about 5 times faster.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
open System.Collections.Generic

/// A helper function that generates a sequence for the specified range.
/// (This takes the step and also an operator to use for checking at the end)
let inline rangeStepImpl (lo:^T) (hi:^T) (step:^T) geq = 
  { new IEnumerable< ^T > with
      member x.GetEnumerator() =
        let current = ref (lo - step)
        { new IEnumerator< ^T > with
            member x.Current = current.Value
          interface System.Collections.IEnumerator with
            member x.Current = box current.Value
            member x.MoveNext() = 
              if geq current.Value hi then false
              else current.Value <- current.Value + step; true
            member x.Reset() = current.Value <- lo - step
          interface System.IDisposable with
            member x.Dispose() = ()  }
    interface System.Collections.IEnumerable with
      member x.GetEnumerator() = (x :?> IEnumerable< ^T >).GetEnumerator() :> _ }

/// A helper function that generates a sequence for the specified range of
/// int or int64 values. This is notably faster than using `lo .. step .. hi`.
let inline rangeStep (lo:^T) (step:^T) (hi:^T) = 
  if lo <= hi then rangeStepImpl lo hi step (>=)
  else rangeStepImpl lo hi step (<=)

/// A helper function that generates a sequence for the specified range of
/// int or int64 values. This is notably faster than using `lo .. hi`.
let inline range (lo:^T) (hi:^T) = 
  if lo <= hi then rangeStepImpl lo hi LanguagePrimitives.GenericOne (>=)
  else rangeStepImpl lo hi LanguagePrimitives.GenericOne (<=)

#time

// The following takes about 350-400ms on my machine
seq { for x in 0 .. 5000000 -> 0 } |> Seq.length
seq { for x in 0L .. 5000000L -> 0 } |> Seq.length
seq { for x in 0. .. 5000000. -> 0 } |> Seq.length
seq { for x in 0 .. 10 .. 50000000 -> 0 } |> Seq.length
seq { for x in 0L .. 10L .. 50000000L -> 0 } |> Seq.length
seq { for x in 0. .. 10. .. 50000000. -> 0 } |> Seq.length

// The following takes about 75ms on my machine
seq { for x in range 0 5000000 -> 0 } |> Seq.length
seq { for x in range 0L 5000000L -> 0 } |> Seq.length
seq { for x in range 0. 5000000. -> 0 } |> Seq.length
seq { for x in rangeStep 0 10 50000000 -> 0 } |> Seq.length
seq { for x in rangeStep 0L 10L 50000000L -> 0 } |> Seq.length
seq { for x in rangeStep 0. 10. 50000000. -> 0 } |> Seq.length

// Oh look, I can override the default operators :)
let inline (..) a b = range a b
let inline (.. ..) a s b = rangeStep a s b
namespace System
namespace System.Collections
namespace System.Collections.Generic
val rangeStepImpl : lo:'T -> hi:'T -> step:'T -> geq:('T -> 'T -> bool) -> IEnumerable<'T> (requires member ( - ) and member ( + ))

Full name: Script.rangeStepImpl


 A helper function that generates a sequence for the specified range.
 (This takes the step and also an operator to use for checking at the end)
val lo : 'T (requires member ( - ) and member ( + ))
val hi : 'T (requires member ( - ) and member ( + ))
val step : 'T (requires member ( - ) and member ( + ))
val geq : ('T -> 'T -> bool) (requires member ( - ) and member ( + ))
type IEnumerable<'T> =
  member GetEnumerator : unit -> IEnumerator<'T>

Full name: System.Collections.Generic.IEnumerable<_>
val x : IEnumerable<'T> (requires member ( - ) and member ( + ))
IEnumerable.GetEnumerator() : IEnumerator<'T>
val current : 'T ref (requires member ( - ) and member ( + ))
Multiple items
val ref : value:'T -> 'T ref

Full name: Microsoft.FSharp.Core.Operators.ref

--------------------
type 'T ref = Ref<'T>

Full name: Microsoft.FSharp.Core.ref<_>
type IEnumerator<'T> =
  member Current : 'T

Full name: System.Collections.Generic.IEnumerator<_>
val x : IEnumerator<'T> (requires member ( - ) and member ( + ))
property IEnumerator.Current: 'T
property Ref.Value: 'T
type IEnumerator =
  member Current : obj
  member MoveNext : unit -> bool
  member Reset : unit -> unit

Full name: System.Collections.IEnumerator
val x : System.Collections.IEnumerator
property System.Collections.IEnumerator.Current: obj
val box : value:'T -> obj

Full name: Microsoft.FSharp.Core.Operators.box
System.Collections.IEnumerator.MoveNext() : bool
System.Collections.IEnumerator.Reset() : unit
type IDisposable =
  member Dispose : unit -> unit

Full name: System.IDisposable
val x : System.IDisposable
System.IDisposable.Dispose() : unit
type IEnumerable =
  member GetEnumerator : unit -> IEnumerator

Full name: System.Collections.IEnumerable
val x : System.Collections.IEnumerable
System.Collections.IEnumerable.GetEnumerator() : System.Collections.IEnumerator
val rangeStep : lo:'T -> step:'T -> hi:'T -> IEnumerable<'T> (requires comparison and member ( - ) and member ( + ))

Full name: Script.rangeStep


 A helper function that generates a sequence for the specified range of
 int or int64 values. This is notably faster than using `lo .. step .. hi`.
val lo : 'T (requires comparison and member ( - ) and member ( + ))
val step : 'T (requires comparison and member ( - ) and member ( + ))
val hi : 'T (requires comparison and member ( - ) and member ( + ))
val range : lo:'T -> hi:'T -> IEnumerable<'T> (requires comparison and member ( - ) and member ( + ) and member get_One)

Full name: Script.range


 A helper function that generates a sequence for the specified range of
 int or int64 values. This is notably faster than using `lo .. hi`.
val lo : 'T (requires comparison and member ( - ) and member ( + ) and member get_One)
val hi : 'T (requires comparison and member ( - ) and member ( + ) and member get_One)
module LanguagePrimitives

from Microsoft.FSharp.Core
val GenericOne<'T (requires member get_One)> : 'T (requires member get_One)

Full name: Microsoft.FSharp.Core.LanguagePrimitives.GenericOne
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val x : int
module Seq

from Microsoft.FSharp.Collections
val length : source:seq<'T> -> int

Full name: Microsoft.FSharp.Collections.Seq.length
val x : int64
val x : float
val a : 'a (requires member get_One and member ( + ) and member ( - ) and comparison)
val b : 'a (requires member get_One and member ( + ) and member ( - ) and comparison)
val a : 'a (requires member ( - ) and member ( + ) and comparison)
val s : 'a (requires member ( - ) and member ( + ) and comparison)
val b : 'a (requires member ( - ) and member ( + ) and comparison)

More information

Link:http://fssnip.net/rJ
Posted:8 years ago
Author:Tomas Petricek
Tags: sequences