Perché alcune funzioni del modulo Seq sono ottimizzate mentre altre non erano in F #?

Question

Si tratta di un follow-up alla mia precedente question per quanto riguarda le Seqiter e map funzioni del modulo di essere molto più lento rispetto agli equivalenti modulo Array e List.

Guardando alla fonte, posso vedere che alcune funzioni come isEmpty e length esegue un controllo di tipo molto semplice per ottimizzare per gli array e le liste prima di ricorrere all'utilizzo di 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 

Nel caso del iter lo stesso approccio può essere fatto per migliorare notevolmente le sue prestazioni, quando ho shadowed la funzione iter ha presentato aumenti significativi rispetto alla versione built-in:

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

mio la domanda è, dato che alcune delle funzioni nel modulosono state ottimizzate per l'uso con specifici tipi di raccolta (array, lista < T>, ecc.) come mai altre funzioni come iter e nth non sono state operative timized in un modo simile?

Inoltre, nel caso della funzione map, come indicato da @mausch, non è possibile utilizzare un approccio simile a Enumerable.Select (vedere di seguito) e creare iteratori specializzati per diversi tipi di raccolta?

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); 
    } 

Molte grazie in anticipo.

Answer 1

In superficie, i tipi di controllo in Seq.length/isEmpty sembrano errori. Presumo che la maggior parte delle funzioni Seq non esegua tali verifiche per l'ortogonalità: esistono già versioni specifiche per tipo nei moduli List/Array. Perché duplicarli?

Questi controlli hanno più senso in LINQ poiché utilizza solo IEnumerable direttamente.

Answer 2

Nel caso di ITER lo stesso approccio può essere fatto per migliorare notevolmente le sue prestazioni

Penso che questo è dove la risposta alla tua domanda è. Il tuo test è artificiale e in realtà non prova alcun esempio reale di questi metodi. Hai testato 10.000.000 di iterazioni di questi metodi per ottenere differenze nei tempi in ms.

riconvertito per voce costi, eccoli:

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

Questi metodi sono in genere utilizzati una volta per la raccolta, il che significa questo costo è un fattore lineare aggiuntivo per le prestazioni di algoritmi. Nel peggiore dei casi, stai perdendo meno di 100 ns per articolo in un elenco (che non dovresti usare se ti preoccupi troppo delle prestazioni).

Contrasto con il caso di length che è sempre lineare nel caso generale. Aggiungendo questa ottimizzazione si fornisce un enorme vantaggio a qualcuno che ha dimenticato di memorizzare manualmente la lunghezza della cache, ma per fortuna viene sempre data una lista.

Allo stesso modo è possibile chiamare isEmpty molte volte e aggiungere un'altra creazione di oggetto è sciocco se è possibile chiedere direttamente. (Questo argomento non è così forte)

Un'altra cosa da tenere a mente è che nessuno di questi metodi considera effettivamente più di un elemento dell'output. Che cosa ti aspetti dal seguente codice (escluso errori di sintassi o metodi mancanti)

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()))