lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jpou...@apache.org
Subject svn commit: r1411712 - in /lucene/dev/trunk/lucene: ./ core/src/java/org/apache/lucene/util/ core/src/test/org/apache/lucene/util/
Date Tue, 20 Nov 2012 15:59:41 GMT
Author: jpountz
Date: Tue Nov 20 15:59:39 2012
New Revision: 1411712

URL: http://svn.apache.org/viewvc?rev=1411712&view=rev
Log:
LUCENE-2221: Use JVM intrinsics instead of BitUtil.{ntz,pop}.

Removed:
    lucene/dev/trunk/lucene/core/src/test/org/apache/lucene/util/TestBitUtil.java
Modified:
    lucene/dev/trunk/lucene/CHANGES.txt
    lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/BitUtil.java
    lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java
    lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/OpenBitSet.java

Modified: lucene/dev/trunk/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/CHANGES.txt?rev=1411712&r1=1411711&r2=1411712&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/CHANGES.txt (original)
+++ lucene/dev/trunk/lucene/CHANGES.txt Tue Nov 20 15:59:39 2012
@@ -149,6 +149,11 @@ Bug Fixes
 
 Optimizations
 
+* LUCENE-2221: oal.util.BitUtil was modified to use Long.bitCount and
+  Long.numberOfTrailingZeros (which are intrinsics since Java 6u18) instead of
+  pure java bit twiddling routines in order to improve performance on modern
+  JVMs/hardware. (Dawid Weiss, Adrien Grand)
+
 * LUCENE-4509: Enable stored fields compression by default in the Lucene 4.1
   default codec. (Adrien Grand)
 

Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/BitUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/BitUtil.java?rev=1411712&r1=1411711&r2=1411712&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/BitUtil.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/BitUtil.java Tue Nov 20 15:59:39
2012
@@ -24,791 +24,57 @@ public final class BitUtil {
 
   private BitUtil() {} // no instance
 
-  /** Returns the number of bits set in the long */
-  public static int pop(long x) {
-  /* Hacker's Delight 32 bit pop function:
-   * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
-   *
-  int pop(unsigned x) {
-     x = x - ((x >> 1) & 0x55555555);
-     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
-     x = (x + (x >> 4)) & 0x0F0F0F0F;
-     x = x + (x >> 8);
-     x = x + (x >> 16);
-     return x & 0x0000003F;
+  // The pop methods used to rely on bit-manipulation tricks for speed but it
+  // turns out that it is faster to use the Long.bitCount method (which is an
+  // intrinsic since Java 6u18) in a naive loop, see LUCENE-2221
+
+  /** Returns the number of set bits in an array of longs. */
+  public static long pop_array(long[] arr, int wordOffset, int numWords) {
+    long popCount = 0;
+    for (int i = wordOffset, end = wordOffset + numWords; i < end; ++i) {
+      popCount += Long.bitCount(arr[i]);
     }
-  ***/
-
-    // 64 bit java version of the C function from above
-    x = x - ((x >>> 1) & 0x5555555555555555L);
-    x = (x & 0x3333333333333333L) + ((x >>>2 ) & 0x3333333333333333L);
-    x = (x + (x >>> 4)) & 0x0F0F0F0F0F0F0F0FL;
-    x = x + (x >>> 8);
-    x = x + (x >>> 16);
-    x = x + (x >>> 32);
-    return ((int)x) & 0x7F;
-  }
-
-  /*** Returns the number of set bits in an array of longs. */
-  public static long pop_array(long A[], int wordOffset, int numWords) {
-    /*
-    * Robert Harley and David Seal's bit counting algorithm, as documented
-    * in the revisions of Hacker's Delight
-    * http://www.hackersdelight.org/revisions.pdf
-    * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
-    *
-    * This function was adapted to Java, and extended to use 64 bit words.
-    * if only we had access to wider registers like SSE from java...
-    *
-    * This function can be transformed to compute the popcount of other functions
-    * on bitsets via something like this:
-    * sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
-    *
-    */
-    int n = wordOffset+numWords;
-    long tot=0, tot8=0;
-    long ones=0, twos=0, fours=0;
-
-    int i;
-    for (i = wordOffset; i <= n - 8; i+=8) {
-      /***  C macro from Hacker's Delight
-       #define CSA(h,l, a,b,c) \
-       {unsigned u = a ^ b; unsigned v = c; \
-       h = (a & b) | (u & v); l = u ^ v;}
-       ***/
-
-      long twosA,twosB,foursA,foursB,eights;
-
-      // CSA(twosA, ones, ones, A[i], A[i+1])
-      {
-        long b=A[i], c=A[i+1];
-        long u=ones ^ b;
-        twosA=(ones & b)|( u & c);
-        ones=u^c;
-      }
-      // CSA(twosB, ones, ones, A[i+2], A[i+3])
-      {
-        long b=A[i+2], c=A[i+3];
-        long u=ones^b;
-        twosB =(ones&b)|(u&c);
-        ones=u^c;
-      }
-      //CSA(foursA, twos, twos, twosA, twosB)
-      {
-        long u=twos^twosA;
-        foursA=(twos&twosA)|(u&twosB);
-        twos=u^twosB;
-      }
-      //CSA(twosA, ones, ones, A[i+4], A[i+5])
-      {
-        long b=A[i+4], c=A[i+5];
-        long u=ones^b;
-        twosA=(ones&b)|(u&c);
-        ones=u^c;
-      }
-      // CSA(twosB, ones, ones, A[i+6], A[i+7])
-      {
-        long b=A[i+6], c=A[i+7];
-        long u=ones^b;
-        twosB=(ones&b)|(u&c);
-        ones=u^c;
-      }
-      //CSA(foursB, twos, twos, twosA, twosB)
-      {
-        long u=twos^twosA;
-        foursB=(twos&twosA)|(u&twosB);
-        twos=u^twosB;
-      }
-
-      //CSA(eights, fours, fours, foursA, foursB)
-      {
-        long u=fours^foursA;
-        eights=(fours&foursA)|(u&foursB);
-        fours=u^foursB;
-      }
-      tot8 += pop(eights);
-    }
-
-    // handle trailing words in a binary-search manner...
-    // derived from the loop above by setting specific elements to 0.
-    // the original method in Hackers Delight used a simple for loop:
-    //   for (i = i; i < n; i++)      // Add in the last elements
-    //  tot = tot + pop(A[i]);
-
-    if (i<=n-4) {
-      long twosA, twosB, foursA, eights;
-      {
-        long b=A[i], c=A[i+1];
-        long u=ones ^ b;
-        twosA=(ones & b)|( u & c);
-        ones=u^c;
-      }
-      {
-        long b=A[i+2], c=A[i+3];
-        long u=ones^b;
-        twosB =(ones&b)|(u&c);
-        ones=u^c;
-      }
-      {
-        long u=twos^twosA;
-        foursA=(twos&twosA)|(u&twosB);
-        twos=u^twosB;
-      }
-      eights=fours&foursA;
-      fours=fours^foursA;
-
-      tot8 += pop(eights);
-      i+=4;
-    }
-
-    if (i<=n-2) {
-      long b=A[i], c=A[i+1];
-      long u=ones ^ b;
-      long twosA=(ones & b)|( u & c);
-      ones=u^c;
-
-      long foursA=twos&twosA;
-      twos=twos^twosA;
-
-      long eights=fours&foursA;
-      fours=fours^foursA;
-
-      tot8 += pop(eights);
-      i+=2;
-    }
-
-    if (i<n) {
-      tot += pop(A[i]);
-    }
-
-    tot += (pop(fours)<<2)
-            + (pop(twos)<<1)
-            + pop(ones)
-            + (tot8<<3);
-
-    return tot;
+    return popCount;
   }
 
   /** Returns the popcount or cardinality of the two sets after an intersection.
-   * Neither array is modified.
-   */
-  public static long pop_intersect(long A[], long B[], int wordOffset, int numWords) {
-    // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
-    int n = wordOffset+numWords;
-    long tot=0, tot8=0;
-    long ones=0, twos=0, fours=0;
-
-    int i;
-    for (i = wordOffset; i <= n - 8; i+=8) {
-      long twosA,twosB,foursA,foursB,eights;
-
-      // CSA(twosA, ones, ones, (A[i] & B[i]), (A[i+1] & B[i+1]))
-      {
-        long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
-        long u=ones ^ b;
-        twosA=(ones & b)|( u & c);
-        ones=u^c;
-      }
-      // CSA(twosB, ones, ones, (A[i+2] & B[i+2]), (A[i+3] & B[i+3]))
-      {
-        long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
-        long u=ones^b;
-        twosB =(ones&b)|(u&c);
-        ones=u^c;
-      }
-      //CSA(foursA, twos, twos, twosA, twosB)
-      {
-        long u=twos^twosA;
-        foursA=(twos&twosA)|(u&twosB);
-        twos=u^twosB;
-      }
-      //CSA(twosA, ones, ones, (A[i+4] & B[i+4]), (A[i+5] & B[i+5]))
-      {
-        long b=(A[i+4] & B[i+4]), c=(A[i+5] & B[i+5]);
-        long u=ones^b;
-        twosA=(ones&b)|(u&c);
-        ones=u^c;
-      }
-      // CSA(twosB, ones, ones, (A[i+6] & B[i+6]), (A[i+7] & B[i+7]))
-      {
-        long b=(A[i+6] & B[i+6]), c=(A[i+7] & B[i+7]);
-        long u=ones^b;
-        twosB=(ones&b)|(u&c);
-        ones=u^c;
-      }
-      //CSA(foursB, twos, twos, twosA, twosB)
-      {
-        long u=twos^twosA;
-        foursB=(twos&twosA)|(u&twosB);
-        twos=u^twosB;
-      }
-
-      //CSA(eights, fours, fours, foursA, foursB)
-      {
-        long u=fours^foursA;
-        eights=(fours&foursA)|(u&foursB);
-        fours=u^foursB;
-      }
-      tot8 += pop(eights);
-    }
-
-
-    if (i<=n-4) {
-      long twosA, twosB, foursA, eights;
-      {
-        long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
-        long u=ones ^ b;
-        twosA=(ones & b)|( u & c);
-        ones=u^c;
-      }
-      {
-        long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
-        long u=ones^b;
-        twosB =(ones&b)|(u&c);
-        ones=u^c;
-      }
-      {
-        long u=twos^twosA;
-        foursA=(twos&twosA)|(u&twosB);
-        twos=u^twosB;
-      }
-      eights=fours&foursA;
-      fours=fours^foursA;
-
-      tot8 += pop(eights);
-      i+=4;
-    }
-
-    if (i<=n-2) {
-      long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
-      long u=ones ^ b;
-      long twosA=(ones & b)|( u & c);
-      ones=u^c;
-
-      long foursA=twos&twosA;
-      twos=twos^twosA;
-
-      long eights=fours&foursA;
-      fours=fours^foursA;
-
-      tot8 += pop(eights);
-      i+=2;
-    }
-
-    if (i<n) {
-      tot += pop((A[i] & B[i]));
-    }
-
-    tot += (pop(fours)<<2)
-            + (pop(twos)<<1)
-            + pop(ones)
-            + (tot8<<3);
-
-    return tot;
+   *  Neither array is modified. */
+  public static long pop_intersect(long[] arr1, long[] arr2, int wordOffset, int numWords)
{
+    long popCount = 0;
+    for (int i = wordOffset, end = wordOffset + numWords; i < end; ++i) {
+      popCount += Long.bitCount(arr1[i] & arr2[i]);
+    }
+    return popCount;
   }
 
-  /** Returns the popcount or cardinality of the union of two sets.
-    * Neither array is modified.
-    */
-   public static long pop_union(long A[], long B[], int wordOffset, int numWords) {
-     // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \| B[\1]\)/g'
-     int n = wordOffset+numWords;
-     long tot=0, tot8=0;
-     long ones=0, twos=0, fours=0;
-
-     int i;
-     for (i = wordOffset; i <= n - 8; i+=8) {
-       /***  C macro from Hacker's Delight
-        #define CSA(h,l, a,b,c) \
-        {unsigned u = a ^ b; unsigned v = c; \
-        h = (a & b) | (u & v); l = u ^ v;}
-        ***/
-
-       long twosA,twosB,foursA,foursB,eights;
-
-       // CSA(twosA, ones, ones, (A[i] | B[i]), (A[i+1] | B[i+1]))
-       {
-         long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
-         long u=ones ^ b;
-         twosA=(ones & b)|( u & c);
-         ones=u^c;
-       }
-       // CSA(twosB, ones, ones, (A[i+2] | B[i+2]), (A[i+3] | B[i+3]))
-       {
-         long b=(A[i+2] | B[i+2]), c=(A[i+3] | B[i+3]);
-         long u=ones^b;
-         twosB =(ones&b)|(u&c);
-         ones=u^c;
-       }
-       //CSA(foursA, twos, twos, twosA, twosB)
-       {
-         long u=twos^twosA;
-         foursA=(twos&twosA)|(u&twosB);
-         twos=u^twosB;
-       }
-       //CSA(twosA, ones, ones, (A[i+4] | B[i+4]), (A[i+5] | B[i+5]))
-       {
-         long b=(A[i+4] | B[i+4]), c=(A[i+5] | B[i+5]);
-         long u=ones^b;
-         twosA=(ones&b)|(u&c);
-         ones=u^c;
-       }
-       // CSA(twosB, ones, ones, (A[i+6] | B[i+6]), (A[i+7] | B[i+7]))
-       {
-         long b=(A[i+6] | B[i+6]), c=(A[i+7] | B[i+7]);
-         long u=ones^b;
-         twosB=(ones&b)|(u&c);
-         ones=u^c;
-       }
-       //CSA(foursB, twos, twos, twosA, twosB)
-       {
-         long u=twos^twosA;
-         foursB=(twos&twosA)|(u&twosB);
-         twos=u^twosB;
-       }
-
-       //CSA(eights, fours, fours, foursA, foursB)
-       {
-         long u=fours^foursA;
-         eights=(fours&foursA)|(u&foursB);
-         fours=u^foursB;
-       }
-       tot8 += pop(eights);
+   /** Returns the popcount or cardinality of the union of two sets.
+    *  Neither array is modified. */
+   public static long pop_union(long[] arr1, long[] arr2, int wordOffset, int numWords) {
+     long popCount = 0;
+     for (int i = wordOffset, end = wordOffset + numWords; i < end; ++i) {
+       popCount += Long.bitCount(arr1[i] | arr2[i]);
      }
-
-
-     if (i<=n-4) {
-       long twosA, twosB, foursA, eights;
-       {
-         long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
-         long u=ones ^ b;
-         twosA=(ones & b)|( u & c);
-         ones=u^c;
-       }
-       {
-         long b=(A[i+2] | B[i+2]), c=(A[i+3] | B[i+3]);
-         long u=ones^b;
-         twosB =(ones&b)|(u&c);
-         ones=u^c;
-       }
-       {
-         long u=twos^twosA;
-         foursA=(twos&twosA)|(u&twosB);
-         twos=u^twosB;
-       }
-       eights=fours&foursA;
-       fours=fours^foursA;
-
-       tot8 += pop(eights);
-       i+=4;
-     }
-
-     if (i<=n-2) {
-       long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
-       long u=ones ^ b;
-       long twosA=(ones & b)|( u & c);
-       ones=u^c;
-
-       long foursA=twos&twosA;
-       twos=twos^twosA;
-
-       long eights=fours&foursA;
-       fours=fours^foursA;
-
-       tot8 += pop(eights);
-       i+=2;
-     }
-
-     if (i<n) {
-       tot += pop((A[i] | B[i]));
-     }
-
-     tot += (pop(fours)<<2)
-             + (pop(twos)<<1)
-             + pop(ones)
-             + (tot8<<3);
-
-     return tot;
+     return popCount;
    }
 
-  /** Returns the popcount or cardinality of A & ~B
-   * Neither array is modified.
-   */
-  public static long pop_andnot(long A[], long B[], int wordOffset, int numWords) {
-    // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& ~B[\1]\)/g'
-    int n = wordOffset+numWords;
-    long tot=0, tot8=0;
-    long ones=0, twos=0, fours=0;
-
-    int i;
-    for (i = wordOffset; i <= n - 8; i+=8) {
-      /***  C macro from Hacker's Delight
-       #define CSA(h,l, a,b,c) \
-       {unsigned u = a ^ b; unsigned v = c; \
-       h = (a & b) | (u & v); l = u ^ v;}
-       ***/
-
-      long twosA,twosB,foursA,foursB,eights;
-
-      // CSA(twosA, ones, ones, (A[i] & ~B[i]), (A[i+1] & ~B[i+1]))
-      {
-        long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
-        long u=ones ^ b;
-        twosA=(ones & b)|( u & c);
-        ones=u^c;
-      }
-      // CSA(twosB, ones, ones, (A[i+2] & ~B[i+2]), (A[i+3] & ~B[i+3]))
-      {
-        long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
-        long u=ones^b;
-        twosB =(ones&b)|(u&c);
-        ones=u^c;
-      }
-      //CSA(foursA, twos, twos, twosA, twosB)
-      {
-        long u=twos^twosA;
-        foursA=(twos&twosA)|(u&twosB);
-        twos=u^twosB;
-      }
-      //CSA(twosA, ones, ones, (A[i+4] & ~B[i+4]), (A[i+5] & ~B[i+5]))
-      {
-        long b=(A[i+4] & ~B[i+4]), c=(A[i+5] & ~B[i+5]);
-        long u=ones^b;
-        twosA=(ones&b)|(u&c);
-        ones=u^c;
-      }
-      // CSA(twosB, ones, ones, (A[i+6] & ~B[i+6]), (A[i+7] & ~B[i+7]))
-      {
-        long b=(A[i+6] & ~B[i+6]), c=(A[i+7] & ~B[i+7]);
-        long u=ones^b;
-        twosB=(ones&b)|(u&c);
-        ones=u^c;
-      }
-      //CSA(foursB, twos, twos, twosA, twosB)
-      {
-        long u=twos^twosA;
-        foursB=(twos&twosA)|(u&twosB);
-        twos=u^twosB;
-      }
-
-      //CSA(eights, fours, fours, foursA, foursB)
-      {
-        long u=fours^foursA;
-        eights=(fours&foursA)|(u&foursB);
-        fours=u^foursB;
-      }
-      tot8 += pop(eights);
-    }
-
-
-    if (i<=n-4) {
-      long twosA, twosB, foursA, eights;
-      {
-        long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
-        long u=ones ^ b;
-        twosA=(ones & b)|( u & c);
-        ones=u^c;
-      }
-      {
-        long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
-        long u=ones^b;
-        twosB =(ones&b)|(u&c);
-        ones=u^c;
-      }
-      {
-        long u=twos^twosA;
-        foursA=(twos&twosA)|(u&twosB);
-        twos=u^twosB;
-      }
-      eights=fours&foursA;
-      fours=fours^foursA;
-
-      tot8 += pop(eights);
-      i+=4;
+  /** Returns the popcount or cardinality of A & ~B.
+   *  Neither array is modified. */
+  public static long pop_andnot(long[] arr1, long[] arr2, int wordOffset, int numWords) {
+    long popCount = 0;
+    for (int i = wordOffset, end = wordOffset + numWords; i < end; ++i) {
+      popCount += Long.bitCount(arr1[i] & ~arr2[i]);
+    }
+    return popCount;
+  }
+
+  /** Returns the popcount or cardinality of A ^ B
+    * Neither array is modified. */
+  public static long pop_xor(long[] arr1, long[] arr2, int wordOffset, int numWords) {
+    long popCount = 0;
+    for (int i = wordOffset, end = wordOffset + numWords; i < end; ++i) {
+      popCount += Long.bitCount(arr1[i] ^ arr2[i]);
     }
-
-    if (i<=n-2) {
-      long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
-      long u=ones ^ b;
-      long twosA=(ones & b)|( u & c);
-      ones=u^c;
-
-      long foursA=twos&twosA;
-      twos=twos^twosA;
-
-      long eights=fours&foursA;
-      fours=fours^foursA;
-
-      tot8 += pop(eights);
-      i+=2;
-    }
-
-    if (i<n) {
-      tot += pop((A[i] & ~B[i]));
-    }
-
-    tot += (pop(fours)<<2)
-            + (pop(twos)<<1)
-            + pop(ones)
-            + (tot8<<3);
-
-    return tot;
-  }
-
-  public static long pop_xor(long A[], long B[], int wordOffset, int numWords) {
-    int n = wordOffset+numWords;
-    long tot=0, tot8=0;
-    long ones=0, twos=0, fours=0;
-
-    int i;
-    for (i = wordOffset; i <= n - 8; i+=8) {
-      /***  C macro from Hacker's Delight
-       #define CSA(h,l, a,b,c) \
-       {unsigned u = a ^ b; unsigned v = c; \
-       h = (a & b) | (u & v); l = u ^ v;}
-       ***/
-
-      long twosA,twosB,foursA,foursB,eights;
-
-      // CSA(twosA, ones, ones, (A[i] ^ B[i]), (A[i+1] ^ B[i+1]))
-      {
-        long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
-        long u=ones ^ b;
-        twosA=(ones & b)|( u & c);
-        ones=u^c;
-      }
-      // CSA(twosB, ones, ones, (A[i+2] ^ B[i+2]), (A[i+3] ^ B[i+3]))
-      {
-        long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
-        long u=ones^b;
-        twosB =(ones&b)|(u&c);
-        ones=u^c;
-      }
-      //CSA(foursA, twos, twos, twosA, twosB)
-      {
-        long u=twos^twosA;
-        foursA=(twos&twosA)|(u&twosB);
-        twos=u^twosB;
-      }
-      //CSA(twosA, ones, ones, (A[i+4] ^ B[i+4]), (A[i+5] ^ B[i+5]))
-      {
-        long b=(A[i+4] ^ B[i+4]), c=(A[i+5] ^ B[i+5]);
-        long u=ones^b;
-        twosA=(ones&b)|(u&c);
-        ones=u^c;
-      }
-      // CSA(twosB, ones, ones, (A[i+6] ^ B[i+6]), (A[i+7] ^ B[i+7]))
-      {
-        long b=(A[i+6] ^ B[i+6]), c=(A[i+7] ^ B[i+7]);
-        long u=ones^b;
-        twosB=(ones&b)|(u&c);
-        ones=u^c;
-      }
-      //CSA(foursB, twos, twos, twosA, twosB)
-      {
-        long u=twos^twosA;
-        foursB=(twos&twosA)|(u&twosB);
-        twos=u^twosB;
-      }
-
-      //CSA(eights, fours, fours, foursA, foursB)
-      {
-        long u=fours^foursA;
-        eights=(fours&foursA)|(u&foursB);
-        fours=u^foursB;
-      }
-      tot8 += pop(eights);
-    }
-
-
-    if (i<=n-4) {
-      long twosA, twosB, foursA, eights;
-      {
-        long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
-        long u=ones ^ b;
-        twosA=(ones & b)|( u & c);
-        ones=u^c;
-      }
-      {
-        long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
-        long u=ones^b;
-        twosB =(ones&b)|(u&c);
-        ones=u^c;
-      }
-      {
-        long u=twos^twosA;
-        foursA=(twos&twosA)|(u&twosB);
-        twos=u^twosB;
-      }
-      eights=fours&foursA;
-      fours=fours^foursA;
-
-      tot8 += pop(eights);
-      i+=4;
-    }
-
-    if (i<=n-2) {
-      long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
-      long u=ones ^ b;
-      long twosA=(ones & b)|( u & c);
-      ones=u^c;
-
-      long foursA=twos&twosA;
-      twos=twos^twosA;
-
-      long eights=fours&foursA;
-      fours=fours^foursA;
-
-      tot8 += pop(eights);
-      i+=2;
-    }
-
-    if (i<n) {
-      tot += pop((A[i] ^ B[i]));
-    }
-
-    tot += (pop(fours)<<2)
-            + (pop(twos)<<1)
-            + pop(ones)
-            + (tot8<<3);
-
-    return tot;
-  }
-
-  /* python code to generate ntzTable
-  def ntz(val):
-    if val==0: return 8
-    i=0
-    while (val&0x01)==0:
-      i = i+1
-      val >>= 1
-    return i
-  print ','.join([ str(ntz(i)) for i in range(256) ])
-  ***/
-  /** table of number of trailing zeros in a byte */
-  public static final byte[] ntzTable = {8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0};
-
-
-  /** Returns number of trailing zeros in a 64 bit long value. */
-  public static int ntz(long val) {
-    // A full binary search to determine the low byte was slower than
-    // a linear search for nextSetBit().  This is most likely because
-    // the implementation of nextSetBit() shifts bits to the right, increasing
-    // the probability that the first non-zero byte is in the rhs.
-    //
-    // This implementation does a single binary search at the top level only
-    // so that all other bit shifting can be done on ints instead of longs to
-    // remain friendly to 32 bit architectures.  In addition, the case of a
-    // non-zero first byte is checked for first because it is the most common
-    // in dense bit arrays.
-
-    int lower = (int)val;
-    int lowByte = lower & 0xff;
-    if (lowByte != 0) return ntzTable[lowByte];
-
-    if (lower!=0) {
-      lowByte = (lower>>>8) & 0xff;
-      if (lowByte != 0) return ntzTable[lowByte] + 8;
-      lowByte = (lower>>>16) & 0xff;
-      if (lowByte != 0) return ntzTable[lowByte] + 16;
-      // no need to mask off low byte for the last byte in the 32 bit word
-      // no need to check for zero on the last byte either.
-      return ntzTable[lower>>>24] + 24;
-    } else {
-      // grab upper 32 bits
-      int upper=(int)(val>>32);
-      lowByte = upper & 0xff;
-      if (lowByte != 0) return ntzTable[lowByte] + 32;
-      lowByte = (upper>>>8) & 0xff;
-      if (lowByte != 0) return ntzTable[lowByte] + 40;
-      lowByte = (upper>>>16) & 0xff;
-      if (lowByte != 0) return ntzTable[lowByte] + 48;
-      // no need to mask off low byte for the last byte in the 32 bit word
-      // no need to check for zero on the last byte either.
-      return ntzTable[upper>>>24] + 56;
-    }
-  }
-
-  /** Returns number of trailing zeros in a 32 bit int value. */
-  public static int ntz(int val) {
-    // This implementation does a single binary search at the top level only.
-    // In addition, the case of a non-zero first byte is checked for first
-    // because it is the most common in dense bit arrays.
-
-    int lowByte = val & 0xff;
-    if (lowByte != 0) return ntzTable[lowByte];
-    lowByte = (val>>>8) & 0xff;
-    if (lowByte != 0) return ntzTable[lowByte] + 8;
-    lowByte = (val>>>16) & 0xff;
-    if (lowByte != 0) return ntzTable[lowByte] + 16;
-    // no need to mask off low byte for the last byte.
-    // no need to check for zero on the last byte either.
-    return ntzTable[val>>>24] + 24;
-  }
-
-  /** returns 0 based index of first set bit
-   * (only works for x!=0)
-   * <br/> This is an alternate implementation of ntz()
-   */
-  public static int ntz2(long x) {
-   int n = 0;
-   int y = (int)x;
-   if (y==0) {n+=32; y = (int)(x>>>32); }   // the only 64 bit shift necessary
-   if ((y & 0x0000FFFF) == 0) { n+=16; y>>>=16; }
-   if ((y & 0x000000FF) == 0) { n+=8; y>>>=8; }
-   return (ntzTable[ y & 0xff ]) + n;
-  }
-
-  /** returns 0 based index of first set bit
-   * <br/> This is an alternate implementation of ntz()
-   */
-  public static int ntz3(long x) {
-   // another implementation taken from Hackers Delight, extended to 64 bits
-   // and converted to Java.
-   // Many 32 bit ntz algorithms are at http://www.hackersdelight.org/HDcode/ntz.cc
-   int n = 1;
-
-   // do the first step as a long, all others as ints.
-   int y = (int)x;
-   if (y==0) {n+=32; y = (int)(x>>>32); }
-   if ((y & 0x0000FFFF) == 0) { n+=16; y>>>=16; }
-   if ((y & 0x000000FF) == 0) { n+=8; y>>>=8; }
-   if ((y & 0x0000000F) == 0) { n+=4; y>>>=4; }
-   if ((y & 0x00000003) == 0) { n+=2; y>>>=2; }
-   return n - (y & 1);
-  }
-
-  /** table of number of leading zeros in a byte */
-  public static final byte[] nlzTable = {8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
-
-  /** Returns the number of leading zero bits.
-   */
-  public static int nlz(long x) {
-   int n = 0;
-   // do the first step as a long
-   int y = (int)(x>>>32);
-   if (y==0) {n+=32; y = (int)(x); }
-   if ((y & 0xFFFF0000) == 0) { n+=16; y<<=16; }
-   if ((y & 0xFF000000) == 0) { n+=8; y<<=8; }
-   return n + nlzTable[y >>> 24];
- /* implementation without table:
-   if ((y & 0xF0000000) == 0) { n+=4; y<<=4; }
-   if ((y & 0xC0000000) == 0) { n+=2; y<<=2; }
-   if ((y & 0x80000000) == 0) { n+=1; y<<=1; }
-   if ((y & 0x80000000) == 0) { n+=1;}
-   return n;
-  */
-  }
-
-
-  /** returns true if v is a power of two or zero*/
-  public static boolean isPowerOfTwo(int v) {
-    return ((v & (v-1)) == 0);
-  }
-
-  /** returns true if v is a power of two or zero*/
-  public static boolean isPowerOfTwo(long v) {
-    return ((v & (v-1)) == 0);
+    return popCount;
   }
 
   /** returns the next highest power of two, or the current value if it's already a power
of two or zero*/

Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java?rev=1411712&r1=1411711&r2=1411712&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java Tue Nov
20 15:59:39 2012
@@ -155,13 +155,13 @@ public final class FixedBitSet extends D
     long word = bits[i] >> subIndex;  // skip all the bits to the right of index
 
     if (word!=0) {
-      return (i<<6) + subIndex + BitUtil.ntz(word);
+      return (i<<6) + subIndex + Long.numberOfTrailingZeros(word);
     }
 
     while(++i < bits.length) {
       word = bits[i];
       if (word != 0) {
-        return (i<<6) + BitUtil.ntz(word);
+        return (i<<6) + Long.numberOfTrailingZeros(word);
       }
     }
 

Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/OpenBitSet.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/OpenBitSet.java?rev=1411712&r1=1411711&r2=1411712&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/OpenBitSet.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/OpenBitSet.java Tue Nov 20
15:59:39 2012
@@ -629,12 +629,12 @@ public class OpenBitSet extends DocIdSet
     long word = bits[i] >> subIndex;  // skip all the bits to the right of index
 
     if (word!=0) {
-      return (i<<6) + subIndex + BitUtil.ntz(word);
+      return (i<<6) + subIndex + Long.numberOfTrailingZeros(word);
     }
 
     while(++i < wlen) {
       word = bits[i];
-      if (word!=0) return (i<<6) + BitUtil.ntz(word);
+      if (word!=0) return (i<<6) + Long.numberOfTrailingZeros(word);
     }
 
     return -1;
@@ -650,12 +650,12 @@ public class OpenBitSet extends DocIdSet
     long word = bits[i] >>> subIndex;  // skip all the bits to the right of index
 
     if (word!=0) {
-      return (((long)i)<<6) + (subIndex + BitUtil.ntz(word));
+      return (((long)i)<<6) + (subIndex + Long.numberOfTrailingZeros(word));
     }
 
     while(++i < wlen) {
       word = bits[i];
-      if (word!=0) return (((long)i)<<6) + BitUtil.ntz(word);
+      if (word!=0) return (((long)i)<<6) + Long.numberOfTrailingZeros(word);
     }
 
     return -1;



Mime
View raw message