liupanfeng created LUCENE-9886:
----------------------------------
Summary: error param use in RadixSelector
Key: LUCENE-9886
URL: https://issues.apache.org/jira/browse/LUCENE-9886
Project: Lucene - Core
Issue Type: Improvement
Components: core/other
Affects Versions: 8.8
Environment: None
Reporter: liupanfeng
There is a param use error in *org.apache.lucene.util.RadixSelector#select(int,
int, int, int, int).*
What is we expected in this method is:
if the range becomes narrow or when the maximum level of recursion has been
exceeded, then we get a fall-back selector(it's a IntroSelector).
*So, we should use the recursion level(param f) compare to LEVEL_THRESHOLD.
NOT the byte index of value(param d).*
effect:
This bug will not affect the correctness of the program. but affect performance
in some bad case. In average, RadixSelector and IntroSelector are all in linear
time. This bug will let we choose a fall-back selector too early, then the
constant of O(n) will be bigger.
other evidence:
# In comments, said we use recursion level (f) not byte index of value(d).
# if *d* is right, then the *param f* could be deleted because of it was not
used by any method.
verification:
# It also can select right value if i change d -> f.
# I did some benchmark works. but the result was unstable on random data.
Thanks for your read. I'm new of lucene. So please reply me if I am wrong. Or
fix it in future.
I will do benchmark. But I can't promised the result is better. If you need the
result. Ask for me.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
