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
diff --git a/src/java.base/share/classes/java/util/ComparableTimSort.java b/src/java.base/share/classes/java/util/ComparableTimSort.java
--- a/src/java.base/share/classes/java/util/ComparableTimSort.java
+++ b/src/java.base/share/classes/java/util/ComparableTimSort.java
@@ -183,6 +183,17 @@
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) {
+ Comparable o0 = (Comparable) a[0];
+ Object o1 = a[1];
+
+ if (o0.compareTo(o1) > 0) {
+ a[0] = o1;
+ a[1] = o0;
+ }
+ return;
+ }
+
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi);
diff --git a/src/java.base/share/classes/java/util/TimSort.java b/src/java.base/share/classes/java/util/TimSort.java
--- a/src/java.base/share/classes/java/util/TimSort.java
+++ b/src/java.base/share/classes/java/util/TimSort.java
@@ -215,6 +215,17 @@
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) {
+ T o0 = a[0];
+ T o1 = a[1];
+ if (c.compare(o0, o1) > 0) {
+ a[0] = o1;
+ a[1] = o0;
+ }
+ return;
+ }
+
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
