Asynchronous cancelling structured_task_group?

Question

I've been trying to write a parallel_find which works like so:
- Split the range up in to chunks for each core
- Run the first chunk on the calling thread to reduce overhead
- If the first chunk returns and has found the element, cancel the task and return the iterator.  There is no point doing any more work as soon as something is found in the first chunk of elements.

For example, if the element was found in the very first element in the range, the function should return as quickly as possible.

However, if I run() a series of tasks on a structured_task_group, determine that work should be cancelled, then call structured_task_group::cancel(), a missing_wait exception is thrown.  If I add a wait() after cancel(), according to my measurements a significant amount of time is wasted waiting for other thread(s) to finish up, when the answer is already known and ready to return.

Is it possible to add a kind of asynchronous_cancel() for this kind of situation?  It would simply return execution immediately but wind down the threads in the background (possibly blocking if another structured_task_group immediately runs after).

I have tried to come up with my own solution involving creating, waiting and destroying structured_task_groups on demand, but it seems like a pretty big hack.

Answer 1

Ashley,

consider the following implementation of parallel_all_of (I'll put something like this in the next version of our sample pack). It relies on using parallel_for_each and cancellation to achieve the result, it should be somewhat similar to parallel_find.

If you're using structured_task_group, you must call wait, or you get the exception mentioned.  Here I'm using a task_group *just* for cancellation the overhead should be minimal.


template<class _InIt,class _Pr>
inline bool parallel_all_of(_InIt _First, _InIt _Last, _Pr _Pred)
{
    _DEBUG_RANGE(_First, _Last);
    _DEBUG_POINTER(_Pred);

    typedef iterator_traits<_InIt>::value_type _Item_type;

    //create a structured task group
    structured_task_group _Tasks;

    auto _For_Each_Predicate = [&_Pred,&_Tasks](const _Item_type& _Cur){
            if (!_Pred(_Cur))
                _Tasks.cancel();
    };

    auto _Task = make_task([&_First,&_Last,&_Pred,&_Tasks,&_For_Each_Predicate](){
        parallel_for_each(_First,_Last,_For_Each_Predicate);
    });

    _Tasks.run(_Task);
    return _Tasks.wait() != canceled;
}

---

Rick Molloy Parallel Computing Platform : http://blogs.msdn.com/nativeconcurrency