¿Qué puede hacer que el código F # no optimizado sea más rápido que el código optimizado?

Question

Así que he decidido probar F # y porté uno de los algoritmos que le escribí en C#. En un momento dado, me di cuenta de que la compilación de depuración se ejecuta más rápido que la versión de lanzamiento. Luego jugué con la configuración de optimización y obtuve estos resultados:

Los tiempos muestran el tiempo total de ejecución del algoritmo sobre 100000 ejecuciones. Estoy usando el compilador F # que viene con Visual Studio 2010 SP1. La plataforma objetivo es Cualquier CPU.

Opt off, tail calls off: 5.81s 
Opt off, tail calls on : 5.79s 
Opt on , tail calls off: 6.48s 
Opt on , tail calls on : 6.40s 

Estoy realmente desconcertado por esto - ¿por qué la optimización hace que el código funcione más lento? La versión C# del algoritmo no muestra este comportamiento (aunque se implementa de una manera ligeramente diferente)

Aquí hay una versión reducida del código F #, es un algoritmo que encuentra patrones en las moléculas. Todo el código en el que se basa este programa F # está escrito en F #.

namespace Motives 
    module Internal = 
    type Motive = 
     { ResidueSet: Set<Residue>; AtomSet: Set<IAtom> } 
     member this.Atoms : IAtom seq = 
     seq { 
      for r in this.ResidueSet do yield! r.Atoms 
      yield! this.AtomSet 
     } 
     static member fromResidues (residues : Residue seq) = residues |> Seq.fold (fun (m: Set<Residue>) r -> m.Add(r)) Set.empty |> fun rs -> { ResidueSet = rs; AtomSet = Set.empty } 
     static member fromAtoms (atoms : IAtom seq) = atoms |> Seq.fold (fun (m: Set<IAtom>) a -> m.Add(a)) Set.empty |> fun atoms -> { ResidueSet = Set.empty; AtomSet = atoms } 
     static member merge (m1: Motive) (m2: Motive) = { ResidueSet = Set.union m1.ResidueSet m2.ResidueSet; AtomSet = Set.union m1.AtomSet m2.AtomSet } 
     static member distance (m1: Motive) (m2: Motive) = Seq.min (seq { for a in m1.Atoms do for b in m2.Atoms -> a.Position.DistanceTo(b.Position) }) 

    type Structure with 
     static member fromMotive (m: Motive) (parent: IStructure) (addBonds: bool) : IStructure = 
     let atoms = AtomCollection.FromUniqueAtoms(m.Atoms) 
     let bonds = 
      match addBonds with 
      | true -> BondCollection.Create(atoms |> Seq.map (fun a -> parent.Bonds.[a]) |> Seq.concat) 
      | _ -> BondCollection.Empty 
     Structure.Create (parent.Id + "_" + atoms.[0].Id.ToString(), atoms, bonds) 

    // KDTree used for range queries 
    // AminoChains used for regex queries 
    type StructureContext = 
     { Structure: IStructure; KDTree: Lazy<KDAtomTree>; AminoChains: Lazy<(Residue array * string) list> } 
     static member create (structure: IStructure) = 
     match structure.IsPdbStructure() with 
     | false -> { Structure = structure; KDTree = Lazy.Create(fun() -> structure.Atoms.ToKDTree()); AminoChains = Lazy.CreateFromValue([]) } 
     | true -> 
      let aminoChains = new System.Func<(Residue array * string) list> (fun() -> 
      let residues = structure.PdbResidues() |> Seq.filter (fun r -> r.IsAmino) 
      residues 
      |> Seq.groupBy (fun r -> r.ChainIdentifier) 
      |> Seq.map (fun (k,rs) -> rs |> Array.ofSeq, String.concat "" (rs |> Seq.map (fun r -> r.ShortName))) 
      |> List.ofSeq) 
      { Structure = structure; KDTree = Lazy.Create(fun() -> structure.Atoms.ToKDTree()); AminoChains = Lazy.Create(aminoChains) } 

    // Remember the named motives from named patterns 
    type MatchContext = 
     { StructureContext: StructureContext; NamedMotives: Map<string, Motive> } 
     static member merge (c1: MatchContext) (c2: MatchContext) = 
     { StructureContext = c1.StructureContext; NamedMotives = c2.NamedMotives |> Map.fold (fun m k v -> m.Add(k,v)) c1.NamedMotives } 

    type MatchedMotive = Motive * MatchContext 

    type Pattern = 
     | EmptyPattern 
     | GeneratingPattern of (StructureContext -> MatchedMotive seq) 
     | ConstraintPattern of (MatchedMotive -> MatchedMotive option) * Pattern 
     static member matches (p: Pattern) (context: StructureContext) : MatchedMotive seq = 
     match p with 
     | GeneratingPattern generator -> generator context 
     | ConstraintPattern (transform, pattern) -> 
      Pattern.matches pattern context 
      |> Seq.choose (fun m -> transform m) 
     | _ -> Seq.empty 

    let ringPattern (names: string list) = 
     let fingerprint = 
     names 
     |> Seq.map (fun s -> ElementSymbol.Create(s).ToString()) 
     |> Seq.sort 
     |> String.concat "" 
     let generator (context: StructureContext) = 
     let rings = context.Structure.Rings().GetRingsByFingerprint(fingerprint) 
     rings |> Seq.map (fun r -> Motive.fromAtoms r.Atoms, { StructureContext = context; NamedMotives = Map.empty }) 
     GeneratingPattern generator 

    open Internal 

    type MotiveFinder (pattern: string) = 
    // I am using a hard coded pattern here for testing purposes 
    let pattern = ringPattern ["C"; "C"; "C"; "C"; "C"; "O"] 
    member this.Matches (structure: IStructure) = 
     Pattern.matches pattern (StructureContext.create structure) 
     |> Seq.map (fun (m, mc) -> Structure.fromMotive m mc.StructureContext.Structure false) 
     |> List.ofSeq 
     |> List.sortBy (fun s -> s.Atoms.[0].Id) 

/////////////////////////////////////////////////////////////////// 
// performance test 

let warmUp = (new MotiveFinder("")).Matches (StructureReader.ReadPdb(filename, computeBonds = true)) 
printfn "%i" (List.length warmUp) 

let structure = StructureReader.ReadPdb(filename, computeBonds = true) 
let stopWatch = System.Diagnostics.Stopwatch.StartNew() 
let nruns = 100000 
let result = 
    seq { 
    for i in 1 .. nruns do 
     yield (new MotiveFinder("")).Matches structure 
    } |> Seq.nth (nruns-1) 

stopWatch.Stop() 
printfn "Time elapsed: %f seconds" stopWatch.Elapsed.TotalSeconds 

Edit2:

me parece que han reducido el problema a la aplicación del tipo Set.

Para que este código:

let stopWatch = System.Diagnostics.Stopwatch.StartNew() 
let runs = 1000000 
let result = 
    seq { 
    for i in 1 .. runs do 
     let setA = [ 1 .. (i % 10) + 5 ] |> Set.ofList 
     let setB = [ 1 .. (i % 10) + 5 ] |> Set.ofList 
     yield Set.union setA setB 
    } |> Seq.nth (runs - 1) 

stopWatch.Stop() 
printfn "Time elapsed: %f seconds" stopWatch.Elapsed.TotalSeconds 
printfn "%A" result 

me sale ~ 7.5s con la optimización de apagado y ~ 8.0s con la optimización sucesivamente. Aún objetivo = Cualquier CPU (y tengo procesador i7-860).

EDIT3: Y justo después de publicar la edición anterior pensé que debería intentarlo en las listas solamente.

Así que para

let stopWatch = System.Diagnostics.Stopwatch.StartNew() 
let runs = 1000000 
let result1 = 
    seq { 
    for i in 1 .. runs do 
     let list = [ 1 .. i % 100 + 5 ] 
     yield list 
    } |> Seq.nth (runs - 1) 

stopWatch.Stop() 
printfn "Time elapsed: %f seconds" stopWatch.Elapsed.TotalSeconds 
printfn "%A" result1 

consigo ~ 3s con opc. apagado y ~ 3.5s con opt. en.

EDIT4:

Si quito el constructor siguientes y sólo hago

let stopWatch = System.Diagnostics.Stopwatch.StartNew() 
let runs = 1000000 
let mutable ret : int list = [] 
for i in 1 .. runs do 
    let list = [ 1 .. i % 100 + 5 ] 
    ret <- list 

stopWatch1.Stop() 
printfn "Time elapsed: %f seconds" stopWatch.Elapsed.TotalSeconds 
printfn "%A" ret 

consigo ~ 3s con la optimización tanto dentro como fuera. Por lo tanto, parece que el problema está en algún lugar en la optimización del código de constructor de seq.

Curiosamente, me escribió una aplicación de prueba en C#:

var watch = Stopwatch.StartNew(); 

int runs = 1000000; 

var result = Enumerable.Range(1, runs) 
    .Select(i => Microsoft.FSharp.Collections.ListModule.OfSeq(Enumerable.Range(1, i % 100 + 5))) 
    .ElementAt(runs - 1); 

watch.Stop(); 

Console.WriteLine(result); 
Console.WriteLine("Time: {0}s", watch.Elapsed.TotalSeconds); 

Y el código pasa a correr el doble de rápido que el # solución de F a ~ 1.7s.

EDIT5:

Sobre la base de la discusión con Jon Harrop he descubierto lo que está causando el código optimizado correr más lento (todavía no sé por qué aunque).

Si cambio de Motive.Atoms

member this.Atoms : IAtom seq = 
    seq { 
    for r in this.ResidueSet do yield! r.Atoms 
     yield! this.AtomSet 
    } 

a

member this.Atoms : IAtom seq = 
    Seq.append (this.ResidueSet |> Seq.collect (fun r -> r.Atoms)) this.AtomSet 

entonces el programa se ejecuta ~ 7.1s tanto en versión optimizada y no optimizado. Que es más lento que la versión seq, pero al menos constante.

Parece que el compilador F # no puede optimizar las expresiones de cálculo y las hace más lentas al intentarlo.

Answer 1

También puedo observar el código del contenedor y el penúltimo ejemplo ejecutándose un poco más lento con optimizaciones habilitadas pero la diferencia es inferior al 10% y, aunque anómala, no me sorprende que las optimizaciones a veces puedan degradar ligeramente el rendimiento.

Debo señalar que su estilo de codificación deja mucho espacio para la optimización, pero sin el código fuente completo no me es posible optimizarlo. Su ejemplo se utiliza el siguiente código:

let result1 = 
    seq { 
    for i in 1 .. runs do 
     let list = [ 1 .. i % 100 + 5 ] 
     yield list 
    } |> Seq.nth (runs - 1) 

cuando este es más corto, más idiomática y órdenes de magnitud más rápido:

let result1 = 
    Seq.init runs (fun i -> List.init ((i+1) % 100 + 5) ((+) 1)) 
    |> Seq.nth (runs - 1) 

EDITAR

En sus comentarios a continuación se dice que desea para ejecutar el argumento de la función, en cuyo caso no asumiría que Seq.nth hará esto por usted, así que usaría un bucle for en su lugar:

let mutable list = [] 
for i=1 to runs do 
    list <- List.init (i % 100 + 5) ((+) 1) 
list 

Esto es todavía 9 × más rápido que el original.