Efficient foreach child evaluation in parallel

Question

I have a list of objects, each with a bool ShouldRun() method on them.

I am currently iterating over the list of objects, and checking ShouldRun() on each object, and calling Run() on the first one to return true

foreach (child in Children)
{
   if (child.ShouldRun())
   {
      child.Run();
      break;
    }
 }

I would like to do this in parallel, because evaluating shouldRun can take a decent amount of time, and it is advantageous to let later elements in the collection start their evaluation early.

However, I cannot think of a way to do this that will satisfy these conditions :

1 Only run one item

2 Do not run a later item if an earlier item is true, or has not finished evaluating yet

3 If all "earlier" items have returned false, and a middle item returns true, do not wait on a later item to finish evaluating because you know it can't override anything earlier.

I thought of doing a parallel "where" linq query to retrieve all the items that shouldRun() and then sorting, but this will violate condition #3

Ideas?

Background info :

The system is for a generalized robotics AI system.

Some of the higher priority tasks can be triggered by immediately known sensor variables eg : Im falling over, fix it!

other tasks might be computationally intensive (do image recognition from the camera, and approach visible objectives)

other tasks might be database or remotely driven (look up a list of probable objective locations from a database, and then navigate there to see if you can get into visible range of one of them)

Some of the tasks themselves have child tasks, which is essentially going to start this process over recursively at a subset of tasks, and the grandchild task will be passed up through the chain

Answer 1

Just a concept of way I would try to do it.

Run all ShouldRun()'s in parallel. Put the results to the ordered list along with the items and indexes of the items (e.g. ShouldRun() of third item ends with false, the list would contain something like: 2,false,item).

In another thread, keep current index starting with 0 and check the ordered list periodically. If the next index on the list equals to current, process the result and advance the current index.

Answer 2

You should be able to do a parallel select with the indices attached, then sort the result based on index and pick the first which returned true. I don't have an IDE on this machine so this is untested, but something like:

var runnables = Children.AsParallel()
                        .Select(child, index => 
                                new { 
                                        Index = index, 
                                        ShouldRun = child.ShouldRun(),
                                        Child = child 
                                    })
                        .ToList(); //force evaluation
var firstRunner = runnables.OrderBy(r => r.Index)
                           .First(r => r.ShouldRun) //assuming at least one
                                   //else use FirstOrDefault and null-check
                           .Child;
firstRunner.Run();

edit: better query for the first runner -

var firstRunner = runnables.Where(r => r.ShouldRun) // less stuff to sort later
                           .OrderBy(r => r.Index)
                           .First(); // no need for predicate here anymore

edit2: this doesn't satisfy your condition #3, though.

Answer 3

I'm puzzled as to why you have a "ShouldRun" flag on each child, rather than having earlier placed each child that you would mark as "ShouldRun" into a "RunThese" set.

Then you only have to ask if the RunThese set size is zero or not, and if not zero, run them all.

[Of course, if you are going to run them, why even mark/set union them? You could just launch them when you discover you should run them. If you think the ShouldRun logic is expensive, then fork it the moment you have the child to decide whether you should run the child.]

Answer 4

I'm not a PLINQ genius, but wouldn't this simpler answer suffice?

var childToRun = Children.AsParallel().AsOrdered()
    .Where(x => x.ShouldRun()).FirstOrDefault();
childToRun.Run();