Concurrent mapping with GCD.

gistfile1.m

- (void)mapConcurrent;
{
  NSArray *originals = self.listOfObjects;

  NSUInteger count = originals.count;
  NSMutableArray *collected = [[NSMutableArray alloc] initWithCapacity:count];

  dispatch_group_t workGroup = dispatch_group_create();
  dispatch_queue_t assignmentQueue = dispatch_queue_create("com.example.SerialAssignmentQueue", DISPATCH_QUEUE_SERIAL);
  dispatch_queue_t concurrentQueue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);

  for (NSUInteger i = 0; i < count; i++) {
    dispatch_group_async(workGroup, assignmentQueue, ^{
      // First ensure the destination slot exists, otherwise we can't assign the
      // slot by index later on.
      [collected addObject:[NSNull null]];

      dispatch_group_async(workGroup, concurrentQueue, ^{
        id original = originals[i];
        id result = [original performWork];
        dispatch_group_async(workGroup, assignmentQueue, ^{
          collected[i] = result;
        });
      });
    });
  }

  dispatch_group_wait(workGroup, DISPATCH_TIME_FOREVER);
}

let me put some Pseudocode of my people

class Array
  def p_map &block
    access_queue = Dispatch::Queue.new('result.queue')
    group = Dispatch::Group.new
    collected = NSMutableArray.alloc.initWithCapacity self.count

    Dispatch::Queue.concurrent.apply(self.count) do |idx|
      obj = self[idx]
      current_value = block[obj] # of course I have to execute the block in
     # the concurrent queue, otherwise I could just use a serial one 
      access_queue.async(group) { collected << current_value }  if current_value
    end

    group.wait
    collected
  end
end

@seanlilmateus Aaah, you see, from reading the dispatch_apply docs, I had not understood that the C version also yields a counter, so I thought I’d have to do that in a thread-safe manner as well. Awesome!

Hmm, no, wait. I still need to fill the array as well and I now realise that my version was not doing that in a safe manner either, because one of the work blocks could access it at the same time I push a null object…

I have update the original gist to ensure the null object is pushed onto the array in the same assignment queue.

I can see a few ways to make this code shorter, but I think I’ll first implement the real heavy work and then profile to ensure I get the fastest way possible.

I should have replied earlier, but what about this approach: http://blog.aki-null.net/blog/2009/10/14/grand-central-dispatch-part-2/?

Basically, I searched for "dispatch_apply nsmutablearray" and found that link describes what I may have ended up with. The last version, using a semaphore, looks solid.

@kastiglione actually looks like my pseudocode, the only difference is that he is using dispatch_semaphore in place of a serial queue.

@seanlilmateus indeed, I wonder what the pros & cons are of the two approaches. Maybe someone will benchmark and post the result here.

@alloy here's a fork to illustrate: https://gist.github.com/kastiglione/5679834

To skip the for loop that null-fills the array, maybe calloc an array of ids and then use +arrayWithObjects:count: to build the collected array.

@kastiglione I believe with my approach no dispatch_queue get "locked". Semaphore lock the thread on the current dispatch_queue, on the other side a serial queue enqueues all blocks and execute one by one. the dispatch_group waits until the queue is empty. does it make sense? but I measurement is indeed needed :-)

@kastiglione @seanlilmateus I haven’t had the time this evening, but I will take a close look tomorrow, thanks!

@kastiglione I have the same feeling that @seanlilmateus has regarding locking the concurrent queue, although the question is probably what GCD actually does under the hood. I’m going to remove some noise from my version and once the app has all the required functionality I’ll do some benchmarking of the three options.

PS: A carray or a NSPointerArray is probably indeed an appropriate solution for pre-filling the list.

I got a benchmark partially going, and the early results have semaphores beating async to a serial queue, at least on my hardware. I'll post it soonish.

@alloy @seanlilmateus Here's my benchmark, be your own judge, but spinlocks FTW?

https://gist.github.com/kastiglione/5685814

@alloy huh, I had no idea about NSPointerArray. I must have seen it somewhere, but I know I've never used it or read its docs.

@kastiglione Damn, that does look like a clear winner. Thanks!

PS does mentioning people on gists really never send a notification?

I’m wrapping up my work stuff, then I will read some docs and add a version that does no serialisation/locking, because what can go wrong when you already have the memory allocated and you just fill memory at predetermined locations that don’t overlap.

Glad I could show you the wrong way to do it!

Are there no libraries that do map and others via GCD? I've seen plenty that add -map: but none that do a -pmap:

So yeah, unexpectedly faster :) https://gist.github.com/alloy/5686542

I couldn’t find a lib that provides pmap:, just some snippets here and there. Should we create one that provides just a couple of these?

Yeah I think so, save others from reinventing, and maybe it would invite improvements.

What are you thinking? -map:, -each:, -valueForKey:{,Path:}?

I was mainly thinking map and filter. each can already be done with -[NSArray enumerateObjectsWithOptions:usingBlock:] and NSEnumerationConcurrent, plus it doesn’t have to be sync like map and filter need to be.

And then define those on NSArray, NSDictionary, and possibly NSSet.

What would -valueForKey:{,Path:} do?

...it doesn’t have to be sync and in order...

Ah right, I forgot about NSEnumerationConcurrent.

-valueForKey:{,Path:} on an array is essentially a map, so I thought why not have a concurrent equivalent, for convenience. Ignore the names, but the following two would be equivalent:

[array concurrentValueForKey:@"foo"];

[array concurrentMap:^(id item) {
    return [item valueForKey:@"foo"];
}];

What are you thinking for the implementation of filter? Use dispatch_apply to build a sparse array and then do a linear pass over the array to build a compact copy for supplying to NSArray? Or something else?

@alloy It's interesting that on your machine, the semaphore locking was slower than using the serial queue. So hardware alone can impact which one is more performant.

-valueForKey:{,Path:} on an array is essentially a map, so I thought why not have a concurrent equivalent, for convenience.

I’m not sure it’s really needed vs just using the block version directly. The other problem is that you can use all sorts of funky syntax in normal KVC collection key paths and I don’t know if that would be easy to support.

What are you thinking for the implementation of filter? Use dispatch_apply to build a sparse array and then do a linear pass over the array to build a compact copy for supplying to NSArray? Or something else?

Yeah, something like that.

PS I’m gone this weekend, so don’t wait for me if you want to hack on this :)

It's interesting that on your machine, the semaphore locking was slower than using the serial queue. So hardware alone can impact which one is more performant.

I hadn’t even noticed that. I’ve run it few more times and it’s pretty consistent.

I’m not sure it’s really needed vs just using the block version directly. The other problem is that you can use all sorts of funky syntax in normal KVC collection key paths and I don’t know if that would be easy to support.

Good points. I think the universe is telling me something, this isn't the first "convenience" method I've suggested in the past couple weeks that had its issues.

PS I’m gone this weekend, so don’t wait for me if you want to hack on this :)

Have a good weekend then. I may spend some time on this diversion, we'll see how the weekend plays out.