## Developing an Algorithm in F#: Fast Rotational Alignments with Gosper’s Hack

This post is for the 7th day of the 2014 F# Advent Calendar.

It has been said that functional languages can’t be as fast as their imperative cousins because of all of the allocation and garbage collection, this is patently false (as far as F# is concerned at least) largely because the CLR has value types.

Recently Louis Thrall and I ran into an interesting problem at work: how do you efficiently compare all rotations of one array to another to select the best? This is easy when the arrays are the same size, just shift the indices around:

Which is equivalent to a nested for loop, the top one rotating and the inner doing comparisons.

But what about differently sized arrays? It turns out this is more complicated, even for comparing a size 2 array to size 3:

Like comparing beads on two strings, there is much shifting as the indices are rotated around. The extra freedom from this shifting means that more comparisons must be made even though there total number of combined elements is smaller.

This problem also has an interesting structure, as it costs the most when one array is about half the size of the other. When the smaller array is size 1 then it simply needs to be moved around, and when the arrays are equal in size it’s a simple matter of rotations.

After some research Lou noted that this we were “counting the number of cyclic suborders of size k of a cyclic order of size n” which produces k(n choose k) different configurations.

Now that we had bounds and knew what we were doing was reasonable we had to figure out an algorithm for this process. It occurred to us that it would be ideal to pre-compute the comparison values to avoid repeated comparisons. Given this matrix of comparison values it wasn’t too difficult to determine a procedure for checking all possible configurations.

Each time a pair is chosen, it further constrains what the rest of the assignments may be. The bottom level is somewhat obvious, just select each of the possible starting combinations down the y-axis. In the next column you potentially have a range of possible “downward” (using clock arithmetic) selections bounded by the difference in lengths and what has already been fixed.

Now it was time to implement, and the first stab was nice and concise and functional and worked pretty well.

``` 1: open System
2:
3: // arr1 is always equal in size or smaller than arr2
4: let bestRot (f: 'a -> 'a -> float) (arr1: 'a []) (arr2: 'a []) =
5:     // Pre-calculate similarities
6:     let scores =
7:         Array2D.init arr1.Length arr2.Length
8:                     (fun i j -> f arr1.[i] arr2.[j])
9:     // inner function for recursively finding paths
10:     // col = previous column, prow = previous row
11:     // df = degrees of freedom, path = path accumulator
12:     let rec inner col prow df path =
13:         seq {
14:             // when we're out of columns to assign we're done
15:             if col >= arr1.Length then yield path |> List.rev
16:             else
17:                 // We have df "degrees of freedom" left
18:                 for d = 1 to df + 1 do
19:                     // Clock arithmetic for the row
20:                     let nrow = (prow + d) % arr2.Length
21:                     // Recurse yielding out all further paths
22:                     yield! inner (col + 1) nrow (df + 1 - d)
23:                                  ((col, nrow) :: path)
24:         }
25:     let res, score =
26:         // the difference in length
27:         // is the starting "degrees of freedom"
28:         let diff = arr2.Length - arr1.Length
29:         seq {
30:             // for each y-axis starting point
31:             for y = 0 to arr2.Length - 1 do
32:                 // 1 selected, r is the starting point (on y),
33:                 //    starting is always 0 on x.
34:                 // ((0, y) :: []) is the accumulator
35:                 //    with the initial (0, y) coordinates
36:                 yield! inner 1 y diff ((0, y) :: [])
37:         }
38:         // Sum each path to find total similarity
39:         |> Seq.map
40:             (fun l -> l, l |> Seq.sumBy (fun (i,j) -> scores.[i,j]))
41:         // Get the path with the highest similarity
42:         |> Seq.maxBy snd
43:     // Create output array and copy in the results
44:     let out = Array.create arr1.Length Int32.MinValue
45:     for (i,j) in res do
46:         out.[i] <- j
47:     // Return results
48:     out, score```
namespace System
val bestRot : ('a -> 'a -> float) -> 'a [] -> 'a [] -> int [] * float

Full name: Snippet.bestRot

val f : ('a -> 'a -> float)
Multiple items
val float : 'T -> float (requires member op_Explicit)

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

——————–
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>

type: float<'Measure>
implements: IComparable
implements: IConvertible
implements: IFormattable
implements: IComparable<float<'Measure>>
implements: IEquatable<float<'Measure>>
inherits: ValueType

——————–
type float = Double

Full name: Microsoft.FSharp.Core.float

type: float
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<float>
implements: IEquatable<float>
inherits: ValueType

val arr1 : 'a []

type: 'a []
implements: ICloneable
implements: Collections.IList
implements: Collections.ICollection
implements: Collections.IStructuralComparable
implements: Collections.IStructuralEquatable
implements: Collections.Generic.IList<'a>
implements: Collections.Generic.ICollection<'a>
implements: seq<'a>
implements: Collections.IEnumerable
inherits: Array

val arr2 : 'a []

type: 'a []
implements: ICloneable
implements: Collections.IList
implements: Collections.ICollection
implements: Collections.IStructuralComparable
implements: Collections.IStructuralEquatable
implements: Collections.Generic.IList<'a>
implements: Collections.Generic.ICollection<'a>
implements: seq<'a>
implements: Collections.IEnumerable
inherits: Array

val scores : float [,]

type: float [,]
implements: ICloneable
implements: Collections.IList
implements: Collections.ICollection
implements: Collections.IEnumerable
implements: Collections.IStructuralComparable
implements: Collections.IStructuralEquatable
inherits: Array

module Array2D

from Microsoft.FSharp.Collections

val init : int -> int -> (int -> int -> 'T) -> 'T [,]

Full name: Microsoft.FSharp.Collections.Array2D.init

property Array.Length: int
val i : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val j : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val inner : (int -> int -> int -> (int * int) list -> seq<(int * int) list>)
val col : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val prow : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val df : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val path : (int * int) list

type: (int * int) list
implements: Collections.IStructuralEquatable
implements: IComparable<List<int * int>>
implements: IComparable
implements: Collections.IStructuralComparable
implements: Collections.Generic.IEnumerable<int * int>
implements: Collections.IEnumerable

Multiple items
val seq : seq<'T> -> seq<'T>

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

——————–
type seq<'T> = Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

type: seq<'T>
inherits: Collections.IEnumerable

Multiple items
module List

from Microsoft.FSharp.Collections

——————–
type List<'T> =
| ( [] )
| ( :: ) of 'T * 'T list
with
interface Collections.IEnumerable
interface Collections.Generic.IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list
end

Full name: Microsoft.FSharp.Collections.List<_>

type: List<'T>
implements: Collections.IStructuralEquatable
implements: IComparable<List<'T>>
implements: IComparable
implements: Collections.IStructuralComparable
implements: Collections.Generic.IEnumerable<'T>
implements: Collections.IEnumerable

val rev : 'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev

val d : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val nrow : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val res : (int * int) list

type: (int * int) list
implements: Collections.IStructuralEquatable
implements: IComparable<List<int * int>>
implements: IComparable
implements: Collections.IStructuralComparable
implements: Collections.Generic.IEnumerable<int * int>
implements: Collections.IEnumerable

val score : float

type: float
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<float>
implements: IEquatable<float>
inherits: ValueType

val diff : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val y : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

module Seq

from Microsoft.FSharp.Collections

val map : ('T -> 'U) -> seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map

val l : (int * int) list

type: (int * int) list
implements: Collections.IStructuralEquatable
implements: IComparable<List<int * int>>
implements: IComparable
implements: Collections.IStructuralComparable
implements: Collections.Generic.IEnumerable<int * int>
implements: Collections.IEnumerable

val sumBy : ('T -> 'U) -> seq<'T> -> 'U (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.Seq.sumBy

val maxBy : ('T -> 'U) -> seq<'T> -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.Seq.maxBy

val snd : ('T1 * 'T2) -> 'T2

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

val out : int []

type: int []
implements: ICloneable
implements: Collections.IList
implements: Collections.ICollection
implements: Collections.IStructuralComparable
implements: Collections.IStructuralEquatable
implements: Collections.Generic.IList<int>
implements: Collections.Generic.ICollection<int>
implements: seq<int>
implements: Collections.IEnumerable
inherits: Array

type Array =
class
member Clone : unit -> obj
member CopyTo : System.Array * int -> unit
member CopyTo : System.Array * int64 -> unit
member GetEnumerator : unit -> System.Collections.IEnumerator
member GetLength : int -> int
member GetLongLength : int -> int64
member GetLowerBound : int -> int
member GetUpperBound : int -> int
member GetValue : int [] -> obj
member GetValue : int -> obj
member GetValue : int64 -> obj
member GetValue : int64 [] -> obj
member GetValue : int * int -> obj
member GetValue : int64 * int64 -> obj
member GetValue : int * int * int -> obj
member GetValue : int64 * int64 * int64 -> obj
member Initialize : unit -> unit
member IsFixedSize : bool
member IsSynchronized : bool
member Length : int
member LongLength : int64
member Rank : int
member SetValue : obj * int -> unit
member SetValue : obj * int [] -> unit
member SetValue : obj * int64 -> unit
member SetValue : obj * int64 [] -> unit
member SetValue : obj * int * int -> unit
member SetValue : obj * int64 * int64 -> unit
member SetValue : obj * int * int * int -> unit
member SetValue : obj * int64 * int64 * int64 -> unit
member SyncRoot : obj
static member BinarySearch : System.Array * obj -> int
static member BinarySearch<'T> : 'T [] * 'T -> int
static member BinarySearch : System.Array * obj * System.Collections.IComparer -> int
static member BinarySearch<'T> : 'T [] * 'T * System.Collections.Generic.IComparer<'T> -> int
static member BinarySearch : System.Array * int * int * obj -> int
static member BinarySearch<'T> : 'T [] * int * int * 'T -> int
static member BinarySearch : System.Array * int * int * obj * System.Collections.IComparer -> int
static member BinarySearch<'T> : 'T [] * int * int * 'T * System.Collections.Generic.IComparer<'T> -> int
static member Clear : System.Array * int * int -> unit
static member ConstrainedCopy : System.Array * int * System.Array * int * int -> unit
static member ConvertAll<'TInput,'TOutput> : 'TInput [] * System.Converter<'TInput,'TOutput> -> 'TOutput []
static member Copy : System.Array * System.Array * int -> unit
static member Copy : System.Array * System.Array * int64 -> unit
static member Copy : System.Array * int * System.Array * int * int -> unit
static member Copy : System.Array * int64 * System.Array * int64 * int64 -> unit
static member CreateInstance : System.Type * int -> System.Array
static member CreateInstance : System.Type * int [] -> System.Array
static member CreateInstance : System.Type * int64 [] -> System.Array
static member CreateInstance : System.Type * int * int -> System.Array
static member CreateInstance : System.Type * int [] * int [] -> System.Array
static member CreateInstance : System.Type * int * int * int -> System.Array
static member Exists<'T> : 'T [] * System.Predicate<'T> -> bool
static member Find<'T> : 'T [] * System.Predicate<'T> -> 'T
static member FindAll<'T> : 'T [] * System.Predicate<'T> -> 'T []
static member FindIndex<'T> : 'T [] * System.Predicate<'T> -> int
static member FindIndex<'T> : 'T [] * int * System.Predicate<'T> -> int
static member FindIndex<'T> : 'T [] * int * int * System.Predicate<'T> -> int
static member FindLast<'T> : 'T [] * System.Predicate<'T> -> 'T
static member FindLastIndex<'T> : 'T [] * System.Predicate<'T> -> int
static member FindLastIndex<'T> : 'T [] * int * System.Predicate<'T> -> int
static member FindLastIndex<'T> : 'T [] * int * int * System.Predicate<'T> -> int
static member ForEach<'T> : 'T [] * System.Action<'T> -> unit
static member IndexOf : System.Array * obj -> int
static member IndexOf<'T> : 'T [] * 'T -> int
static member IndexOf : System.Array * obj * int -> int
static member IndexOf<'T> : 'T [] * 'T * int -> int
static member IndexOf : System.Array * obj * int * int -> int
static member IndexOf<'T> : 'T [] * 'T * int * int -> int
static member LastIndexOf : System.Array * obj -> int
static member LastIndexOf<'T> : 'T [] * 'T -> int
static member LastIndexOf : System.Array * obj * int -> int
static member LastIndexOf<'T> : 'T [] * 'T * int -> int
static member LastIndexOf : System.Array * obj * int * int -> int
static member LastIndexOf<'T> : 'T [] * 'T * int * int -> int
static member Resize<'T> : 'T [] * int -> unit
static member Reverse : System.Array -> unit
static member Reverse : System.Array * int * int -> unit
static member Sort : System.Array -> unit
static member Sort<'T> : 'T [] -> unit
static member Sort : System.Array * System.Array -> unit
static member Sort : System.Array * System.Collections.IComparer -> unit
static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] -> unit
static member Sort<'T> : 'T [] * System.Collections.Generic.IComparer<'T> -> unit
static member Sort<'T> : 'T [] * System.Comparison<'T> -> unit
static member Sort : System.Array * int * int -> unit
static member Sort : System.Array * System.Array * System.Collections.IComparer -> unit
static member Sort<'T> : 'T [] * int * int -> unit
static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] * System.Collections.Generic.IComparer<'TKey> -> unit
static member Sort : System.Array * System.Array * int * int -> unit
static member Sort : System.Array * int * int * System.Collections.IComparer -> unit
static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] * int * int -> unit
static member Sort<'T> : 'T [] * int * int * System.Collections.Generic.IComparer<'T> -> unit
static member Sort : System.Array * System.Array * int * int * System.Collections.IComparer -> unit
static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] * int * int * System.Collections.Generic.IComparer<'TKey> -> unit
static member TrueForAll<'T> : 'T [] * System.Predicate<'T> -> bool
end

Full name: System.Array

type: Array
implements: ICloneable
implements: Collections.IList
implements: Collections.ICollection
implements: Collections.IEnumerable
implements: Collections.IStructuralComparable
implements: Collections.IStructuralEquatable

val create : int -> 'T -> 'T []

Full name: Microsoft.FSharp.Collections.Array.create

type Int32 =
struct
member CompareTo : obj -> int
member CompareTo : int -> int
member Equals : obj -> bool
member Equals : int -> bool
member GetHashCode : unit -> int
member GetTypeCode : unit -> System.TypeCode
member ToString : unit -> string
member ToString : string -> string
member ToString : System.IFormatProvider -> string
member ToString : string * System.IFormatProvider -> string
static val MaxValue : int
static val MinValue : int
static member Parse : string -> int
static member Parse : string * System.Globalization.NumberStyles -> int
static member Parse : string * System.IFormatProvider -> int
static member Parse : string * System.Globalization.NumberStyles * System.IFormatProvider -> int
static member TryParse : string * int -> bool
static member TryParse : string * System.Globalization.NumberStyles * System.IFormatProvider * int -> bool
end

Full name: System.Int32

type: Int32
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

field Int32.MinValue = -2147483648

However, after real world trials we found that it was taking an astonishing 20% of our runtime. We had to find a better way. We soon found Gosper’s hack which did mostly what we wanted. It gave us the combinations, and we found we could just rotate each of those around to give us all of our cyclic suborders.

And so we went about rewriting our nice functional sample to use Gosper’s Hack to avoid the need to generate paths and also to be (nearly) minimally allocating to avoid garbage collection overhead.

``` 1: open System
2:
3: // arr1 is always equal in size or smaller than arr2
4: let bestRotGos (f: 'a -> 'a -> float) (arr1: 'a []) (arr2: 'a []) =
5:     // Start Gosper's Hack Machinery Bootstrap
6:     let bitsConfig = Array.create arr1.Length Int32.MinValue
7:
8:     let inline setBits v =
9:         let inline getBit x i = x &&& (1 <<< i) <> 0
10:         let mutable idx = 0
11:         for i = 0 to 31 do
12:             if getBit v i then
13:                 bitsConfig.[idx] <- i
14:                 idx <- idx + 1
15:
16:     let inline nextGosper set =
17:         let c = set &&& -set
18:         let r = set + c
19:         r + (((r^^^set)/c)>>>2)
20:
21:     let limit =
22:         let n = arr2.Length
23:         (1 <<< n)
24:
25:     let mutable set =
26:         let k = arr1.Length
27:         (1 <<< k) - 1
28:     // End Gosper's Hack Machinery Bootstrap
29:
30:     // Pre-calculate sims and init placeholder variables
31:     let scores = Array2D.init arr1.Length arr2.Length
32:                     (fun i j -> f arr1.[i] arr2.[j])
33:
34:     let mutable maxScore = Double.NegativeInfinity
35:     let bestConfig = Array.create arr1.Length Int32.MinValue
36:
37:     while (set < limit) do
38:         setBits set // Turn "set" bits into indices in "bitsConfig"
39:
40:         // For each rotation
41:         for i = 0 to bitsConfig.Length - 1 do
42:
43:             // calculate score and compare with previous best
44:             let mutable totalScore = 0.0
45:             for i = 0 to bitsConfig.Length - 1 do
46:                 let tokenScore = scores.[i,bitsConfig.[i]]
47:                 totalScore <- totalScore + tokenScore
48:             if totalScore > maxScore then
49:                 // and replace if better
50:                 maxScore <- totalScore
51:                 Array.blit bitsConfig 0
52:                            bestConfig 0
53:                            bitsConfig.Length
54:
55:             // Rotate the array
56:             let firstElement = bitsConfig.[0]
57:             for i = 0 to bitsConfig.Length - 2 do
58:                 bitsConfig.[i] <- bitsConfig.[i + 1]
59:             bitsConfig.[bitsConfig.Length - 1] <- firstElement
60:
61:         set <- nextGosper set // Put the next combination in "set"
62:     bestConfig, maxScore```
namespace System
val bestRotGos : ('a -> 'a -> float) -> 'a [] -> 'a [] -> int [] * float

Full name: Snippet.bestRotGos

val f : ('a -> 'a -> float)
Multiple items
val float : 'T -> float (requires member op_Explicit)

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

——————–
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>

type: float<'Measure>
implements: IComparable
implements: IConvertible
implements: IFormattable
implements: IComparable<float<'Measure>>
implements: IEquatable<float<'Measure>>
inherits: ValueType

——————–
type float = Double

Full name: Microsoft.FSharp.Core.float

type: float
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<float>
implements: IEquatable<float>
inherits: ValueType

val arr1 : 'a []

type: 'a []
implements: ICloneable
implements: Collections.IList
implements: Collections.ICollection
implements: Collections.IStructuralComparable
implements: Collections.IStructuralEquatable
implements: Collections.Generic.IList<'a>
implements: Collections.Generic.ICollection<'a>
implements: seq<'a>
implements: Collections.IEnumerable
inherits: Array

val arr2 : 'a []

type: 'a []
implements: ICloneable
implements: Collections.IList
implements: Collections.ICollection
implements: Collections.IStructuralComparable
implements: Collections.IStructuralEquatable
implements: Collections.Generic.IList<'a>
implements: Collections.Generic.ICollection<'a>
implements: seq<'a>
implements: Collections.IEnumerable
inherits: Array

val bitsConfig : int []

type: int []
implements: ICloneable
implements: Collections.IList
implements: Collections.ICollection
implements: Collections.IStructuralComparable
implements: Collections.IStructuralEquatable
implements: Collections.Generic.IList<int>
implements: Collections.Generic.ICollection<int>
implements: seq<int>
implements: Collections.IEnumerable
inherits: Array

type Array =
class
member Clone : unit -> obj
member CopyTo : System.Array * int -> unit
member CopyTo : System.Array * int64 -> unit
member GetEnumerator : unit -> System.Collections.IEnumerator
member GetLength : int -> int
member GetLongLength : int -> int64
member GetLowerBound : int -> int
member GetUpperBound : int -> int
member GetValue : int [] -> obj
member GetValue : int -> obj
member GetValue : int64 -> obj
member GetValue : int64 [] -> obj
member GetValue : int * int -> obj
member GetValue : int64 * int64 -> obj
member GetValue : int * int * int -> obj
member GetValue : int64 * int64 * int64 -> obj
member Initialize : unit -> unit
member IsFixedSize : bool
member IsSynchronized : bool
member Length : int
member LongLength : int64
member Rank : int
member SetValue : obj * int -> unit
member SetValue : obj * int [] -> unit
member SetValue : obj * int64 -> unit
member SetValue : obj * int64 [] -> unit
member SetValue : obj * int * int -> unit
member SetValue : obj * int64 * int64 -> unit
member SetValue : obj * int * int * int -> unit
member SetValue : obj * int64 * int64 * int64 -> unit
member SyncRoot : obj
static member BinarySearch : System.Array * obj -> int
static member BinarySearch<'T> : 'T [] * 'T -> int
static member BinarySearch : System.Array * obj * System.Collections.IComparer -> int
static member BinarySearch<'T> : 'T [] * 'T * System.Collections.Generic.IComparer<'T> -> int
static member BinarySearch : System.Array * int * int * obj -> int
static member BinarySearch<'T> : 'T [] * int * int * 'T -> int
static member BinarySearch : System.Array * int * int * obj * System.Collections.IComparer -> int
static member BinarySearch<'T> : 'T [] * int * int * 'T * System.Collections.Generic.IComparer<'T> -> int
static member Clear : System.Array * int * int -> unit
static member ConstrainedCopy : System.Array * int * System.Array * int * int -> unit
static member ConvertAll<'TInput,'TOutput> : 'TInput [] * System.Converter<'TInput,'TOutput> -> 'TOutput []
static member Copy : System.Array * System.Array * int -> unit
static member Copy : System.Array * System.Array * int64 -> unit
static member Copy : System.Array * int * System.Array * int * int -> unit
static member Copy : System.Array * int64 * System.Array * int64 * int64 -> unit
static member CreateInstance : System.Type * int -> System.Array
static member CreateInstance : System.Type * int [] -> System.Array
static member CreateInstance : System.Type * int64 [] -> System.Array
static member CreateInstance : System.Type * int * int -> System.Array
static member CreateInstance : System.Type * int [] * int [] -> System.Array
static member CreateInstance : System.Type * int * int * int -> System.Array
static member Exists<'T> : 'T [] * System.Predicate<'T> -> bool
static member Find<'T> : 'T [] * System.Predicate<'T> -> 'T
static member FindAll<'T> : 'T [] * System.Predicate<'T> -> 'T []
static member FindIndex<'T> : 'T [] * System.Predicate<'T> -> int
static member FindIndex<'T> : 'T [] * int * System.Predicate<'T> -> int
static member FindIndex<'T> : 'T [] * int * int * System.Predicate<'T> -> int
static member FindLast<'T> : 'T [] * System.Predicate<'T> -> 'T
static member FindLastIndex<'T> : 'T [] * System.Predicate<'T> -> int
static member FindLastIndex<'T> : 'T [] * int * System.Predicate<'T> -> int
static member FindLastIndex<'T> : 'T [] * int * int * System.Predicate<'T> -> int
static member ForEach<'T> : 'T [] * System.Action<'T> -> unit
static member IndexOf : System.Array * obj -> int
static member IndexOf<'T> : 'T [] * 'T -> int
static member IndexOf : System.Array * obj * int -> int
static member IndexOf<'T> : 'T [] * 'T * int -> int
static member IndexOf : System.Array * obj * int * int -> int
static member IndexOf<'T> : 'T [] * 'T * int * int -> int
static member LastIndexOf : System.Array * obj -> int
static member LastIndexOf<'T> : 'T [] * 'T -> int
static member LastIndexOf : System.Array * obj * int -> int
static member LastIndexOf<'T> : 'T [] * 'T * int -> int
static member LastIndexOf : System.Array * obj * int * int -> int
static member LastIndexOf<'T> : 'T [] * 'T * int * int -> int
static member Resize<'T> : 'T [] * int -> unit
static member Reverse : System.Array -> unit
static member Reverse : System.Array * int * int -> unit
static member Sort : System.Array -> unit
static member Sort<'T> : 'T [] -> unit
static member Sort : System.Array * System.Array -> unit
static member Sort : System.Array * System.Collections.IComparer -> unit
static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] -> unit
static member Sort<'T> : 'T [] * System.Collections.Generic.IComparer<'T> -> unit
static member Sort<'T> : 'T [] * System.Comparison<'T> -> unit
static member Sort : System.Array * int * int -> unit
static member Sort : System.Array * System.Array * System.Collections.IComparer -> unit
static member Sort<'T> : 'T [] * int * int -> unit
static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] * System.Collections.Generic.IComparer<'TKey> -> unit
static member Sort : System.Array * System.Array * int * int -> unit
static member Sort : System.Array * int * int * System.Collections.IComparer -> unit
static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] * int * int -> unit
static member Sort<'T> : 'T [] * int * int * System.Collections.Generic.IComparer<'T> -> unit
static member Sort : System.Array * System.Array * int * int * System.Collections.IComparer -> unit
static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] * int * int * System.Collections.Generic.IComparer<'TKey> -> unit
static member TrueForAll<'T> : 'T [] * System.Predicate<'T> -> bool
end

Full name: System.Array

type: Array
implements: ICloneable
implements: Collections.IList
implements: Collections.ICollection
implements: Collections.IEnumerable
implements: Collections.IStructuralComparable
implements: Collections.IStructuralEquatable

val create : int -> 'T -> 'T []

Full name: Microsoft.FSharp.Collections.Array.create

property Array.Length: int
type Int32 =
struct
member CompareTo : obj -> int
member CompareTo : int -> int
member Equals : obj -> bool
member Equals : int -> bool
member GetHashCode : unit -> int
member GetTypeCode : unit -> System.TypeCode
member ToString : unit -> string
member ToString : string -> string
member ToString : System.IFormatProvider -> string
member ToString : string * System.IFormatProvider -> string
static val MaxValue : int
static val MinValue : int
static member Parse : string -> int
static member Parse : string * System.Globalization.NumberStyles -> int
static member Parse : string * System.IFormatProvider -> int
static member Parse : string * System.Globalization.NumberStyles * System.IFormatProvider -> int
static member TryParse : string * int -> bool
static member TryParse : string * System.Globalization.NumberStyles * System.IFormatProvider * int -> bool
end

Full name: System.Int32

type: Int32
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

field Int32.MinValue = -2147483648
val setBits : (int -> unit)
val v : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val getBit : (int -> int32 -> bool)
val x : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val i : int32

type: int32
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val mutable idx : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val i : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val nextGosper : ('b -> 'd) (requires member ( ~- ) and member ( &&& ) and member ( + ) and member ( ^^^ ) and member ( / ) and member ( + ) and member ( >>> ))
val set : 'b (requires member ( ~- ) and member ( &&& ) and member ( + ) and member ( ^^^ ) and member ( / ) and member ( + ) and member ( >>> ))
val c : 'b (requires member ( ~- ) and member ( &&& ) and member ( + ) and member ( ^^^ ) and member ( / ) and member ( + ) and member ( >>> ))
val r : 'b (requires member ( ~- ) and member ( &&& ) and member ( + ) and member ( ^^^ ) and member ( / ) and member ( + ) and member ( >>> ))
val limit : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val n : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val mutable set : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val k : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val scores : float [,]

type: float [,]
implements: ICloneable
implements: Collections.IList
implements: Collections.ICollection
implements: Collections.IEnumerable
implements: Collections.IStructuralComparable
implements: Collections.IStructuralEquatable
inherits: Array

module Array2D

from Microsoft.FSharp.Collections

val init : int -> int -> (int -> int -> 'T) -> 'T [,]

Full name: Microsoft.FSharp.Collections.Array2D.init

val j : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

val mutable maxScore : float

type: float
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<float>
implements: IEquatable<float>
inherits: ValueType

type Double =
struct
member CompareTo : obj -> int
member CompareTo : float -> int
member Equals : obj -> bool
member Equals : float -> bool
member GetHashCode : unit -> int
member GetTypeCode : unit -> System.TypeCode
member ToString : unit -> string
member ToString : string -> string
member ToString : System.IFormatProvider -> string
member ToString : string * System.IFormatProvider -> string
static val MinValue : float
static val MaxValue : float
static val Epsilon : float
static val NegativeInfinity : float
static val PositiveInfinity : float
static val NaN : float
static member IsInfinity : float -> bool
static member IsNaN : float -> bool
static member IsNegativeInfinity : float -> bool
static member IsPositiveInfinity : float -> bool
static member Parse : string -> float
static member Parse : string * System.Globalization.NumberStyles -> float
static member Parse : string * System.IFormatProvider -> float
static member Parse : string * System.Globalization.NumberStyles * System.IFormatProvider -> float
static member TryParse : string * float -> bool
static member TryParse : string * System.Globalization.NumberStyles * System.IFormatProvider * float -> bool
end

Full name: System.Double

type: Double
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<float>
implements: IEquatable<float>
inherits: ValueType

field Double.NegativeInfinity = -Infinity
val bestConfig : int []

type: int []
implements: ICloneable
implements: Collections.IList
implements: Collections.ICollection
implements: Collections.IStructuralComparable
implements: Collections.IStructuralEquatable
implements: Collections.Generic.IList<int>
implements: Collections.Generic.ICollection<int>
implements: seq<int>
implements: Collections.IEnumerable
inherits: Array

val mutable totalScore : float

type: float
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<float>
implements: IEquatable<float>
inherits: ValueType

val tokenScore : float

type: float
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<float>
implements: IEquatable<float>
inherits: ValueType

val blit : 'T [] -> int -> 'T [] -> int -> int -> unit

Full name: Microsoft.FSharp.Collections.Array.blit

val firstElement : int

type: int
implements: IComparable
implements: IFormattable
implements: IConvertible
implements: IComparable<int>
implements: IEquatable<int>
inherits: ValueType

A quick test shows that the new algorithm is about seven times faster across a variety of test inputs:

``` 1: let f x y = if x = y then 1.0 else 0.0
2:
3: let cmp = [|"one"; "two"; "three"; "four"|]
4: let cmps =
5:     [| for i = 0 to cmp.Length - 1 do
6:            for j = i to cmp.Length - 1 do
7:                // Longer array is second
8:                yield cmp.[j..], cmp.[i..]
9:     |]
10:
11: #time
12: for i = 0 to 1000000 do
13:     for c1,c2 in cmps do
14:         bestRot f c1 c2 |> ignore
15: //Real: 00:00:41.800, CPU: 00:00:41.812,
16: // GC gen0: 10175, gen1: 6, gen2: 1
17: #time
18:
19: #time
20: for i = 0 to 1000000 do
21:     for c1,c2 in cmps do
22:         bestRotGos f c1 c2 |> ignore
23: //Real: 00:00:06.378, CPU: 00:00:06.375,
24: // GC gen0: 689, gen1: 1, gen2: 0
25: #time
26: ```
val f : 'a -> 'a -> float (requires equality)

Full name: Snippet.f

val x : 'a (requires equality)
val y : 'a (requires equality)
val cmp : string []

Full name: Snippet.cmp

type: string []
implements: System.ICloneable
implements: System.Collections.IList
implements: System.Collections.ICollection
implements: System.Collections.IStructuralComparable
implements: System.Collections.IStructuralEquatable
implements: System.Collections.Generic.IList<string>
implements: System.Collections.Generic.ICollection<string>
implements: seq<string>
implements: System.Collections.IEnumerable
inherits: System.Array

val cmps : (string [] * string []) []

Full name: Snippet.cmps

type: (string [] * string []) []
implements: System.ICloneable
implements: System.Collections.IList
implements: System.Collections.ICollection
implements: System.Collections.IStructuralComparable
implements: System.Collections.IStructuralEquatable
implements: System.Collections.Generic.IList<string [] * string []>
implements: System.Collections.Generic.ICollection<string [] * string []>
implements: seq<string [] * string []>
implements: System.Collections.IEnumerable
inherits: System.Array

val i : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

property System.Array.Length: int
val j : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val c1 : string []

type: string []
implements: System.ICloneable
implements: System.Collections.IList
implements: System.Collections.ICollection
implements: System.Collections.IStructuralComparable
implements: System.Collections.IStructuralEquatable
implements: System.Collections.Generic.IList<string>
implements: System.Collections.Generic.ICollection<string>
implements: seq<string>
implements: System.Collections.IEnumerable
inherits: System.Array

val c2 : string []

type: string []
implements: System.ICloneable
implements: System.Collections.IList
implements: System.Collections.ICollection
implements: System.Collections.IStructuralComparable
implements: System.Collections.IStructuralEquatable
implements: System.Collections.Generic.IList<string>
implements: System.Collections.Generic.ICollection<string>
implements: seq<string>
implements: System.Collections.IEnumerable
inherits: System.Array

val ignore : 'T -> unit

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

Of course, there are a few more things that could be done to make this even faster mostly related to further reducing allocations. For example, we could potentially use larger fixed sized arrays if we knew our input was bounded and pass in the arrays as references letting the calling function handle proper recycling.

However, at this point the function no longer appeared anywhere near significant when profiling our overall usage and so we found this was fast enough. It’s not worth making things uglier and more prone to breakage for minor gains when what we have right now is a referentially transparent function with predictable behavior.

Enjoy this post? Continue the conversation with me on twitter.