List .AddRange implementazione ottimale

Question

Profiling mia C # applicazione ha indicato che molto tempo è trascorso in List<T>.AddRange. Utilizzando riflettore a guardare il codice in questo metodo ha indicato che chiama List<T>.InsertRange che è implementato come tale:

public void InsertRange(int index, IEnumerable<T> collection)
{
    if (collection == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
    }
    if (index > this._size)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
    }
    ICollection<T> is2 = collection as ICollection<T>;
    if (is2 != null)
    {
        int count = is2.Count;
        if (count > 0)
        {
            this.EnsureCapacity(this._size + count);
            if (index < this._size)
            {
                Array.Copy(this._items, index, this._items, index + count, this._size - index);
            }
            if (this == is2)
            {
                Array.Copy(this._items, 0, this._items, index, index);
                Array.Copy(this._items, (int) (index + count), this._items, (int) (index * 2), (int) (this._size - index));
            }
            else
            {
                T[] array = new T[count];          // (*)
                is2.CopyTo(array, 0);              // (*)
                array.CopyTo(this._items, index);  // (*)
            }
            this._size += count;
        }
    }
    else
    {
        using (IEnumerator<T> enumerator = collection.GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                this.Insert(index++, enumerator.Current);
            }
        }
    }
    this._version++;
}

private T[] _items;

Si può sostenere che la semplicità dell'interfaccia (solo avente uno sovraccarico InsertRange) giustifica l'overhead prestazioni di tipo runtime cheching e colata. Ma quello che potrebbe essere il motivo dietro le 3 linee che ho indicato con (*)? Penso che potrebbe essere riscritto per l'alternativa più veloce:

is2.CopyTo(this._items, index);

Non si vede alcuna ragione per non usare questa alternativa più semplice e apparentemente più veloce?

Modifica

Grazie per le risposte. Quindi opinione consenso è che si tratta di una misura di protezione contro la raccolta di input attuazione del CopyTo in maniera difettosa / dannoso. A me sembra un eccessivo a pagare costantemente il prezzo di tipo 1) runtime controllo 2) l'allocazione dinamica della array temporaneo 3) doppio l'operazione di copia, quando tutto questo avrebbe potuto essere salvato attraverso la definizione di 2 o di un paio di sovraccarichi di InsertRange , uno ottenendo IEnumerable come ora, la seconda ottenendo un List<T>, terzo ottenendo T[]. Gli ultimi due avrebbe potuto essere implementato per correre due volte più veloce come nel caso attuale.

Modifica 2:

Ho implementare un elenco rapido classe, identica alla lista, tranne che fornisce anche un sovraccarico di AddRange che prende un argomento T []. Questo sovraccarico non ha bisogno della verifica di tipo dinamico, e fare doppio copia di elementi. Ho fatto Profilo Questo FastList.AddRange contro List.AddRange con l'aggiunta di array di 4 byte 1000 volte ad una lista che era inizialmente vuoto Fai. La mia implementazione batte la velocità di List.AddRange standard con un fattore di 9 (nove!). List.AddRange richiede circa il 5% del tempo di esecuzione in uno dei più importanti scenari di utilizzo della nostra applicazione, in sostituzione di List con una classe che fornisce un AddRange più veloce potrebbe migliorare runtime applicativo del 4%.

Answer 1

Essi impediscono l'attuazione di ICollection<T> di accedere indici della lista destinazioni di fuori dei limiti di inserimento. L'attuazione sopra i risultati in un IndexOutOfBoundsException se un guasto (o "manipolatore") attuazione CopyTo viene chiamato.

Tenete a mente che è abbastanza T[].CopyTo implementato letteralmente internamente come memcpy, in modo che il sovraccarico delle prestazioni di aggiungere quella linea è minuto. Quando si dispone di un basso costo di aggiungere la sicurezza a un numero enorme di telefonate, si potrebbe anche farlo.

Modifica La parte che trovo strano è il fatto che la chiamata a ICollection<T>.CopyTo (copia per l'array temporaneo) non si verifica immediatamente dopo la chiamata a EnsureCapacity. Se venisse spostato in quella posizione, quindi dopo i eccezione sincrono l'elenco sarebbe rimasto invariato. Così com'è e tale condizione vale solo se l'inserimento avviene alla fine della lista. Il ragionamento è:

• L'assegnazione avviene prima necessario modificare gli elementi dell'elenco.
• Le chiamate al Array.Copy non può fallire perché
  • La memoria è già allocato
  • I limiti sono già controllati
  • I tipi di elementi della partita matrici di origine e destinazione
  • Non c'è un "costruttore di copia" usato come in C ++ - E 'solo una memcpy
• Gli unici elementi che possono generare un'eccezione sono la chiamata esterna al ICollection.CopyTo e gli stanziamenti necessari per il ridimensionamento della lista e l'assegnazione del array temporaneo. Se tutti e tre di questi si verificano prima di elementi in movimento per l'inserimento, l'operazione per modificare l'elenco non può un'eccezione sincrona.
• Nota finale:. Questo indirizzo comportamento rigorosamente eccezionale - quanto sopra logica non aggiungere thread-sicurezza

Modifica 2 (risposta alla modifica del PO): Hai profilata questo? Si stanno facendo alcune affermazioni audaci che Microsoft avrebbe dovuto scelto un API più complicato, quindi è necessario assicurarsi che siete sulla strada giusta nelle affermazioni che l'attuale metodo è lento. Non ho mai avuto un problema con le prestazioni di InsertRange, e sono abbastanza sicuro che qualsiasi problemi di prestazioni qualcuno faccia con esso sarà meglio risolti con una riprogettazione algoritmo che da reimplementare l'elenco dinamico. Solo così si non mi prendi come dura in modo negativo, tenere presente quanto segue:

• I non vogliono non sopporto la gente del mio team di sviluppo che, come per reinventare la ruota quadrato.
• I sicuramente vuole che la gente del mio team che si occupano di potenziali problemi di prestazioni, e porre domande circa gli effetti collaterali il loro codice può avere. Questo punto vince quando presente - ma fino a quando la gente si chiede domande che li guiderà per trasformare le loro domande in risposte concrete. Se mi si può dimostrare che un'applicazione guadagna un vantaggio significativo attraverso quello che sembra inizialmente essere una cattiva idea, allora questo è solo il modo in cui le cose vanno a volte.

Answer 2

E 'una buona domanda, sto lottando per trovare una ragione. Non c'è nessun accenno nel sorgente del riferimento. Una possibilità è che si cerca di evitare un problema quando la classe che implementa ICollection <>. CopyTo () metodo di oggetti contro la copia ad un indice di partenza diverso da 0. O come misura di sicurezza, impedendo la raccolta di fare scherzi con gli elementi dell'array non dovrebbe avere accesso.

Un altro è che questa è una contromisura quando la raccolta viene utilizzato in modo thread-pericoloso. Se un elemento ottenuto aggiunta alla raccolta da un altro thread sarà il metodo della classe di raccolta CopyTo () che non riesce, non il codice di Microsoft. La persona giusta otterrà la chiamata di servizio.

Queste non sono grandi spiegazioni.

Answer 3

C'è un problema con la soluzione, se ci pensate per un minuto, se si modifica il codice in questo modo si sono essenzialmente dando la raccolta che deve essere aggiunto l'accesso a un datastructure interna.

Questa non è una buona idea, per esempio, se l'autore della Lista datastructure capisce una migliore struttura di base per memorizzare i dati di un array non v'è alcun modo per modificare l'implementazione di List in quanto tutta la linea si aspettano un array in la funzione CopyTo.

In sostanza si sarebbe cementare l'implementazione della classe List, anche se programmazione orientata agli oggetti ci dice che l'implementazione interna di un datastructure dovrebbe essere qualcosa che può essere modificato senza rompere altro codice.