PLINQ problem / techniques to impliment multi-threaded, lock-free lists (in C#).

Question

Here's the code in question:

             parentNodes.AsParallel().ForAll(parent =>
            {
                List<Piece> plist = parent.Field.GetValidOrientations(pieceQueue[parent.Level]);

                plist.ForEach(p =>
                {
                    TreeNode child = new TreeNode(p, parent);
                    var score = child.CalculateScore(root);
                    levelNodes.Add(child);
                });

            });

On runtime, that code occasionally leaves null references in levelNodes. I suspect this is due to thread lock, because the problem disappears if a normal (non-parallel) ForEach is called in place of the ForAll.

With the PLINQ implimentation, 'levelNodes.Add(child);' also occasionally throws an IndexOutOfRangeException with the message: "Source array was not long enough. Check srcIndex and length, and the array's lower bounds."

Any suggestions to eliminate this problem?
Or perhaps performance would be increased with a lock-free List implimentation? (How might one go about this?)

Answer 1

Do you really need both levels of parallelism here? Is it not enough to just parallelise over the parent nodes?

Anyway, writing to a List<T> from multiple threads without locking if definitely not a good idea. However, PFX comes with a concurrent collection which may fit your needs: ConcurrentBag. It's unordered (to allow it to be lock-free) but given the interplay between threads here, I guess that's not an issue for you.