ArraySortHelper.cs: Possible unnecessary bounds checks

[colgreen]

This relates to the PickPivotAndPartition() method, of which there are four implementations within ArraySortHelper.cs. The four are:

1. ArraySortHelper<T>
    private static int PickPivotAndPartition(Span<T> keys, Comparison<T> comparer);

2. GenericArraySortHelper<T>
    private static int PickPivotAndPartition(Span<T> keys)

3. ArraySortHelper<TKey, TValue>
    private static int PickPivotAndPartition(Span<TKey> keys, Span<TValue> values, IComparer<TKey> comparer)

4. GenericArraySortHelper<TKey, TValue>
    private static int PickPivotAndPartition(Span<TKey> keys, Span<TValue> values)

('Generic' here just means 'general purpose', it has nothing to do with C#/.NET generic types).

Implementation number 2 (on GenericArraySortHelper) makes extensive use of Unsafe.Add(), Unsafe.IsAddressLessThan(), and Unsafe.IsAddressGreaterThan(), presumably for performance reasons, because that method handles the simplest scenario of a single array of keys that are either native types, or IComparable. However, it does make the code somewhat harder to read, and that has perhaps caused this redundant code to be missed.

In the two implementations that take an IComparer, these inherently handle null keys as the null values are simply passed to IComparer.Compare(a,b). The other two implementations must contain a null key check, like so (/pivot/ is a key value, and may be null) (this is taken from implementation number 4, in GenericArraySortHelper<TKey, TValue>):

        while (left < right)
        {
            if (pivot == null)
            {
                while (left < (hi - 1) && keys[++left] == null) ;
                while (right > 0 && keys[--right] != null) ;
            }
            else
            {
                while (GreaterThan(ref pivot, ref keys[++left])) ;
                while (LessThan(ref pivot, ref keys[--right])) ;
            }
            [...]
        }

Notice that the first inner while loop increments left until a non-null value is found, or some bound is reached. That bound check is not necessary when the pivot is non-null (as per the lower else block).

Now let's look at the equivalent section from implementation number 2, in GenericArraySortHelper:

        while (Unsafe.IsAddressLessThan(ref leftRef, ref rightRef))
        {
            if (pivot == null)
            {
                while (Unsafe.IsAddressLessThan(ref leftRef, ref nextToLastRef) && (leftRef = ref Unsafe.Add(ref leftRef, 1)) == null) ;
                while (Unsafe.IsAddressGreaterThan(ref rightRef, ref zeroRef) && (rightRef = ref Unsafe.Add(ref rightRef, -1)) != null) ;
            }
            else
            {
                while (Unsafe.IsAddressLessThan(ref leftRef, ref nextToLastRef) && GreaterThan(ref pivot, ref leftRef = ref Unsafe.Add(ref leftRef, 1))) ;
                while (Unsafe.IsAddressGreaterThan(ref rightRef, ref zeroRef) && LessThan(ref pivot, ref rightRef = ref Unsafe.Add(ref rightRef, -1))) ;
            }
            [...]
        }

Note that the lower else block contains the unnecessary bounds tests.

I believe these are redundant. Or, if they are not, then they are missing from implementation 4, in GenericArraySortHelper<TKey, TValue>!

-- Update: I wonder if this is intentional, to make absolutely sure the loop doesn't progress beyond the ends of the keys span, given that this is not using the safe span 'indexer' syntax. But that just makes me wonder why the Unsafe. methods are used here, i.e, doesn't the JIT compiler produce equivalent code now for spans anyway? So maybe we just revert to using indexers instead of Unsafe. methods, and then remove the redundant bounds checks(?)

[ghost]

Tagging subscribers to this area: @eiriktsarpalis See info in area-owners.md if you want to be subscribed.

Issue Details

---

This relates to the PickPivotAndPartition() method, of which there are four implementations within ArraySortHelper.cs. The four are: 1. ArraySortHelper private static int PickPivotAndPartition(Span keys, Comparison comparer); 2. GenericArraySortHelper private static int PickPivotAndPartition(Span keys) 3. ArraySortHelper private static int PickPivotAndPartition(Span keys, Span values, IComparer comparer) 4. GenericArraySortHelper private static int PickPivotAndPartition(Span keys, Span values) ('Generic' here just means 'general purpose', it has nothing to do with C#/.NET generic types). Implementation number 2 (on GenericArraySortHelper) makes extensive use of Unsafe.Add(), Unsafe.IsAddressLessThan, and Unsafe.IsAddressGreaterThan, presumably for performance reasons, because that method handles the simplest scenario of a single array of keys that are either native types, or IComparable. However, it does make the code somewhat harder to read, and that has perhaps caused this redundant code to be missed. In the two implementations that take an IComparer, these inherently handle null keys as they are simply passed to IComparer.Compare(a,b). The other two implementations contain must contain a null key check, like so (/pivot/ is a key value, and may be null) (this is taken from implementation number 4, in GenericArraySortHelper): while (left < right) { if (pivot == null) { while (left < (hi - 1) && keys[++left] == null) ; while (right > 0 && keys[--right] != null) ; } else { while (GreaterThan(ref pivot, ref keys[++left])) ; while (LessThan(ref pivot, ref keys[--right])) ; } [...] } Notice that the first inner while loop increments _left_ until a non-null value is found, or some bound is reached. That bound check is not necessary when the pivot is non-null (as per the lower _else_ block). Now let's look at the equivalent section from implementation number 2, in GenericArraySortHelper: while (Unsafe.IsAddressLessThan(ref leftRef, ref rightRef)) { if (pivot == null) { while (Unsafe.IsAddressLessThan(ref leftRef, ref nextToLastRef) && (leftRef = ref Unsafe.Add(ref leftRef, 1)) == null) ; while (Unsafe.IsAddressGreaterThan(ref rightRef, ref zeroRef) && (rightRef = ref Unsafe.Add(ref rightRef, -1)) != null) ; } else { while (Unsafe.IsAddressLessThan(ref leftRef, ref nextToLastRef) && GreaterThan(ref pivot, ref leftRef = ref Unsafe.Add(ref leftRef, 1))) ; while (Unsafe.IsAddressGreaterThan(ref rightRef, ref zeroRef) && LessThan(ref pivot, ref rightRef = ref Unsafe.Add(ref rightRef, -1))) ; } [...] } Note that the lower _else_ block contains the unnecessary bounds tests. I believe these are redundant. Or, if they are not, then they are missing from implementation 4, in GenericArraySortHelper!

Author:	colgreen
Assignees:	-
Labels:	`area-System.Collections`, `tenet-performance`, `untriaged`
Milestone:	-

[stephentoub]

This is by design. An erroneous comparer could cause the loop to walk off the end of the span, otherwise. With the indexer, the runtime provides bounds check, but when using unsafe code, we need to make absolutely sure the code is still safe even in the face of a poorly-implemented comparer.

In general we shy away from using unsafe code for performance except for critical, hot-path functions... and this is one such function.

If you'd like to experiment with using safe code instead, please feel free.

[colgreen]

Thanks @stephentoub . In which case, I may look into the performance differential between unsafe vs safe code, as (a) my suspicion is that the difference will be minimal due to JITter improvements, and (b) it does cause a functional difference, i.e., in the 'erroneous comparer' scenario, the safe code will throw an index-out-of-range exception, whereas the unsafe code will continue executing the overall sort routine.

I appreciate there is a lot of nuance here, e.g. the type and size/width of the key type, the different types of comparer (native inline, IComparable, IComparer), CPU/hardware platform. So it's not an easy thing to nail down and say one approach is definitively faster/better than another.

[stephentoub]

the safe code will throw an index-out-of-range exception

It's caught higher in the stack.

my suspicion is that the difference will be minimal due to JITter improvments

It was quite measurable here the last time I looked several months ago. But, yes, things are always improving, so maybe you can come up with a better approach.

[colgreen]

If you have any performance test code that you think I could use then feel free to point me to it (or send it my way). E.g. code that tries a range of different scenarios (different ordered data, and data types).

My expectation is that either (a) your optimisation will still be faster (given that you observed that recently), or (b) the safe span indexer approach will match performance, which would then give us the option of changing back to safe code, but for no perf gain.

[stephentoub]

would then give us the option of changing back to safe code, but for no perf gain.

If we could get equivalent performance here without using unsafe code, we would happily accept a PR.

If you have any performance test code that you think I could use then feel free to point me to it (or send it my way).

There are some sorting tests in the dotnet/performance repo. I suggest starting with those. https://github.com/dotnet/performance/blob/master/src/benchmarks/micro/libraries/System.Collections/Sort.cs

You might also use the microbenchmarks from: https://github.com/dotnet/coreclr/pull/27700

[stephentoub]

As the question has been answered, I'm going to close the issue. If you come up with a good improvement, please do submit a PR :)

Thanks.

[colgreen]

@stephentoub just an fyi for now, but looks like the benchmarks are broken :(

See https://github.com/dotnet/BenchmarkDotNet/issues/1636

Closely related to your bug report https://github.com/dotnet/BenchmarkDotNet/issues/730