On Thu, Oct 15, 2009 at 5:59 PM, Jake Mannix <jake.man...@gmail.com> wrote:
>> I don't think we do any branch tuning on the PQ insertion -- the ifs >> involved in re-heapifying the PQ are simply hard for the CPU to >> predict (though, apparently, not as hard as comparing strings ;). > > But it does look like you do some nice short-circuting where you compare > to bottom instead of doing the naive insertWithOverflow() and check the > result, which is cool. Right, every little bit helps :) >> > The single-PQ approach requires only O(K * log(K) * log(M)) >> > insertions, but each one requires, instead of O(log(K)) int compares, >> > O(log(K)) *string* compares, and a segment conversion. >> >> Right, except, for a large segment, if it has enough insertions, as >> more entries in the PQ belong to that segment, more of the comparisons >> become ints. > > Assuming you're processing the larger segments first, as Yonik said > was done, then this won't typically help very much, right? If the > second segment is much smaller than the first, then not as many > replacements will happen, leaving the majority of the PQ having > entries from the previous segment. Additionally - as you move to further > and further segments, whether they are the same size or smaller than > previous, the bottom element of the PQ is getting better and better, and > so you're chances of actually filling up even a significant minority of it > with entries from the current segment is very small. True, though as the segments get smaller, and the PQ "converges", there is less insertion being done anyway. So the first few insertions are costly (all string comparisons), but as more insertions go in, more of the comparisons become ints. >> Looking back through LUCENE-1483, we were seeing much more sizable >> gains in the new API vs the old single-PQ-only-int-comparison approach >> (which should be faster than both the single and multi PQ approaches >> we are discussing here). BUT: those tests combined searching by >> segment AND the new FieldCollector API, plus other more basic code >> speedups. Though it'd be odd if the switch to searching by segment >> really was most of the gains here. I'm confused (for now) on where >> the gains we were seeing in that issue came from... > > You don't give yourself enough credit here: it could certainly that the > perf improvement was from more basic code-level speedups, as we're > only dealing with the sub-leading behavior here, and the constants > look like they most certainly matter! Well let's get to the bottom of it, and if the simpler API is indeed faster across the board, we should switch back. Mike --------------------------------------------------------------------- To unsubscribe, e-mail: java-dev-unsubscr...@lucene.apache.org For additional commands, e-mail: java-dev-h...@lucene.apache.org
