apache / apache/lucene

Remove ArrayUtil.timSort? [LUCENE-7268]

Open
#8,323 10 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Major type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

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](https://issues.apache.org/jira/browse/LUCENE-7268) by Robert Muir (@rmuir), updated May 02 2016
Attachments: [LUCENE-7268_mods.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-7268/LUCENE-7268_mods.patch)

Contributor guide

Open the contributing guide

Research direction

Start with ArrayUtil.timSort and the Polygon2D edge-sorting call site mentioned in the issue; compare it with Arrays.sort using the linked Cleveland polygon workload. Review LUCENE-7268_mods.patch and the existing comments, then make a benchmark-backed decision on whether the custom sort should remain or be removed.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.