¿Sin ConcurrentList <T> en .Net 4.0?

198

Me emocionó ver el nuevo System.Collections.Concurrentespacio de nombres en .Net 4.0, ¡bastante agradable! Yo he visto ConcurrentDictionary, ConcurrentQueue, ConcurrentStack, ConcurrentBagy BlockingCollection.

Una cosa que parece faltar misteriosamente es una ConcurrentList<T>. ¿Tengo que escribir eso yo mismo (o sacarlo de la web :))?

¿Me estoy perdiendo algo obvio aquí?

Alan
fuente
77
ConcurrentBag <T> ( msdn.microsoft.com/pt-br/library/… )
Rodrigo Reis
44
@RodrigoReis, ConcurrentBag <T> es una colección desordenada, mientras que List <T> está ordenada.
Adam Calvet Bohl
44
¿Cómo podría tener una colección ordenada en un entorno multiproceso? Nunca tendrías control de la secuencia de elementos, por diseño.
Jeremy Holovacs
Utilice un candado en su lugar
Erik Bergstedt
hay un archivo llamado ThreadSafeList.cs en el código fuente de dotnet que se parece mucho a algunos de los siguientes códigos. También usa ReaderWriterLockSlim y estaba tratando de entender por qué usar eso en lugar de un simple bloqueo (obj).
Colin Lamarre

Respuestas:

166

Lo intenté hace un tiempo (también: en GitHub ). Mi implementación tuvo algunos problemas, que no voy a abordar aquí. Déjame decirte, lo más importante, lo que aprendí.

En primer lugar, no hay forma de que pueda obtener una implementación completa de IList<T>eso es sin bloqueo y sin hilos. En particular, las inserciones y eliminaciones aleatorias son no funcionarán, a menos que también se olvide del acceso aleatorio O (1) (es decir, a menos que "engañe" y simplemente use algún tipo de lista vinculada y deje que la indexación sea un asco).

Lo que pensé que podría valer la pena era un subconjunto limitado de flujos seguros IList<T>: en particular, que permitiría una Addy proporcionar al azar de sólo lectura el acceso de índice (pero no Insert, RemoveAt, etc., y también hay aleatoria de escritura de acceso).

Este fue el objetivo de mi ConcurrentList<T>implementación . Pero cuando probé su rendimiento en escenarios de subprocesos múltiples, descubrí que simplemente sincronizar las adiciones a a List<T>era más rápido . Básicamente, agregar a un ya List<T>es muy rápido; La complejidad de los pasos computacionales involucrados es minúscula (incrementar un índice y asignar a un elemento en una matriz; eso es realmente ). Necesitaría un montón de escrituras concurrentes para ver cualquier tipo de contención de bloqueo en esto; e incluso entonces, el rendimiento promedio de cada escritura aún superaría la implementación más costosa, aunque sin bloqueo ConcurrentList<T>.

En el caso relativamente raro de que la matriz interna de la lista deba redimensionarse, usted paga un pequeño costo. Así que, en última instancia, llegué a la conclusión de que este era el único escenario de nicho en el que un ConcurrentList<T>tipo de colección de solo agregar tendría sentido: cuando desea garantizar una baja sobrecarga de agregar un elemento en cada llamada (por lo tanto, a diferencia de un objetivo de rendimiento amortizado).

Simplemente no es una clase tan útil como parece.

Dan Tao
fuente
52
Y si necesita algo similar a lo List<T>que usa la sincronización basada en monitor de old skool, hay SynchronizedCollection<T>BCL oculto: msdn.microsoft.com/en-us/library/ms668265.aspx
LukeH
8
Una pequeña adición: use el parámetro Constructor de capacidad para evitar (tanto como sea posible) el escenario de cambio de tamaño.
Henk Holterman
2
El escenario más grande donde a ConcurrentListsería una victoria sería cuando no hay mucha actividad agregando a la lista, pero hay muchos lectores concurrentes. Se podría reducir la sobrecarga de los lectores a una sola barrera de memoria (y eliminar incluso eso si los lectores no estuvieran preocupados por datos ligeramente obsoletos).
supercat
2
@Kevin: Es bastante trivial construir un producto ConcurrentList<T>de tal manera que se garantice a los lectores que vean un estado consistente sin necesidad de ningún bloqueo, con una sobrecarga adicional relativamente leve. Cuando la lista se expande, por ejemplo, de tamaño 32 a 64, mantenga la matriz de tamaño 32 y cree una nueva matriz de tamaño 64. Al agregar cada uno de los siguientes 32 elementos, colóquelo en la ranura 32-63 de la nueva matriz y copie un elemento antiguo de la matriz de tamaño 32 a la nueva. Hasta que se agregue el elemento 64, los lectores buscarán en la matriz de tamaño 32 los elementos 0-31 y en la matriz de tamaño 64 los elementos 32-63.
supercat
2
Una vez que se agrega el elemento 64, la matriz de tamaño 32 seguirá funcionando para recuperar elementos 0-31, pero los lectores ya no necesitarán usarlo. Pueden usar la matriz de tamaño 64 para todos los elementos 0-63 y una matriz de tamaño 128 para los elementos 64-127. La sobrecarga de seleccionar cuál de las dos matrices usar, más una barrera de memoria si se desea, sería menor que la sobrecarga de incluso el bloqueo lector-escritor más eficiente imaginable. Las escrituras probablemente deberían usar bloqueos (sin bloqueo sería posible, especialmente si a uno no le importa crear una nueva instancia de objeto con cada inserción, pero el bloqueo debería ser económico.
Supercat
38

¿Para qué usarías una ConcurrentList?

El concepto de un contenedor de acceso aleatorio en un mundo enhebrado no es tan útil como parece. La declaración

  if (i < MyConcurrentList.Count)  
      x = MyConcurrentList[i]; 

en su conjunto todavía no sería seguro para subprocesos.

En lugar de crear una lista concurrente, intente crear soluciones con lo que hay allí. Las clases más comunes son ConcurrentBag y especialmente BlockingCollection.

Henk Holterman
fuente
Buen punto. Aún así, lo que estoy haciendo es un poco más mundano. Solo estoy tratando de asignar el ConcurrentBag <T> en una IList <T>. Podría cambiar mi propiedad a un IEnumerable <T>, pero luego no puedo. Agregarle cosas.
Alan
1
@ Alan: No hay forma de implementar eso sin bloquear la lista. Dado Monitorque de todos modos ya puede hacerlo, no hay razón para una lista concurrente.
Billy ONeal
66
@dcp: sí, esto es inherentemente no apto para subprocesos. ConcurrentDictionary tiene métodos especiales que hacen esto en una operación atómica, como AddOrUpdate, GetOrAdd, TryUpdate, etc. Todavía tienen ContainsKey porque a veces solo desea saber si la clave está allí sin modificar el diccionario (piense en HashSet)
Zarat
3
@dcp: ContainsKey es seguro para subprocesos por sí mismo, su ejemplo (¡no ContainsKey!) solo tiene una condición de carrera porque realiza una segunda llamada dependiendo de la primera decisión, que en ese momento ya puede estar desactualizada.
Zarat
2
Henk, no estoy de acuerdo. Creo que hay un escenario simple en el que podría ser muy útil. El subproceso de trabajo escrito en él leerá la interfaz de usuario y actualizará la interfaz en consecuencia. Si desea agregar un elemento ordenado, requerirá escritura de acceso aleatorio. También puede usar una pila y una vista de los datos, pero tendrá que mantener 2 colecciones :-(.
Eric Ouellet
19

Con el debido respeto a las excelentes respuestas proporcionadas ya, hay veces que simplemente quiero una IList segura para subprocesos. Nada avanzado o elegante. El rendimiento es importante en muchos casos, pero a veces eso no es una preocupación. Sí, siempre habrá desafíos sin métodos como "TryGetValue", etc., pero en la mayoría de los casos solo quiero algo que pueda enumerar sin tener que preocuparme por bloquear todo. Y sí, alguien probablemente pueda encontrar algún "error" en mi implementación que pueda conducir a un punto muerto o algo así (supongo), pero seamos honestos: cuando se trata de subprocesos múltiples, si no escribe su código correctamente, se va a un punto muerto de todos modos. Con eso en mente, decidí hacer una implementación simple de ConcurrentList que satisfaga estas necesidades básicas.

Y para lo que vale: hice una prueba básica de agregar 10,000,000 artículos a List y ConcurrentList regulares y los resultados fueron:

Lista terminada en: 7793 milisegundos. Concurrente terminado en: 8064 milisegundos.

public class ConcurrentList<T> : IList<T>, IDisposable
{
    #region Fields
    private readonly List<T> _list;
    private readonly ReaderWriterLockSlim _lock;
    #endregion

    #region Constructors
    public ConcurrentList()
    {
        this._lock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);
        this._list = new List<T>();
    }

    public ConcurrentList(int capacity)
    {
        this._lock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);
        this._list = new List<T>(capacity);
    }

    public ConcurrentList(IEnumerable<T> items)
    {
        this._lock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);
        this._list = new List<T>(items);
    }
    #endregion

    #region Methods
    public void Add(T item)
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.Add(item);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public void Insert(int index, T item)
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.Insert(index, item);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public bool Remove(T item)
    {
        try
        {
            this._lock.EnterWriteLock();
            return this._list.Remove(item);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public void RemoveAt(int index)
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.RemoveAt(index);
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public int IndexOf(T item)
    {
        try
        {
            this._lock.EnterReadLock();
            return this._list.IndexOf(item);
        }
        finally
        {
            this._lock.ExitReadLock();
        }
    }

    public void Clear()
    {
        try
        {
            this._lock.EnterWriteLock();
            this._list.Clear();
        }
        finally
        {
            this._lock.ExitWriteLock();
        }
    }

    public bool Contains(T item)
    {
        try
        {
            this._lock.EnterReadLock();
            return this._list.Contains(item);
        }
        finally
        {
            this._lock.ExitReadLock();
        }
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        try
        {
            this._lock.EnterReadLock();
            this._list.CopyTo(array, arrayIndex);
        }
        finally
        {
            this._lock.ExitReadLock();
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        return new ConcurrentEnumerator<T>(this._list, this._lock);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return new ConcurrentEnumerator<T>(this._list, this._lock);
    }

    ~ConcurrentList()
    {
        this.Dispose(false);
    }

    public void Dispose()
    {
        this.Dispose(true);
    }

    private void Dispose(bool disposing)
    {
        if (disposing)
            GC.SuppressFinalize(this);

        this._lock.Dispose();
    }
    #endregion

    #region Properties
    public T this[int index]
    {
        get
        {
            try
            {
                this._lock.EnterReadLock();
                return this._list[index];
            }
            finally
            {
                this._lock.ExitReadLock();
            }
        }
        set
        {
            try
            {
                this._lock.EnterWriteLock();
                this._list[index] = value;
            }
            finally
            {
                this._lock.ExitWriteLock();
            }
        }
    }

    public int Count
    {
        get
        {
            try
            {
                this._lock.EnterReadLock();
                return this._list.Count;
            }
            finally
            {
                this._lock.ExitReadLock();
            }
        }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }
    #endregion
}

    public class ConcurrentEnumerator<T> : IEnumerator<T>
{
    #region Fields
    private readonly IEnumerator<T> _inner;
    private readonly ReaderWriterLockSlim _lock;
    #endregion

    #region Constructor
    public ConcurrentEnumerator(IEnumerable<T> inner, ReaderWriterLockSlim @lock)
    {
        this._lock = @lock;
        this._lock.EnterReadLock();
        this._inner = inner.GetEnumerator();
    }
    #endregion

    #region Methods
    public bool MoveNext()
    {
        return _inner.MoveNext();
    }

    public void Reset()
    {
        _inner.Reset();
    }

    public void Dispose()
    {
        this._lock.ExitReadLock();
    }
    #endregion

    #region Properties
    public T Current
    {
        get { return _inner.Current; }
    }

    object IEnumerator.Current
    {
        get { return _inner.Current; }
    }
    #endregion
}
Brian Booth
fuente
55
OK, respuesta anterior pero aún así: RemoveAt(int index)nunca Insert(int index, T item)es seguro para subprocesos, solo es seguro para index == 0, el retorno de IndexOf()está inmediatamente desactualizado, etc. Ni siquiera comience con el this[int].
Henk Holterman
2
Y no necesitas y no quieres un ~ Finalizador ().
Henk Holterman
2
Dice que ha renunciado a evitar la posibilidad de un punto muerto, y que ReaderWriterLockSlimse puede hacer un punto muerto fácilmente mediante el uso EnterUpgradeableReadLock()simultáneo. Sin embargo, no lo usa, no hace que la cerradura sea accesible al exterior y, por ejemplo, no llama a un método que ingresa un bloqueo de escritura mientras mantiene un bloqueo de lectura, por lo que usar su clase ya no hace puntos muertos. probable.
Eugene Beresovsky
1
La interfaz no concurrente no es apropiada para el acceso concurrente. Por ejemplo, lo siguiente no es atómico var l = new ConcurrentList<string>(); /* ... */ l[0] += "asdf";. En general, cualquier combinación de lectura y escritura puede llevarlo a serios problemas cuando se realiza simultáneamente. Es por eso que las estructuras de datos concurrentes generalmente proporcionan métodos para aquellos, como ConcurrentDictionary's AddOrGetetc. NB Su constante (y redundante porque los miembros ya están marcados como tales por el guión bajo) repetición de this.desorden.
Eugene Beresovsky
1
Gracias Eugene Soy un gran usuario de .NET Reflector que pone "esto". en todos los campos no estáticos. Como tal, he crecido para preferir lo mismo. En cuanto a que esta interfaz no concurrente no es apropiada: tiene toda la razón de que intentar realizar múltiples acciones contra mi implementación puede volverse poco confiable. Pero el requisito aquí es simplemente que se puedan realizar acciones individuales (agregar, eliminar, borrar o enumerar) sin dañar la colección. Básicamente elimina la necesidad de poner sentencias de bloqueo alrededor de todo.
Brian Booth
11

ConcurrentList(como una matriz redimensionable, no una lista vinculada) no es fácil de escribir con operaciones sin bloqueo. Su API no se traduce bien a una versión "concurrente".

Stephen Cleary
fuente
12
No solo es difícil de escribir, incluso es difícil encontrar una interfaz útil.
CodesInChaos
11

La razón por la que no hay ConcurrentList es porque fundamentalmente no se puede escribir. La razón es que varias operaciones importantes en IList dependen de índices, y eso simplemente no funcionará. Por ejemplo:

int catIndex = list.IndexOf("cat");
list.Insert(catIndex, "dog");

El efecto que busca el autor es insertar "perro" antes de "gato", pero en un entorno multiproceso, cualquier cosa puede pasar a la lista entre esas dos líneas de código. Por ejemplo, podría funcionar otro subproceso list.RemoveAt(0), desplazando toda la lista a la izquierda, pero de manera crucial, catIndex no cambiará. El impacto aquí es que la Insertoperación realmente pondrá al "perro" detrás del gato, no antes.

Las diversas implementaciones que ves que se ofrecen como "respuestas" a esta pregunta son bien intencionadas, pero como se muestra arriba, no ofrecen resultados confiables. Si realmente desea una semántica similar a una lista en un entorno multiproceso, no puede lograrlo colocando cerraduras dentro los métodos de implementación de la lista. Debe asegurarse de que cualquier índice que utilice viva completamente dentro del contexto del bloqueo. El resultado es que puede usar una Lista en un entorno multiproceso con el bloqueo correcto, pero no se puede hacer que la lista exista en ese mundo.

Si cree que necesita una lista concurrente, en realidad solo hay dos posibilidades:

  1. Lo que realmente necesitas es una bolsa concurrente
  2. Necesita crear su propia colección, tal vez implementada con una Lista y su propio control de concurrencia.

Si tiene un ConcurrentBag y está en una posición en la que necesita pasarlo como una IList, entonces tiene un problema, porque el método al que está llamando ha especificado que podrían intentar hacer algo como lo hice anteriormente con el gato & perro. En la mayoría de los mundos, lo que eso significa es que el método al que está llamando simplemente no está diseñado para funcionar en un entorno multiproceso. Eso significa que lo refactoriza para que esté o, si no puede, tendrá que manejarlo con mucho cuidado. Es casi seguro que se te pedirá que crees tu propia colección con sus propios bloqueos y que llames al método ofensivo dentro de un bloqueo.

Steve Benz
fuente
5

En los casos en que las lecturas superan en número a las escrituras, o (aunque sean frecuentes) las escrituras no son concurrentes , una copia en escritura enfoque de puede ser apropiado.

La implementación que se muestra a continuación es

  • sin cerradura
  • increíblemente rápido para lecturas concurrentes , incluso mientras las modificaciones concurrentes están en curso, sin importar cuánto tiempo demoren
  • debido a que las "instantáneas" son inmutables, la atomicidad sin bloqueo es posible, es decir var snap = _list; snap[snap.Count - 1];, nunca se lanzará (bueno, excepto por una lista vacía, por supuesto), y también obtendrá una enumeración segura de subprocesos con semántica de instantáneas gratis ... ¡cómo ME ENCANTA la inmutabilidad!
  • implementado genéricamente , aplicable a cualquier estructura de datos y cualquier tipo de modificación
  • muy simple , es decir, fácil de probar, depurar, verificar leyendo el código
  • utilizable en .Net 3.5

Para que la copia en escritura funcione, debe mantener sus estructuras de datos efectivamente inmutables , es decir, a nadie se le permite cambiarlas después de ponerlas a disposición de otros hilos. Cuando quieres modificar, tú

  1. clonar la estructura
  2. hacer modificaciones en el clon
  3. intercambiar atómicamente la referencia al clon modificado

Código

static class CopyOnWriteSwapper
{
    public static void Swap<T>(ref T obj, Func<T, T> cloner, Action<T> op)
        where T : class
    {
        while (true)
        {
            var objBefore = Volatile.Read(ref obj);
            var newObj = cloner(objBefore);
            op(newObj);
            if (Interlocked.CompareExchange(ref obj, newObj, objBefore) == objBefore)
                return;
        }
    }
}

Uso

CopyOnWriteSwapper.Swap(ref _myList,
    orig => new List<string>(orig),
    clone => clone.Add("asdf"));

Si necesita más rendimiento, ayudará a desgenerizar el método, por ejemplo, crear un método para cada tipo de modificación (Agregar, Eliminar, ...) que desee y codificar los punteros de función clonery op.

NB # 1 Es su responsabilidad asegurarse de que nadie modifique la estructura de datos (supuestamente) inmutable. No hay nada que podamos hacer en una implementación genérica para evitar eso, pero cuando se especialice List<T>, podría protegerse contra modificaciones utilizando List.AsReadOnly ()

NB # 2 Tenga cuidado con los valores en la lista. El enfoque de copia en escritura anterior protege solo su pertenencia a la lista, pero si no pone cadenas, sino algunos otros objetos mutables, debe tener cuidado de la seguridad del hilo (por ejemplo, bloqueo). Pero eso es ortogonal a esta solución y, por ejemplo, el bloqueo de los valores mutables se puede usar fácilmente sin problemas. Solo necesitas estar consciente de ello.

NB # 3 Si su estructura de datos es enorme y la modifica con frecuencia, el enfoque de copiar todo en escritura podría ser prohibitivo tanto en términos de consumo de memoria como del costo de copia de la CPU involucrado. En ese caso, es posible que desee utilizar las colecciones inmutables de MS en su lugar.

Eugene Beresovsky
fuente
3

System.Collections.Generic.List<t>ya es seguro para múltiples lectores. Intentar hacer que sea seguro para múltiples escritores no tendría sentido. (Por razones que Henk y Stephen ya mencionaron)

Billy ONeal
fuente
¿No puede ver un escenario en el que podría haber 5 hilos agregados a una lista? De esta manera, podría ver la lista acumular registros incluso antes de que todos terminen.
Alan
9
@Alan: eso sería un ConcurrentQueue, ConcurrentStack o ConcurrentBag. Para dar sentido a una lista concurrente, debe proporcionar un caso de uso donde las clases disponibles no sean suficientes. No veo por qué desearía acceso indexado cuando los elementos en los índices pueden cambiar aleatoriamente mediante eliminaciones simultáneas. Y para una lectura "bloqueada" ya puede tomar instantáneas de las clases concurrentes existentes y ponerlas en una lista.
Zarat
Tienes razón: no quiero acceso indexado. Generalmente uso IList <T> como proxy para un IEnumerable al que puedo .Agregar (T) nuevos elementos. De ahí viene la pregunta, de verdad.
Alan
@ Alan: Entonces quieres una cola, no una lista.
Billy ONeal
3
Creo que estas equivocado. Decir: seguro para múltiples lectores no significa que no puedas escribir al mismo tiempo. Escribir también significaría eliminar y obtendrá un error si elimina mientras itera en él.
Eric Ouellet
2

Algunas personas destacaron algunos puntos de bienes (y algunos de mis pensamientos):

  • Podría parecer una locura no poder acceder aleatoriamente (indexador) pero a mí me parece bien. Solo tiene que pensar que hay muchos métodos en colecciones de subprocesos múltiples que podrían fallar como Indexer y Delete. También puede definir la acción de falla (reserva) para el descriptor de acceso como "falla" o simplemente "agregar al final".
  • No es porque sea una colección multiproceso que siempre se utilizará en un contexto multiproceso. O también podría ser utilizado por un solo escritor y un lector.
  • Otra forma de poder usar el indexador de manera segura podría ser envolver acciones en un bloqueo de la colección utilizando su raíz (si se hace pública).
  • Para muchas personas, hacer visible un rootLock se convierte en una "Buena práctica". No estoy 100% seguro sobre este punto porque si está oculto, se elimina mucha flexibilidad para el usuario. Siempre debemos recordar que la programación multiproceso no es para nadie. No podemos evitar todo tipo de uso incorrecto.
  • Microsoft tendrá que hacer algo de trabajo y definir un nuevo estándar para introducir el uso adecuado de la colección multiproceso. Primero, el IEnumerator no debe tener moveNext, sino que debe tener un GetNext que devuelva verdadero o falso y obtenga un parámetro de salida del tipo T (de esta manera, la iteración ya no se bloqueará). Además, Microsoft ya usa "usar" internamente en el foreach, pero a veces usa IEnumerator directamente sin envolverlo con "using" (un error en la vista de recopilación y probablemente en más lugares). Microsoft recomienda el uso de envoltura de IEnumerator. Este error elimina un buen potencial para un iterador seguro ... Iterador que bloquea la colección en el constructor y desbloquea en su método Dispose, para un método foreach de bloqueo.

Esa no es una respuesta. Estos son solo comentarios que realmente no se ajustan a un lugar específico.

... Mi conclusión, Microsoft tiene que hacer algunos cambios profundos en el "foreach" para que la colección MultiThreaded sea más fácil de usar. También tiene que seguir sus propias reglas de uso de IEnumerator. Hasta ese momento, podemos escribir una MultiThreadList fácilmente que usaría un iterador de bloqueo pero que no seguirá a "IList". En su lugar, tendrá que definir su propia interfaz "IListPersonnal" que podría fallar en "insertar", "eliminar" y el acceso aleatorio (indexador) sin excepción. Pero, ¿quién querrá usarlo si no es estándar?

Eric Ouellet
fuente
Uno podría escribir fácilmente uno ConcurrentOrderedBag<T>que incluiría una implementación de solo lectura IList<T>, pero también ofrecería un int Add(T value)método totalmente seguro para subprocesos . No veo por qué ForEachse necesitarían cambios. Aunque Microsoft no lo dice explícitamente, su práctica sugiere que es perfectamente aceptable IEnumerator<T>enumerar los contenidos de la colección que existían cuando se creó; la excepción modificada por la colección solo se requiere si el enumerador no podría garantizar una operación sin fallas.
supercat
Iterando a través de una colección MT, la forma en que está diseñado podría conducir, como usted dijo, a una excepción ... Cuál no sé. ¿Atraparías todas las excepciones? En mi propio libro, la excepción es una excepción y no debería ocurrir en la ejecución normal del código. De lo contrario, para evitar excepciones, debe bloquear la colección u obtener una copia (de manera segura, es decir, bloquear) o implementar un mecanismo muy complejo en la colección para evitar que se produzca una excepción debido a la concurrencia. Sin embargo, pensé que sería bueno agregar un IEnumeratorMT que bloquearía la colección mientras se producía un código para cada uno y agregaría código relacionado ...
Eric Ouellet
La otra cosa que también podría ocurrir es que cuando obtienes un iterador, puedes bloquear la colección y cuando tu iterador es GC recogido puedes desbloquear la colección. Según Microsfot, ya verifican si el IEnumerable también es un ID disponible y llaman al GC si es así al final de un ForEach. El principal problema es que también usan el IEnumerable en otro lugar sin llamar al GC, entonces no puede confiar en eso. Tener una nueva interfaz MT clara para el bloqueo de habilitación IEnumerable resolvería el problema, al menos en parte. (No evitaría que la gente no lo llame).
Eric Ouellet
Es una muy mala forma para un GetEnumeratormétodo público dejar una colección bloqueada después de que regrese; Tales diseños pueden conducir fácilmente a un punto muerto. No IEnumerable<T>proporciona ninguna indicación de si se puede esperar que se complete una enumeración incluso si se modifica una colección; lo mejor que puede hacer es escribir sus propios métodos para que lo hagan, y tener métodos que acepten IEnumerable<T>documentar el hecho de que solo será seguro para IEnumerable<T>subprocesos si admite la enumeración segura para subprocesos.
supercat
Lo que habría sido más útil hubiera sido si IEnumerable<T>hubiera incluido un método de "Instantánea" con el tipo de retorno IEnumerable<T>. Las colecciones inmutables podrían devolverse; una colección limitada si no otra cosa podría copiarse en una List<T>o T[]y llamada GetEnumeratoren eso. Se podrían implementar algunas colecciones ilimitadas Snapshot, y aquellas que no podrían podrían lanzar una excepción sin tratar de llenar una lista con sus contenidos.
supercat
1

Al ejecutar secuencialmente el código, las estructuras de datos utilizadas son diferentes del código de ejecución simultánea (bien escrito). La razón es que el código secuencial implica un orden implícito. Sin embargo, el código concurrente no implica ningún orden; ¡mejor aún implica la falta de un orden definido!

Debido a esto, las estructuras de datos con orden implícito (como List) no son muy útiles para resolver problemas concurrentes. Una lista implica orden, pero no define claramente cuál es ese orden. Debido a esto, el orden de ejecución del código que manipula la lista determinará (hasta cierto punto) el orden implícito de la lista, que está en conflicto directo con una solución concurrente eficiente.

¡Recuerde que la concurrencia es un problema de datos, no un problema de código! No puede implementar el código primero (o reescribir el código secuencial existente) y obtener una solución concurrente bien diseñada. Primero debe diseñar las estructuras de datos teniendo en cuenta que el ordenamiento implícito no existe en un sistema concurrente.

Plano41
fuente
1

El enfoque de copiar y escribir sin cerradura funciona muy bien si no se trata de demasiados elementos. Aquí hay una clase que escribí:

public class CopyAndWriteList<T>
{
    public static List<T> Clear(List<T> list)
    {
        var a = new List<T>(list);
        a.Clear();
        return a;
    }

    public static List<T> Add(List<T> list, T item)
    {
        var a = new List<T>(list);
        a.Add(item);
        return a;
    }

    public static List<T> RemoveAt(List<T> list, int index)
    {
        var a = new List<T>(list);
        a.RemoveAt(index);
        return a;
    }

    public static List<T> Remove(List<T> list, T item)
    {
        var a = new List<T>(list);
        a.Remove(item);
        return a;
    }

}

ejemplo de uso: orders_BUY = CopyAndWriteList.Clear (orders_BUY);

Rob The Quant
fuente
en lugar de bloquear, crea una copia de la lista, modifica la lista y establece la referencia a la nueva lista. Por lo tanto, cualquier otro subproceso que esté iterando no causará ningún problema.
Rob The Quant
0

Implementé uno similar al de Brian . El mío es diferente:

  • Administro la matriz directamente.
  • No entro en las cerraduras dentro del bloque de prueba.
  • Yo uso yield returnpara producir un enumerador.
  • Apoyo la recursividad de bloqueo. Esto permite lecturas de la lista durante la iteración.
  • Uso bloqueos de lectura actualizables siempre que sea posible.
  • DoSyncy GetSyncmétodos que permiten interacciones secuenciales que requieren acceso exclusivo a la lista.

El código :

public class ConcurrentList<T> : IList<T>, IDisposable
{
    private ReaderWriterLockSlim _lock = new ReaderWriterLockSlim(LockRecursionPolicy.SupportsRecursion);
    private int _count = 0;

    public int Count
    {
        get
        { 
            _lock.EnterReadLock();
            try
            {           
                return _count;
            }
            finally
            {
                _lock.ExitReadLock();
            }
        }
    }

    public int InternalArrayLength
    { 
        get
        { 
            _lock.EnterReadLock();
            try
            {           
                return _arr.Length;
            }
            finally
            {
                _lock.ExitReadLock();
            }
        }
    }

    private T[] _arr;

    public ConcurrentList(int initialCapacity)
    {
        _arr = new T[initialCapacity];
    }

    public ConcurrentList():this(4)
    { }

    public ConcurrentList(IEnumerable<T> items)
    {
        _arr = items.ToArray();
        _count = _arr.Length;
    }

    public void Add(T item)
    {
        _lock.EnterWriteLock();
        try
        {       
            var newCount = _count + 1;          
            EnsureCapacity(newCount);           
            _arr[_count] = item;
            _count = newCount;                  
        }
        finally
        {
            _lock.ExitWriteLock();
        }       
    }

    public void AddRange(IEnumerable<T> items)
    {
        if (items == null)
            throw new ArgumentNullException("items");

        _lock.EnterWriteLock();

        try
        {           
            var arr = items as T[] ?? items.ToArray();          
            var newCount = _count + arr.Length;
            EnsureCapacity(newCount);           
            Array.Copy(arr, 0, _arr, _count, arr.Length);       
            _count = newCount;
        }
        finally
        {
            _lock.ExitWriteLock();          
        }
    }

    private void EnsureCapacity(int capacity)
    {   
        if (_arr.Length >= capacity)
            return;

        int doubled;
        checked
        {
            try
            {           
                doubled = _arr.Length * 2;
            }
            catch (OverflowException)
            {
                doubled = int.MaxValue;
            }
        }

        var newLength = Math.Max(doubled, capacity);            
        Array.Resize(ref _arr, newLength);
    }

    public bool Remove(T item)
    {
        _lock.EnterUpgradeableReadLock();

        try
        {           
            var i = IndexOfInternal(item);

            if (i == -1)
                return false;

            _lock.EnterWriteLock();
            try
            {   
                RemoveAtInternal(i);
                return true;
            }
            finally
            {               
                _lock.ExitWriteLock();
            }
        }
        finally
        {           
            _lock.ExitUpgradeableReadLock();
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        _lock.EnterReadLock();

        try
        {    
            for (int i = 0; i < _count; i++)
                // deadlocking potential mitigated by lock recursion enforcement
                yield return _arr[i]; 
        }
        finally
        {           
            _lock.ExitReadLock();
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    public int IndexOf(T item)
    {
        _lock.EnterReadLock();
        try
        {   
            return IndexOfInternal(item);
        }
        finally
        {
            _lock.ExitReadLock();
        }
    }

    private int IndexOfInternal(T item)
    {
        return Array.FindIndex(_arr, 0, _count, x => x.Equals(item));
    }

    public void Insert(int index, T item)
    {
        _lock.EnterUpgradeableReadLock();

        try
        {                       
            if (index > _count)
                throw new ArgumentOutOfRangeException("index"); 

            _lock.EnterWriteLock();
            try
            {       
                var newCount = _count + 1;
                EnsureCapacity(newCount);

                // shift everything right by one, starting at index
                Array.Copy(_arr, index, _arr, index + 1, _count - index);

                // insert
                _arr[index] = item;     
                _count = newCount;
            }
            finally
            {           
                _lock.ExitWriteLock();
            }
        }
        finally
        {
            _lock.ExitUpgradeableReadLock();            
        }


    }

    public void RemoveAt(int index)
    {   
        _lock.EnterUpgradeableReadLock();
        try
        {   
            if (index >= _count)
                throw new ArgumentOutOfRangeException("index");

            _lock.EnterWriteLock();
            try
            {           
                RemoveAtInternal(index);
            }
            finally
            {
                _lock.ExitWriteLock();
            }
        }
        finally
        {
            _lock.ExitUpgradeableReadLock();            
        }
    }

    private void RemoveAtInternal(int index)
    {           
        Array.Copy(_arr, index + 1, _arr, index, _count - index-1);
        _count--;

        // release last element
        Array.Clear(_arr, _count, 1);
    }

    public void Clear()
    {
        _lock.EnterWriteLock();
        try
        {        
            Array.Clear(_arr, 0, _count);
            _count = 0;
        }
        finally
        {           
            _lock.ExitWriteLock();
        }   
    }

    public bool Contains(T item)
    {
        _lock.EnterReadLock();
        try
        {   
            return IndexOfInternal(item) != -1;
        }
        finally
        {           
            _lock.ExitReadLock();
        }
    }

    public void CopyTo(T[] array, int arrayIndex)
    {       
        _lock.EnterReadLock();
        try
        {           
            if(_count > array.Length - arrayIndex)
                throw new ArgumentException("Destination array was not long enough.");

            Array.Copy(_arr, 0, array, arrayIndex, _count);
        }
        finally
        {
            _lock.ExitReadLock();           
        }
    }

    public bool IsReadOnly
    {   
        get { return false; }
    }

    public T this[int index]
    {
        get
        {
            _lock.EnterReadLock();
            try
            {           
                if (index >= _count)
                    throw new ArgumentOutOfRangeException("index");

                return _arr[index]; 
            }
            finally
            {
                _lock.ExitReadLock();               
            }           
        }
        set
        {
            _lock.EnterUpgradeableReadLock();
            try
            {

                if (index >= _count)
                    throw new ArgumentOutOfRangeException("index");

                _lock.EnterWriteLock();
                try
                {                       
                    _arr[index] = value;
                }
                finally
                {
                    _lock.ExitWriteLock();              
                }
            }
            finally
            {
                _lock.ExitUpgradeableReadLock();
            }

        }
    }

    public void DoSync(Action<ConcurrentList<T>> action)
    {
        GetSync(l =>
        {
            action(l);
            return 0;
        });
    }

    public TResult GetSync<TResult>(Func<ConcurrentList<T>,TResult> func)
    {
        _lock.EnterWriteLock();
        try
        {           
            return func(this);
        }
        finally
        {
            _lock.ExitWriteLock();
        }
    }

    public void Dispose()
    {   
        _lock.Dispose();
    }
}
Ronnie Overby
fuente
¿Qué sucede si dos hilos entran al comienzo del trybloque Removeo al indexador al mismo tiempo?
James
@ James que no parece posible. Lea las observaciones en msdn.microsoft.com/en-us/library/… . Al ejecutar este código, nunca ingresará ese bloqueo por segunda vez: gist.github.com/ronnieoverby/59b715c3676127a113c3
Ronnie Overby
@Ronny Overby: Interesante. Dado eso, sospecho que esto funcionaría mucho mejor si eliminara el UplableReadLock de todas las funciones donde la única operación realizada en el tiempo entre el bloqueo de lectura actualizable y el bloqueo de escritura: la sobrecarga de tomar cualquier tipo de bloqueo es mucho más que la verificación para ver si el parámetro está fuera del rango que solo haciendo esa verificación dentro del bloqueo de escritura probablemente funcionaría mejor.
James
Esta clase tampoco parece muy útil, ya que las funciones basadas en desplazamiento (la mayoría de ellas) realmente no se pueden usar de manera segura a menos que haya un esquema de bloqueo externo de todos modos porque la colección podría cambiar cuando decidas dónde colocar o obtener algo de y cuando realmente lo obtengas.
James
1
Quería dejar constancia diciendo que reconozco que la utilidad de la IListsemántica en escenarios concurrentes es, en el mejor de los casos, limitada. Escribí este código probablemente antes de darme cuenta de eso. Mi experiencia es la misma que la del escritor de la respuesta aceptada: lo intenté con lo que sabía sobre sincronización e IList <T> y aprendí algo al hacerlo.
Ronnie Overby