Transforming a code to Grand Central Dispatch

Question

I have an array of NSNumbers that have to pass thru 20 tests. If one test fails than the array is invalid if all tests pass than the array is valid. I am trying to do it in a way that as soon as the first failure happens it stops doing the remaining tests. If a failure happens on the 3rd test then stop evaluating other tests.

I am trying to convert the code I have that is serial processing, to parallel processing with grand central dispatch, but I cannot wrap my head around it.

This is what I have.

First the definition of the tests to be done. This array is used to run the tests.

Every individual test returns YES when it fails and NO when it is ok.

#define TESTS  @[         \
    @"averageNotOK:",     \
    @"numbersOverRange:", \
    @"numbersUnderRange:",\
    @"numbersForbidden:", \
    // ... etc etc
    @"numbersNotOnCurve:"]


- (BOOL) numbersPassedAllTests:(NSArray *)numbers {

  NSInteger count = [TESTS count];

  for (int i=0; i<count; i++) {

    NSString *aMethodName = TESTS[i];

        SEL selector = NSSelectorFromString(aMethodName);

        BOOL failed = NO;

        NSMethodSignature *signature = [[self class] instanceMethodSignatureForSelector:selector];

        NSInvocation *invocation = [NSInvocation invocationWithMethodSignature:signature];
        [invocation setSelector:selector];
        [invocation setTarget:self];
        [invocation setArgument:&numbers atIndex:2];
        [invocation invoke];


        [invocation getReturnValue:&failed];

        if (failed) {
          return NO;
        }
  }
  return YES;

}

This work perfectly but perform the tests sequentially.

How do I do that perform these tests in parallel executing the less amount of tests as needed?

Answer 1

I assume you've spotted dispatch_apply which is the trivial parallel for. You've realised it can't do an early exit. Hence the question.

I'm afraid the answer is you'll need to do some bookkeeping for yourself, but luckily it shouldn't be too hard. To avoid repeating what you've got, pretend I'd turned the stuff inside your loop into:

BOOL failedTest(int);

So your serial loop looks like:

for (int i=0; i<count; i++) {

    if(failedTest(i))
      return NO;
}

return YES;

Then you might do:

#import <libkern/OSAtomic.h>

volatile __block int32_t hasFailed = 0;
dispatch_apply(
    count, 
    dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0), 
    ^(size_t i)
    {
        // do no computation if somebody else already failed
        if(hasFailed) return;
        if(failedTest(i))
            OSAtomicIncrement32(&hasFailed);
    });

return !hasFailed;

So it'll keep starting tests until one of them has previously failed. The OSAtomicIncrement32 just ensures atomicity without requiring a mutex. It'll usually turn into a cheap single instruction. You could get away with just using a BOOL as atomicity isn't really going to be a problem but why not just do it properly?

EDIT: also, you could just use @selector directly and create an array of selectors rather than using NSSelectorFromString with an array of strings, to save lookup time. If your tests are really cheap then consider doing them part serial, part parallel by having the dispatch_apply do, say, count/10 dispatches and having each dispatch do 10 tests. Otherwise GCD will just issue count instances of the block and issuing has an associated cost.