[PATCH] Enhancement proposal for TimSort and ComparableTimSort

[Martin Buchholz]

One learns to be sceptical of such special cases.  Especially when so much
effort was put into optimizing the original code.

         if (nRemaining < 2)
             return;  // Arrays of size 0 and 1 are always sorted

+        //when array's size is 2 we just need to swap items
+        //if the first item is greater than the second one
+        if (nRemaining == 2) {


If you're going to have a fastpath for small arrays, it should probably
start with

nRemaining <= 2 instead of nRemaining < 2 to avoid slowing down the normal
path.


On Fri, Sep 15, 2017 at 2:49 AM, Сергей Цыпанов <sergei.tsypanov at yandex.ru>
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