CODEWITHSUNDEEP
c#multithreadingparallel-processingtask-parallel-library
Alejandro Piad
Alejandro Piad

Reputation: 1877

Unexpected thread contention in Parallel.Foreach

I have tried to implement the following algorithm using Parallel.Foreach. I thought it would be trivial to make parallel, since it has no synchronization issues. It is basically a Monte-Carlo tree search, where I explore every child in a parallel. The Monte-Carlo stuff is not really important, all you have to know is that I have a method which works a some tree, and which I call with Parallel.Foreach on the root children. Here is the snippet where the parallel call is being made.

    public void ExpandParallel(int time, Func<TGame, TGame> gameFactory)
    {
        int start = Environment.TickCount;

        // Creating all of root's children
        while (root.AvailablePlays.Count > 0)
            Expand(root, gameInstance);

        // Create the children games
        var games = root.Children.Select(c =>
        {
            var g = gameFactory(gameInstance);
            c.Play.Apply(g.Board);
            return g;

        }).ToArray();

        // Create a task to expand each child
        Parallel.ForEach(root.Children, (tree, state, i) =>
        {
            var game = games[i];

            // Make sure we don't waste time
            while (Environment.TickCount - start < time && !tree.Completed)
                Expand(tree, game);
        });

        // Update (reset) the root data
        root.Wins = root.Children.Sum(c => c.Wins);
        root.Plays = root.Children.Sum(c => c.Plays);
        root.TotalPayoff = root.Children.Sum(c => c.TotalPayoff);
    }

The Func<TGame, TGame> delegate is a cloning factory, so that each child has its own clone of the game state. I can explain the internals of the Expand method if required, but I can assure that it only accesses the state of the current sub-tree and game instances and there are no static members in any of those types. I thought it may be that Environment.TickCount is making the contention, but I ran an experiment just calling EnvironmentTickCount inside a Parallel.Foreach loop, and got nearly 100 % processor usage.

I only get 45% to 50% use on a Core i5.

Upvotes: 0

Views: 466

Answers (1)

csharptest.net
csharptest.net

Reputation: 64218

This is a common symptom of GC thrashing. Without knowing more about what your doing inside of the Expand method, my best guess is this would be your root-cause. It's also possible that some shared data access is also the culprit, either by calling to a remote system, or by locking access to shared resources.

Before you do anything, You need to determine the exact cause with a profiler or other tool. Don't guess as this will just waste your time, and don't wait for an answer here as without your complete program it can not be answered. As you already know from experimentation, there is nothing in the Parallel.ForEach that would cause this.

Upvotes: 2

Related Questions