You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "dungba88 (via GitHub)" <gi...@apache.org> on 2024/07/21 07:34:57 UTC

[PR] Optimize binary search call [lucene]

dungba88 opened a new pull request, #13595:
URL: https://github.com/apache/lucene/pull/13595

   ### Description
   
   I think `advance` is usually not called in backward, so we can run the binary search from the current position +1 instead of 0. Also cap the fromIndex to scoreDocs.length to avoid overflow.
   
   From the Javadoc of `advance`
   
   ```
      * <p>The behavior of this method is <b>undefined</b> when called with <code> target &le; current
      * </code>, or after the iterator has exhausted. Both cases may result in unpredicted behavior.
   ```


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Optimize binary search call [lucene]

Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #13595:
URL: https://github.com/apache/lucene/pull/13595#issuecomment-2263350507

   Ah yeah, OK thanks @jpountz. Makes sense.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Optimize binary search call [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #13595:
URL: https://github.com/apache/lucene/pull/13595#issuecomment-2263244861

   If `DocIdSetIterator#advance` gets called on large increments, then there are only so many calls that can be done because the doc ID space is quickly exhausted. However, if you only advance by small intervals, then you could end up with millions of calls to `DocIdSetIterator#advance`, so this tends to be the case worth optimizing. E.g. the recent change to skip data removed the higher levels of skip data that help advance by large increments, yet queries observed a speedup rather than a slowdown.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Optimize binary search call [lucene]

Posted by "dungba88 (via GitHub)" <gi...@apache.org>.
dungba88 commented on PR #13595:
URL: https://github.com/apache/lucene/pull/13595#issuecomment-2264454968

   @jpountz I was reading `IntArrayDocIdSetIterator`, it is a private class only exposed through `IntArrayDocIdSet`. I think we need to extend the capability here (storing the score, having both score + doc ID instead of just doc ID). I think we can just re-implement the exponential search here. I can cut follow-up to move implementation to a common place, maybe ArrayUtil. WDYT?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Optimize binary search call [lucene]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #13595:
URL: https://github.com/apache/lucene/pull/13595#issuecomment-3408724365

   This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the dev@lucene.apache.org list. Thank you for your contribution!


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Optimize binary search call [lucene]

Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #13595:
URL: https://github.com/apache/lucene/pull/13595#issuecomment-2263219440

   I _think_ exponential search will only outperform binary search in this case if we expect the next target to be relatively close to the "min" we're constantly "pushing up" (thanks to your change). Is that the case? (Specifically, I think the math works out that exponential search is only better if the target is in the next `sqrt(N)` elements where `N` is the size of the remaining list being searched... but I could be wrong).


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Optimize binary search call [lucene]

Posted by "dungba88 (via GitHub)" <gi...@apache.org>.
dungba88 commented on PR #13595:
URL: https://github.com/apache/lucene/pull/13595#issuecomment-2262677876

   The `advance` will keep reducing the array size and we will generally advance small steps ahead right? Then I think exponential search makes sense. I'll try to use `IntArrayDocIdSetIterator` in next rev


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Optimize binary search call [lucene]

Posted by "dungba88 (via GitHub)" <gi...@apache.org>.
dungba88 commented on PR #13595:
URL: https://github.com/apache/lucene/pull/13595#issuecomment-2543558374

   @jpountz I have changed the code to exponential search, and move the functionality to ArrayUtil. We still need two different method for `int[]` and generic array, as Java doesn't seem to allow genericize primitive types. Can you give some feedbacks on the new revision?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Optimize binary search call [lucene]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #13595:
URL: https://github.com/apache/lucene/pull/13595#issuecomment-2294481483

   This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the dev@lucene.apache.org list. Thank you for your contribution!


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Optimize binary search call [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #13595:
URL: https://github.com/apache/lucene/pull/13595#issuecomment-2260043321

   This makes sense to me. Maybe we should go one step further and perform an exponential search instead, e.g. by reusing `IntArrayDocIdSetIterator`.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Optimize binary search call [lucene]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #13595:
URL: https://github.com/apache/lucene/pull/13595#issuecomment-2566031064

   This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the dev@lucene.apache.org list. Thank you for your contribution!


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org