Auf der Suche nach einer schnelleren Implementierung für iEnumerable/iEnumerator

Question

Ich versuche, eine gleichzeitige Sammlung zu optimieren, die versucht, die Verriegelungskonkurrenz für Lesevorgänge zu minimieren. Der erste Pass verwendete eine verknüpfte Liste, mit der ich nur Schreibvorgänge sperren konnte, während viele gleichzeitige Lesevorgänge unverbödert werden konnten. Dies verwendete einen Brauch IEnumerator zu Ertrag der nächste Linkwert. Als ich anfing, die Iteration über die Sammlung mit einer Ebene zu vergleichen List<T> Ich bemerkte, dass meine Implementierung ungefähr halb so schnell war (für from x in c select x Auf einer Sammlung von 1* m* Artikeln bekam ich 24 ms zum List<T> und 49 ms für meine Sammlung).

Also dachte ich, ich würde eine benutzen ReaderWriteLockSlim und opfere ein wenig Streit auf Lesevorgänge, damit ich a benutzen konnte List<T> als mein interner Speicher. Da ich das Lese -Sperre für Iterationsstart erfassen und nach Abschluss freigeben muss, habe ich zum ersten Mal ein Ertragsmuster für meine gemacht IEnumerable, für jedenÜber die Innere List<T>. Jetzt bekam ich nur noch 66 ms.

Ich schaute auf die Liste, die tatsächlich tut, und es verwendet einen internen Geschäft von T[] und ein Brauch IEnumerator Dadurch wird der Index vorwärts geschaltet und gibt den aktuellen Indexwert zurück. Jetzt manuell benutzen T[] als Speicherung bedeutet viel mehr Wartungsarbeiten, Aber mit WT, Ich jage Mikrosekunden.

Allerdings sogar nachahmten die IEnumerator Wenn ich den Index in einem Array bewegen konnte, war das Beste, was ich tun konnte ~ 38 ms. Also was gibt List<T> Seine geheime Sauce oder alternativ Was ist eine schnellere Implementierung für einen Iterator?

AKTUALISIEREN: Es stellt sich heraus List<T> ist offensichtlich ein Veröffentlichungskompilieren. Bei der Freigabe ist meine Implementierung immer noch ein Haar langsamer als List<T>, Altough auf Mono, es ist jetzt schneller.

Ein weiterer Vorschlag, den ich von einem Freund bekommen habe, ist, dass die BCL schneller ist, weil sie im GAC ist und daher vom System vorkompiliert werden kann. Muss meinen Test in die GAC setzen, um diese Theorie zu testen.

Answer 1

Das Erwerb und Verlassen der Sperre für jede Iteration klingt nach einer schlechten Idee - denn wenn Sie eine ausführen Add oder Remove Während Sie über die Liste iteriert werden, wird dies den Iterator ungültig machen. List<T> Das würde das zum Beispiel sicherlich nicht mögen.

Würde Ihr Anwendungsfall den Anrufern erlauben, a zu nehmen? ReaderWriterLockSlim Um ihren gesamten Iterationsprozess, statt auf pro-oder-oder-Grundlage? Das wäre effizienter und robuster. Wenn nicht, wie planen Sie, mit dem Problem der Parallelität umzugehen? Wenn ein Autor ein Element früher als den Ort hinzufügt, an dem ich angegangen bin, würde eine einfache Implementierung das gleiche Element zweimal zurückgeben. Das Gegenteil würde bei einer Entfernung passieren - der Iterator würde ein Element überspringen.

Schließlich ist .NET 4.0 eine Option? Ich weiß, dass es dort einige hoch optimierte gleichzeitige Sammlungen gibt ...

Bearbeiten: Ich bin mir nicht ganz sicher, wie Ihre aktuelle Situation im Hinblick auf den Aufbau eines Iterators von Hand ist, aber eine Sache, die Sie möglicherweise untersuchen möchten, ist, eine Struktur für die zu verwenden IEnumerator<T>, und Ihre Sammlung ausdrücklich erklären, dass sie das zurückgibt - das ist was List<T> tut. Es tut Ich meine eine veränderliche Struktur, die Kätzchen auf der ganzen Welt weinen lässt, aber wenn dies für die Leistung absolut von entscheidender Bedeutung ist und Sie denken, Sie können mit dem Horror leben, ist es zumindest einen Versuch wert.