Benchmarking of new optimized Dual-Pivot Quicksort

[Vladimir Yaroslavskiy]

Hi all,
With the help of Laurent Bourges I run benchmarking of new optimized Dual-Pivot Quicksort
and summarized results. The tests were run for all types (int / long / ... / double), for both types:
sequential and parallel sorting, for small, medium and large sizes. The comparison was done
on several data types, such as: random, period, sorted, equal, stagger, shuffle.
Here is the summary of total gains. The gain is defined as (jdk_time - dpqs_time) / jdk_time,
where jdk_time is sorting time by the current jdk14 and dpqs_time is sorting time by new
optimized Dual-Pivot Quicksort. To get stable and reproducible results, min time of many
invocations is taken.
You can find all detailed results there
https://github.com/iaroslavski/sorting/tree/master/benchmarking/results  

Sources of benchmarking tests are there
https://github.com/iaroslavski/sorting/tree/master/benchmarking/sources

You can see not good performance for float / double types (parallel sorting).
This behavior can be explained by existing bug in jdk, when NaNs and -0.0s
are not processed properly. New sorting has total losses for small float / double
arrays, few percents only. For all other cases new optimized sorting is winner.

--------------------------------------------------------------------------------------------------------
[int]
sequential, Length = 150, Gain: 0.15
sequential, Length = 30000, Gain: 0.28
sequential, Length = 1000000, Gain: 0.31
parallel 8, Length = 150, Gain: 0.14
parallel 8, Length = 30000, Gain: 0.15
parallel 8, Length = 1000000, Gain: 0.14
[long]
sequential, Length = 150, Gain: 0.12
sequential, Length = 30000, Gain: 0.23
sequential, Length = 1000000, Gain: 0.32
parallel 8, Length = 150, Gain: 0.11
parallel 8, Length = 30000, Gain: 0.16
parallel 8, Length = 1000000, Gain: 0.24
parallel 88 processors, Length = 1000000, Gain: 0.05
[byte]
sequential, Length = 150, Gain: 0.06
sequential, Length = 30000, Gain: 0.36
sequential, Length = 1000000, Gain: 0.37
parallel 8, Length = 150, Gain: 0.13
parallel 8, Length = 30000, Gain: 0.73
parallel 8, Length = 1000000, Gain: 0.65
[char]
sequential, Length = 150, Gain: 0.10
sequential, Length = 30000, Gain: 0.00
sequential, Length = 1000000, Gain: 0.17
parallel 8, Length = 150, Gain: 0.10
parallel 8, Length = 30000, Gain: 0.33
parallel 8, Length = 1000000, Gain: 0.62
[short]
sequential, Length = 150, Gain: 0.14
sequential, Length = 30000, Gain: 0.10
sequential, Length = 1000000, Gain: 0.18
parallel 8, Length = 150, Gain: 0.13
parallel 8, Length = 30000, Gain: 0.41
parallel 8, Length = 1000000, Gain: 0.65
[float]
sequential, Length = 150, Gain: -0.02
sequential, Length = 30000, Gain: 0.21
sequential, Length = 1000000, Gain: 0.24
parallel 8, Length = 150, Gain: -0.05
parallel 8, Length = 30000, Gain: -0.04
parallel 8, Length = 1000000, Gain: -0.12
[double]
sequential, Length = 150, Gain: -0.03
sequential, Length = 30000, Gain: 0.19
sequential, Length = 1000000, Gain: 0.23
parallel 8, Length = 150, Gain: -0.05
parallel 8, Length = 30000, Gain: 0.05
parallel 8, Length = 1000000, Gain: 0.15
Thank you,
Vladimir