lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael McCandless (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (LUCENE-7905) Optimizations for OrdinalMap
Date Wed, 12 Jul 2017 16:43:00 GMT

    [ https://issues.apache.org/jira/browse/LUCENE-7905?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16084281#comment-16084281
] 

Michael McCandless commented on LUCENE-7905:
--------------------------------------------

bq. Its a bit tricky to see the diffs since the file got moved too, but basically it just
replaces MultiTermsEnum with a standard PQ?

That's it, except I also changed:

{noformat}
          while (segmentOrds[segmentIndex] <= segmentOrd) {
            ordDeltaBits[segmentIndex] |= delta;
            ordDeltas[segmentIndex].add(delta);
            segmentOrds[segmentIndex]++;
          }
{noformat}

to:

{noformat}
        assert segmentOrds[segmentIndex] <= segmentOrd;
        do {
          ordDeltas[segmentIndex].add(delta);
          segmentOrds[segmentIndex]++;
        } while (segmentOrds[segmentIndex] <= segmentOrd);
{noformat}

Which should make the branch easier to predict (since the loop will always run the first time),
but maybe the effect is negligible.

I think likely the cost we're saving from MTE is its {{TermMergeQueue.fillTop}} method?  It's
doing a lot of work, sort of recursing into the PQ, with a if inside a for inside a while,
to find all subs on the current term, and then it has to do {{pushTop}} after that.  In general
MTE is not allowed to .next() the subs because it doesn't know if the caller will ask for
postings on this term.  [~rcmuir] suggested we could maybe make pullTop()/pushTop() lazy which
is a neat idea...

> Optimizations for OrdinalMap
> ----------------------------
>
>                 Key: LUCENE-7905
>                 URL: https://issues.apache.org/jira/browse/LUCENE-7905
>             Project: Lucene - Core
>          Issue Type: Improvement
>            Reporter: Michael McCandless
>            Assignee: Michael McCandless
>             Fix For: 7.1
>
>         Attachments: LUCENE-7905.patch
>
>
> {{OrdinalMap}} is a useful class to quickly map per-segment ordinals to global space,
but it's fairly costly to build, which must typically be done on every NRT refresh.
> I'm using it quite heavily in two different places, one for {{SortedSetDocValuesFacetCounts}},
and another custom usage, and I found some small optimizations to improve its construction
time.
> I switched it to use a simple priority queue to merge the terms instead of the more general
{{MultiTermsEnum}}, which does extra work since it must also provide postings, implement seekExact,
etc.
> I also pulled {{OrdinalMap}} out into its own oal.index class.
> When testing construction time for my case the patch is ~16% faster (159.9s -> 134.2s)
in one case with 91.4 M terms and ~9% faster (115.6s -> 105.7s) in another case with 26.6
M terms.



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

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


Mime
View raw message