Remove ArrayUtil.timSort? [LUCENE-7268]

[asfimport]

Is there some workload where our timSort is better than the JDK one? Should we just remove ours if its slower?

Not that its a great test, but i switched Polygon2D edge sorting (just the one where it says "sort the edges then build a balanced tree from them") from Arrays.sort to ArrayUtil.timSort and was surprised when performance was much slower for an enormous polygon (http://people.apache.org/\~mikemccand/geobench/cleveland.poly.txt.gz)

---

Migrated from LUCENE-7268 by Robert Muir (@rmuir), updated May 02 2016
Attachments: LUCENE-7268_mods.patch

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

here are the local mods i have.

With the luceneutil geo benchmark, you can test this polygon with -points -polyFile /data/cleveland.poly.txt.gz. It will also print the tree construction time since its basically what makes this polygon slow.

I see this with Arrays.sort (construction time ~240ms):
BEST M hits/sec: 0.04010849804890369
BEST QPS: 3.429835646391628

On the other hand with ArrayUtil.timSort (construction time ~ 400ms):
BEST M hits/sec: 0.02554894823234268
BEST QPS: 2.1847911948300567

Its just one data point really, but I am curious what advantages ArrayUtil.timSort is supposed to have over Arrays.sort?

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

+1

I don't think it is expected to have advantages over Arrays.timSort. It'd be interesting to try to understand why our timSort is slower, maybe it has a performance bug.

[asfimport]

Dawid Weiss (@dweiss) (migrated from JIRA)

Other than consistency of having our own implementation I don't think this matters? I recall issues with TimSort that affected various jdk versions, so performance may depend on jvm version (and data).. Also, is the algorithm explicitly fixed to TimSort in Arrays.sort? I don't think so since it used to be merge sort before they switched it to timSort.

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

The javadocs for this arrays.sort method explicitly state timsort. Polygon edges are always clockwise or counterclockwise so kinda sorted already... So i think timsort makes sense?

But other use cases like index sorting have a similar situation... If there is a perf bug here it could be affecting many things

[asfimport]

Dawid Weiss (@dweiss) (migrated from JIRA)

The javadocs for this arrays.sort method explicitly state timsort.

But do you think this normative or just a feature of Oracle's particular implementation? I honestly don't know (not that it matters much in practice as there are effectively no other radically different implementations of the base package).

Tried to find the mails concerning TimSort but failed. Perhaps I confused it with something else, but I could swear it was on the mailing list pretty recently... I may try to look it up again once home.

[asfimport]

Dawid Weiss (@dweiss) (migrated from JIRA)

Sorry, it was this one affecting DualPivot.
https://bugs.openjdk.java.net/browse/JDK-8154049

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

I dont know. Afaik javadocs are the spec. But it relates to why i was looking at our timsort... to be explicit this is the sort to use, since we have reasons for this case.

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

I did some testing and the difference seems to be due to how our impl in ArrayUtil tries to save memory: it uses a hard-coded array.length/64 as the maximum size of the temporary Object[] that it may use for merging. If it needs less memory than that, it will use this temporary Object[], but for larger merges it will switch to an in-place merge routine that is much slower (the same logic that InPlaceMergeSorter uses). I get the following build times with the patch:

Arrays.sort	222ms
ArrayUtil.timSort - max temp storage = array.length	262ms
ArrayUtil.timSort - max temp storage = array.length/64 (like in master)	383ms
ArrayUtil.timSort - max temp storage = 0	444ms

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

interesting, arrays.sort declares it will use at most array.length/2 temporary storage:

"Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays."

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

That is right for our TimSort too, my bad. I did the test with a max temporary storage of array.length above, but it would work the same with a mamimum temporary storage of about array.length/2, and it would still not merge in place.