performance - 为什么 Seq 模块中的某些功能得到了优化，而其他功能却没有在 F# 中进行优化？

Question

这是我之前的 question 的后续关于Seq模块的iter和 map与 Array 相比，函数要慢得多和 List模块等价物。

看源码可以看到isEmpty等一些函数和 length在使用 IEnumerator 之前执行一个非常简单的类型检查以优化数组和列表.

[<CompiledName("IsEmpty")>]
let isEmpty (source : seq<'T>)  = 
    checkNonNull "source" source
    match source with 
    | :? ('T[]) as a -> a.Length = 0
    | :? list<'T> as a -> a.IsEmpty
    | :? ICollection<'T> as a -> a.Count = 0
    | _ -> 
        use ie = source.GetEnumerator()
        not (ie.MoveNext())

[<CompiledName("Length")>]
let length (source : seq<'T>)    = 
    checkNonNull "source" source
    match source with 
    | :? ('T[]) as a -> a.Length
    | :? ('T list) as a -> a.Length
    | :? ICollection<'T> as a -> a.Count
    | _ -> 
        use e = source.GetEnumerator() 
        let mutable state = 0 
        while e.MoveNext() do
            state <-  state + 1;
        state

在 iter 的情况下当我 shadowed iter与内置版本相比，它提供了显着的功能:

[<CompiledName("Iterate")>]
let iter f (source : seq<'T>) = 
    checkNonNull "source" source
    use e = source.GetEnumerator()
    while e.MoveNext() do
        f e.Current;

我的问题是，鉴于 Seq 中的某些功能模块已针对特定集合类型(数组、列表< T> 等)进行了优化。其他函数如 iter和 nth没有以类似的方式优化？

此外，对于 map正如@mausch 指出的那样，函数是否不可能采用与 Enumerable.Select 类似的方法？ (见下文)并为不同的集合类型建立专门的迭代器？

public static IEnumerable<TResult> Select<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector)
    {
      if (source == null)
        throw Error.ArgumentNull("source");
      if (selector == null)
        throw Error.ArgumentNull("selector");
      if (source is Enumerable.Iterator<TSource>)
        return ((Enumerable.Iterator<TSource>) source).Select<TResult>(selector);
      if (source is TSource[])
        return (IEnumerable<TResult>) new Enumerable.WhereSelectArrayIterator<TSource, TResult>((TSource[]) source, (Func<TSource, bool>) null, selector);
      if (source is List<TSource>)
        return (IEnumerable<TResult>) new Enumerable.WhereSelectListIterator<TSource, TResult>((List<TSource>) source, (Func<TSource, bool>) null, selector);
      else
        return (IEnumerable<TResult>) new Enumerable.WhereSelectEnumerableIterator<TSource, TResult>(source, (Func<TSource, bool>) null, selector);
    }

提前谢谢了。

Answer 1

In the case of the iter the same approach can be done to vastly improve its performance

我认为这就是您问题的答案所在。您的测试是人为的，实际上并没有测试这些方法的任何真实示例。您测试了这些方法的 10,000,000 次迭代，以获得 ms 中的时间差异。 .

转换回每件商品的成本，它们是:

          Array   List
Seq.iter   4 ns    7 ns
Seq.map   20 ns   91 ns

这些方法通常在每个集合中使用一次，这意味着此成本是算法性能的额外线性因素。在最坏的情况下，您的损失少于 100 ns列表中的每个项目(如果您非常关心性能，则不应该使用它)。

将此与 length 的情况进行对比。在一般情况下总是线性的。通过添加此优化，您可以为忘记手动缓存长度但幸运的是总是得到一个列表的人提供巨大的好处。

同样您可以调用 isEmpty很多时候，如果您可以直接询问，添加另一个对象创建是愚蠢的。 (这不是一个强有力的论点)

要记住的另一件事是，这些方法实际上都不会查看多个输出元素。您希望以下代码做什么(不包括语法错误或缺少方法)

type Custom() =
  interface IEnumerable with
    member x.GetEnumerator() =
      return seq {
        yield 1
        yield 2
      }
  interface IList with
    member x.Item with
      get(index) = index
    member x.Count = 12

 let a = Custom()
 a |> Seq.iter (v -> printfn (v.ToString()))