Argumentnullexception bei Parallel.Foreach
Hallo!
(Auch auf die Gefahr hin, dass gleich wieder die Grundlagenkeule geschwungen wird, frage ich einfach mal)
Ich habe derzeit zwei Listen von Objekten, die ich miteinander verlgeichen muss. Tritt ein Element aus Liste 1 auch in Liste 2 auf, wird es in eine dritte Liste kopiert.
Die Listen haben beide etwa 300.000 Elemente, was bedeutet, dass der Rechenaufwand schon erheblich sein kann.
Mit der "naiven" Vergleichsmethode (O(|R| * |S|)) benötige ich etwa 186.099ms bei 100.000 Elementen.
Mein optimierter Algorithmus benötigt bei 100.000 Elementen 2.636ms.
Nun habe ich mich ein wenig mit Tasks beschäftigt und dachte, ich könnte doch mal versuchen, die Algorithmen zu parallelisieren.
Dazu habe ich mal Galileo Openbook gelesen und gleich im Anschluss einige Kapitel in Patterns for Parallel Programming: Understanding and Applying Parallel Patterns with the .NET Framework 4.
Anfangen wollte ich mit der Umsetzung des "naiven" Algorithmuses:
private void compareNaivSynch()
{
foreach (String firstItem in firstList)
{
foreach (String secondItem in secondList)
{
if (firstItem == secondItem)
{
comparedList.Add(firstItem);
}
}
}
}
private ParallelLoopResult compareNaivParallel()
{
return Parallel.ForEach(firstList, firstItem =>
{
foreach (String secondItem in secondList)
{
if (firstItem == secondItem)
{
comparedList.Add(firstItem);
}
}
});
}
Die parallele Methode benötigt "nur" 49.209ms auf 100.000 Elemente. Scheint also schon mal ganz gut zu funktionieren.
Die gleichen Elemente der dritten Liste gebe ich mit:
listBox3.Items.AddRange(comparedList.ToArray());
in eine ListBox aus, um zu sehen, ob alles korrekt ist.
Bei 100.000 Elementen funktioniert das alles, wie gesagt, ganz prima. Versuche ich das ganze aber mit 300.000 Elementen, erhalte ich immer die "Argumentnullexception" bei der Methode
listBox3.Items.AddRange(comparedList.ToArray());
.
Hat jemand da eine Idee?
Interessant wäre natürlich noch zu Erfahren, was die Exception als Message-Text enthält, und was du beim Debugging herausgefunden hast.
Die List<T>.ToArray-Methode gibt jedenfalls kein null zurück, und ein anderes Argument übergibst du nicht in der von dir geposteten Code-Zeile. Wenn die Exception nicht in einer Sub-Methode geworfen wird (auch das steht in der Beschreibung der Exception), dann verwendest du sicher die ToArray Methode aus dem System.Linq-Namespace. Dann könnte die Ursache sein, daß comparedList null ist.
Weeks of programming can save you hours of planning
Hallo,
also offensichtlich ist ja bei
listBox3.Items.AddRange(comparedList.ToArray());
entweder Items oder comparedList grade null (ich tippe auf comparedList).
Da du Ultimate hast kannst du ja vielleicht zurückspulen und schauen, warum das so ist.
Im übrigen was deinen Algoritmus angeht:
zwei Sortierte Mengen sind relativ einfach zu vergleichen:
- zwei Zeiger (also Indexzähler)
- auf der Menge mit dem aktuell kleineren Wert den Index hochzählen
- bei gleichen Einträgen den aktuellen kopieren
damit bekommst du eine Laufzeit (ohne Sortieren) von O(R+S) allerdings nicht paralellisierbar
Ebenfalls könnte dir ein IEnumerable<>.Join() das gewünschte ergebnis bringen (da kenn ich aber die Laufzeit nicht)
Der Vorteil der Klugheit liegt darin, dass man sich dumm stellen kann - umgekehrt ist das schon schwieriger (K. Tucholsky)
Das Problem mit Internet-Zitaten ist, dass sie oftmals zu unrecht als authentisch angenommen werden. (K. Adenauer)
Im übrigen was deinen Algoritmus angeht:
zwei Sortierte Mengen sind relativ einfach zu vergleichen:
- zwei Zeiger (also Indexzähler)
- auf der Menge mit dem aktuell kleineren Wert den Index hochzählen
- bei gleichen Einträgen den aktuellen kopieren
damit bekommst du eine Laufzeit (ohne Sortieren) von O(R+S) allerdings nicht paralellisierbar
Ja, kenn ich. Nennt sich Merge-Join 😉
Es geht mir bei dem Versuch auch mehr um das Experimentieren mit Parallität. Im Rahmen von Datenbanken gibt es ja auch deutlich effizientere parallele Join - Algorithmen und wie gesagt, ich wollte damit mal rumspielen.
entweder Items oder comparedList grade null (ich tippe auf comparedList).
Da du Ultimate hast kannst du ja vielleicht zurückspulen und schauen, warum das so ist.
Ich schau mir das mal an!
Nachtrag:
Ich habe es gerade noch einmal getestet und muss leider festellen, dass das Problem nicht immer auftritt.
Manchmal funtkioniert es und manchmal nicht. Wovon das abhängt, ist mir leider nicht ganz klar.
Bevor du dir etwas falsches beibringst:
Thread-safe Collections in .NET Framework 4 and Their Performance Characteristics
Du verletzt mit deinem Code ein paar der Regeln. Wirkliche Performance bekommst du nur mit Temporären Listen und indem du die Quellisten in Blöcke aufteilst. Außerdem gewinnst du gerade bei so vielen Elementen enorm viel, wenn du die Listen mit einer ausreichenden Größe vorinitialisierst.
Ich würde meine Hand ins Feuer legen, das die Naive Methode mit entsprechenden Listeninitialisierungen einen massiven Performanceboost erlebt.
Zum anfänglichen Problem.
Es gibt in der Liste tatsächlich ein einziges Element mit einem null-wert an der Position 65537.
Ich habe keine Ahnung, warum das so ist.
[EDIT] Könnte es damit etwas zu tun haben, dass .add() nicht thread-safe ist?
Ich hab gelesen, dass es mehr schlechter Stil wäre, lock() in einer Parallel.ForEach zu verwenden. [/EDIT]
Bevor du dir etwas falsches beibringst:
>
Leider kann ich den Link nicht öffnen.
Link repariert.
Aus welchem Namespace kommt denn die Liste?
und noch etwas für dich:
Patterns for parallel programming
Aus welchem Namespace kommt denn die Liste?
System.Collections.Generic;
Hallo Wirtschaftsinformatiker,
hast du PLinq schon in Erwägung gezogen? Das wäre hier wohl passender als Paralle.ForEach.
Und ist dir auch bewusst dass das absolut nicht sprachunbhängig ist? - SCNR
mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
Was ich bisher festgestellt habe:
Mit der Verwendung einer Liste von System.Collections.Concurrent funktioniert es.
Mit einer Liste aus System.Collections.Generics und lock() funktioniert es nicht.
Was ich daraus schließe:
Die NULL-Werte tauchen immer bei Vielfachen von 8 auf. D.h., das auf Element 65536 folgende Element kann null sein, das auf Element 131072 folgende Element kann null sein, etc.pp...
Ich denke, das Problem hängt also mit der Standardkapazität der Listen zusammen. "Capacity ist immer größer oder gleich Count. Wenn beim Hinzufügen von Elementen der Wert von Count den Wert von Capacity überschreitet, wird die Kapazität durch automatisches Neureservieren des internen Arrays erhöht, bevor die alten Elemente kopiert und die neuen Elemente hinzugefügt werden. "
Irgendwas läuft dort beim parallelen Ablauf wohl schief.
hast du PLinq schon in Erwägung gezogen? Das wäre hier wohl passender als Paralle.ForEach.
Nein, ich schau mir das mal an.
Und ist dir auch bewusst dass das absolut nicht sprachunbhängig ist? - SCNR
Ja, das ist auch mein Privatvergnügen. Ich weiß auch gar nicht genau, wie man sowas in Java umsetzt...
Hallo Wirtschaftsinformatiker,
Mit der Verwendung einer Liste von System.Collections.Concurrent funktioniert es.
In diesem Namespace gibt es keine Liste. Verwende hier am ehesten den ConcurrentBag<T> - oder aber PLinq denn das ist dafür entwickelt worden.
mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
In diesem Namespace gibt es keine Liste. Verwende hier am ehesten den ConcurrentBag<T> - oder aber PLinq denn das ist dafür entwickelt worden.
Genau den verwende ich.
Hallo Wirtschaftsinformatiker,
das war wohl eher ein sprachliches Missverständnis —ConcurrentBag<T> implementiert IList<T> nicht und ist deshalb in dem Sinne keine Liste.
ConcurrentBag<T> ist allerdings eine Collection, denn es werden ICollection<T>, IEnumerable<T> und IEnumerable implementiert.
m0rius
Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg
Ich denke, das Problem hängt also mit der Standardkapazität der Listen zusammen.
Nein. Das hat damit nichts zu tun.
wird die Kapazität durch automatisches Neureservieren des internen Arrays erhöht, bevor die alten Elemente kopiert und die neuen Elemente hinzugefügt werden. "
Irgendwas läuft dort beim parallelen Ablauf wohl schief.
Willkommen in der Welt des Multithreadings. Jetzt hast du den Fehlerort gefunden, auch wenn du die Ursache nach wie vor nicht nachvollziehen kannst.
Multithreading ist eine komplexe Angelegenheit. Vor allem dann, wenn du auch noch Closures und Lambdas ins Spiel bringst. Dann schaut alles immer so sauber und Korrekt aus aber zur Laufzeit ist es der Horror.
Hallo Wirtschaftsinformatiker,
..., wird die Kapazität durch automatisches Neureservieren des internen Arrays erhöht, bevor die alten Elemente kopiert und die neuen Elemente hinzugefügt werden.
klar, dadurch dauert die Add-Operation ein vielfaches länger, als wenn die Kapazität noch ausreicht (O(n) statt O(1)) und damit steigt die Wahrscheinlichkeit deutlich, dass zwei oder mehr Add-Operationen ineinander verzahnt ausgeführt werden. Aber das sollte sich erstens von selbst verstehen und zum anderen sollte sich von selbst verstehen, dass der parallele Zugriff auf eine Collection, die nicht thread-safe ist, immer Probleme verursachen kann, selbst wenn die Kapazität noch ausreicht.
(Auch auf die Gefahr hin, dass gleich wieder die Grundlagenkeule geschwungen wird, frage ich einfach mal)
Ja, die kommt auch diesmal wieder. Deine Eingangsfragen als solche sind zwar keine Grundlagenfragen, aber du lässt immer wieder an bestimmten Punkten erkennbar die Grundlagen des jeweiligen Themengebiets außer acht, was dann überhaupt erst zu Problemen und Fragen führen. Dass man bei parallelen (erst recht schreibenden) Zugriffen eine Collection verwenden muss, die threadsafe ist, muss man einfach wissen, wenn man sich an Multithreading macht.
Es geht mir bei dem Versuch auch mehr um das Experimentieren mit Parallität. Im Rahmen von Datenbanken gibt es ja auch deutlich effizientere parallele Join - Algorithmen und wie gesagt, ich wollte damit mal rumspielen.
Es gibt bessere Möglichkeiten mit Threading zu spielen, als nun gerade bei einem Problem, das man durch Threading nur marginal (konstanter Faktor), durch einen anderen/besseren Algorithmus (z.B. eben durch die Sortierung oder durch HashSets) aber drastisch (niedrigere Aufwandsklasse) beschleunigen kann. Es sind solche Punkte, die meisten deiner Threads immer etwas schräg erscheinen lassen.
Ich sage das nicht, um dich niederzumachen, sondern um dir (in die Spur) zu helfen.
herbivore