[ https://issues.apache.org/jira/browse/LUCENE-8796?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16855534#comment-16855534 ]
Adrien Grand commented on LUCENE-8796: -------------------------------------- Hmm it's disappointing it's not making things noticeably faster, but in the other hand your patch provides a better worst-case cost, in the case that advance is always called by very small intervals. If I'm not mistaken, this worst-case scenario runs in O(cost * log(cost)) today without your patch and O(cost) with your patch. > Use exponential search in IntArrayDocIdSet advance method > --------------------------------------------------------- > > Key: LUCENE-8796 > URL: https://issues.apache.org/jira/browse/LUCENE-8796 > Project: Lucene - Core > Issue Type: Improvement > Reporter: Luca Cavanna > Priority: Minor > Time Spent: 10m > Remaining Estimate: 0h > > Chatting with [~jpountz] , he suggested to improve IntArrayDocIdSet by making > its advance method use exponential search instead of binary search. This > should help performance of queries including conjunctions: given that > ConjunctionDISI uses leap frog, it advances through doc ids in small steps, > hence exponential search should be faster when advancing on average compared > to binary search. > -- This message was sent by Atlassian JIRA (v7.6.3#76005) --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org