Keine ConcurrentList <T> in .Net 4.0?

198

Ich war begeistert, den neuen System.Collections.ConcurrentNamespace in .Net 4.0 zu sehen, ganz nett! Ich habe gesehen ConcurrentDictionary, ConcurrentQueue, ConcurrentStack, ConcurrentBagund BlockingCollection.

Eine Sache, die auf mysteriöse Weise zu fehlen scheint, ist a ConcurrentList<T>. Muss ich das selbst schreiben (oder aus dem Internet holen :))?

Vermisse ich hier etwas Offensichtliches?

Alan
quelle
7
ConcurrentBag <T> ( msdn.microsoft.com/pt-br/library/… )
Rodrigo Reis
4
@RodrigoReis, ConcurrentBag <T> ist eine ungeordnete Sammlung, während List <T> bestellt ist.
Adam Calvet Bohl
4
Wie könnten Sie möglicherweise eine bestellte Sammlung in einer Multithread-Umgebung haben? Sie hätten niemals die Kontrolle über die Reihenfolge der Elemente.
Jeremy Holovacs
Verwenden Sie stattdessen ein Schloss
Erik Bergstedt
Im Dotnet-Quellcode befindet sich eine Datei namens ThreadSafeList.cs, die dem folgenden Code sehr ähnlich sieht. Es verwendet auch ReaderWriterLockSlim und versuchte herauszufinden, warum dies anstelle einer einfachen Sperre (obj) verwendet wird.
Colin Lamarre

Antworten:

166

Ich habe es vor einiger Zeit versucht (auch: auf GitHub ). Meine Implementierung hatte einige Probleme, auf die ich hier nicht eingehen werde. Lassen Sie mich vor allem sagen, was ich gelernt habe.

Erstens gibt es keine Möglichkeit, eine vollständige Implementierung zu erhalten IList<T>, die sperrenlos und threadsicher ist. Insbesondere werden zufällige Einfügungen und Entfernungen nicht funktionieren, es sei denn, Sie vergessen auch den O (1) -Wahlzugriff (dh, Sie "betrügen" und verwenden einfach eine verknüpfte Liste und lassen die Indizierung saugen).

Was ich dachte , vielleicht war ein Thread-sicher, begrenzte Teilmenge von mir lohnen IList<T>: insbesondere eine , die eine erlauben würde , Addund bietet zufälligen Nur - Lese- Zugriff Index (aber nicht Insert, RemoveAtusw. und auch keine zufälligen Schreibzugriff).

Dies war das Ziel meiner ConcurrentList<T>Implementierung . Als ich jedoch die Leistung in Multithread-Szenarien testete, stellte ich fest, dass das einfache Synchronisieren von Adds zu a List<T>schneller war . Grundsätzlich ist das Hinzufügen zu a List<T>bereits blitzschnell; Die Komplexität der beteiligten Rechenschritte ist winzig (Index erhöhen und einem Element in einem Array zuweisen; das war's wirklich ). Sie würden eine Menge gleichzeitiger Schreibvorgänge benötigen , um jegliche Art von Sperrenkonflikten zu sehen. und selbst dann würde die durchschnittliche Leistung jedes Schreibvorgangs die teurere, wenn auch sperrenlose Implementierung in übertreffen ConcurrentList<T>.

In dem relativ seltenen Fall, dass die Größe des internen Arrays der Liste selbst geändert werden muss, zahlen Sie geringe Kosten. Letztendlich kam ich zu dem Schluss, dass dies das einzige Nischenszenario ist, in dem ein Nur-Add- ConcurrentList<T>Collection-Typ sinnvoll ist: Wenn Sie einen garantierten geringen Overhead für das Hinzufügen eines Elements bei jedem einzelnen Aufruf wünschen (im Gegensatz zu einem amortisierten Leistungsziel).

Es ist einfach nicht annähernd so nützlich wie man denkt.

Dan Tao
quelle
52
Und wenn Sie etwas Ähnliches benötigen, List<T>das eine altmodische, monitorbasierte Synchronisation verwendet, ist es SynchronizedCollection<T>in der BCL versteckt: msdn.microsoft.com/en-us/library/ms668265.aspx
LukeH
8
Ein kleiner Zusatz: Verwenden Sie den Capacity-Konstruktorparameter, um das Größenänderungsszenario (so weit wie möglich) zu vermeiden.
Henk Holterman
2
Das größte Szenario, in dem ein ConcurrentListGewinn wäre, wäre, wenn nicht viel Aktivität zur Liste hinzugefügt wird, aber es gibt viele gleichzeitige Leser. Man könnte den Overhead der Leser auf eine einzige Speicherbarriere reduzieren (und selbst das beseitigen, wenn die Leser sich keine Gedanken über leicht veraltete Daten machen).
Supercat
2
@ Kevin: Es ist ziemlich trivial, einen ConcurrentList<T>so zu konstruieren, dass die Leser garantiert einen konsistenten Zustand sehen, ohne dass eine Sperre erforderlich ist, mit relativ geringem zusätzlichen Aufwand. Wenn die Liste von z. B. Größe 32 auf 64 erweitert wird, behalten Sie das Array Größe 32 bei und erstellen Sie ein neues Array Größe 64. Wenn Sie jedes der nächsten 32 Elemente hinzufügen, setzen Sie es in Steckplatz 32-63 des neuen Arrays und kopieren Sie ein altes Element aus dem Array der Größe 32 in das neue. Bis das 64. Element hinzugefügt wird, suchen die Leser im Array der Größe 32 nach den Elementen 0-31 und im Array der Größe 64 nach den Elementen 32-63.
Supercat
2
Sobald das 64. Element hinzugefügt wurde, funktioniert das Array der Größe 32 weiterhin zum Abrufen der Elemente 0 bis 31, aber die Leser müssen es nicht mehr verwenden. Sie können das Array Größe 64 für alle Elemente 0-63 und ein Array Größe 128 für die Elemente 64-127 verwenden. Der Aufwand für die Auswahl eines von zwei zu verwendenden Arrays sowie eine Speicherbarriere, falls gewünscht, wäre geringer als der Aufwand selbst für die effizienteste Lese- / Schreibsperre, die man sich vorstellen kann. Schreibvorgänge sollten wahrscheinlich Sperren verwenden (sperrfrei wäre möglich, insbesondere wenn es nichts ausmacht, bei jeder Einfügung eine neue Objektinstanz zu erstellen, aber die Sperre sollte billig sein.
Supercat
38

Wofür würden Sie eine ConcurrentList verwenden?

Das Konzept eines Direktzugriffscontainers in einer Thread-Welt ist nicht so nützlich, wie es scheint. Die Aussage

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

insgesamt wäre immer noch nicht threadsicher.

Versuchen Sie, anstatt eine ConcurrentList zu erstellen, Lösungen mit den vorhandenen Komponenten zu erstellen. Die gebräuchlichsten Klassen sind die ConcurrentBag und insbesondere die BlockingCollection.

Henk Holterman
quelle
Guter Punkt. Trotzdem ist das, was ich tue, etwas weltlicher. Ich versuche nur, die ConcurrentBag <T> einer IList <T> zuzuweisen. Ich könnte meine Eigenschaft in eine IEnumerable <T> ändern, aber dann kann ich nichts hinzufügen.
Alan
1
@ Alan: Es gibt keine Möglichkeit, dies zu implementieren, ohne die Liste zu sperren. Da Sie Monitordies ohnehin bereits verwenden können, gibt es keinen Grund für eine gleichzeitige Liste.
Billy ONeal
6
@dcp - ja das ist von Natur aus nicht threadsicher. ConcurrentDictionary verfügt über spezielle Methoden, die dies in einer atomaren Operation ausführen, wie AddOrUpdate, GetOrAdd, TryUpdate usw. Sie haben immer noch ContainsKey, da Sie manchmal nur wissen möchten, ob der Schlüssel vorhanden ist, ohne das Wörterbuch zu ändern (denken Sie an HashSet)
Zarat
3
@dcp - ContainsKey ist für sich genommen threadsicher. Ihr Beispiel (nicht ContainsKey!) hat nur eine Racebedingung, da Sie abhängig von der ersten Entscheidung einen zweiten Aufruf ausführen, der zu diesem Zeitpunkt möglicherweise bereits veraltet ist.
Zarat
2
Henk, ich bin nicht einverstanden. Ich denke, dass es ein einfaches Szenario gibt, in dem es sehr nützlich sein könnte. Durch das Schreiben des Arbeitsthreads wird die Benutzeroberfläche des UI-Threads entsprechend gelesen und aktualisiert. Wenn Sie ein Element sortiert hinzufügen möchten, ist ein Schreibzugriff mit wahlfreiem Zugriff erforderlich. Sie können auch einen Stapel und eine Ansicht der Daten verwenden, müssen jedoch 2 Sammlungen verwalten :-(.
Eric Ouellet
19

Bei allem Respekt vor den bereits gegebenen großartigen Antworten möchte ich manchmal einfach einen thread-sicheren IList. Nichts fortgeschrittenes oder ausgefallenes. Leistung ist in vielen Fällen wichtig, aber manchmal ist das einfach kein Problem. Ja, es wird immer Herausforderungen ohne Methoden wie "TryGetValue" usw. geben, aber in den meisten Fällen möchte ich nur etwas, das ich aufzählen kann, ohne mir Sorgen machen zu müssen, dass alles gesperrt wird. Und ja, jemand kann wahrscheinlich einen "Fehler" in meiner Implementierung finden, der zu einem Deadlock oder etwas anderem führen könnte (nehme ich an), aber seien wir ehrlich: Wenn Sie beim Multithreading Ihren Code nicht richtig schreiben, ist dies der Fall geht sowieso ins Stocken. Vor diesem Hintergrund habe ich mich für eine einfache ConcurrentList-Implementierung entschieden, die diese Grundanforderungen erfüllt.

Und was es wert ist: Ich habe einen grundlegenden Test durchgeführt, bei dem 10.000.000 Elemente zur regulären Liste und ConcurrentList hinzugefügt wurden. Die Ergebnisse waren:

Liste beendet in: 7793 Millisekunden. Gleichzeitig beendet in: 8064 Millisekunden.

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
quelle
5
OK, alte Antwort, aber immer noch: RemoveAt(int index)ist nie threadsicher, Insert(int index, T item)ist nur sicher für index == 0, die Rückgabe von IndexOf()ist sofort veraltet usw. Beginnen Sie nicht einmal mit dem this[int].
Henk Holterman
2
Und du brauchst und willst keinen ~ Finalizer ().
Henk Holterman
2
Sie sagen, Sie haben es aufgegeben, die Möglichkeit eines Deadlocks zu verhindern - und ein einziger ReaderWriterLockSlimkann bei gleichzeitiger Verwendung leicht zum Deadlock gebracht werden EnterUpgradeableReadLock(). Sie verwenden es jedoch nicht, Sie machen die Sperre nicht nach außen zugänglich, und Sie rufen beispielsweise keine Methode auf, die eine Schreibsperre eingibt, während Sie eine Lesesperre halten, sodass die Verwendung Ihrer Klasse keine Deadlocks mehr verursacht wahrscheinlich.
Eugene Beresovsky
1
Die nicht gleichzeitige Schnittstelle ist nicht für den gleichzeitigen Zugriff geeignet. ZB ist das Folgende nicht atomar var l = new ConcurrentList<string>(); /* ... */ l[0] += "asdf";. Im Allgemeinen kann jede Lese- / Schreibkombination bei gleichzeitiger Ausführung zu großen Problemen führen. Deshalb ist im Allgemeinen der gleichzeitigen Datenstrukturen Methoden für diejenigen bieten, wie ConcurrentDictionary‚s AddOrGetusw. NB Ihre Konstante (und überflüssig , weil die Mitglieder sind bereits als solche durch einen Strich gekennzeichnet) Wiederholung von this.clutters.
Eugene Beresovsky
1
Danke Eugene. Ich bin ein starker Benutzer von .NET Reflector, der "dies" ausdrückt. auf allen nicht statischen Feldern. Als solches habe ich das gleiche bevorzugt. Da diese nicht gleichzeitige Schnittstelle nicht geeignet ist: Sie haben absolut Recht, dass der Versuch, mehrere Aktionen gegen meine Implementierung auszuführen, unzuverlässig werden kann. Die Anforderung hier ist jedoch einfach, dass einzelne Aktionen (Hinzufügen oder Entfernen oder Löschen oder Aufzählen) ausgeführt werden können, ohne die Sammlung zu beschädigen. Grundsätzlich entfällt die Notwendigkeit, Lock-Anweisungen um alles zu setzen.
Brian Booth
11

ConcurrentList(als anpassbares Array, nicht als verknüpfte Liste) ist mit nicht blockierenden Vorgängen nicht einfach zu schreiben. Die API lässt sich nicht gut in eine "gleichzeitige" Version übersetzen.

Stephen Cleary
quelle
12
Es ist nicht nur schwierig zu schreiben, es ist sogar schwierig, eine nützliche Schnittstelle zu finden.
CodesInChaos
11

Der Grund, warum es keine ConcurrentList gibt, ist, dass sie grundsätzlich nicht geschrieben werden kann. Der Grund dafür ist, dass einige wichtige Operationen in IList auf Indizes beruhen und dass dies einfach nicht funktioniert. Beispielsweise:

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

Der Effekt, den der Autor anstrebt, besteht darin, "Hund" vor "Katze" einzufügen. In einer Multithread-Umgebung kann jedoch alles mit der Liste zwischen diesen beiden Codezeilen geschehen. Zum Beispiel könnte ein anderer Thread list.RemoveAt(0)die gesamte Liste nach links verschieben, aber entscheidend ist, dass sich catIndex nicht ändert. Die Auswirkung hier ist, dass die InsertOperation tatsächlich den "Hund" hinter die Katze stellt, nicht davor.

Die verschiedenen Implementierungen, die Sie als "Antworten" auf diese Frage sehen, sind gut gemeint, aber wie oben gezeigt, bieten sie keine zuverlässigen Ergebnisse. Wenn Sie wirklich eine listenähnliche Semantik in einer Multithread-Umgebung wünschen, können Sie nicht dorthin gelangen, indem Sie Sperren in die Listenimplementierungsmethoden einfügen. Sie müssen sicherstellen, dass jeder Index, den Sie verwenden, vollständig im Kontext der Sperre lebt. Das Ergebnis ist, dass Sie eine Liste in einer Multithread-Umgebung mit der richtigen Sperre verwenden können, aber die Liste selbst kann nicht in dieser Welt existieren.

Wenn Sie glauben, dass Sie eine gleichzeitige Liste benötigen, gibt es wirklich nur zwei Möglichkeiten:

  1. Was Sie wirklich brauchen, ist eine ConcurrentBag
  2. Sie müssen Ihre eigene Sammlung erstellen, möglicherweise implementiert mit einer Liste und Ihrer eigenen Parallelitätskontrolle.

Wenn Sie eine ConcurrentBag haben und sich in einer Position befinden, in der Sie sie als IList übergeben müssen, haben Sie ein Problem, da die von Ihnen aufgerufene Methode angegeben hat, dass sie möglicherweise versuchen, etwas wie oben mit der Katze & zu tun Hund. In den meisten Welten bedeutet dies, dass die von Ihnen aufgerufene Methode einfach nicht für die Verwendung in einer Multithread-Umgebung ausgelegt ist. Das bedeutet, dass Sie es entweder so umgestalten, dass es so ist, oder wenn Sie nicht können, müssen Sie sehr vorsichtig damit umgehen. Mit ziemlicher Sicherheit müssen Sie Ihre eigene Sammlung mit eigenen Sperren erstellen und die fehlerhafte Methode innerhalb einer Sperre aufrufen.

Steve Benz
quelle
5

In Fällen, in denen Lesevorgänge die Anzahl der Schreibvorgänge erheblich übersteigen oder (wie häufig auch immer) Schreibvorgänge nicht gleichzeitig ausgeführt werden , kann ein Copy-on-Write- Ansatz angebracht sein.

Die unten gezeigte Implementierung ist

  • schlosslos
  • Sehr schnell für gleichzeitige Lesevorgänge , auch wenn gleichzeitig Änderungen vorgenommen werden - egal wie lange sie dauern
  • Da "Schnappschüsse" unveränderlich sind, ist eine sperrenlose Atomizität möglich, dh sie var snap = _list; snap[snap.Count - 1];wird niemals ( naja , abgesehen von einer leeren Liste natürlich) geworfen, und Sie erhalten außerdem kostenlos eine thread-sichere Aufzählung mit Schnappschuss-Semantik. Wie ich Unveränderlichkeit LIEBE!
  • generisch implementiert , anwendbar auf jede Datenstruktur und jede Art von Modifikation
  • ganz einfach , dh einfach zu testen, zu debuggen, zu überprüfen, indem Sie den Code lesen
  • verwendbar in .Net 3.5

Damit Copy-on-Write funktioniert, müssen Sie Ihre Datenstrukturen effektiv unveränderlich halten , dh niemand darf sie ändern, nachdem Sie sie anderen Threads zur Verfügung gestellt haben. Wenn Sie ändern möchten, Sie

  1. Klonen Sie die Struktur
  2. Nehmen Sie Änderungen am Klon vor
  3. tauschen Sie den Verweis auf den modifizierten Klon atomar aus

Code

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

Verwendung

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

Wenn Sie mehr Leistung benötigen, wird es helfen , die Methode ungenerify, zum Beispiel ein Verfahren für jede Art von Modifikation erstellen (Hinzufügen, Entfernen, ...) Sie wollen, und harte Code , um die Funktionszeiger clonerund op.

NB # 1 Es liegt in Ihrer Verantwortung sicherzustellen, dass niemand die (angeblich) unveränderliche Datenstruktur ändert. In einer generischen Implementierung können wir nichts tun, um dies zu verhindern. Wenn List<T>Sie sich jedoch darauf spezialisieren, können Sie sich mit List.AsReadOnly () vor Änderungen schützen.

NB # 2 Achten Sie auf die Werte in der Liste. Der obige Ansatz zum Kopieren beim Schreiben schützt nur die Listenmitgliedschaft. Wenn Sie jedoch keine Zeichenfolgen, sondern einige andere veränderbare Objekte einfügen möchten, müssen Sie sich um die Thread-Sicherheit kümmern (z. B. Sperren). Dies ist jedoch orthogonal zu dieser Lösung, und z. B. kann das Sperren der veränderlichen Werte problemlos ohne Probleme verwendet werden. Sie müssen sich nur dessen bewusst sein.

Hinweis Nr. 3 Wenn Ihre Datenstruktur sehr umfangreich ist und Sie sie häufig ändern, ist der Ansatz des Kopierens beim Schreiben möglicherweise sowohl hinsichtlich des Speicherverbrauchs als auch der CPU-Kosten für das Kopieren unerschwinglich. In diesem Fall möchten Sie möglicherweise stattdessen die unveränderlichen Sammlungen von MS verwenden.

Eugene Beresovsky
quelle
3

System.Collections.Generic.List<t>ist bereits threadsicher für mehrere Leser. Der Versuch, den Thread für mehrere Autoren sicher zu machen, wäre nicht sinnvoll. (Aus Gründen, die Henk und Stephen bereits erwähnt haben)

Billy ONeal
quelle
Sie können kein Szenario sehen, in dem möglicherweise 5 Threads zu einer Liste hinzugefügt werden? Auf diese Weise können Sie sehen, dass die Liste Datensätze sammelt, noch bevor sie alle beendet werden.
Alan
9
@Alan - das wäre eine ConcurrentQueue, ConcurrentStack oder ConcurrentBag. Um eine ConcurrentList zu verstehen, sollten Sie einen Anwendungsfall angeben, bei dem die verfügbaren Klassen nicht ausreichen. Ich verstehe nicht, warum ich einen indizierten Zugriff wünschen würde, wenn sich die Elemente an den Indizes durch gleichzeitiges Entfernen zufällig ändern können. Und für einen "gesperrten" Lesevorgang können Sie bereits Schnappschüsse der vorhandenen gleichzeitigen Klassen erstellen und in eine Liste aufnehmen.
Zarat
Sie haben Recht - ich möchte keinen indizierten Zugriff. Im Allgemeinen verwende ich IList <T> als Proxy für eine IEnumerable, zu der ich neue Elemente hinzufügen kann. Daher kommt die Frage wirklich.
Alan
@ Alan: Dann willst du eine Warteschlange, keine Liste.
Billy ONeal
3
Ich denke du liegst falsch. Sprichwort: Sicher für mehrere Leser bedeutet nicht, dass Sie nicht gleichzeitig schreiben können. Schreiben würde auch Löschen bedeuten und Sie erhalten eine Fehlermeldung, wenn Sie während der Iteration löschen.
Eric Ouellet
2

Einige Leute haben einige Warenpunkte (und einige meiner Gedanken) hervorgehoben:

  • Es könnte verrückt aussehen, wenn ein zufälliger Zugriff (Indexer) nicht möglich ist, aber für mich scheint es in Ordnung zu sein. Sie müssen nur denken, dass es viele Methoden für Multithread-Sammlungen gibt, die fehlschlagen können, z. B. Indexer und Löschen. Sie können auch eine Fehleraktion (Fallback) für Schreibzugriffsberechtigte wie "Fehler" oder einfach "Am Ende hinzufügen" definieren.
  • Nicht weil es sich um eine Multithread-Sammlung handelt, wird sie immer in einem Multithread-Kontext verwendet. Oder es kann auch nur von einem Schriftsteller und einem Leser verwendet werden.
  • Eine andere Möglichkeit, den Indexer auf sichere Weise verwenden zu können, besteht darin, Aktionen mithilfe ihres Stammverzeichnisses in eine Sperre der Sammlung zu packen (sofern veröffentlicht).
  • Für viele Menschen ist es eine gute Praxis, ein rootLock sichtbar zu machen. Ich bin mir in diesem Punkt nicht 100% sicher, denn wenn es versteckt ist, entziehen Sie dem Benutzer viel Flexibilität. Wir müssen immer daran denken, dass das Programmieren von Multithread für niemanden geeignet ist. Wir können nicht jede Art von falscher Verwendung verhindern.
  • Microsoft muss einige Arbeiten ausführen und einen neuen Standard definieren, um die ordnungsgemäße Verwendung der Multithreaded-Sammlung einzuführen. Erstens sollte der IEnumerator keinen moveNext haben, sondern einen GetNext, der true oder false zurückgibt und einen out-Parameter vom Typ T erhält (auf diese Weise würde die Iteration nicht mehr blockieren). Außerdem verwendet Microsoft "using" bereits intern in foreach, verwendet den IEnumerator jedoch manchmal direkt, ohne ihn mit "using" zu verpacken (ein Fehler in der Sammlungsansicht und wahrscheinlich an mehreren Stellen). Das Umschließen der Verwendung von IEnumerator wird von Microsoft empfohlen. Dieser Fehler beseitigt ein gutes Potenzial für einen sicheren Iterator ... Iterator, der die Sammlung im Konstruktor sperrt und die Dispose-Methode entsperrt - für eine blockierende foreach-Methode.

Das ist keine Antwort. Dies sind nur Kommentare, die nicht wirklich zu einem bestimmten Ort passen.

... Mein Fazit: Microsoft muss einige tiefgreifende Änderungen am "foreach" vornehmen, um die Verwendung der MultiThreaded-Sammlung zu vereinfachen. Außerdem muss es dort eigene Regeln für die Verwendung von IEnumerator befolgen. Bis dahin können wir leicht eine MultiThreadList schreiben, die einen blockierenden Iterator verwenden würde, aber nicht "IList" folgt. Stattdessen müssen Sie eine eigene "IListPersonnal" -Schnittstelle definieren, die ausnahmslos bei "Einfügen", "Entfernen" und zufälligem Zugriff (Indexer) fehlschlagen kann. Aber wer wird es verwenden wollen, wenn es nicht Standard ist?

Eric Ouellet
quelle
Man könnte leicht eine schreiben, ConcurrentOrderedBag<T>die eine schreibgeschützte Implementierung von beinhaltet IList<T>, aber auch eine vollständig threadsichere int Add(T value)Methode bietet . Ich verstehe nicht, warum ForEachÄnderungen erforderlich wären. Obwohl Microsoft dies nicht ausdrücklich sagt, deutet ihre Praxis darauf hin, dass es durchaus akzeptabel ist IEnumerator<T>, die zum Zeitpunkt der Erstellung vorhandenen Sammlungsinhalte aufzulisten. Die sammlungsmodifizierte Ausnahme ist nur erforderlich, wenn der Enumerator keinen störungsfreien Betrieb garantieren kann.
Supercat
Das Durchlaufen einer MT-Kollektion könnte, wie Sie sagten, zu einer Ausnahme führen ... Welche ich nicht kenne. Würden Sie alle Ausnahmen einfangen? In meinem eigenen Buch ist eine Ausnahme eine Ausnahme und sollte bei der normalen Ausführung von Code nicht auftreten. Andernfalls müssen Sie, um eine Ausnahme zu vermeiden, entweder die Sammlung sperren oder eine Kopie (auf sichere Weise, dh sperren) abrufen oder einen sehr komplexen Mechanismus in der Sammlung implementieren, um zu verhindern, dass eine Ausnahme aufgrund von Parallelität auftritt. Mein Gedanke war jedoch, dass es schön wäre, einen IEnumeratorMT hinzuzufügen, der die Sammlung sperrt, während ein für jeden auftritt und verwandten Code hinzufügt ...
Eric Ouellet
Das andere, was ebenfalls auftreten kann, ist, dass Sie die Sammlung sperren können, wenn Sie einen Iterator erhalten, und wenn Ihr Iterator GC-gesammelt ist, können Sie die Sammlung entsperren. Laut Microsfot prüfen sie bereits, ob die IEnumerable auch eine IDisposable ist, und rufen den GC gegebenenfalls am Ende eines ForEach auf. Das Hauptproblem ist, dass sie die IEnumerable auch an anderer Stelle verwenden, ohne den GC aufzurufen. Darauf können Sie sich dann nicht verlassen. Eine neue klare MT-Schnittstelle für die IEnumerable-Aktivierungssperre würde das Problem zumindest teilweise lösen. (Es würde die Leute nicht daran hindern, es nicht zu nennen).
Eric Ouellet
Es ist eine sehr schlechte Form für eine öffentliche GetEnumeratorMethode, eine Sammlung nach ihrer Rückkehr gesperrt zu lassen. Solche Designs können leicht zu einem Deadlock führen. Dies IEnumerable<T>gibt keinen Hinweis darauf, ob erwartet werden kann, dass eine Aufzählung abgeschlossen wird, selbst wenn eine Sammlung geändert wird. Das Beste, was man tun kann, ist, seine eigenen Methoden so zu schreiben, dass sie dies tun, und Methoden zu haben, die IEnumerable<T>die Tatsache dokumentieren, dass sie nur dann threadsicher sind, wenn sie IEnumerable<T>eine thread-sichere Aufzählung unterstützen.
Supercat
Am hilfreichsten wäre gewesen, wenn IEnumerable<T>eine "Snapshot" -Methode mit Rückgabetyp enthalten gewesen wäre IEnumerable<T>. Unveränderliche Sammlungen könnten sich selbst zurückgeben; Eine begrenzte Sammlung könnte sich, wenn nichts anderes, in ein List<T>oder kopieren T[]und das aufrufen GetEnumerator. Einige unbegrenzte Sammlungen könnten implementiert werden Snapshot, und diejenigen, die keine Ausnahme auslösen könnten , ohne zu versuchen, eine Liste mit ihrem Inhalt zu füllen.
Supercat
1

Bei der sequentiellen Ausführung von Code unterscheiden sich die verwendeten Datenstrukturen von (gut geschriebenen) gleichzeitig ausgeführten Codes. Der Grund ist, dass sequentieller Code implizite Reihenfolge impliziert. Gleichzeitiger Code impliziert jedoch keine Reihenfolge; Besser noch, es impliziert das Fehlen einer definierten Reihenfolge!

Aus diesem Grund sind Datenstrukturen mit impliziter Reihenfolge (wie List) für die Lösung gleichzeitiger Probleme nicht sehr nützlich. Eine Liste impliziert eine Reihenfolge, definiert jedoch nicht klar, um welche Reihenfolge es sich handelt. Aus diesem Grund bestimmt die Ausführungsreihenfolge des Codes, der die Liste manipuliert, (bis zu einem gewissen Grad) die implizite Reihenfolge der Liste, die in direktem Konflikt mit einer effizienten gleichzeitigen Lösung steht.

Denken Sie daran, dass Parallelität ein Datenproblem ist, kein Codeproblem! Sie können den Code nicht zuerst implementieren (oder vorhandenen sequentiellen Code neu schreiben) und erhalten eine gut gestaltete gleichzeitige Lösung. Sie müssen zuerst die Datenstrukturen entwerfen und dabei berücksichtigen, dass in einem gleichzeitigen System keine implizite Reihenfolge vorhanden ist.

Blaupause41
quelle
1

Der sperrlose Kopier- und Schreibansatz funktioniert hervorragend, wenn Sie nicht mit zu vielen Elementen arbeiten. Hier ist eine Klasse, die ich geschrieben habe:

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

}

Anwendungsbeispiel: orders_BUY = CopyAndWriteList.Clear (orders_BUY);

Rob The Quant
quelle
Anstatt zu sperren, wird eine Kopie der Liste erstellt, die Liste geändert und der Verweis auf die neue Liste festgelegt. Alle anderen Threads, die iterieren, verursachen also keine Probleme.
Rob The Quant
0

Ich habe eine ähnliche wie Brian implementiert . Meins ist anders:

  • Ich verwalte das Array direkt.
  • Ich betrete die Sperren nicht innerhalb des Try-Blocks.
  • ich benutze yield return für die Erstellung eines Enumerators.
  • Ich unterstütze die Sperrekursion. Dies ermöglicht das Lesen aus der Liste während der Iteration.
  • Ich verwende nach Möglichkeit aktualisierbare Lesesperren.
  • DoSyncund GetSyncMethoden, die sequentielle Interaktionen ermöglichen, die exklusiven Zugriff auf die Liste erfordern.

Der Code :

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
quelle
Was passiert, wenn zwei Threads gleichzeitig in den tryBlockanfang Removeoder in den Indexer-Setter gelangen?
James
@ James das scheint nicht möglich. Lesen Sie die Anmerkungen unter msdn.microsoft.com/en-us/library/… . Wenn
Ronnie Overby
@ Ronny Overby: Interessant. Angesichts dessen vermute ich, dass dies viel besser funktionieren würde, wenn Sie das UpgradableReadLock aus allen Funktionen entfernen würden, bei denen die einzige Operation in der Zeit zwischen der aktualisierbaren Lesesperre und der Schreibsperre ausgeführt wurde - der Aufwand für das Aufnehmen einer Sperre ist so viel höher als die Überprüfung, ob der Parameter außerhalb des Bereichs liegt, würde eine einfache Überprüfung innerhalb der Schreibsperre wahrscheinlich eine bessere Leistung erbringen.
James
Diese Klasse scheint auch nicht sehr nützlich zu sein, da die Offset-basierten Funktionen (die meisten von ihnen) nur dann wirklich sicher verwendet werden können, wenn es ohnehin ein externes Sperrschema gibt, da sich die Sammlung zwischen der Entscheidung, wo oder wo sie sich befinden soll, ändern kann Holen Sie sich etwas von und wann Sie es tatsächlich bekommen.
James
1
Ich wollte festhalten, dass ich erkenne, dass der Nutzen der IListSemantik in gleichzeitigen Szenarien bestenfalls begrenzt ist. Ich habe diesen Code wahrscheinlich geschrieben, bevor ich zu dieser Erkenntnis kam. Meine Erfahrung ist die gleiche wie die des Autors der akzeptierten Antwort: Ich habe es mit dem versucht, was ich über Synchronisation und IList <T> wusste, und dadurch etwas gelernt.
Ronnie Overby