Как Grand Central Dispatch так быстро?(Для этого алгоритма быстрой сортировки) - PullRequest
Новая
       1

Как Grand Central Dispatch так быстро?(Для этого алгоритма быстрой сортировки)

5 голосов
/ 27 ноября 2011

Чтобы попытаться развлечься с многопоточностью / сортировкой, я решил собрать тест Quicksort (написанный на Objective-C), который использует Grand Central Dispatch, чтобы определить, насколько быстрее использовать многоядерные машины.

main.m

QuickSort.m

Это выводсгенерировано: 

2011-11-27 13:10:55.595 Quicksort[1583:707] Took 4.731876 seconds to sort 1000000 elements with NO GCD
2011-11-27 13:10:55.670 Quicksort[1583:707] Took 0.070753 seconds to sort 1000000 elements WITH GCD

Это довольно простой алгоритм, использующий Простую версию , упомянутую на странице Википедии:

Быстрая сортировка в Википедии

Я использую это на машине с i7, поэтому можно ожидать, что увеличение производительности составит порядка 8х или около того.Вместо этого алгоритм работает на приблизительно в 60-70 раз быстрее при использовании Grand Central Dispatch.

Разница вызвана ошибкой кодирования с моей стороны, или есть техническое преимущество использования GCD, котороеЯ просто не в курсе?

Ответы [ 2 ]

2 голосов
/ 27 ноября 2011

У вас есть ошибка где-то в вашем коде, я изменил строки 

    NSLog(@"Took %f seconds to sort %lu elements WITH GCD", duration, NUM_ELEMENTS);

до 

    NSLog(@"Took %f seconds to sort %lu elements WITH GCD", duration, [sorted count]);

теперь вывод 

2011-11-27 18:40:28.020 qs[37855:707] Took 5.412689 seconds to sort 1000000 elements with NO GCD
2011-11-27 18:40:28.104 qs[37855:707] Took 0.082455 seconds to sort 1 elements WITH GCD

Все еще выясняю, почему, однако ...

1 голос
/ 26 января 2012

отличный алгоритм. в основном разделить работу на более мелкие куски (потоки) и объединить результат в конце.

как таковые семафоры не ждут. изменение его на dispatch_semaphore_create (0) действительно помогает с ожиданием, однако в моем SL-компьютере GCD, похоже, возвращается к глубокому, то есть: я могу получить более 500 рабочих потоков. в этот момент код просто зависает.

с меньшим подмножеством данных, он прекрасно работает.

...

еще одна вещь. похоже, есть еще одна проблема с памятью, по крайней мере, на моем модифицированном примере решение, добавьте сохранение в dispatch_async () и затем соответствующий выпуск после dispatch_semaphore_wait () 

    // Create semaphore and sort the left side
    __block NSArray*  lessSorted = nil;
    dispatch_semaphore_t  lessSem = dispatch_semaphore_create(0);

    dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0), ^{
        lessSorted = [QuickSort sort:less useGCD:useGCD];

        [lessSorted retain];
        dispatch_semaphore_signal(lessSem);
    });

    // Create semaphore and sort the right side
    __block NSArray*  moreSorted = nil;
    dispatch_semaphore_t  moreSem = dispatch_semaphore_create(0);

    dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0), ^{
        moreSorted = [QuickSort sort:more useGCD:useGCD];

        [moreSorted retain];
        dispatch_semaphore_signal(moreSem);
    });

    // Wait for both sides to finish sorting
    dispatch_semaphore_wait(lessSem, DISPATCH_TIME_FOREVER);
    dispatch_semaphore_wait(moreSem, DISPATCH_TIME_FOREVER);

    // Merge
    [concat addObjectsFromArray:lessSorted];
    [concat addObject:pivotObj];
    [concat addObjectsFromArray:moreSorted];

    dispatch_release(lessSem);            
    dispatch_release(moreSem);
    [lessSorted release];
    [less release];
    [moreSorted release];
    [more release];
...