Uploaded image for project: 'Lucene - Core'
  1. Lucene - Core
  2. LUCENE-9886

error param use in RadixSelector

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Resolved
    • Trivial
    • Resolution: Won't Do
    • 8.8
    • None
    • core/other
    • None

    • Patch Available
    • Yes

    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.

       

      Attachments

        Activity

          People

            Unassigned Unassigned
            liupanfeng liupanfeng
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: