A little tuning can go a long way...

The application that I'm current developing uses Lucene for searching and data retrieval.  We recently had a rather special need to use one of the utility classes in Lucene, OpenBitSet.  OpenBitSet is not unlike the regular BitSet provided by the java.util package.  The biggest difference is that the class is NOT final.  So for someone like me, that tinkers and optimizes to get every last bit of performance out of my application, final classes are a major PITA.

The problem:

OpenBitSet provides an optimized "find the next set bit starting here" method called nextSetBit(long index).  However I needed to find the previous set bit, so naturally I started by using the built-in api.  Iterate backwards over each bit starting at given position until a bit that it is set to true is found.  Probably not the fastest way, but it works.  I thought that if I wrote my own "find the previous set bit starting here" method it could be potently a lot faster.  And because the class is not final and the internals are not private I can extend it, YAY!

So after some work and some tests I came up with this:

    /**
     * Finds the previous set bit in the bitset, start looking at the index position.
     * @param index the index to start looking.
     * @return the previous position in the bitset that is set.
     */
    public long prevSetBit(long index) {
        //get index of the word to start with
        int i = (int) (index >>> 6); //div by 64
        if (i >= wlen) {
            //if the index requested is greater than the actual
            //max word, just start with the last word
            i = wlen - 1;
        }
        //loop backwards over the bits[] until a non-zero word is found
        while (i >= 0) {
            long word = bits[i];
            if (word != 0) {
                //find the position of the most significant bit
                int pomsb = getPositionOfMostSigBit(word);
                //multiply by 64
                long l = ((long) i) << 6;
                //add together to find the actual position
                return l + pomsb;
            }
            i--;
        }
        return -1;
    }
    
    /**
     * The word passed in, should not be 0.
     * @param word the word to find the position of the most significant bit.
     * @return the position in the word.
     */
    private int getPositionOfMostSigBit(long word) {
        if (word == 1l) {
            return 0;
        }
        int i = 0;
        while (word != 1) {
            word = word >>> 1;
            i++;
        }
        return i;
    }

And of course I had to write a performance test to make sure that my work had produced something useful.  Here's the test:

    public static void main(String[] args) {
        CustomOpenBitSet bitSet = new CustomOpenBitSet(Integer.MAX_VALUE);
        int maxCount = 1000000;
        fillBitSet(bitSet, maxCount);
        
        for (int i = 0; i < 10; i++) {
            double s1 = System.nanoTime();
            int slow = runSlowReverseSeeksToSetBits(bitSet, maxCount);
            double e1 = System.nanoTime();
            
            double s2 = System.nanoTime();
            int fast = runFastReverseSeeksToSetBits(bitSet, maxCount);
            double e2 = System.nanoTime();
            
            assert (slow == fast);
            
            System.out.println("The slow time took " + ((e1-s1) / ONE_BILLION) + " seconds");
            System.out.println("The fast time took " + ((e2-s2) / ONE_BILLION) + " seconds");
        }
    }

    private static int runFastReverseSeeksToSetBits(CustomOpenBitSet bitSet, int maxCount) {
        int count = 0;
        long start = Integer.MAX_VALUE;
        while (count < maxCount - 1) {
            long position = bitSet.prevSetBit(start);
            count++;
            start = position - 1;
        }
        return count;
    }

    private static int runSlowReverseSeeksToSetBits(CustomOpenBitSet bitSet, int maxCount) {
        int count = 0;
        long start = Integer.MAX_VALUE;
        while (count < maxCount - 1) {
            long position = slowSeek(bitSet,start);
            count++;
            start = position - 1;
        }
        return count;
    }

    private static long slowSeek(CustomOpenBitSet bitSet, long position) {
        while (!bitSet.get(position)) {
            position--;
            if (position < 0) {
                return -1;
            }
        }
        return position;
    }

    private static void fillBitSet(CustomOpenBitSet bitSet, int numberOfBitsToSet) {
        Random random = new Random();
        int nextInt = -1;
        for (int i = 0; i < numberOfBitsToSet; i++) {
            do {
                nextInt = random.nextInt(Integer.MAX_VALUE);
            } while (bitSet.fastGet(nextInt));
            bitSet.set(nextInt);
        }
    }

The test creates a BitSet that is Integer.MAX_VALUE long and randomly populates it with 1 million bits set to true.  Then starting at Integer.MAX_VALUE, find all the bits that are set to true, moving from the greatest position to the smallest position.  Do this 10 times and print off the time taken to perform both algorithms.

Pass [0], the slow time took 7.867899136 seconds
Pass [0], the fast time took 0.059851008 seconds
Pass [1], the slow time took 7.84461184 seconds
Pass [1], the fast time took 0.051954944 seconds
Pass [2], the slow time took 7.820731904 seconds
Pass [2], the fast time took 0.07801088 seconds
Pass [3], the slow time took 7.81953408 seconds
Pass [3], the fast time took 0.074951168 seconds
Pass [4], the slow time took 7.798106112 seconds
Pass [4], the fast time took 0.07792384 seconds
Pass [5], the slow time took 7.742498048 seconds
Pass [5], the fast time took 0.067644928 seconds
Pass [6], the slow time took 7.664754944 seconds
Pass [6], the fast time took 0.07476992 seconds
Pass [7], the slow time took 7.841472768 seconds
Pass [7], the fast time took 0.073187072 seconds
Pass [8], the slow time took 7.927188992 seconds
Pass [8], the fast time took 0.07574912 seconds
Pass [9], the slow time took 7.85273088 seconds
Pass [9], the fast time took 0.076514048 seconds

So as you can see the new method is about 100 times faster than just iterating backwards over the bitset, given this sample data.  I would assume that if the sample size of 1 million were to increase, the gap between the 2 methods would narrow.