Lucene - Core
  1. Lucene - Core
  2. LUCENE-6878

TopDocs.merge should use updateTop instead of pop / add

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Trivial Trivial
    • Resolution: Fixed
    • Affects Version/s: 6.0
    • Fix Version/s: 5.4, 6.0
    • Component/s: core/search
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      The function TopDocs.merge uses PriorityQueue in a pattern: pop, update value (ref.hitIndex++), add. JavaDocs for PriorityQueue.updateTop say that using this function instead should be at least twice as fast.

      1. LUCENE-6878.patch
        0.9 kB
        Daniel Jelinski
      2. speedtest.tar.gz
        1 kB
        Daniel Jelinski

        Activity

        Hide
        Michael McCandless added a comment -

        +1

        I know we are discussing how to benchmark this change but I don't think that's needed before committing ... this is a good change ... it's only needed to satisfy curiosity

        Show
        Michael McCandless added a comment - +1 I know we are discussing how to benchmark this change but I don't think that's needed before committing ... this is a good change ... it's only needed to satisfy curiosity
        Hide
        Toke Eskildsen added a comment -

        In light of my own recent experiments with PriorityQueue (SOLR-6828), I'll note that microbenchmarks are exceedingly simple to screw up, especially in Java. I ended up doing comparative testing with pre-generated test inputs, multiple runs, discarding the first runs, alternating between the implementation multiple times and removing outliers. And the results are still not very stable.

        Show
        Toke Eskildsen added a comment - In light of my own recent experiments with PriorityQueue ( SOLR-6828 ), I'll note that microbenchmarks are exceedingly simple to screw up, especially in Java. I ended up doing comparative testing with pre-generated test inputs, multiple runs, discarding the first runs, alternating between the implementation multiple times and removing outliers. And the results are still not very stable.
        Hide
        ASF subversion and git services added a comment -

        Commit 1712298 from Adrien Grand in branch 'dev/trunk'
        [ https://svn.apache.org/r1712298 ]

        LUCENE-6878: Speed up TopDocs.merge.

        Show
        ASF subversion and git services added a comment - Commit 1712298 from Adrien Grand in branch 'dev/trunk' [ https://svn.apache.org/r1712298 ] LUCENE-6878 : Speed up TopDocs.merge.
        Hide
        ASF subversion and git services added a comment -

        Commit 1712299 from Adrien Grand in branch 'dev/branches/branch_5x'
        [ https://svn.apache.org/r1712299 ]

        LUCENE-6878: Speed up TopDocs.merge.

        Show
        ASF subversion and git services added a comment - Commit 1712299 from Adrien Grand in branch 'dev/branches/branch_5x' [ https://svn.apache.org/r1712299 ] LUCENE-6878 : Speed up TopDocs.merge.
        Hide
        Adrien Grand added a comment -

        I know we are discussing how to benchmark this change but I don't think that's needed before committing

        Agreed, I just committed the change.

        Daniel: I am marking the issue resolved since it was committed, but feel free to comment on it about your findings about potential performance improvements.

        Show
        Adrien Grand added a comment - I know we are discussing how to benchmark this change but I don't think that's needed before committing Agreed, I just committed the change. Daniel: I am marking the issue resolved since it was committed, but feel free to comment on it about your findings about potential performance improvements.
        Hide
        Daniel Jelinski added a comment -

        I merged 64 ScoreDoc lists, 100k docs each, and took top 100k results, in 3 different score distributions. For time calculations, each test was repeated 60 times, and I averaged the results of 10 subsequent runs, discarding any outliers. For the number of lessThan calls in random case, I run the test 3 times and took an average. The number of lessThan calls for case 1 and 2 is constant.
        I tested score lists generated using 3 different methods.
        1) All scores equal to 1. This is the case where the patch made a greatest difference, mostly because of tie breaks in lessThan methods. Results:
        Without the patch - 2.66 msec per merge call, 1600057 calls to lessThan
        With the patch - 0.32 msec per merge call, 200071 calls to lessThan.
        Overall, ~88% savings on time and lessThan calls
        2) Each list contains scores 100000,99999,....,1
        Without the patch - 3.5 msec per merge call, 1100063 calls to lessThan
        With the patch - 2.6 msec per merge call, 1005390 calls to lessThan
        Overall, ~25% savings on time, 9% savings on lessThan calls
        3) Each list starts with doc with score 100000, score of other docs is calculated as score of previous doc minus Math.random()
        Without the patch - 3.5 msec per merge call, ~1156500 calls to lessThan
        With the patch, 2.7 msec per merge call, ~960500 calls to lessThan
        Overall, ~23% savings on time, 17% savings on lessThan calls.

        In the random case the gain is much less than the advertised double speed, but it's still a net improvement.
        I attached the code I used to measure the speed, in case anyone is interested. Fair warning, it's not pretty.

        Show
        Daniel Jelinski added a comment - I merged 64 ScoreDoc lists, 100k docs each, and took top 100k results, in 3 different score distributions. For time calculations, each test was repeated 60 times, and I averaged the results of 10 subsequent runs, discarding any outliers. For the number of lessThan calls in random case, I run the test 3 times and took an average. The number of lessThan calls for case 1 and 2 is constant. I tested score lists generated using 3 different methods. 1) All scores equal to 1. This is the case where the patch made a greatest difference, mostly because of tie breaks in lessThan methods. Results: Without the patch - 2.66 msec per merge call, 1600057 calls to lessThan With the patch - 0.32 msec per merge call, 200071 calls to lessThan. Overall, ~88% savings on time and lessThan calls 2) Each list contains scores 100000,99999,....,1 Without the patch - 3.5 msec per merge call, 1100063 calls to lessThan With the patch - 2.6 msec per merge call, 1005390 calls to lessThan Overall, ~25% savings on time, 9% savings on lessThan calls 3) Each list starts with doc with score 100000, score of other docs is calculated as score of previous doc minus Math.random() Without the patch - 3.5 msec per merge call, ~1156500 calls to lessThan With the patch, 2.7 msec per merge call, ~960500 calls to lessThan Overall, ~23% savings on time, 17% savings on lessThan calls. In the random case the gain is much less than the advertised double speed, but it's still a net improvement. I attached the code I used to measure the speed, in case anyone is interested. Fair warning, it's not pretty.
        Hide
        Adrien Grand added a comment -

        These results make sense to me given the change. Thank you Daniel!

        Show
        Adrien Grand added a comment - These results make sense to me given the change. Thank you Daniel!

          People

          • Assignee:
            Adrien Grand
            Reporter:
            Daniel Jelinski
          • Votes:
            0 Vote for this issue
            Watchers:
            6 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development