Re[2]: New portion of improvements for Dual-Pivot Quicksort

[Vladimir Iaroslavski]

Hello Josh, Dmytro,

I've modified the DQP and now it doesn't touch elements outside of
the range and doesn't set a sentinel at all. Elements from the left
part are used as a sentinel (as it was suggested by Dmytro) and index
fromIndex is used as left boundary (suggestion from Josh). The index
fromIndex is the initial left boundary and passed down through the
recursions. No any tricks with changing outside of the range and
negative infinity.

The fragment of code is (full version see in attachment):

 * ...
 * @param fromIndex the first index of the original range to be sorted
 */
private static void dualPivotQuicksort(int[] a, int left, int right, int fromIndex) {
    int length = right - left + 1;

    // Use insertion sort on tiny arrays
    if (length < INSERTION_SORT_THRESHOLD) {
        if (left > fromIndex) {
            /*
             * TODO
             */
            for (int j, i = left + 1; i <= right; i++) {
                int ai = a[i];
                for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {
                    a[j + 1] = a[j];
                }
                a[j + 1] = ai;
            }
        } else {
            /*
             * For case, when left == fromIndex, traditional (without
             * sentinel) insertion sort, optimized for server VM, is used.
             */
            for (int i = fromIndex, j = i; i < right; j = ++i) {
                int ai = a[i + 1];
                while (ai < a[j]) {
                    a[j + 1] = a[j];
                    if (j-- == fromIndex) {
                        break;
                    }
                }
                a[j + 1] = ai;
            }
        }
        return;
    }
    ...

This variant is little bit faster (~0.5%) on client VM and slower (~2%)
on server VM than original variant. I think that it is not too bad.
What do you think?

And one question: the method declaration

private static void dualPivotQuicksort(int[] a, int left, int right, int fromIndex) {

now is too long, how should I format it? What is the guideline?

Thank you,
Vladimir

Wed, 5 May 2010 18:21:18 -0400 письмо от Joshua Bloch <jjb at google.com>:

> Vladimir,
> 
> On Wed, May 5, 2010 at 12:57 AM, Joshua Bloch <jjb at google.com> wrote:
> 
> The sentinel technique that you use in lines 118 - 136 is questionable: you are modifying a portion of the array outside the specified range of the call, which arguably violates the contract of the call, and could be observed in a multithreaded program. It's not beyond the realm of reason that it could break existing clients. I will discuss it with Doug Lea and let you know what he says.
> 
> I talked to Doug, and he agrees that it's not acceptable to modify any location outside the array range that the caller has asked you to sort. This doesn't entirely kill the optimization; it's still OK to use on subranges that don't include the first element of the range that you were asked to sort. In other words, this test
> 
> 120       if (left > 0) {
> 
> Should be replaced by:
> 
> 120       if (left > fromIndex + 1) {
> 
> and you have to pass original fromIndex down to the recursive calls (in fact, you could pass fromIndex +1 to avoid the cost of the addition in each test). It's not clear whether the cost of passing this index down through the recursive calls will eliminate the gains of the optimization, but it's worth performing the experiment.
> 
> Sorry,
> Josh
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DualPivotQuicksortWithoutSentinel.java
Type: application/octet-stream
Size: 96996 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20100507/72d59244/DualPivotQuicksortWithoutSentinel.java>