You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Michael McCandless (JIRA)" <ji...@apache.org> on 2009/11/01 12:08:59 UTC
[jira] Commented: (LUCENE-1997) Explore performance of multi-PQ vs
single-PQ sorting API
[ https://issues.apache.org/jira/browse/LUCENE-1997?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12772309#action_12772309 ]
Michael McCandless commented on LUCENE-1997:
--------------------------------------------
The number of insertions into the queue is miniscule for these tests.
EG with topN=10, the query "1" against the 5M wikipedia index, causes
110 insertions.
Even at topN=1000 we see only 8053 insertions.
So, the time difference of these runs is really driven by the "compare
to bottom" check that's done for every hit.
What baffles me is even if I take the inline-single-PQ from the last
patch, and instead of invoking a separate class's
"IntDocValues.intValue(doc)" I look it up straight from the int[] I
get from FieldCache, I'm still seeing worse performance vs trunk.
I think at this point this test is chasing java ghosts, so, we really
can't conclude much.
Also, I think, if you are sorting by native value per doc, likely the
fastest way to take "bottom" into account is to push the check all the
way down into the bottom TermScorers that're pulling docIDs from the
posting lists. Ie, if your queue has converged, and you know a given
doc must have value < 7 (say) to get into the queue, you can check
each doc's value immediately on pulling it from the posting list and
skip it if it won't compete (and, if you don't require exact total
hits count).
For queries that are otherwise costly, this can save alot of CPU.
This is what the source code specialization (LUCENE-1594) does, and it
results in excellent gains (if I'm remembering right!).
> Explore performance of multi-PQ vs single-PQ sorting API
> --------------------------------------------------------
>
> Key: LUCENE-1997
> URL: https://issues.apache.org/jira/browse/LUCENE-1997
> Project: Lucene - Java
> Issue Type: Improvement
> Components: Search
> Affects Versions: 2.9
> Reporter: Michael McCandless
> Assignee: Michael McCandless
> Attachments: LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch
>
>
> Spinoff from recent "lucene 2.9 sorting algorithm" thread on java-dev,
> where a simpler (non-segment-based) comparator API is proposed that
> gathers results into multiple PQs (one per segment) and then merges
> them in the end.
> I started from John's multi-PQ code and worked it into
> contrib/benchmark so that we could run perf tests. Then I generified
> the Python script I use for running search benchmarks (in
> contrib/benchmark/sortBench.py).
> The script first creates indexes with 1M docs (based on
> SortableSingleDocSource, and based on wikipedia, if available). Then
> it runs various combinations:
> * Index with 20 balanced segments vs index with the "normal" log
> segment size
> * Queries with different numbers of hits (only for wikipedia index)
> * Different top N
> * Different sorts (by title, for wikipedia, and by random string,
> random int, and country for the random index)
> For each test, 7 search rounds are run and the best QPS is kept. The
> script runs singlePQ then multiPQ, and records the resulting best QPS
> for each and produces table (in Jira format) as output.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: [jira] Commented: (LUCENE-1997) Explore performance of multi-PQ
vs single-PQ sorting API
Posted by Mark Miller <ma...@gmail.com>.
Yeah, this is what I saw when profiling a week or two ago. Pretty much
everything was the same - the only diff I can remember was that the
collect method bubbled up slightly different (though ended up roughly
the same), and for the single queue, after the collect method bubbled
up, the compare bottom method quickly bubbled up to 2% at the end. No
other method of interest appeared to be involved and everything else
looked relatively the same.
Michael McCandless (JIRA) wrote:
> [ https://issues.apache.org/jira/browse/LUCENE-1997?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12772309#action_12772309 ]
>
> Michael McCandless commented on LUCENE-1997:
> --------------------------------------------
>
> The number of insertions into the queue is miniscule for these tests.
> EG with topN=10, the query "1" against the 5M wikipedia index, causes
> 110 insertions.
>
> Even at topN=1000 we see only 8053 insertions.
>
> So, the time difference of these runs is really driven by the "compare
> to bottom" check that's done for every hit.
>
> What baffles me is even if I take the inline-single-PQ from the last
> patch, and instead of invoking a separate class's
> "IntDocValues.intValue(doc)" I look it up straight from the int[] I
> get from FieldCache, I'm still seeing worse performance vs trunk.
>
> I think at this point this test is chasing java ghosts, so, we really
> can't conclude much.
>
> Also, I think, if you are sorting by native value per doc, likely the
> fastest way to take "bottom" into account is to push the check all the
> way down into the bottom TermScorers that're pulling docIDs from the
> posting lists. Ie, if your queue has converged, and you know a given
> doc must have value < 7 (say) to get into the queue, you can check
> each doc's value immediately on pulling it from the posting list and
> skip it if it won't compete (and, if you don't require exact total
> hits count).
>
> For queries that are otherwise costly, this can save alot of CPU.
> This is what the source code specialization (LUCENE-1594) does, and it
> results in excellent gains (if I'm remembering right!).
>
>
>
>> Explore performance of multi-PQ vs single-PQ sorting API
>> --------------------------------------------------------
>>
>> Key: LUCENE-1997
>> URL: https://issues.apache.org/jira/browse/LUCENE-1997
>> Project: Lucene - Java
>> Issue Type: Improvement
>> Components: Search
>> Affects Versions: 2.9
>> Reporter: Michael McCandless
>> Assignee: Michael McCandless
>> Attachments: LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch, LUCENE-1997.patch
>>
>>
>> Spinoff from recent "lucene 2.9 sorting algorithm" thread on java-dev,
>> where a simpler (non-segment-based) comparator API is proposed that
>> gathers results into multiple PQs (one per segment) and then merges
>> them in the end.
>> I started from John's multi-PQ code and worked it into
>> contrib/benchmark so that we could run perf tests. Then I generified
>> the Python script I use for running search benchmarks (in
>> contrib/benchmark/sortBench.py).
>> The script first creates indexes with 1M docs (based on
>> SortableSingleDocSource, and based on wikipedia, if available). Then
>> it runs various combinations:
>> * Index with 20 balanced segments vs index with the "normal" log
>> segment size
>> * Queries with different numbers of hits (only for wikipedia index)
>> * Different top N
>> * Different sorts (by title, for wikipedia, and by random string,
>> random int, and country for the random index)
>> For each test, 7 search rounds are run and the best QPS is kept. The
>> script runs singlePQ then multiPQ, and records the resulting best QPS
>> for each and produces table (in Jira format) as output.
>>
>
>
--
- Mark
http://www.lucidimagination.com
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org