Stack overflow when sorting IntArrayList

[javafanboy]

I was trying to sort a 10 million element IntArrayList with a custom IntComparator - can it be that the sort method sortThis may be recursively implemented or something as I get a stack overflow?!

I ended up using this implementation that was able to sort even a 50 million length array without stack overflow:

import org.eclipse.collections.api.block.comparator.primitive.IntComparator;
import org.eclipse.collections.api.list.primitive.MutableIntList;

public class IterativeTimSort {
    private static final int MIN_RUN = 32;

    public static void customSort(MutableIntList array, IntComparator comparator) {
        int n = array.size();
        for (int i = 0; i < n; i += MIN_RUN) {
            insertionSort(array, i, Math.min(i + MIN_RUN - 1, n - 1), comparator);
        }

        for (int size = MIN_RUN; size < n; size = 2 * size) {
            for (int left = 0; left < n; left += 2 * size) {
                int mid = Math.min(left + size - 1, n - 1);
                int right = Math.min(left + 2 * size - 1, n - 1);
                if (mid < right) {
                    merge(array, left, mid, right, comparator);
                }
            }
        }
    }
    
    private static void insertionSort(MutableIntList array, int left, int right, IntComparator comparator) {
        for (int i = left + 1; i <= right; i++) {
            int j = i;
            while (j > left && comparator.compare(array.get(j - 1), array.get(j)) > 0) {
                array.swap(j, j - 1);
                j--;
            }
        }
    }

    private static void merge(MutableIntList array, int left, int mid, int right, IntComparator comparator) {
        int len1 = mid - left + 1;
        int len2 = right - mid;
        int[] leftArray = new int[len1];
        int[] rightArray = new int[len2];
        for (int i = 0; i < len1; i++) {
            leftArray[i] = array.get(left + i);
        }
        for (int i = 0; i < len2; i++) {
            rightArray[i] = array.get(mid + 1 + i);
        }
        int i = 0, j = 0, k = left;
        while (i < len1 && j < len2) {
            if (comparator.compare(leftArray[i], rightArray[j]) <= 0) {
                array.set(k++, leftArray[i++]);
            } else {
                array.set(k++, rightArray[j++]);
            }
        }
        while (i < len1) {
            array.set(k++, leftArray[i++]);
        }
        while (j < len2) {
            array.set(k++, rightArray[j++]);
        }
    }
}

[motlin]

Could you share the stack trace you saw?

[donraab]

I was able to cause the stack overflow issue with 100K element IntList that is in order.

@Test
public void bigIntArrayList()
{
    MutableIntList list = IntInterval.oneTo(100_000).toList();
    // list.shuffleThis();
    list.sortThis(new IntComparator() {
        @Override
        public int compare(int value1, int value2)
        {
            return value2 - value1;
        }
    });
    System.out.println(list.get(0)); 
    System.out.println(list.get(10));
}

Shuffling the list or reversing the value2 and value1 in the Comparator will cause the code to run fine.

Stack trace:

java.lang.StackOverflowError
	at org.eclipse.collections.impl.utility.primitive.IntQuickSort.sort(IntQuickSort.java:116)
	at org.eclipse.collections.impl.utility.primitive.IntQuickSort.sort(IntQuickSort.java:116)
	at org.eclipse.collections.impl.utility.primitive.IntQuickSort.sort(IntQuickSort.java:116)
	at org.eclipse.collections.impl.utility.primitive.IntQuickSort.sort(IntQuickSort.java:116)
	at org.eclipse.collections.impl.utility.primitive.IntQuickSort.sort(IntQuickSort.java:116)
	at org.eclipse.collections.impl.utility.primitive.IntQuickSort.sort(IntQuickSort.java:116)
	at org.eclipse.collections.impl.utility.primitive.IntQuickSort.sort(IntQuickSort.java:116)
	at org.eclipse.collections.impl.utility.primitive.IntQuickSort.sort(IntQuickSort.java:116)
	at org.eclipse.collections.impl.utility.primitive.IntQuickSort.sort(IntQuickSort.java:116)
	at org.eclipse.collections.impl.utility.primitive.IntQuickSort.sort(IntQuickSort.java:116)
	at org.eclipse.collections.impl.utility.primitive.IntQuickSort.sort(IntQuickSort.java:116)
	at org.eclipse.collections.impl.utility.primitive.IntQuickSort.sort(IntQuickSort.java:116)
	at org.eclipse.collections.impl.utility.primitive.IntQuickSort.sort(IntQuickSort.java:116)

[vmzakharov]

sortThis(...) and sortThisBy(...) methods ultimately delegate to IntQuickSort.sort(...) for IntLists (and so on for all primitives). IntQuickSort is basically a classic quicksort with some tweaks so it is recursive. It may be a good idea to move to TimSort as the safer (and stable!) sort algorithm.

[javafanboy]

Since I wrote this I have changed my application and the tests a bit and when switching back to the built in sort I no longer get stack overflow so cant provide a stacks trace but sorting instead takes a *very long time* to complete. In my use case the int list is an "index" into a binary buffer (that is retreived by the custom comparator) making each comparison somewhat slow and my data do indeed contain long already sorted sequences so I assume the problem is basically that quick sort (that is great in many cases) do not work well in this case and indeed even can result in stack overflow (as your one responder confirmed was possible with a quite small sorted list). To address my issue and get best possible performance I for now subclassed IntList only overriding the sort method calling TimSort instead of quick sort - this way I could perform sorting directly on the int array just like the built in quicksort (instead of using the get&set methods as I first did to test out TimSort without subclassing) and this worked really well for my use case as this algorithm benefits from partly sorted input. Now performance is as good as I expected and needed. I realize it may be difficult to switch sorting algorithm in a library as it probably will result in WORSE performance for somebody but perhaps it would be possible to find a nice way to optionally provide the sorting algorithm yourself or perhaps be able to select from a few different without subclassing as I did now?! The TimSort I ended up using looks like this - it is authored by ChatGPT but I have modified it slightly and also tested it with quite a number of different cases including the test that was created a good number of years ago when a flaw in TimSort was discovered by theoretical algorithm proving) but there may of course still exist bugs.... I played a bit with calculating the theoretically best MIN_RUN but this gave almost no improvement for any of my test cases compared to a fixed value of 32 but this is a possible improvement if doing an implementation for the library as it at least in theory should give an even better result. import org.eclipse.collections.api.block.comparator.primitive.IntComparator; public class IterativeTimSort { private static final int MIN_RUN = 32; public static void sort(int[] array, int length, IntComparator comparator) { if (length < 0 || length > array.length) { throw new IllegalArgumentException("Illegal length!"); } for (int i = 0; i < length; i += MIN_RUN) { insertionSort(array, i, Math.min(i + MIN_RUN - 1, length - 1), comparator); } for (int size = MIN_RUN; size < length; size = 2 * size) { for (int left = 0; left < length; left += 2 * size) { int mid = Math.min(left + size - 1, length - 1); int right = Math.min(left + 2 * size - 1, length - 1); if (mid < right) { merge(array, left, mid, right, comparator); } } } } private static void insertionSort(int[] array, int left, int right, IntComparator comparator) { for (int i = left + 1; i <= right; i++) { int temp = array[i]; int j = i - 1; while (j >= left && comparator.compare(array[j], temp) > 0) { array[j + 1] = array[j]; j--; } array[j + 1] = temp; } } private static void merge(int[] array, int left, int mid, int right, IntComparator comparator) { int len1 = mid - left + 1; int len2 = right - mid; int[] leftArray = new int[len1]; int[] rightArray = new int[len2]; System.arraycopy(array, left, leftArray, 0, len1); System.arraycopy(array, mid + 1, rightArray, 0, len2); int i = 0, j = 0, k = left; while (i < len1 && j < len2) { if (comparator.compare(leftArray[i], rightArray[j]) <= 0) { array[k++] = leftArray[i++]; } else { array[k++] = rightArray[j++]; } } while (i < len1) { array[k++] = leftArray[i++]; } while (j < len2) { array[k++] = rightArray[j++]; } } }

[vmzakharov]

@javafanboy - thank you for the detailed write up (and for opening the issue).

A couple of thoughts:

1. We can make the sorting algorithm pluggable. I see three options for the scope: globally, per collection type (easiest to implement I think), per sort call. What do folks think - any of that makes sense?
2. Separately, replacing the current sort implementation with TimSort seems like a good idea - see the reasons in my perv comment. And if we do the pluggable approach, it can just be the default option. I don't think we should be taking ChatGPT authored code, but a clean room TimSort implementation shouldn't be a problem.

[javafanboy]

I would personally think it would make most sense to specify the sorting method per *collection* *instance* - I would assume a developer knows what type of data that will be stored in each instance of a list or Map etc. and therefore what kind of sort algorithm that would be most suitable. If none is specified the default could be quicksort as today for backward compatibility or TimSort for stability property and optimization for partly sorted data etc. One could also allow overriding the sort method for each sort call but I would say that rarely should be needed but there are cases - the first time a structure is sorted quicksort could be a good choice while additional sorts (after just a few more entries have been edited) TimSort could be prefered etc. It should be easy to find "clean room" TimSort implementations, even one that includes dynamic selection of the hybrid sorting limit. Just pick one that is modern and not suffering from that old bug that was discovered quite many years ago now. I could not see much difference with my data of using arraycopy but, as this method is native implemented, is should be faster I suppose... I really love collections with pluggable comparator and hashing/equals etc. - it provides so much flexibility also for special use-cases!

…

On Thu, Aug 29, 2024 at 7:13 PM Vladimir Zakharov ***@***.***> wrote: @javafanboy <https://github.com/javafanboy> - thank you for the detailed write up (and for opening the issue). A couple of thoughts: 1. We can make the sorting algorithm pluggable. I see three options for the scope: globally, per collection type (easiest to implement I think), per sort call. What do folks think - any of that makes sense? 2. Separately, replacing the current sort implementation with TimSort seems like a good idea - see the reasons in my perv comment. And if we do the pluggable approach, it can just be the default option. I don't think we should be taking ChatGPT authored code, but a clean room TimSort implementation shouldn't be a problem. — Reply to this email directly, view it on GitHub <#1685 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AADXQFYIABREAJ4473IRTWTZT5JB7AVCNFSM6AAAAABNI35O62VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDGMJYGQYTCMJUG4> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[motlin]

Just use Arrays.sort()

[vmzakharov]

[Primitive]ArrayList.sortThis() does use Arrays.sort() for ascending sorting by list value order. You need something else if your requirement is to sort based on a comparator so [Primitive]ArrayList.sortThis(<comparator>) variants use a bespoke sort implementation.

[donraab]

Just use Arrays.sort()

Arrays.sort() does not accept a Comparator equivalent for primitive types.

[Riya-Sharma12]

If the code is taking too much much time to execute, then there can be two possible solutions -

1.Tune the MIN_RUN size : you might find that increasing or decreasing MIN_RUN can yield better performance. Larger values reduce the number of runs, leading to fewer merges but more work during the initial sorting phase.
2.Optimize the merging process.

Here's the optimized merging method

private static void merge(int[] array, int left, int mid, int right, IntComparator comparator) {

   if (comparator.compare(array[mid], array[mid + 1]) <= 0) {
    // The arrays are already sorted, no need to merge
    return;
    }
    int len1 = mid - left + 1;
    int len2 = right - mid;
    int[] leftArray = new int[len1];
    int[] rightArray = new int[len2];

    System.arraycopy(array, left, leftArray, 0, len1);
    System.arraycopy(array, mid + 1, rightArray, 0, len2);

    int i = 0, j = 0, k = left;
    while (i < len1 && j < len2) {
        if (comparator.compare(leftArray[i], rightArray[j]) <= 0) {
            array[k++] = leftArray[i++];
        } else {
            array[k++] = rightArray[j++];
        }
    }

    while (i < len1) {
        array[k++] = leftArray[i++];
    }
    while (j < len2) {
        array[k++] = rightArray[j++];
    }
}

[javafanboy]

If the code is taking too much much time to execute, then there can be two possible solutions...

Thanks for your reply and sorry if I was unclear - with TimSort the performance is really good for all the cases I have tried with even with the algorithm I posted above (with fixed MIN_RUN etc.). It was the built in (quicksort based) method that executed really slowly on my already partly sorted data.

I have not seen your proposed optimization in any TimSort implementation but it seems intuitively correct and my test cases still passed with it - the performance improvement was just a precent or two (i.e. quite rare that the sub-arrays are already FULLY sorted and this must be out weighted by an additional comparison) for my data but every improvement counts!

[javafanboy]

It also seems like one can replace the two last loops in the merge method with System.arraycopy - my tests still run and it actually shaved of a quite significant ~5% or so with my large arrays.
The code now looks like this:

import org.eclipse.collections.api.block.comparator.primitive.IntComparator;

public class IterativeTimSort {
    private static final int MIN_RUN = 32;

    public static void sort(int[] array, int length, IntComparator comparator) {
        if (length < 0 || length > array.length) {
            throw new IllegalArgumentException("Illegal length!");
        }
        for (int i = 0; i < length; i += MIN_RUN) {
            insertionSort(array, i, Math.min(i + MIN_RUN - 1, length - 1), comparator);
        }

        for (int size = MIN_RUN; size < length; size = 2 * size) {
            for (int left = 0; left < length; left += 2 * size) {
                final int mid = Math.min(left + size - 1, length - 1);
                final int right = Math.min(left + 2 * size - 1, length - 1);
                if (mid < right) {
                    merge(array, left, mid, right, comparator);
                }
            }
        }
    }

    private static void insertionSort(int[] array, int left, int right, IntComparator comparator) {
        for (int i = left + 1; i <= right; i++) {
            final int temp = array[i];
            int j = i - 1;
            while (j >= left && comparator.compare(array[j], temp) > 0) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = temp;
        }
    }

    private static void merge(int[] array, int left, int mid, int right, IntComparator comparator) {
        // If the sorted array halves are in the right order and non-overlapping, there is no need to merge
        if (comparator.compare(array[mid], array[mid + 1]) <= 0) return;
        final int len1 = mid - left + 1;
        final int len2 = right - mid;
        final int[] leftArray = new int[len1];
        final int[] rightArray = new int[len2];
        System.arraycopy(array, left, leftArray, 0, len1);
        System.arraycopy(array, mid + 1, rightArray, 0, len2);
        int i = 0, j = 0, k = left;
        while (i < len1 && j < len2) {
            if (comparator.compare(leftArray[i], rightArray[j]) <= 0) {
                array[k++] = leftArray[i++];
            } else {
                array[k++] = rightArray[j++];
            }
        }
        if (i < len1) System.arraycopy(leftArray, i, array, k, len1 - i);
        if (j < len2) System.arraycopy(rightArray, j, array, k, len2 - j);
    }
}

For data that is not partly sorted (i.e. created some random int arrays) Arrays.sort is about 30% faster than the above TimSort so it is probably a better DEFAULT choice than TimSort. This also avoids altering sorting performance for existing code using the Eclipse collections today. The JDK did after all replace TimSort with the current QuickSort derivate already back in version 6 or something and that was probably for a good reason...

[Riya-Sharma12]

for further performance improvement , can't we use -
private static final int MIN_RUN = 64; ??

[javafanboy]

for further performance improvement , can't we use - private static final int MIN_RUN = 64; ??

With my test (sorting 10 million mostly sorted records) going to 64 actually reduces performance with a few percent.

[mohrezaei]

I had a closer look at this.

TLDR

• There is a genuine bug in our quick sort implementation. It tries to find a better pivot so Don's sorted case doesn't take long, but something is wrong with that code.
• The state of the art general sorting algorithm is probably Java's dual pivot quicksort (dpq). There are various algo's claiming "fastest", but curiously, they don't run benchmarks with dpq.
• There are only two algorithms in the ones I found that are short enough to easily convert to Java and have the right licenses:
  • Latest version of timsort: https://github.com/timsort/cpp-TimSort
  • More of a long shot, piposort: https://github.com/scandum/piposort

Long Version

Top contenders other than dpq:

• pdq (pattern defeating quicksort): https://github.com/orlp/pdqsort used in Go, but apparently slower than dpq slices: use dual-pivot quicksort instead of pdqsort golang/go#61027 (read the issue for the drama about how Go devs don't want to replace it)
• blip: https://github.com/RedBedHed/blipsort no comparison with dpq. Might be portable to Java, but has some code that's very suspect/unportable (use of comparator returned value).
• flux: https://github.com/scandum/fluxsort no comparison with dqp. Would be hard to port to Java, just because of sheer length. Large code is not JIT friendly.
• quad: https://github.com/scandum/quadsort flux depends on this, so this might be more doable, but still very large

Various benchmarks:
https://www.reddit.com/r/cpp/comments/fgxfqa/c_benchmark_timsort_vs_pdqsort_vs_quadsort_vs/
https://github.com/scandum/fluxsort
https://github.com/scandum/quadsort

[vmzakharov]

@mohrezaei - thank you for looking into this. A couple of questions:

1. Any idea why JDK Arrays.sort(..,[comparator]) methods for Objects use TimSort, while Arrays.sort(...) for primitive types use DPQ?
2. Any reason not to try to just go with TimSort as a replacement for the existing sort() primitive with comparator implementation - should be an improvement (performance, stability, fixes this issue)?

[mohrezaei]

The solution here should probably start with a bunch of test cases (random, sorted, reverse sorted, saw ascending, saw descending).
From there, quickest (pun!) might be to fix our quicksort. With a bit more effort, TimSort is probably the next best option.

As a project for someone learning the ropes, doing a comparison with various sort algorithms could be good.

I don't know why TimSort is preferred to DPQ for objects. (Sometimes that's because some internals depend on magnitude, like radix sort, but I don't think that's the case with DPQ)

[mohrezaei]

I don't know why TimSort is preferred to DPQ for objects.

Actually, I think it's because DPQ is not stable. Stability is useless for primitives on the default comparator. It only matters under the following conditions for primitives:

• Using a custom comparator for primitives
• The comparator must claim two different primitive values are equal.

The conditions are a bit unusual, and it's unclear how important stability would be under those conditions. An example for such a comparator (and a good test case): All evens are equals; all odd are equal; evens are less than odds. Implemented as a one-liner: Integer.compare(a & 1, b & 1)