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

error param use in RadixSelector

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Resolved
    • Priority: Trivial
    • Resolution: Won't Do
    • Affects Version/s: 8.8
    • Fix Version/s: None
    • Component/s: core/other
    • Labels:
    • Environment:

      None

    • Lucene Fields:
      Patch Available
    • Review Patch?:
      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

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

              Dates

              • Created:
                Updated:
                Resolved: