c# - example - Lista<T>.AddRange suboptimal de implementación

list addrange unity

Question

Al perfilar mi aplicación de C #, se indica que se pasa mucho tiempo en la List<T>.AddRange . El uso de Reflector para ver el código en este método indicó que llama a la List<T>.InsertRange que se implementa como tal:

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;

Se puede argumentar que la simplicidad de la interfaz (que solo tiene una sobrecarga de InsertRange) justifica la sobrecarga de rendimiento de cheching y casting de tipo runtime. Pero, ¿cuál podría ser la razón detrás de las 3 líneas que he indicado con (*) ? Creo que podría reescribirse a la alternativa más rápida:

is2.CopyTo(this._items, index);

¿Ves alguna razón para no usar esta alternativa más simple y aparentemente más rápida?

Editar:

Gracias por las respuestas. Por lo tanto, la opinión general es que esta es una medida de protección contra la recopilación de entrada que implementa CopyTo de manera defectuosa / maliciosa. A mí me parece una exageración pagar constantemente el precio de 1) verificación del tipo de tiempo de ejecución 2) asignación dinámica de la matriz temporal 3) duplicar la operación de copia, cuando todo esto podría haberse guardado definiendo 2 o unas cuantas sobrecargas más de InsertRange , uno obtiene IEnumerable como ahora, el segundo obtiene una List<T> , el tercero obtiene T[] . Los dos últimos podrían haber sido implementados para correr alrededor del doble de rápido que en el caso actual.

Edición 2:

Implementé una clase FastList, idéntica a la Lista, excepto que también proporciona una sobrecarga de AddRange que toma un argumento T []. Esta sobrecarga no necesita la verificación de tipo dinámico y la copia doble de elementos. Hice un perfil de este FastList.AddRange contra List.AddRange agregando matrices de 4 bytes 1000 veces a una lista que inicialmente estaba vacía. Mi implementación supera la velocidad de List.AddRange estándar con un factor de 9 (¡nueve!). List.AddRange toma aproximadamente el 5% del tiempo de ejecución en uno de los escenarios de uso importantes de nuestra aplicación, reemplazando a List con una clase que proporciona un AddRange más rápido podría mejorar el tiempo de ejecución de la aplicación en un 4%.

Answer 1

Es una buena pregunta, estoy luchando para encontrar una razón. No hay ninguna pista en la Fuente de Referencia. Una posibilidad es que intenten evitar un problema cuando la clase que implementa los objetos del método ICollection <>. CopyTo () no se copia en un índice de inicio distinto de 0. O como medida de seguridad, evita que la colección se mezcle con los elementos de la matriz No debería tener acceso a.

Otra es que se trata de una contramedida cuando la colección se utiliza de manera no segura para subprocesos. Si un elemento fue agregado a la colección por otro hilo, será el método CopyTo () de la clase de colección el que falle, no el código de Microsoft. La persona adecuada recibirá la llamada de servicio.

Estas no son grandes explicaciones.

Answer 2

Hay un problema con su solución si lo piensa por un minuto, si cambia el código de esa manera, esencialmente le está dando a la colección que debe agregarse acceso a una estructura de datos interna.

Esta no es una buena idea, por ejemplo, si el autor de la estructura de datos de la Lista descubre una mejor estructura subyacente para almacenar los datos que una matriz, no hay manera de cambiar la implementación de la Lista, ya que toda la colección espera una matriz en la función Copiar .

En esencia, estaría consolidando la implementación de la clase List, aunque la programación orientada a objetos nos diga que la implementación interna de una estructura de datos debe ser algo que se pueda cambiar sin romper otro código.

Answer 3

Impiden que la implementación de ICollection<T> acceda a los índices de la lista de destinos fuera de los límites de inserción. La implementación anterior da como resultado una IndexOutOfBoundsException si se IndexOutOfBoundsException una IndexOutOfBoundsException defectuosa (o "manipulativa") de CopyTo .

Tenga en cuenta que T[].CopyTo se implementa literalmente como memcpy , por lo que la sobrecarga de rendimiento de agregar esa línea es memcpy . Cuando tiene un costo tan bajo de agregar seguridad a una gran cantidad de llamadas, también puede hacerlo.

Edición: La parte que me parece extraña es el hecho de que la llamada a ICollection<T>.CopyTo (copia en la matriz temporal) no se produce inmediatamente después de la llamada a EnsureCapacity de EnsureCapacity . Si se moviera a esa ubicación, luego de cualquier excepción sincrónica, la lista permanecería sin cambios. Tal como está, esa condición solo se cumple si la inserción se realiza al final de la lista. El razonamiento aquí es:

• Toda la asignación necesaria ocurre antes de modificar los elementos de la lista.
• Las llamadas a Array.Copy no pueden fallar porque
  • La memoria ya está asignada.
  • Los límites ya están marcados.
  • Los tipos de elementos de las matrices de origen y destino coinciden
  • No hay un "constructor de copia" usado como en C ++ - es solo un memcpy
• Los únicos elementos que pueden generar una excepción son la llamada externa a ICollection.CopyTo y las asignaciones necesarias para cambiar el tamaño de la lista y asignar la matriz temporal. Si estos tres ocurren antes de mover elementos para la inserción, la transacción para cambiar la lista no puede generar una excepción síncrona.
• Nota final: esta dirección es un comportamiento estrictamente excepcional: el razonamiento anterior no agrega seguridad para subprocesos.

Edición 2 (respuesta a la edición de OP): ¿Ha perfilado esto? Usted está haciendo algunas afirmaciones audaces de que Microsoft debería haber elegido una API más complicada, por lo que debe asegurarse de que está en lo cierto al afirmar que el método actual es lento. Nunca he tenido un problema con el rendimiento de InsertRange , y estoy bastante seguro de que cualquier problema de rendimiento con el que alguien se enfrente se resolverá mejor con un rediseño de algoritmos que con la reimplementación de la lista dinámica. Solo para que no me tomes por ser negativo de una manera negativa, ten en cuenta lo siguiente:

• No quiero no poder soportar a las personas en mi equipo de desarrollo que les gusta reinventar la rueda cuadrada .
• Definitivamente quiero que las personas de mi equipo se preocupen por los posibles problemas de rendimiento y hacen preguntas sobre los efectos secundarios que puede tener su código. Este punto gana cuando está presente, pero mientras las personas hagan preguntas, las conduciré a convertir sus preguntas en respuestas sólidas. Si puedes mostrarme que una aplicación gana una ventaja significativa a través de lo que inicialmente parece ser una mala idea, entonces así es como van las cosas a veces.