Parallel.For Issue
-
I have a program that I'm trying to multithread. It works correctly on a single processor. All I had to do was change the for loop to Parallel.For and add ");" at the end. Basically, the structure is as follows:
Variables (V) that do not get modified inside the loop, including a LinkedList<BigInteger> that does.
Parallel.For (0, 5, j => {
BigInteger Variable that relies on j and another from (V - outside loop).
foreach (BigInteger k in numbers) {
Local Variables.
//Console.WriteLine(Everything in numbers.); if (condition)
{
Add k to LinkedList.
Console.WriteLine(k and other data.);
}
Console.WriteLine(Summary count per loop.);
});This parallel loop is missing a few values when multithreaded. However, if I put a write statement just before the IF to capture everything (commented out), it works. The summary count comes up accurate every time. If I comment it out, it fails, every time starting at higher values of k across all j. Basically, it starts working and slowly degrades. It seems to be that the write statement is slowing it down for it to work. Do I need a more threaded way of adding to the LinkedList array or am I missing something else? Any suggestions would be appreciated. NB - Can't submit code and this is console programming without the use of Visual Studio. Don't ask! :)
-
I have a program that I'm trying to multithread. It works correctly on a single processor. All I had to do was change the for loop to Parallel.For and add ");" at the end. Basically, the structure is as follows:
Variables (V) that do not get modified inside the loop, including a LinkedList<BigInteger> that does.
Parallel.For (0, 5, j => {
BigInteger Variable that relies on j and another from (V - outside loop).
foreach (BigInteger k in numbers) {
Local Variables.
//Console.WriteLine(Everything in numbers.); if (condition)
{
Add k to LinkedList.
Console.WriteLine(k and other data.);
}
Console.WriteLine(Summary count per loop.);
});This parallel loop is missing a few values when multithreaded. However, if I put a write statement just before the IF to capture everything (commented out), it works. The summary count comes up accurate every time. If I comment it out, it fails, every time starting at higher values of k across all j. Basically, it starts working and slowly degrades. It seems to be that the write statement is slowing it down for it to work. Do I need a more threaded way of adding to the LinkedList array or am I missing something else? Any suggestions would be appreciated. NB - Can't submit code and this is console programming without the use of Visual Studio. Don't ask! :)
if your loop iterations have data dependencies (e.g. you are trying to calculate the overall sum in one accumulator), then parallellized code would require synchronization, which could throw away most if not all of your potential performance gains. The normal way to efficiently calculate an overall sum would be to have explicit threads, each thread holding its own accumulator, summing the data entrusted on it; then in a sequential way adding all accumulators together. As always, simple solutions only work well in simple situations... :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
-
Bassam Abdul-Baki wrote:
LinkedList array
What? Anyway you may have a problem there, adding to a linked list is not an atomic operation.
I'm using AddLast. After exhausting all other options, I had a feeling this might be it, but I wasn't sure. So any suggestions on how to fix or work around it?
-
Bassam Abdul-Baki wrote:
LinkedList array
What? Anyway you may have a problem there, adding to a linked list is not an atomic operation.
David1987 wrote:
adding to a linked list is not an atomic operation.
Neither is any operation on a BigInteger! :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
-
if your loop iterations have data dependencies (e.g. you are trying to calculate the overall sum in one accumulator), then parallellized code would require synchronization, which could throw away most if not all of your potential performance gains. The normal way to efficiently calculate an overall sum would be to have explicit threads, each thread holding its own accumulator, summing the data entrusted on it; then in a sequential way adding all accumulators together. As always, simple solutions only work well in simple situations... :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
No summing involved. Just some computations to see if the data gets added to the list or not. Each loop could work independently since they don't really depend on one another, but they all add to the same LinkedList using AddLast.
-
David1987 wrote:
adding to a linked list is not an atomic operation.
Neither is any operation on a BigInteger! :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
Aghhh! That explains it and crap.
-
David1987 wrote:
adding to a linked list is not an atomic operation.
Neither is any operation on a BigInteger! :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
-
No summing involved. Just some computations to see if the data gets added to the list or not. Each loop could work independently since they don't really depend on one another, but they all add to the same LinkedList using AddLast.
Collections (and most every other kind of objects) aren't thread safe by themselves. You may consider having a thread-local list-of-things-to-add-later, fill those in parallel, then add them in sequentially. And if that is the majority of the work, parallellizing won't help you a bit. :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
-
Collections (and most every other kind of objects) aren't thread safe by themselves. You may consider having a thread-local list-of-things-to-add-later, fill those in parallel, then add them in sequentially. And if that is the majority of the work, parallellizing won't help you a bit. :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
Thanks, but it is the majority of the work. :(
-
Bassam Abdul-Baki wrote:
LinkedList array
What? Anyway you may have a problem there, adding to a linked list is not an atomic operation.
Yep, it's the add to the collection that's causing the problem. I'm guessing this is a vast oversimplification because what's posted there is not worth parallelising anyway. Assuming the stuff inside the loop (calculating what's to be put in the list) is the expensive part, have a thread-local list (a local variable to the lambda) and merge them all at the end. If it's actually adding millions of simple things to a list then you'll need to be cleverer about how you put things in there, for example creating an array large enough for everything beforehand and interleaving the results into well defined indices so they can't collide.
-
locals are fine; however when there is one BigInteger, there is bound to be more, and the code looked rather abstract and incomplete, so I mentioned it just in case it would ring a bell. :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
-
Yep, it's the add to the collection that's causing the problem. I'm guessing this is a vast oversimplification because what's posted there is not worth parallelising anyway. Assuming the stuff inside the loop (calculating what's to be put in the list) is the expensive part, have a thread-local list (a local variable to the lambda) and merge them all at the end. If it's actually adding millions of simple things to a list then you'll need to be cleverer about how you put things in there, for example creating an array large enough for everything beforehand and interleaving the results into well defined indices so they can't collide.
BobJanova wrote:
creating an array large enough for everything beforehand and interleaving the results into well defined indices so they can't collide
I had never thought of that before. :doh: :thumbsup:
-
Thanks, but it is the majority of the work. :(
Since it seems you are already using .NET 4, you can give a look to the new Thread-safe collections.
-
Yep, it's the add to the collection that's causing the problem. I'm guessing this is a vast oversimplification because what's posted there is not worth parallelising anyway. Assuming the stuff inside the loop (calculating what's to be put in the list) is the expensive part, have a thread-local list (a local variable to the lambda) and merge them all at the end. If it's actually adding millions of simple things to a list then you'll need to be cleverer about how you put things in there, for example creating an array large enough for everything beforehand and interleaving the results into well defined indices so they can't collide.
-
Since it seems you are already using .NET 4, you can give a look to the new Thread-safe collections.