Lucene - Core
  1. Lucene - Core
  2. LUCENE-5856

remove useless & 0x3f from *BitSet.get and company

    Details

    • Type: Improvement Improvement
    • Status: Resolved
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 4.10, 6.0
    • Component/s: None
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      java specification says:

      If the promoted type of the left-hand operand is long, then only the six lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x3f (0b111111). The shift distance actually used is therefore always in the range 0 to 63, inclusive.

      and x86 works the same way.

      if we remove this, we just see less instructions with printassembly...

        Activity

        Hide
        Robert Muir added a comment -

        simple patch.

        i tried to figure out a way to benchmark, so i used matchalldocs+filters of different densities (and forced fixedbitset).

        Gives me numbers like:

                            Task   QPS trunk      StdDev   QPS patch      StdDev                Pct diff
                           F50.0       14.76      (1.2%)       15.67      (0.1%)    6.1% (   4% -    7%)
                          F100.0       20.28      (2.4%)       21.61      (0.0%)    6.6% (   3% -    9%)
                           F99.0       20.05      (2.4%)       21.40      (0.1%)    6.7% (   4% -    9%)
                           F95.0       19.21      (2.2%)       20.54      (0.2%)    6.9% (   4% -    9%)
                           F90.0       18.40      (2.1%)       19.71      (0.3%)    7.1% (   4% -    9%)
                           F75.0       16.39      (1.5%)       17.60      (0.6%)    7.4% (   5% -    9%)
                           F20.0       27.04      (1.0%)       29.09      (0.1%)    7.6% (   6% -    8%)
                           F10.0       42.09      (1.0%)       46.16      (0.5%)    9.7% (   8% -   11%)
                            F5.0       56.77      (0.8%)       64.46      (0.6%)   13.6% (  12% -   15%)
                            F2.0       70.43      (0.5%)       83.48      (0.7%)   18.5% (  17% -   19%)
                            F1.0       76.42      (0.3%)       92.60      (0.7%)   21.2% (  20% -   22%)
                            F0.5       80.01      (0.2%)       98.15      (0.6%)   22.7% (  21% -   23%)
        

        I suppose F0.5 looks the best, because it has less noise from priority queue checks and other things going on.

        Show
        Robert Muir added a comment - simple patch. i tried to figure out a way to benchmark, so i used matchalldocs+filters of different densities (and forced fixedbitset). Gives me numbers like: Task QPS trunk StdDev QPS patch StdDev Pct diff F50.0 14.76 (1.2%) 15.67 (0.1%) 6.1% ( 4% - 7%) F100.0 20.28 (2.4%) 21.61 (0.0%) 6.6% ( 3% - 9%) F99.0 20.05 (2.4%) 21.40 (0.1%) 6.7% ( 4% - 9%) F95.0 19.21 (2.2%) 20.54 (0.2%) 6.9% ( 4% - 9%) F90.0 18.40 (2.1%) 19.71 (0.3%) 7.1% ( 4% - 9%) F75.0 16.39 (1.5%) 17.60 (0.6%) 7.4% ( 5% - 9%) F20.0 27.04 (1.0%) 29.09 (0.1%) 7.6% ( 6% - 8%) F10.0 42.09 (1.0%) 46.16 (0.5%) 9.7% ( 8% - 11%) F5.0 56.77 (0.8%) 64.46 (0.6%) 13.6% ( 12% - 15%) F2.0 70.43 (0.5%) 83.48 (0.7%) 18.5% ( 17% - 19%) F1.0 76.42 (0.3%) 92.60 (0.7%) 21.2% ( 20% - 22%) F0.5 80.01 (0.2%) 98.15 (0.6%) 22.7% ( 21% - 23%) I suppose F0.5 looks the best, because it has less noise from priority queue checks and other things going on.
        Hide
        Michael McCandless added a comment -

        +1, nice!

        Show
        Michael McCandless added a comment - +1, nice!
        Hide
        Adrien Grand added a comment -

        +1!

        Show
        Adrien Grand added a comment - +1!
        Hide
        Ryan Ernst added a comment -

        +1

        Show
        Ryan Ernst added a comment - +1
        Hide
        ASF subversion and git services added a comment -

        Commit 1614787 from Robert Muir in branch 'dev/trunk'
        [ https://svn.apache.org/r1614787 ]

        LUCENE-5856: Optimize Fixed/Open/LongBitSet to remove unnecessary AND

        Show
        ASF subversion and git services added a comment - Commit 1614787 from Robert Muir in branch 'dev/trunk' [ https://svn.apache.org/r1614787 ] LUCENE-5856 : Optimize Fixed/Open/LongBitSet to remove unnecessary AND
        Hide
        ASF subversion and git services added a comment -

        Commit 1614790 from Robert Muir in branch 'dev/branches/branch_4x'
        [ https://svn.apache.org/r1614790 ]

        LUCENE-5856: Optimize Fixed/Open/LongBitSet to remove unnecessary AND

        Show
        ASF subversion and git services added a comment - Commit 1614790 from Robert Muir in branch 'dev/branches/branch_4x' [ https://svn.apache.org/r1614790 ] LUCENE-5856 : Optimize Fixed/Open/LongBitSet to remove unnecessary AND
        Hide
        Uwe Schindler added a comment -

        Thanks, cool! Reading the JVM spec is sometimes useful. It is interesting why Hotspot oitsself does not remove the & in our code during optimization.

        Show
        Uwe Schindler added a comment - Thanks, cool! Reading the JVM spec is sometimes useful. It is interesting why Hotspot oitsself does not remove the & in our code during optimization.
        Hide
        Yonik Seeley added a comment -

        It is interesting why Hotspot oitsself does not remove the & in our code during optimization.

        Indeed. I just tested if I should make the corresponding changes in heliosearch's native code, but both gcc and llvm(clang) did this optimization with -O or above. That's good since C/C++ standards leave shifting by an amount outside 0..63 as undefined.

        Show
        Yonik Seeley added a comment - It is interesting why Hotspot oitsself does not remove the & in our code during optimization. Indeed. I just tested if I should make the corresponding changes in heliosearch's native code, but both gcc and llvm(clang) did this optimization with -O or above. That's good since C/C++ standards leave shifting by an amount outside 0..63 as undefined.

          People

          • Assignee:
            Unassigned
            Reporter:
            Robert Muir
          • Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development