8
\$\begingroup\$

I am playing with async and I figured I'd write a parallel implementation of Quicksort while trying to look at various optimizations. I want to keep the generics (and the overhead of the virtual calls going on here). Other than that I am looking for optimizations that can be made.

class Program
{
    static int[] initial; //generating random array only once and using copies of it later
    private static void Main(string[] args)
    {
        initial = Enumerable.Range(0, 100000000).ToArray();
        Shuffle();
        TestLength<Quicksort<int>>(5);
        TestLength<Quicksort<int>>(10);
        TestLength<Quicksort<int>>(100);
        TestLength<Quicksort<int>>(1000);
        TestLength<Quicksort<int>>(10000);
        TestLength<Quicksort<int>>(100000);
        TestLength<Quicksort<int>>(1000000);
        TestLength<Quicksort<int>>(10000000);

        //oom when trying this one for me
        //TestLength<Quicksort<int>>(100000000);
        Console.ReadKey();
    }

    private static void Shuffle()
    {
        //simple Fisher-Yates shuffle
        var random = new Random();
        for (int i = initial.Length - 1; i > 0; i--)
        {
            int j = random.Next(i);
            int value = initial[i];
            initial[i] = initial[j];
            initial[j] = value;
        }
    }

    private static void TestLength<T>(int length) where T:ISortAlgorithm<int>,new()
    {   
        int[] arr = new int[length];
        Array.Copy(initial, arr, length);

        int[] arr2 = new int[length];
        Array.Copy(initial, arr2, length);

        Console.WriteLine("Length: " + length);

        var timer = new Stopwatch();
        var algorithm = new T { Elements = arr };
        timer.Start();
        algorithm.SortAsync().GetAwaiter().GetResult();
        timer.Stop();

        Console.WriteLine("Elapsed async: " + timer.Elapsed);

        timer.Reset();
        algorithm = new T { Elements = arr };
        timer.Start();
        algorithm.Sort();
        timer.Stop();
        Console.WriteLine("Elapsed:       " + timer.Elapsed);
        Console.WriteLine();
    }
}

public interface ISortAlgorithm<T> where T : IComparable
{
    T[] Elements { get; set; }
    Task SortAsync();
    void Sort();
    void SortNoRecursion();

}

public class Quicksort<T> : ISortAlgorithm<T> where T : IComparable
{
    T[] elements;

    //begin interface implementation
    public T[] Elements { get { return elements; } set { elements = value; } }

    public async Task SortAsync()
    {
        await SortAsync(0, elements.Length, 0);
    }

    public void Sort()
    {
        Sort(0, elements.Length, 0);
    }

    public void SortNoRecursion()
    {
        SortNoRecursion(0, elements.Length);
    }
    //end interface implementation; everything beyond is fair game

    //for debugging: see how many threads run
    //public static int numthreads = 0;
    //public static int maxthreads = 0;
    private async Task SortAsync(int low, int high, int depth)
    {
        //numthreads++;
        //maxthreads = Math.Max(numthreads, maxthreads);

        if (high - low < 5000)
        {
            //anything under 5000 elements (ish) can be sorted many times faster serially
            Sort(low, high, depth+1);
            //numthreads--;
            return;
        }

        //yields to the caller and continues on a separate thread
        await Task.Yield();

        if (high - low < 2)
        {
            //numthreads--;
            return;
        }

        T pivot = ChoosePivot(low, high);
        var store = low;
        for (var i = low; i < high - 1; i++)
        {
            if (elements[i].CompareTo(pivot) < 0)
            {
                var temp = elements[store];
                elements[store] = elements[i];
                elements[i] = temp;
                store++;
            }
        }
        elements[high - 1] = elements[store];
        elements[store] = pivot;

        //numthreads--;
        await Task.WhenAll(SortAsync(low, store, depth + 1), SortAsync(store + 1, high, depth + 1));
    }

    private T ChoosePivot(int low, int high)
    {
        T pivot = elements[high - 1];
        T pivot2 = elements[low];
        T pivot3 = elements[(low + high) / 2];

        if (pivot.CompareTo(pivot2) < 0 && pivot.CompareTo(pivot3) < 0)
        {
            if (pivot2.CompareTo(pivot3) < 0)
            {
                elements[high - 1] = pivot2;
                elements[low] = pivot;
                pivot = pivot2;
            }
            else
            {
                elements[high - 1] = pivot;
                elements[(low + high) / 2] = pivot;
                pivot = pivot3;
            }
        }
        else if (pivot.CompareTo(pivot2) > 0 && pivot.CompareTo(pivot3) > 0)
        {
            if (pivot2.CompareTo(pivot3) < 0)
            {
                elements[high - 1] = pivot;
                elements[(low + high) / 2] = pivot;
                pivot = pivot3;
            }
            else
            {
                elements[high - 1] = pivot2;
                elements[low] = pivot;
                pivot = pivot2;
            }
        }
        return pivot;
    }

    private void Sort(int low, int high, int depth)
    {
        if (depth > 7000)
        {
            //avoids stack overflow at what appears to be a massive runtime cost
            SortNoRecursion(low, high);
            return;
        }
        if (high - low < 2) return;

        T pivot = ChoosePivot(low, high);
        var store = low;
        for (var i = low; i < high - 1; i++)
        {
            if (elements[i].CompareTo(pivot) < 0)
            {
                var temp = elements[store];
                elements[store] = elements[i];
                elements[i] = temp;
                store++;
            }
        }
        elements[high - 1] = elements[store];
        elements[store] = pivot;

        Sort(low, store, depth+1);
        Sort(store + 1, high, depth+1);
    }

    struct Frame
    {
        public int Low;
        public int High;
    }

    private void SortNoRecursion(int low, int high)
    {
        //reimplementation of serial version while handling the recursion as a stack explicitly
        Stack<Frame> stack = new Stack<Frame>();
        stack.Push(new Frame { Low = low, High = high });
        while (stack.Count > 0)
        {
            var frame = stack.Pop();
            low = frame.Low;
            high = frame.High;

            if (high - low >= 2)
            {

                T pivot = ChoosePivot(low, high);
                var store = low;
                for (var i = low; i < high - 1; i++)
                {
                    if (elements[i].CompareTo(pivot) < 0)
                    {
                        var temp = elements[store];
                        elements[store] = elements[i];
                        elements[i] = temp;
                        store++;
                    }
                }
                elements[high - 1] = elements[store];
                elements[store] = pivot;

                stack.Push(new Frame { Low = low, High = store });
                stack.Push(new Frame { Low = store + 1, High = high });
            }
        }
    }
}

Here is the output:

Length: 5
Elapsed async: 00:00:00.0062427
Elapsed:       00:00:00.0000926

Length: 10
Elapsed async: 00:00:00.0000068
Elapsed:       00:00:00.0000053

Length: 100
Elapsed async: 00:00:00.0000306
Elapsed:       00:00:00.0000206

Length: 1000
Elapsed async: 00:00:00.0003799
Elapsed:       00:00:00.0002608

Length: 10000
Elapsed async: 00:00:00.0292752
Elapsed:       00:00:00.0034726

Length: 100000
Elapsed async: 00:00:00.1027803
Elapsed:       00:00:00.0388378

Length: 1000000
Elapsed async: 00:00:00.2632137
Elapsed:       00:00:00.4372638

Length: 10000000
Elapsed async: 00:00:02.7949153
Elapsed:       00:00:05.0790855
\$\endgroup\$
  • \$\begingroup\$ I think you should at least await algorithm.SortAsync(), and Task creation will always have an overhead. \$\endgroup\$ – Mikko Viitala Feb 22 '15 at 20:31
  • \$\begingroup\$ Task creation does have an overhead, you can see it clearly at the 10,000 length (for lengths under 5000, which I got to via a bit of toying around and can almost certainly be better, SortAsync simply calls Sort). As to the await, do you mean in the test function? \$\endgroup\$ – Bill Barry Feb 23 '15 at 14:20
  • 1
    \$\begingroup\$ Note that for the second time (synchronous call) you're sorting already sorted array arr instead of arr2: algorithm = new T { Elements = arr }; \$\endgroup\$ – almaz Mar 6 '15 at 13:47
  • 1
    \$\begingroup\$ And please, do not use await Task.Yield to schedule the execution on a threadpool. You'll get a single threaded execution as soon as you use it from UI thread. If you want to schedule the execution on a threadpool - just use the Task.Run \$\endgroup\$ – almaz Mar 6 '15 at 13:53
7
+100
\$\begingroup\$

Your first mistake is to do something with async that is CPU bound. That is not what you use async code for, async code is good for IO bound work, not CPU bound work.

That you have to use Task.Yield() is indeed a indication you are using async code wrong. You should probably switch to the TPL library, and call something like Parallel.Invoke(() => SortAsync(low, store, depth + 1), () => SortAsync(store + 1, high, depth + 1));

(Edit: Parallel.Invoke is actually slightly slower above 100000+ elements, but more reliable and faster below. You should probably tweak the threshold to switch to normal sort in that case, like this).

Your numthreads variable looks more like a numTasks counter.

In your TestLength method, you do not use arr2, i think you meant to use arr2 for the second sort pass, myself i would copy the line Array.Copy(initial, arr, length); after the Console.WriteLine so you can reuse arr

\$\endgroup\$
4
\$\begingroup\$

With the answer from Dorus and a few minor optimizations, I've made these changes:

class Program 
{
    static int[] initial; //generating random array only once and using copies of it later
    private static void Main(string[] args) 
    {
        initial = Enumerable.Range(0, 100000000).ToArray();
        Shuffle();
        TestLength<Quicksort<int>>(5);
        TestLength<Quicksort<int>>(10);
        TestLength<Quicksort<int>>(100);
        TestLength<Quicksort<int>>(1000);
        TestLength<Quicksort<int>>(10000);
        TestLength<Quicksort<int>>(100000);
        TestLength<Quicksort<int>>(1000000);
        TestLength<Quicksort<int>>(10000000);

        TestLength<Quicksort<int>>(100000000);
        Console.ReadKey();
    }

    private static void Shuffle() 
    {
        //simple Fisher-Yates shuffle
        var random = new Random();
        for (int i = initial.Length - 1; i > 0; i--) 
        {
            int j = random.Next(i);
            int value = initial[i];
            initial[i] = initial[j];
            initial[j] = value;
        }
    }

    private static void TestLength<T>(int length) where T : ISortAlgorithm<int>, new() 
    {
        var arr = new int[length];

        Console.WriteLine("Length: " + length);

        Array.Copy(initial, arr, length);
        var timer = new Stopwatch();
        var algorithm = new T { Elements = arr };
        timer.Start();
        algorithm.ParallelSort();
        timer.Stop();

        Console.WriteLine("Elapsed para: " + timer.Elapsed);

        Array.Copy(initial, arr, length);
        timer.Reset();
        algorithm = new T { Elements = arr };
        timer.Start();
        algorithm.Sort();
        timer.Stop();
        Console.WriteLine("Elapsed:      " + timer.Elapsed);
        Console.WriteLine();
    }
}

public interface ISortAlgorithm<T> where T : IComparable 
{
    T[] Elements { get; set; }
    void ParallelSort();
    void Sort();
    void SortNoRecursion();
}

public class Quicksort<T> : ISortAlgorithm<T> where T : IComparable 
{
    T[] _elements;
    int _threshold;

    //begin interface implementation
    public T[] Elements 
    {
        get 
        { 
            return _elements; 
        }
        set 
        {
            _elements = value;
            _threshold = (int)Math.Sqrt(Math.Log(value.Length));
        }
    }

    public void ParallelSort() 
    {
        Sort(0, _elements.Length, 0, (int)Math.Log(Environment.ProcessorCount, 2) + 4);
        var s = new InsertionSort<T> 
        {
            Elements = _elements
        };
        s.SortNoRecursion();
    }

    public void Sort() 
    {
        Sort(0, _elements.Length, 0, 0);
        var s = new InsertionSort<T> 
        { 
            Elements = _elements 
        };
        s.SortNoRecursion();
    }

    public void SortNoRecursion() 
    {
        SortNoRecursion(0, _elements.Length);
        var s = new InsertionSort<T> 
        { 
            Elements = _elements 
        };
        s.SortNoRecursion();
    }
    //end interface implementation

    private void Sort(int low, int high, int depth, int pdepth) 
    {
        if (high - low < _threshold) 
        {
            return;
        }
        if (depth > 7000) 
        {
            //avoids stack overflow
            SortNoRecursion(low, high);
            return;
        }

        var mid = Partition(low, high);

        if (pdepth > 0) 
        {
            Parallel.Invoke(
                () => Sort(low, mid, depth + 1, pdepth - 1), 
                () => Sort(mid + 1, high, depth + 1, pdepth - 1)
                );
        }
        else 
        {
            Sort(low, mid, depth + 1, 0);
            Sort(mid + 1, high, depth + 1, 0);
        }
    }

    private struct Frame 
    {
        public int Low;
        public int High;
    }

    private void SortNoRecursion(int low, int high) 
    {
        var stack = new Stack<Frame>();
        stack.Push(new Frame { Low = low, High = high });
        while (stack.Count > 0) 
        {
            var frame = stack.Pop();
            low = frame.Low;
            high = frame.High;

            if (high - low < _threshold) 
            {
                continue;
            }

            var mid = Partition(low, high);

            stack.Push(new Frame { Low = low, High = mid });
            stack.Push(new Frame { Low = mid + 1, High = high });
        }
    }

    private int Partition(int low, int high) {
        var pivot = ChoosePivot(low, high);
        var store = low;
        for (var i = low; i < high - 1; i++) 
        {
            if (_elements[i].CompareTo(pivot) >= 0)
            {
                continue;
            }
            var temp = _elements[store];
            _elements[store] = _elements[i];
            _elements[i] = temp;
            store++;
        }
        _elements[high - 1] = _elements[store];
        _elements[store] = pivot;
        return store;
    }

    private T ChoosePivot(int low, int high) 
    {
        T pivot = _elements[high - 1];
        T pivot2 = _elements[low];
        T pivot3 = _elements[(low + high) / 2];

        if (pivot.CompareTo(pivot2) < 0 && pivot.CompareTo(pivot3) < 0) 
        {
            if (pivot2.CompareTo(pivot3) < 0) 
            {
                _elements[high - 1] = pivot2;
                _elements[low] = pivot;
                pivot = pivot2;
            }
            else 
            {
                _elements[high - 1] = pivot3;
                _elements[(low + high) / 2] = pivot;
                pivot = pivot3;
            }
        } 
        else if (pivot.CompareTo(pivot2) > 0 && pivot.CompareTo(pivot3) > 0) 
        {
            if (pivot2.CompareTo(pivot3) < 0) 
            {
                _elements[high - 1] = pivot3;
                _elements[(low + high) / 2] = pivot;
                pivot = pivot3;
            }
            else 
            {
                _elements[high - 1] = pivot2;
                _elements[low] = pivot;
                pivot = pivot2;
            }
        }
        return pivot;
    }
}

public class InsertionSort<T> : ISortAlgorithm<T> where T: IComparable 
{
    T[] _elements;
    public T[] Elements { get { return _elements; } set { _elements = value; } }
    public void ParallelSort() 
    {
        SortNoRecursion();
    }
    public void Sort() 
    {
        SortNoRecursion();
    }
    public void SortNoRecursion() 
    {
        var length = _elements.Length;
        for (var i = 1; i < length; i++) 
        {
            var x = _elements[i];
            var j = i;
            while (j > 0 && x.CompareTo(_elements[j - 1]) < 0) 
            {
                _elements[j] = _elements[j - 1];
                j--;
            }
            _elements[j] = x;
        }
    }
}

results in this output (different machine, not directly comparable):

Length: 5
Elapsed para: 00:00:00.0091935
Elapsed:      00:00:00.0001159

Length: 10
Elapsed para: 00:00:00.0059733
Elapsed:      00:00:00.0000072

Length: 100
Elapsed para: 00:00:00.0009330
Elapsed:      00:00:00.0000199

Length: 1000
Elapsed para: 00:00:00.0002725
Elapsed:      00:00:00.0002752

Length: 10000
Elapsed para: 00:00:00.0013338
Elapsed:      00:00:00.0102228

Length: 100000
Elapsed para: 00:00:00.0595273
Elapsed:      00:00:00.0335555

Length: 1000000
Elapsed para: 00:00:00.1774097
Elapsed:      00:00:00.3815720

Length: 10000000
Elapsed para: 00:00:01.8210365
Elapsed:      00:00:04.3097814

Length: 100000000
Elapsed para: 00:00:20.7862539
Elapsed:      00:00:49.1418631

The other changes:

  1. the partition loop was moved into a function to not repeat the same code 3 times
  2. the differences between the parallel and serial sorts were superficial so they were joined into one method
  3. getting rid of the second array and simply copying into the first one twice enabled memory savings that allowed me to enable the last length trial
\$\endgroup\$
  • \$\begingroup\$ Just curious, why does your Quicksort follow up with a call to InsertionSort? \$\endgroup\$ – Dorus Mar 24 '15 at 0:57
  • \$\begingroup\$ There is probably some tweaking to be done there (thinking threshold min of 3 at least?), but the idea is the same as the page you linked to; under a certain length, insertion sort to get through the remaining elements is faster than adding another call stack or two to do a couple of compares. For example if threshold was 5, you might have 3 more calls and 17ish more compares to sort that remaining list (9 due to overhead finding the pivots) but by doing insertion sort you only have a max of 15. [1/2] \$\endgroup\$ – Bill Barry Mar 25 '15 at 1:40
  • \$\begingroup\$ By doing a single pass of insertion sort after quicksort mostly sorts everything, you are calling once instead of log(N) times. This saves a few memory allocations for the trade of 2 compares of elements that are already correctly sorted. You get away with insertion sort (an algorithm that is often close to O(n^2) for unsorted data) by constraining that data to be mostly sorted already O(n*k^2) where k is threshold. By ensuring threshold is around sqrt(log(N)), the resulting algorithm remains O(n*log(n)) in an average case. [2/2] \$\endgroup\$ – Bill Barry Mar 25 '15 at 1:40
  • \$\begingroup\$ Ah right, i'm used to see the insertion sort at the deepest level of the Quicksort, but your reasoning makes sense. \$\endgroup\$ – Dorus Mar 25 '15 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.