How is Grand Central Dispatch so fast? (For this Quicksort algorithm)

Question

In an effort to brush up on some multithreading/sorting fun, I decided to put together a Quicksort test (written in Objective-C) that uses Grand Central Dispatch to determine how much faster it is to leverage multicore machines.

main.m

QuickSort.m

This is the output generated:

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

It's a fairly simple algorithm, using the Simple version mentioned on the Wikipedia page:

Quicksort on Wikipedia

I'm running this on an i7 machine, so would expect the performance increase to be on the order of 8x or so. Instead, the algorithm is approximately 60-70x faster when using Grand Central Dispatch.

Is the difference caused by a coding error on my part, or is there a technical advantage to using GCD that I'm just not aware of?

Answer 1

You have got an error somewhere in your code, I changed the lines

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

to

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

now the output is

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

Still investigating why however...