You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Stefan Pohl (JIRA)" <ji...@apache.org> on 2012/11/07 15:31:12 UTC
[jira] [Created] (LUCENE-4546) SorterTemplate.quicksort incorrect
Stefan Pohl created LUCENE-4546:
-----------------------------------
Summary: SorterTemplate.quicksort incorrect
Key: LUCENE-4546
URL: https://issues.apache.org/jira/browse/LUCENE-4546
Project: Lucene - Core
Issue Type: Bug
Components: core/other
Affects Versions: 4.0, 3.6.1, 4.1
Reporter: Stefan Pohl
Fix For: 4.1, 4.0, 3.6.1
On trying to use the very useful o.a.l.utils.SorterTemplate, I stumbled upon inconsistent sorting behaviour, of course, only a randomized test caught this;)
Because SorterTemplate.quicksort is used in several places in the code (directly BytesRefList, ArrayUtil, BytesRefHash, CollectionUtil and transitively index and search), I'm a bit puzzled that this either hasn't been caught by another higher-level test or that neither my test nor my understanding of an insufficiency in the code is valid;)
If the former holds and given that the same code is released in 3.6 and 4.0, this might even be a more critical issue requiring a higher priority than 'major'.
So, can a second pair of eyes please have a timely look at the attached test and patch?
Basically the current quicksort implementation seems to assume that luckily always the median is chosen as pivot element by grabbing the mid element, not handling the case where the initially chosen pivot ends up not in the middle. Hope this and the test helps to understand the issue.
Reproducible, currently failing test and a patch attached.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-4546) SorterTemplate.quicksort incorrect
Posted by "Uwe Schindler (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-4546?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13492450#comment-13492450 ]
Uwe Schindler commented on LUCENE-4546:
---------------------------------------
By the way we have a random test (TestArrayUtil) that does exactly the same, but the tested ArrayUtil handles the pivot value correctly, so it works correct. If you use your failing example array and sort it with ArrayUtil it passes.
> SorterTemplate.quicksort incorrect
> ----------------------------------
>
> Key: LUCENE-4546
> URL: https://issues.apache.org/jira/browse/LUCENE-4546
> Project: Lucene - Core
> Issue Type: Bug
> Components: core/other
> Affects Versions: 3.6.1, 4.0, 4.1
> Reporter: Stefan Pohl
> Labels: patch
> Fix For: 3.6.1, 4.0, 4.1
>
> Attachments: SorterTemplate.java.patch, TestSorterTemplate.java
>
>
> On trying to use the very useful o.a.l.utils.SorterTemplate, I stumbled upon inconsistent sorting behaviour, of course, only a randomized test caught this;)
> Because SorterTemplate.quicksort is used in several places in the code (directly BytesRefList, ArrayUtil, BytesRefHash, CollectionUtil and transitively index and search), I'm a bit puzzled that this either hasn't been caught by another higher-level test or that neither my test nor my understanding of an insufficiency in the code is valid;)
> If the former holds and given that the same code is released in 3.6 and 4.0, this might even be a more critical issue requiring a higher priority than 'major'.
> So, can a second pair of eyes please have a timely look at the attached test and patch?
> Basically the current quicksort implementation seems to assume that luckily always the median is chosen as pivot element by grabbing the mid element, not handling the case where the initially chosen pivot ends up not in the middle. Hope this and the test helps to understand the issue.
> Reproducible, currently failing test and a patch attached.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Updated] (LUCENE-4546) SorterTemplate.quicksort incorrect
Posted by "Stefan Pohl (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-4546?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Stefan Pohl updated LUCENE-4546:
--------------------------------
Attachment: SorterTemplate.java.patch
TestSorterTemplate.java
Test and patch file now attached.
> SorterTemplate.quicksort incorrect
> ----------------------------------
>
> Key: LUCENE-4546
> URL: https://issues.apache.org/jira/browse/LUCENE-4546
> Project: Lucene - Core
> Issue Type: Bug
> Components: core/other
> Affects Versions: 3.6.1, 4.0, 4.1
> Reporter: Stefan Pohl
> Labels: patch
> Fix For: 3.6.1, 4.0, 4.1
>
> Attachments: SorterTemplate.java.patch, TestSorterTemplate.java
>
>
> On trying to use the very useful o.a.l.utils.SorterTemplate, I stumbled upon inconsistent sorting behaviour, of course, only a randomized test caught this;)
> Because SorterTemplate.quicksort is used in several places in the code (directly BytesRefList, ArrayUtil, BytesRefHash, CollectionUtil and transitively index and search), I'm a bit puzzled that this either hasn't been caught by another higher-level test or that neither my test nor my understanding of an insufficiency in the code is valid;)
> If the former holds and given that the same code is released in 3.6 and 4.0, this might even be a more critical issue requiring a higher priority than 'major'.
> So, can a second pair of eyes please have a timely look at the attached test and patch?
> Basically the current quicksort implementation seems to assume that luckily always the median is chosen as pivot element by grabbing the mid element, not handling the case where the initially chosen pivot ends up not in the middle. Hope this and the test helps to understand the issue.
> Reproducible, currently failing test and a patch attached.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-4546) SorterTemplate.quicksort incorrect
Posted by "Uwe Schindler (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-4546?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13492720#comment-13492720 ]
Uwe Schindler commented on LUCENE-4546:
---------------------------------------
Hi Stefan,
it is some time ago when I worked on SorterTemplate, so I don't have all the facts in mind. There are different implementations of QuickSort available, also those working without any pivot (like yours). But as far as I remember, the performance tests showed, that the additional swaps and compares added some slowdown (depending on the order of input data), so the explicit pivot methods helped. The SorterTemplate quicksort implementation is also the one that was used in Lucene from the beginning, so I did not want to change the algorithm in a minor release. We could add some new performance tests with your implementation and compare the speed, but I think, e.g. CollectionUtil, which uses Collections.swap() would get much slower by this.
I agree, the class is very nice for sorting of non-array data, but it is currently marked as @lucene.internal, so the usability for non-lucene code was never thought of, performance was the only driving force :-) But I checked the javadocs, it is clearly documented that setPivot(i) has to store the value of slot i for later comparison with comparePivot(j).
> SorterTemplate.quicksort incorrect
> ----------------------------------
>
> Key: LUCENE-4546
> URL: https://issues.apache.org/jira/browse/LUCENE-4546
> Project: Lucene - Core
> Issue Type: Bug
> Components: core/other
> Affects Versions: 3.6.1, 4.0, 4.1
> Reporter: Stefan Pohl
> Assignee: Uwe Schindler
> Labels: patch
> Fix For: 3.6.1, 4.0, 4.1
>
> Attachments: SorterTemplate.java.patch, TestSorterTemplate.java, TestSorterTemplate.java
>
>
> On trying to use the very useful o.a.l.utils.SorterTemplate, I stumbled upon inconsistent sorting behaviour, of course, only a randomized test caught this;)
> Because SorterTemplate.quicksort is used in several places in the code (directly BytesRefList, ArrayUtil, BytesRefHash, CollectionUtil and transitively index and search), I'm a bit puzzled that this either hasn't been caught by another higher-level test or that neither my test nor my understanding of an insufficiency in the code is valid;)
> If the former holds and given that the same code is released in 3.6 and 4.0, this might even be a more critical issue requiring a higher priority than 'major'.
> So, can a second pair of eyes please have a timely look at the attached test and patch?
> Basically the current quicksort implementation seems to assume that luckily always the median is chosen as pivot element by grabbing the mid element, not handling the case where the initially chosen pivot ends up not in the middle. Hope this and the test helps to understand the issue.
> Reproducible, currently failing test and a patch attached.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Comment Edited] (LUCENE-4546) SorterTemplate.quicksort
incorrect
Posted by "Uwe Schindler (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-4546?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13492464#comment-13492464 ]
Uwe Schindler edited comment on LUCENE-4546 at 11/7/12 9:25 PM:
----------------------------------------------------------------
Attached the corrected testcase, which passes.
-BTW: Your SorterTemplate implementation fails with with mergeSort completely- :-) _(this was incorrect, mergeSort does not use the pivot methods)_
was (Author: thetaphi):
Attached the corrected testcase, which passes.
BTW: Your SorterTemplate implementation fails with with mergeSort completely :-)
> SorterTemplate.quicksort incorrect
> ----------------------------------
>
> Key: LUCENE-4546
> URL: https://issues.apache.org/jira/browse/LUCENE-4546
> Project: Lucene - Core
> Issue Type: Bug
> Components: core/other
> Affects Versions: 3.6.1, 4.0, 4.1
> Reporter: Stefan Pohl
> Assignee: Uwe Schindler
> Labels: patch
> Fix For: 3.6.1, 4.0, 4.1
>
> Attachments: SorterTemplate.java.patch, TestSorterTemplate.java, TestSorterTemplate.java
>
>
> On trying to use the very useful o.a.l.utils.SorterTemplate, I stumbled upon inconsistent sorting behaviour, of course, only a randomized test caught this;)
> Because SorterTemplate.quicksort is used in several places in the code (directly BytesRefList, ArrayUtil, BytesRefHash, CollectionUtil and transitively index and search), I'm a bit puzzled that this either hasn't been caught by another higher-level test or that neither my test nor my understanding of an insufficiency in the code is valid;)
> If the former holds and given that the same code is released in 3.6 and 4.0, this might even be a more critical issue requiring a higher priority than 'major'.
> So, can a second pair of eyes please have a timely look at the attached test and patch?
> Basically the current quicksort implementation seems to assume that luckily always the median is chosen as pivot element by grabbing the mid element, not handling the case where the initially chosen pivot ends up not in the middle. Hope this and the test helps to understand the issue.
> Reproducible, currently failing test and a patch attached.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-4546) SorterTemplate.quicksort incorrect
Posted by "Stefan Pohl (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-4546?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13492480#comment-13492480 ]
Stefan Pohl commented on LUCENE-4546:
-------------------------------------
Thanks for the clarification, Uwe!
Out of curiosity and for reference, are there any reasons for the abstraction having to overwrite setPivot/comparePivot? Using the implementation in my patch would actually allow to get rid of having to overwrite these methods at all, possibly being faster due to removal of some calls depending on JVM optimization and possibly being slower due to a few more swaps and branches in the code. Pure speculation.
> SorterTemplate.quicksort incorrect
> ----------------------------------
>
> Key: LUCENE-4546
> URL: https://issues.apache.org/jira/browse/LUCENE-4546
> Project: Lucene - Core
> Issue Type: Bug
> Components: core/other
> Affects Versions: 3.6.1, 4.0, 4.1
> Reporter: Stefan Pohl
> Assignee: Uwe Schindler
> Labels: patch
> Fix For: 3.6.1, 4.0, 4.1
>
> Attachments: SorterTemplate.java.patch, TestSorterTemplate.java, TestSorterTemplate.java
>
>
> On trying to use the very useful o.a.l.utils.SorterTemplate, I stumbled upon inconsistent sorting behaviour, of course, only a randomized test caught this;)
> Because SorterTemplate.quicksort is used in several places in the code (directly BytesRefList, ArrayUtil, BytesRefHash, CollectionUtil and transitively index and search), I'm a bit puzzled that this either hasn't been caught by another higher-level test or that neither my test nor my understanding of an insufficiency in the code is valid;)
> If the former holds and given that the same code is released in 3.6 and 4.0, this might even be a more critical issue requiring a higher priority than 'major'.
> So, can a second pair of eyes please have a timely look at the attached test and patch?
> Basically the current quicksort implementation seems to assume that luckily always the median is chosen as pivot element by grabbing the mid element, not handling the case where the initially chosen pivot ends up not in the middle. Hope this and the test helps to understand the issue.
> Reproducible, currently failing test and a patch attached.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-4546) SorterTemplate.quicksort incorrect
Posted by "Uwe Schindler (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-4546?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13492445#comment-13492445 ]
Uwe Schindler commented on LUCENE-4546:
---------------------------------------
Hi,
I think the problem is your test case:
The SorterTemplate in your test does not handle the pivot value correctly - The setPivot() and comparePivot() methods get the index to compare with, but setPivot must store the actual value of the pivot, not the index of the pivot. Your code just stores the pivot index. You can fix this by correctly implementing setPivot: this.pivot = x[i] and implement comparePivot accordingly.
See ArrayUtil for an example.
> SorterTemplate.quicksort incorrect
> ----------------------------------
>
> Key: LUCENE-4546
> URL: https://issues.apache.org/jira/browse/LUCENE-4546
> Project: Lucene - Core
> Issue Type: Bug
> Components: core/other
> Affects Versions: 3.6.1, 4.0, 4.1
> Reporter: Stefan Pohl
> Labels: patch
> Fix For: 3.6.1, 4.0, 4.1
>
> Attachments: SorterTemplate.java.patch, TestSorterTemplate.java
>
>
> On trying to use the very useful o.a.l.utils.SorterTemplate, I stumbled upon inconsistent sorting behaviour, of course, only a randomized test caught this;)
> Because SorterTemplate.quicksort is used in several places in the code (directly BytesRefList, ArrayUtil, BytesRefHash, CollectionUtil and transitively index and search), I'm a bit puzzled that this either hasn't been caught by another higher-level test or that neither my test nor my understanding of an insufficiency in the code is valid;)
> If the former holds and given that the same code is released in 3.6 and 4.0, this might even be a more critical issue requiring a higher priority than 'major'.
> So, can a second pair of eyes please have a timely look at the attached test and patch?
> Basically the current quicksort implementation seems to assume that luckily always the median is chosen as pivot element by grabbing the mid element, not handling the case where the initially chosen pivot ends up not in the middle. Hope this and the test helps to understand the issue.
> Reproducible, currently failing test and a patch attached.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Updated] (LUCENE-4546) SorterTemplate.quicksort incorrect
Posted by "Uwe Schindler (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-4546?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Uwe Schindler updated LUCENE-4546:
----------------------------------
Attachment: TestSorterTemplate.java
Attached the corrected testcase, which passes.
BTW: Your SorterTemplate implementation fails with with mergeSort completely :-)
> SorterTemplate.quicksort incorrect
> ----------------------------------
>
> Key: LUCENE-4546
> URL: https://issues.apache.org/jira/browse/LUCENE-4546
> Project: Lucene - Core
> Issue Type: Bug
> Components: core/other
> Affects Versions: 3.6.1, 4.0, 4.1
> Reporter: Stefan Pohl
> Assignee: Uwe Schindler
> Labels: patch
> Fix For: 3.6.1, 4.0, 4.1
>
> Attachments: SorterTemplate.java.patch, TestSorterTemplate.java, TestSorterTemplate.java
>
>
> On trying to use the very useful o.a.l.utils.SorterTemplate, I stumbled upon inconsistent sorting behaviour, of course, only a randomized test caught this;)
> Because SorterTemplate.quicksort is used in several places in the code (directly BytesRefList, ArrayUtil, BytesRefHash, CollectionUtil and transitively index and search), I'm a bit puzzled that this either hasn't been caught by another higher-level test or that neither my test nor my understanding of an insufficiency in the code is valid;)
> If the former holds and given that the same code is released in 3.6 and 4.0, this might even be a more critical issue requiring a higher priority than 'major'.
> So, can a second pair of eyes please have a timely look at the attached test and patch?
> Basically the current quicksort implementation seems to assume that luckily always the median is chosen as pivot element by grabbing the mid element, not handling the case where the initially chosen pivot ends up not in the middle. Hope this and the test helps to understand the issue.
> Reproducible, currently failing test and a patch attached.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Resolved] (LUCENE-4546) SorterTemplate.quicksort incorrect
Posted by "Uwe Schindler (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-4546?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Uwe Schindler resolved LUCENE-4546.
-----------------------------------
Resolution: Not A Problem
> SorterTemplate.quicksort incorrect
> ----------------------------------
>
> Key: LUCENE-4546
> URL: https://issues.apache.org/jira/browse/LUCENE-4546
> Project: Lucene - Core
> Issue Type: Bug
> Components: core/other
> Affects Versions: 3.6.1, 4.0, 4.1
> Reporter: Stefan Pohl
> Assignee: Uwe Schindler
> Labels: patch
> Fix For: 4.1, 4.0, 3.6.1
>
> Attachments: SorterTemplate.java.patch, TestSorterTemplate.java, TestSorterTemplate.java
>
>
> On trying to use the very useful o.a.l.utils.SorterTemplate, I stumbled upon inconsistent sorting behaviour, of course, only a randomized test caught this;)
> Because SorterTemplate.quicksort is used in several places in the code (directly BytesRefList, ArrayUtil, BytesRefHash, CollectionUtil and transitively index and search), I'm a bit puzzled that this either hasn't been caught by another higher-level test or that neither my test nor my understanding of an insufficiency in the code is valid;)
> If the former holds and given that the same code is released in 3.6 and 4.0, this might even be a more critical issue requiring a higher priority than 'major'.
> So, can a second pair of eyes please have a timely look at the attached test and patch?
> Basically the current quicksort implementation seems to assume that luckily always the median is chosen as pivot element by grabbing the mid element, not handling the case where the initially chosen pivot ends up not in the middle. Hope this and the test helps to understand the issue.
> Reproducible, currently failing test and a patch attached.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Assigned] (LUCENE-4546) SorterTemplate.quicksort incorrect
Posted by "Uwe Schindler (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-4546?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Uwe Schindler reassigned LUCENE-4546:
-------------------------------------
Assignee: Uwe Schindler
> SorterTemplate.quicksort incorrect
> ----------------------------------
>
> Key: LUCENE-4546
> URL: https://issues.apache.org/jira/browse/LUCENE-4546
> Project: Lucene - Core
> Issue Type: Bug
> Components: core/other
> Affects Versions: 3.6.1, 4.0, 4.1
> Reporter: Stefan Pohl
> Assignee: Uwe Schindler
> Labels: patch
> Fix For: 3.6.1, 4.0, 4.1
>
> Attachments: SorterTemplate.java.patch, TestSorterTemplate.java
>
>
> On trying to use the very useful o.a.l.utils.SorterTemplate, I stumbled upon inconsistent sorting behaviour, of course, only a randomized test caught this;)
> Because SorterTemplate.quicksort is used in several places in the code (directly BytesRefList, ArrayUtil, BytesRefHash, CollectionUtil and transitively index and search), I'm a bit puzzled that this either hasn't been caught by another higher-level test or that neither my test nor my understanding of an insufficiency in the code is valid;)
> If the former holds and given that the same code is released in 3.6 and 4.0, this might even be a more critical issue requiring a higher priority than 'major'.
> So, can a second pair of eyes please have a timely look at the attached test and patch?
> Basically the current quicksort implementation seems to assume that luckily always the median is chosen as pivot element by grabbing the mid element, not handling the case where the initially chosen pivot ends up not in the middle. Hope this and the test helps to understand the issue.
> Reproducible, currently failing test and a patch attached.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org