Concurrent map benchmark

gcd_map.mm

#import <Foundation/Foundation.h>
#import <libkern/OSAtomic.h>

@interface NSArray (ConcurrentMap)
- (NSArray*)semaphore_map:(id (^)(id))block;
- (NSArray*)serial_map:(id (^)(id))block;
- (NSArray*)spinlock_map:(id (^)(id))block;
@end

@implementation NSArray (ConcurrentMap)

- (NSArray*)semaphore_map:(id (^)(id))block {
    __strong id* collected = (__strong id*)calloc(self.count, sizeof(id));
    dispatch_semaphore_t semaphore = dispatch_semaphore_create(1);
    dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0);

    dispatch_apply(self.count, queue, ^(size_t i) {
        id result = block(self[i]);
        dispatch_semaphore_wait(semaphore, DISPATCH_TIME_FOREVER);
        collected[i] = result;
        dispatch_semaphore_signal(semaphore);
    });
    
    NSArray* result = [NSArray arrayWithObjects:collected count:self.count];
    free(collected);
    return result;
}

- (NSArray*)serial_map:(id (^)(id))block {
    __strong id* collected = (__strong id*)calloc(self.count, sizeof(id));
    dispatch_group_t group = dispatch_group_create();
    dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0);
    dispatch_queue_t serial = dispatch_queue_create("com.internet", DISPATCH_QUEUE_SERIAL);

    dispatch_apply(self.count, queue, ^(size_t i) {
        id result = block(self[i]);
        dispatch_group_async(group, serial, ^{
            collected[i] = result;
        });
    });
    dispatch_group_wait(group, DISPATCH_TIME_FOREVER);

    NSArray* result = [NSArray arrayWithObjects:collected count:self.count];
    free(collected);
    return result;
}

- (NSArray*)spinlock_map:(id (^)(id))block {
    __strong id* collected = (__strong id*)calloc(self.count, sizeof(id));
    __block volatile OSSpinLock spinLock = OS_SPINLOCK_INIT;
    dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0);

    dispatch_apply(self.count, queue, ^(size_t i) {
        id result = block(self[i]);
        OSSpinLockLock(&spinLock);
        collected[i] = result;
        OSSpinLockUnlock(&spinLock);
    });

    NSArray* result = [NSArray arrayWithObjects:collected count:self.count];
    free(collected);
    return result;
}

@end

int main(int argc, const char* argv[]) {
    @autoreleasepool {
        NSUInteger const ARRAY_SIZE = 1000;
        NSUInteger const LOOP_COUNT = 20000;

        NSMutableArray* numbers = [NSMutableArray arrayWithCapacity:ARRAY_SIZE];
        for (NSUInteger i = 0; i < ARRAY_SIZE; i++) {
            [numbers addObject:@(i)];
        }

        NSDate* start;

        @autoreleasepool {
            start = [NSDate date];
            for (NSUInteger i = 0; i < LOOP_COUNT; i++) {
                [numbers serial_map:^(id value) {
                    return value;
                }];
            }
            NSLog(@"serial_map: %.2fs", -[start timeIntervalSinceNow]);
        }

        @autoreleasepool {
            start = [NSDate date];
            for (NSUInteger i = 0; i < LOOP_COUNT; i++) {
                [numbers semaphore_map:^(id value) {
                    return value;
                }];
            }
            NSLog(@"semaphore_map: %.2fs", -[start timeIntervalSinceNow]);
        }

        @autoreleasepool {
            start = [NSDate date];
            for (NSUInteger i = 0; i < LOOP_COUNT; i++) {
                [numbers spinlock_map:^(id value) {
                    return value;
                }];
            }
            NSLog(@"spinlock_map: %.2fs", -[start timeIntervalSinceNow]);
        }
    }

    return 0;
}

log.txt

2013-05-31 09:34:13.886 ConcurrentMap[84792:303] serial_map: 6.34s
2013-05-31 09:34:18.625 ConcurrentMap[84792:303] semaphore_map: 4.55s
2013-05-31 09:34:21.562 ConcurrentMap[84792:303] spinlock_map: 2.78s

Hello visitor, it has been pointed out that none of the locking is needed for parallel mapping into a c-array. Originally, the code used NSMutableArray, which is not thread safe and requires synchronization of concurrent changes. This may still serve as a good starting point to benchmark the performance of these synchronization approaches.