Stackoverflow with Quicksort Java implementation using ForkJoin

Question

I've been trying to do a quick sort using ForkJoin in Java and while in works for the most part, I get a stackoverflow when each element of the array is equal.

import java.util.Comparator;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class QuickSortMultiThreading extends RecursiveAction {
    private final int threshold = 50000;
    private static Apartment[] arr;
    private int start, end;
    private static final Comparator<Apartment> comparator = new Apartment.ApartmentComparator();

    public QuickSortMultiThreading(Apartment[] arr, int start, int end) {
        this.arr = arr;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {
        if(arr.length == 0){
            return;
        }
        if (end - start <= threshold) {
            quickSort(start, end);
        } else {
            if(start < end)
            {
                int p = partition(start, end);
                QuickSortMultiThreading left = new QuickSortMultiThreading(arr, start, p - 1);
                QuickSortMultiThreading right = new QuickSortMultiThreading(arr, p + 1, end);
                left.fork();
                right.compute();
                left.join();
            }
        }
    }

    static int partition(int low, int high)
    {
        Apartment pivot = arr[high];
        int i = (low - 1);

        for (int j = low; j <= high - 1; j++) {
            if (comparator.compare(arr[j], pivot) < 0) {
                i++;
                swap(i, j);
            }
        }
        swap(i + 1, high);
        return (i + 1);
    }

    private static void swap(int i, int j) {
        Apartment temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private void quickSort(int low, int high) {
        while (low < high) {
            int pi = partition(low, high);

            if (pi - low < high - pi) {
                quickSort(low, pi - 1);
                low = pi + 1;
            } else {
                quickSort(pi + 1, high);
                high = pi - 1;
            }
        }
    }

    public static void main(String[] args) {
        int size = 100000;

        Apartment[] arr = new Apartment[size];

        for (int j = 0; j < size; j++) {
            int var1 = 1;
            int var2 = 2;
            int var3 = 3;
            arr[j] = new Apartment(var1, var2, var3);
        }

        ForkJoinPool pool  = new ForkJoinPool(12);

        pool.invoke(new QuickSortMultiThreading(arr, 0, size - 1));
    }
}

I also have a sequential implementation that doesn't share the same problem

import java.io.*;
import java.util.Comparator;
import java.util.Random;

class SequentialQuicksort {

    static void swap(Apartment[] arr, int i, int j)
    {
        Apartment temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static int partition(Apartment[] arr, int low, int high, Comparator<Apartment> comparator) {
        Apartment pivot = arr[high];
        int i = (low - 1);

        for (int j = low; j <= high - 1; j++) {
            if (comparator.compare(arr[j], pivot) < 0) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return (i + 1);
    }

    static void quickSort(Apartment[] arr, int low, int high, Comparator<Apartment> comparator)
    {
        while (low < high) {
            int pi = partition(arr, low, high, comparator);

            if (pi - low < high - pi) {
                quickSort(arr, low, pi - 1, comparator);
                low = pi + 1;
            } else {
                quickSort(arr, pi + 1, high, comparator);
                high = pi - 1;
            }
        }
    }

    public static void main(String[] args)
    {
        int size = 100000;

        Apartment[] arr = new Apartment[size];

        for (int j = 0; j < size; j++) {
            int var1 = 1;
            int var2 = 2;
            int var3 = 3;
            arr[j] = new Apartment(var1, var2, var3);
        }

        quickSort(arr, 0, arr.length - 1, new Apartment.ApartmentComparator());
    }
}

From what I understand the problem may come from endless recursion, but I'm not sure how to avoid in in parallel implementation

rcgldr · Accepted Answer · 2024-04-18 02:13:58Z

The code is using Lomuto parition scheme, and with all equal elements, the split is 1 element and n-2 elements, which will result in stack overflow. The code needs to do something similar to quicksort(), recursing on smaller partition, looping on larger partition to avoid stack overflow, limiting stack usage to O(log(n)). Worst case time complexity will remain O(n^2). I don't know how to create an array of QuickSortMultiThreading.

Switching to Hoare partition scheme will change all equal elements to best case instead of worst case, but that doesn't address the stack overflow issue for other worst case data patterns.

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme'

It would help performance to switch to insertion sort if (end-start) <= 32.

            QuickSortMultiThreading smaller[8];  // not sure how to create an array 
            // ...
            int i = -1;
            while(start < end){
                int p = partition(start, end);
                if(i < 8){               // max 8 threads
                    if(p - start < end - p){
                        QuickSortMultiThreading smaller[++i] = new 
    QuickSortMultiThreading(arr, start, p - 1);
                        smaller[i].fork();
                        start = p+1;
                    } else {
                        QuickSortMultiThreading smaller[++i] = new 
    QuickSortMultiThreading(arr, p+1, end);
                        smaller[i].fork();
                        end = p-1;
                    }
                } else {
                    if (p - start < end - p) {
                        quickSort(arr, start, p - 1, comparator);
                        start = p + 1;
                    } else {
                        quickSort(arr, p + 1, end, comparator);
                        end = p - 1;
                }
            }
            while(i >= 0)
                smaller[i--].join();

Quicksort doesn't lend itself well to multi-threading because the partition splits are not even except for pseudo random data, or if using Hoare Partition scheme already sorted, reverse-sorted, or all equal data. An alternative for K threads would be to split the array into K parts, sort the K parts, then merge the K parts, but if merging the K parts, might as well as use a multi-threaded merge sort.

Collectives™ on Stack Overflow

Stackoverflow with Quicksort Java implementation using ForkJoin

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related