Value type sorting

[Tobias Hartmann]

Hi Doug,

thanks for trying out value types EA and for reporting back with these results!

I had a look at the 5% performance difference that you were seeing and it turned out that this is
not related to value types. The performance difference comes from the use of the CVal::compareTo()
method in the CVSorter. The implementation has several branches and after inlining, C2 will add
uncommon traps to those branches that profiling suggested are never taken.

As a result, 'a.compareTo(b) < 0' is not always optimized to 'a.field < b.field' but might be
translated into a 'a.field < b.field' and an additional 'a.field == b.field' check that will trap.

I've implemented a JMH benchmark that proves this:
http://cr.openjdk.java.net/~thartmann/valhalla/sorting/TestBenchmark.java

It uses your version of CVSorter and LongSorter and also CVSorter2 [1] which uses a direct field
access instead of a call to compareTo and LongSorter2 [2] which uses a call to compareTo instead of
a direct field access.

Here are the results of a quick run on my machine (needs more runs for lower error):

Benchmark                        (length)   Mode  Cnt   Score   Error  Units
TestBenchmark.sortCV              1000000  thrpt    5  13.326 ± 0.333  ops/s
TestBenchmark.sortCVCompareTo     1000000  thrpt    5  12.613 ± 0.309  ops/s
TestBenchmark.sortLong            1000000  thrpt    5  13.271 ± 0.460  ops/s
TestBenchmark.sortLongCompareTo   1000000  thrpt    5  11.828 ± 0.626  ops/s

It shows that the compareTo versions are significantly slower both for value types as well as for
primitive types. Also, without compareTo, the value types version is as fast as the primitive version.

Best regards,
Tobias

[1] http://cr.openjdk.java.net/~thartmann/valhalla/sorting/CVSorter2.java
[2] http://cr.openjdk.java.net/~thartmann/valhalla/sorting/LongSorter2.java

On 08.08.2018 20:33, Doug Lea wrote:
> I've been exploring sorting algorithms (mainly parallel but also
> sequential) that should apply well to value types. Even though Valhalla
> is not yet at a state where you can use generic by-value Comparables,
> I've been trying things out by manually plugging in various types, in
> part to scope out future issues. Sorting is the most famous example of a
> problem for which no algorithm is always best. Among other things,
> performance varies with element comparison vs copying cost, parallelism
> support, workspace overhead, and trade-offs of average vs worst case
> behavior. I placed a snapshot of the current Goldilocks candidate
> balancing these for value types at:
>   http://gee.cs.oswego.edu/dl/wwwtmp/CVSorter.java
> The internal documentation describes some of the algorithmic choices.
> As the instruction near the top indicate, for now you need to plug in
> any __ByValue class named "CVal". This compiles and runs using current
> (build zero) early access (http://jdk.java.net/valhalla/).
> 
> Just for comparison, there's also an otherwise identical version for
> long[] arrays at:
>   http://gee.cs.oswego.edu/dl/wwwtmp/LongSorter.java
> When using a __ByValue type just emulating a single long, CVSorter seems
> to be only 5% or so slower than LongSorter sorting 100 million elements,
> which is pretty good for using something labeled build zero. But
> CVSorter also works well with various small or medium-sized value types.
> 
> Any feedback would be welcome. It would be especially nice to hear from
> anyone who has actual data and types that need sorting. There are a lot
> of synthetic loads available (it does well on most), but having some
> actual cases that anyone might be dealing with in the future would be
> helpful.
> 
> -Doug