lucene-java-3.4.0/lucene/src/test/org/apache/lucene/util/TestBitUtil.java

   1 /**
   2  * Licensed to the Apache Software Foundation (ASF) under one or more
   3  * contributor license agreements.  See the NOTICE file distributed with
   4  * this work for additional information regarding copyright ownership.
   5  * The ASF licenses this file to You under the Apache License, Version 2.0
   6  * (the "License"); you may not use this file except in compliance with
   7  * the License.  You may obtain a copy of the License at
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17
  18 package org.apache.lucene.util;
  19
  20 public class TestBitUtil extends LuceneTestCase {
  21
  22   private static int slowNlz(long x) {
  23     if (x == 0L) return 64;
  24     int nlz = 0;
  25     while ( ((x << nlz) & (1L << 63)) == 0) {
  26       nlz++;
  27     }
  28     return nlz;
  29   }
  30
  31   private void checkNlz(long x) {
  32     assertEquals(slowNlz(x), BitUtil.nlz(x));
  33     assertEquals(Long.numberOfLeadingZeros(x), BitUtil.nlz(x));
  34   }
  35
  36   public void testNlz() {
  37     checkNlz(0L);
  38     checkNlz(1L);
  39     checkNlz(-1L);
  40     for (int i = 1; i <= 63; i++) {
  41       checkNlz(1L << i);
  42       checkNlz((1L << i) + (1L << (i>>1)));
  43     }
  44   }
  45
  46   public void testBitUtils() {
  47     long num = 100000;
  48     assertEquals( 5, BitUtil.ntz(num) );
  49     assertEquals( 5, BitUtil.ntz2(num) );
  50     assertEquals( 5, BitUtil.ntz3(num) );
  51
  52     num = 10;
  53     assertEquals( 1, BitUtil.ntz(num) );
  54     assertEquals( 1, BitUtil.ntz2(num) );
  55     assertEquals( 1, BitUtil.ntz3(num) );
  56
  57     for (int i=0; i<64; i++) {
  58       num = 1L << i;
  59       assertEquals( i, BitUtil.ntz(num) );
  60       assertEquals( i, BitUtil.ntz2(num) );
  61       assertEquals( i, BitUtil.ntz3(num) );
  62     }
  63   }
  64
  65
  66   private long testArg(int shift) {
  67     return (1L << shift) + (1L << (shift>>1));
  68   }
  69
  70   private long nlzBitUtilBasicLoop(int iters) {
  71     long sumRes = 0;
  72     while (iters-- >= 0) {
  73       for (int i = 1; i <= 63; i++) {
  74         long a = testArg(i);
  75         sumRes += BitUtil.nlz(a);
  76         sumRes += BitUtil.nlz(a+1);
  77         sumRes += BitUtil.nlz(a-1);
  78         sumRes += BitUtil.nlz(a+10);
  79         sumRes += BitUtil.nlz(a-10);
  80       }
  81     }
  82     return sumRes;
  83   }
  84
  85   private long nlzLongBasicLoop(int iters) {
  86     long sumRes = 0;
  87     while (iters-- >= 0) {
  88       for (int i = 1; i <= 63; i++) {
  89         long a = testArg(i);
  90         sumRes += Long.numberOfLeadingZeros(a);
  91         sumRes += Long.numberOfLeadingZeros(a+1);
  92         sumRes += Long.numberOfLeadingZeros(a-1);
  93         sumRes += Long.numberOfLeadingZeros(a+10);
  94         sumRes += Long.numberOfLeadingZeros(a-10);
  95       }
  96     }
  97     return sumRes;
  98   }
  99
 100   public void tstPerfNlz() { // See LUCENE-3197, prefer to use Long.numberOfLeadingZeros() over BitUtil.nlz().
 101     final long measureMilliSecs = 2000;
 102     final int basicIters = 100000;
 103     long startTime;
 104     long endTime;
 105     long curTime;
 106     long dummy = 0; // avoid optimizing away
 107
 108     dummy = 0;
 109     int bitUtilLoops = 0;
 110     startTime = System.currentTimeMillis();
 111     endTime = startTime + measureMilliSecs;
 112     do {
 113       dummy += nlzBitUtilBasicLoop(basicIters);
 114       bitUtilLoops++;
 115       curTime = System.currentTimeMillis();
 116     } while (curTime < endTime);
 117     int bitUtilPsTime = (int) (1000000000 * (curTime - startTime) / (basicIters * 5 * 63 * (float) bitUtilLoops));
 118     System.out.println("BitUtil nlz time: " + (bitUtilPsTime/1) + " picosec/call, dummy: " + dummy);
 119
 120
 121     dummy = 0;
 122     int longLoops = 0;
 123     startTime = System.currentTimeMillis();
 124     endTime = startTime + measureMilliSecs;
 125     do {
 126       dummy += nlzLongBasicLoop(basicIters);
 127       longLoops++;
 128       curTime = System.currentTimeMillis();
 129     } while (curTime < endTime);
 130     int longPsTime = (int) (1000000000 * (curTime - startTime) / (basicIters * 5 * 63 * (float) longLoops));
 131     System.out.println("Long    nlz time: " + longPsTime + " picosec/call, dummy: " + dummy);
 132   }
 133 }