对于循环列表

Question

人们常常使用

for i in [0 .. 10] do something

但afaik创建了一个列表然后迭代,在我看来它使用更有意义

for i = 0 to 10 do something

没有创建那个不必要的列表但具有相同的行为.我错过了什么吗？(我猜是这样的)

Answer 1

你是对的,写入for i in [0 .. 10] do something生成一个列表,它确实有很大的开销.虽然你也可以省略方括号,但在这种情况下它只是构建一个惰性序列(并且,事实证明编译器甚至优化了这种情况).我通常更喜欢写作,in 0 .. 100 do因为它看起来与迭代序列的代码相同.

使用#timeF#interactive 的功能进行简单分析:

for i in [ 0 .. 10000000 ] do // 3194ms (yikes!)
  last <- i

for i in 0 .. 10000000 do     // 3ms
  last <- i

for i = 0 to 10000000 do      // 3ms
  last <- i

for i in seq { 0 .. 10000000 } do // 709ms (smaller yikes!)
  last <- i

因此,事实证明编译器实际上优化了in 0 .. 10000000 do与0 to 10000000 do循环相同的东西.您可以强制它显式创建延迟序列(最后一种情况),这比列表更快,但仍然非常慢.

Answer 2

给出了一些不同的答案,但希望有些人感兴趣

你是对的,因为在这种情况下,F#编译器无法应用快速循环优化.好消息,F#编译器是开源的,我们可以改进它的行为.

所以这是我的免费赠品:

快速循环优化发生在tastops.fs中.它现在相当原始,是我们改进的绝佳机会.

// Detect the compiled or optimized form of a 'for <elemVar> in <startExpr> .. <finishExpr>  do <bodyExpr>' expression over integers
// Detect the compiled or optimized form of a 'for <elemVar> in <startExpr> .. <step> .. <finishExpr>  do <bodyExpr>' expression over integers when step is positive
let (|CompiledInt32ForEachExprWithKnownStep|_|) g expr = 
    match expr with 
    | Let (_enumerableVar, RangeInt32Step g (startExpr, step, finishExpr), _, 
           Let (_enumeratorVar, _getEnumExpr, spBind,
              TryFinally (WhileLoopForCompiledForEachExpr (_guardExpr, Let (elemVar,_currentExpr,_,bodyExpr), m), _cleanupExpr))) -> 

        let spForLoop = match spBind with SequencePointAtBinding(spStart) -> SequencePointAtForLoop(spStart) |  _ -> NoSequencePointAtForLoop 

        Some(spForLoop,elemVar,startExpr,step,finishExpr,bodyExpr,m)
    | _ -> 
        None

let DetectFastIntegerForLoops g expr = 
    match expr with 
    | CompiledInt32ForEachExprWithKnownStep g (spForLoop,elemVar,startExpr,step,finishExpr,bodyExpr,m) 
         // fast for loops only allow steps 1 and -1 steps at the moment
         when step = 1 || step = -1 -> 
            mkFastForLoop  g (spForLoop,m,elemVar,startExpr,(step = 1),finishExpr,bodyExpr)
    | _ -> expr

这里的问题是RangeInt32Step只检测像0..10和的模式0..1..10.它错过了例如[0..10]

让我们介绍另SeqRangeInt32Step一种匹配这些表达式的活动模式:

let (|SeqRangeInt32Step|_|) g expr =
    match expr with
    // detect '[n .. m]'
    | Expr.App(Expr.Val(toList,_,_),_,[TType_var _],
                [Expr.App(Expr.Val(seq,_,_),_,[TType_var _],
                          [Expr.Op(TOp.Coerce, [TType_app (seqT, [TType_var _]); TType_var _],
                                    [RangeInt32Step g (startExpr, step, finishExpr)], _)],_)],_)
        when
            valRefEq g toList (ValRefForIntrinsic g.seq_to_list_info) &&
            valRefEq g seq g.seq_vref &&
            tyconRefEq g seqT g.seq_tcr ->
            Some(startExpr, step, finishExpr)

    | _ -> None

你怎么知道这是你需要模式匹配的？我经常采用的方法是使用正确的属性执行一个简单的F#程序,并在编译期间放置一个断点来检查表达式.从那里我创建匹配的模式:

我们把两种模式放在一起:

let (|ExtractInt32Range|_|) g expr =
  match expr with
  | RangeInt32Step g range -> Some range
  | SeqRangeInt32Step g range -> Some range
  | _ -> None

CompiledInt32ForEachExprWithKnownStep已更新为使用ExtractInt32Range结束RangeInt32Step

完整的解决方案是这样的:

let (|SeqRangeInt32Step|_|) g expr =
    match expr with
    // detect '[n .. m]'
    | Expr.App(Expr.Val(toList,_,_),_,[TType_var _],
                [Expr.App(Expr.Val(seq,_,_),_,[TType_var _],
                          [Expr.Op(TOp.Coerce, [TType_app (seqT, [TType_var _]); TType_var _],
                                    [RangeInt32Step g (startExpr, step, finishExpr)], _)],_)],_)
        when
            valRefEq g toList (ValRefForIntrinsic g.seq_to_list_info) &&
            valRefEq g seq g.seq_vref &&
            tyconRefEq g seqT g.seq_tcr ->
            Some(startExpr, step, finishExpr)

    | _ -> None

let (|ExtractInt32Range|_|) g expr =
  match expr with
  | RangeInt32Step g range -> Some range
  | SeqRangeInt32Step g range -> Some range
  | _ -> None

// Detect the compiled or optimized form of a 'for <elemVar> in <startExpr> .. <finishExpr>  do <bodyExpr>' expression over integers
// Detect the compiled or optimized form of a 'for <elemVar> in <startExpr> .. <step> .. <finishExpr>  do <bodyExpr>' expression over integers when step is positive
let (|CompiledInt32ForEachExprWithKnownStep|_|) g expr = 
    match expr with 
    | Let (_enumerableVar, ExtractInt32Range g (startExpr, step, finishExpr), _,
           Let (_enumeratorVar, _getEnumExpr, spBind,
              TryFinally (WhileLoopForCompiledForEachExpr (_guardExpr, Let (elemVar,_currentExpr,_,bodyExpr), m), _cleanupExpr))) -> 

        let spForLoop = match spBind with SequencePointAtBinding(spStart) -> SequencePointAtForLoop(spStart) |  _ -> NoSequencePointAtForLoop 

        Some(spForLoop,elemVar,startExpr,step,finishExpr,bodyExpr,m)
    | _ -> 
        None

使用简单的测试程序

let print v =
    printfn "%A" v

[<EntryPoint>]
let main argv =
    for x in [0..10] do
        print x

    0

在优化之前,相应的C#代码看起来像这样(IL代码最好检查,但如果一个未使用它可能有点难以理解):

// Test
[EntryPoint]
public static int main(string[] argv)
{
    FSharpList<int> fSharpList = SeqModule.ToList<int>(Operators.CreateSequence<int>(Operators.OperatorIntrinsics.RangeInt32(0, 1, 10)));
    IEnumerator<int> enumerator = ((IEnumerable<int>)fSharpList).GetEnumerator();
    try
    {
        while (enumerator.MoveNext())
        {
            Test.print<int>(enumerator.Current);
        }
    }
    finally
    {
        IDisposable disposable = enumerator as IDisposable;
        if (disposable != null)
        {
            disposable.Dispose();
        }
    }
    return 0;
}

F#创建一个列表,然后使用枚举器迭代它.难怪与经典的for-loop相比,它相当慢.

应用优化后,我们得到以下代码:

// Test
[EntryPoint]
public static int main(string[] argv)
{
    for (int i = 0; i < 11; i++)
    {
        Test.print<int>(i);
    }
    return 0;
}

一个显着的改进.

因此,窃取此代码,将PR发布到https://github.com/Microsoft/visualfsharp/并在荣耀中晒太阳.当然你需要添加单元测试并发出IL代码测试,这对于找到合适的级别来说有点棘手,请检查此提交的灵感

PS.也许应该支持[|0..10|]以及seq {0..10}以及

PS.此外for v in 0L..10L do print v,for v in 0..2..10 do print v在F#中也没有低效率地实现.