Value type sorting

[Doug Lea]

On 08/08/2018 03:34 PM, Remi Forax wrote:
> Hi Doug,
> the example of CVal in CVSorter is weird,
> 
>  * <pre> {@code
>  * __ByValue class CVal {
>  *   final long field1;
>  *   final long field2;
>  *   public CVal(long f2, long f2) { field1 = f1; field2 = f2; }

Thanks. I fixed typo: first f2 should be f1

> why do you have two long fields instead of one, it doesn't seem to be a fair comparison.

It's not fair for comparing vs plain long[] (and is not the version used
for that), but shows a typical case in which not all fields are used in
comparator.

-Doug


> 
> ----- Mail original -----
>> De: "Doug Lea" <dl at cs.oswego.edu>
>> À: "valhalla-dev" <valhalla-dev at openjdk.java.net>
>> Envoyé: Mercredi 8 Août 2018 20:33:01
>> Objet: Value type sorting
> 
>> 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
>