Điều gì có thể làm cho mã F # không được tối ưu hóa nhanh hơn mã được tối ưu hóa?

Question

Vì vậy, tôi đã quyết định cung cấp cho F # một thử và chuyển một trong những thuật toán tôi đã viết bằng C# cho nó. Tại một thời điểm, tôi đã nhận thấy rằng xây dựng gỡ lỗi chạy nhanh hơn bản phát hành gỡ lỗi. Sau đó tôi đã chơi với cài đặt tối ưu hóa và nhận được các kết quả sau:

Thời gian hiển thị tổng thời gian thực hiện của thuật toán trên 100000 lần chạy. Tôi đang sử dụng trình biên dịch F # đi kèm với Visual Studio 2010 SP1. Nền tảng đích là Bất kỳ CPU nào.

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 

Tôi thực sự bối rối vì điều này - tại sao tối ưu hóa làm cho mã chạy chậm hơn? Phiên bản C# của thuật toán không thể hiện hành vi này (nó được thực hiện theo một cách hơi khác)

Đây là một phiên bản rút gọn của mã F #, nó là một thuật toán tìm mẫu trong phân tử. Tất cả mã mà chương trình F # này dựa vào được viết bằng 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:

tôi dường như đã thu hẹp xuống vấn đề để thực hiện các loại Tập.

Đối với mã này:

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 

tôi nhận được ~ 7.5s với tối ưu hóa off và ~ 8.0s với tối ưu hóa trên. Vẫn target = Bất kỳ CPU nào (và tôi có bộ vi xử lý i7-860).

EDIT3: Và ngay sau khi tôi đăng chỉnh sửa trước đó, tôi đã tìm tôi chỉ nên thử trên danh sách.

Vì vậy, đối

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 

tôi nhận được ~ 3s với opt. tắt và ~ 3.5 với lựa chọn. trên.

EDIT4:

Nếu tôi loại bỏ các builder seq và chỉ làm

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 

tôi nhận được ~ 3s với tối ưu hóa cả trong và ngoài. Vì vậy, có vẻ như vấn đề là ở đâu đó trong việc tối ưu hóa mã xây dựng seq.

Lạ lùng thay, tôi đã viết một ứng dụng thử nghiệm trong 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); 

Và mã xảy ra để chạy gần gấp đôi nhanh như # giải pháp F tại ~ 1.7s.

EDIT5:

Dựa trên các cuộc thảo luận với Jon Harrop Tôi đã phát hiện ra điều đó gây ra các mã được tối ưu hóa chạy chậm hơn (tôi vẫn không biết tại sao tho).

Nếu tôi thay đổi Motive.Atoms từ

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

để

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

sau đó chương trình chạy ~ 7.1s trong cả hai phiên bản được tối ưu hóa và không được tối ưu hóa. Cái nào chậm hơn phiên bản seq, nhưng ít nhất là nhất quán.

Vì vậy, có vẻ như trình biên dịch F # không thể tối ưu hóa các biểu thức tính toán và thực sự làm cho chúng chậm hơn bằng cách thử như vậy.

Answer 1

Tôi cũng có thể quan sát mã trình bao bọc và ví dụ điển hình của bạn chạy chậm hơn một chút khi bật tối ưu hóa nhưng chênh lệch nhỏ hơn 10% và, mặc dù bất thường, tôi không ngạc nhiên khi tối ưu hóa đôi khi có thể làm giảm hiệu suất.

Tôi nên lưu ý rằng phong cách mã hóa của bạn để lại rất nhiều chỗ để tối ưu hóa nhưng không có toàn bộ mã nguồn, tôi không thể giúp tối ưu hóa nó. Ví dụ bạn sử dụng đoạn mã sau:

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

khi điều này là ngắn hơn, nhiều thành ngữ và mệnh lệnh của cường độ nhanh:

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

EDIT

Trong bình luận của bạn bên dưới, bạn nói rằng bạn muốn để thực hiện đối số hàm trong trường hợp này tôi sẽ không giả định rằng Seq.nth sẽ làm điều này cho bạn vì vậy tôi sẽ sử dụng vòng lặp for thay thế:

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

Đây vẫn là 9 × nhanh hơn bản gốc.