Value type sorting

[Doug Lea]

On 08/27/2018 08:25 AM, Tobias Hartmann wrote:

> 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.

Thanks. While this can be worked around for particular cases, it will
become a more common issue with generics+values, for which using
Comparables and/or Comparators will be inescapable. It might help to
intrinsify {Integer,Long, etc}.compareTo methods to somehow return coded
condition status registers or somesuch (since only one comparison
instruction is actually needed)? If users know that these primitive
methods are optimized, they can use them to construct more efficient
compareTo methods.

-Doug


> 
> 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
>