[PATCH] Enhancement proposal for TimSort and ComparableTimSort

[Claes Redestad]

Hi,

looks reasonable, but when adding a fast-path branch like this it's just 
as important to show that we don't regress *other* cases, e.g., 
benchmark using input data of randomized lengths, both on sets which 
include and don't include 1- and 2-element arrays.

/Claes


On 2017-09-15 11:49, Сергей Цыпанов wrote:
> Current implementations of TimSort and ComparableTimSort both have fast path for the case when the size of array = 1 i.e. such array is considered to be sorted.
>
> My proposal is to add similar fast path for the case when the size of the array = 2. In this case it's enough to check if the first item is greater than the second one and swap them.
> Otherwise array is considered to be sorted.
>
> I have attached the patch to this mail.
>
> As for performance I have measured array sort with size = 2 using JDK-provided and patched implementations of TimSort and ComparableTimSort both execution time and throughput in two environments:
>
> 1)  Intel Core i5-4690 3,50 GHz
> 2)  Intel Core i3-3220 3,30 GHz
>
> On both environments I have Java version "1.8.0_144"
> Java(TM) SE Runtime Environment (build 1.8.0_144-b01)
> Java HotSpot(TM) 64-Bit Server VM (build 25.144-b01, mixed mode)
>
> Measurement results are
>
> 1)
>
> Benchmark                                                        Mode  Cnt   Score     Error   Units
>
> SortingBenchmark.measureConventionalSort  avgt    500  17,692 ± 0,040  ns/op
> SortingBenchmark.measureEnhancedSort       avgt    500  13,206 ± 0,025  ns/op
>
> SortingBenchmark.measureConventionalSort  thrpt    500  56,962 ± 0,051  ops/us
> SortingBenchmark.measureEnhancedSort       thrpt    500  72,278 ± 0,724  ops/us
>
> 2)
>
> Benchmark                                                        Mode  Cnt   Score    Error  Units
>
> SortingBenchmark.measureConventionalSort  avgt    500  26,173 ± 0,251  ns/op
> SortingBenchmark.measureEnhancedSort       avgt    500  18,191 ± 0,106  ns/op
>
> SortingBenchmark.measureConventionalSort  thrpt    500  36,987 ± 0,437  ops/us
> SortingBenchmark.measureEnhancedSort       thrpt    500  53,499 ± 0,456  ops/us
>
> So in both cases patched implementation demonstrates better throughput and execution time for the case array.lenght = 2.
>
> Regards,
> Sergei Tsypanov