[LUCENE-9887] error param use in RadixSelector

• Type: Improvement
• Status: Closed
• Priority: Trivial
• Resolution: Fixed
• Affects Version/s: 8.8
• Fix Version/s: 8.9
• Component/s: core/other
• Labels: patch
• Lucene Fields: Patch Available
• Review Patch?: Yes
• Assignee: Unassigned
• Reporter: liupanfeng
• Created: 27/Mar/21 12:29
• Updated: 28/Aug/22 16:19
• Resolved: 29/Mar/21 10:27

Description

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 will be bigger.

 

other evidence:

1. In comments, said we use recursion level (f) not byte index of value(d).
2.  if d is right, then the param f could be deleted because of it was not used by any method.

verification:

1. It also can select right value if i change d -> f.
2. 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.