lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Hoss Man (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (LUCENE-6293) TimSort bug
Date Wed, 25 Feb 2015 16:39:05 GMT

    [ https://issues.apache.org/jira/browse/LUCENE-6293?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14336727#comment-14336727
] 

Hoss Man commented on LUCENE-6293:
----------------------------------

bq. There are two suggested ways to fix the issue, either change the max stack size or change
the condition upon which consecutive runs are collapsed. I opted for the first one which is
easier to implement.

Doesn't that cause excessive/unneccessary array allocation? .... it sounds like the same fix
the JVM team applied that the original bug reporter lamented was inefficient...

bq. The reaction of the Java developer community to our report is somewhat disappointing:
instead of using our fixed (and verified!) version of mergeCollapse(), they opted to increase
the allocated runLen “sufficiently”. As we showed, this is not necessary. In consequence,
whoever uses java.utils.Collection.sort() is forced to over allocate space. Given the astronomical
number of program runs that such a central routine is used in, this leads to a considerable
waste of energy.

> TimSort bug
> -----------
>
>                 Key: LUCENE-6293
>                 URL: https://issues.apache.org/jira/browse/LUCENE-6293
>             Project: Lucene - Core
>          Issue Type: Bug
>            Reporter: Adrien Grand
>            Assignee: Adrien Grand
>            Priority: Minor
>         Attachments: LUCENE-6293.patch
>
>
> Robert pointed me to http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
yesterday which explains how most implementations of TimSort are broken. We should check our
TimSorter.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message