[ https://issues.apache.org/jira/browse/LUCENE-8796?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16835629#comment-16835629 ]
Atri Sharma commented on LUCENE-8796: ------------------------------------- bq. We could potentially reduce the number of comparisons (at average) using the property that binary search uses same number of comparisons to search for a value in 2^n and 2^n+1 -1. Could we adjust the lower bound of search space based on that? Something like: {code:java} int lowerBound = 0; while(bound < length && docs[bound] < target) { lowerBound += bound; bound = std::min((bound + 1) * 2 - 1, length); } i = Arrays.binarySearch(docs, lowerBound, (lowerBound + Math.min(bound, length)), target); {code} This might be wrong (I have not run a bunch of tests), but gives the general idea. > 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 > > 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