A little tuning can go a long way...
By Aaron Mccurry
Apr 02, 2009
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:
And of course I had to write a performance test to make sure that my work had produced something useful. Here's the test:
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.
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.
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:
/**<br /> * Finds the previous set bit in the bitset, start looking at the index position.<br /> * @param index the index to start looking.<br /> * @return the previous position in the bitset that is set.<br /> */<br /> public long prevSetBit(long index) {<br /> //get index of the word to start with<br /> int i = (int) (index >>> 6); //div by 64<br /> if (i >= wlen) {<br /> //if the index requested is greater than the actual<br /> //max word, just start with the last word<br /> i = wlen - 1;<br /> }<br /> //loop backwards over the bits[] until a non-zero word is found<br /> while (i >= 0) {<br /> long word = bits[i];<br /> if (word != 0) {<br /> //find the position of the most significant bit<br /> int pomsb = getPositionOfMostSigBit(word);<br /> //multiply by 64<br /> long l = ((long) i) << 6;<br /> //add together to find the actual position<br /> return l + pomsb;<br /> }<br /> i--;<br /> }<br /> return -1;<br /> }<br /> <br /> /**<br /> * The word passed in, should not be 0.<br /> * @param word the word to find the position of the most significant bit.<br /> * @return the position in the word.<br /> */<br /> private int getPositionOfMostSigBit(long word) {<br /> if (word == 1l) {<br /> return 0;<br /> }<br /> int i = 0;<br /> while (word != 1) {<br /> word = word >>> 1;<br /> i++;<br /> }<br /> return i;<br /> }<br /><br />
public static void main(String[] args) {<br /> CustomOpenBitSet bitSet = new CustomOpenBitSet(Integer.MAX_VALUE);<br /> int maxCount = 1000000;<br /> fillBitSet(bitSet, maxCount);<br /> <br /> for (int i = 0; i < 10; i++) {<br /> double s1 = System.nanoTime();<br /> int slow = runSlowReverseSeeksToSetBits(bitSet, maxCount);<br /> double e1 = System.nanoTime();<br /> <br /> double s2 = System.nanoTime();<br /> int fast = runFastReverseSeeksToSetBits(bitSet, maxCount);<br /> double e2 = System.nanoTime();<br /> <br /> assert (slow == fast);<br /> <br /> System.out.println("The slow time took " + ((e1-s1) / ONE_BILLION) + " seconds");<br /> System.out.println("The fast time took " + ((e2-s2) / ONE_BILLION) + " seconds");<br /> }<br /> }<br /><br /> private static int runFastReverseSeeksToSetBits(CustomOpenBitSet bitSet, int maxCount) {<br /> int count = 0;<br /> long start = Integer.MAX_VALUE;<br /> while (count < maxCount - 1) {<br /> long position = bitSet.prevSetBit(start);<br /> count++;<br /> start = position - 1;<br /> }<br /> return count;<br /> }<br /><br /> private static int runSlowReverseSeeksToSetBits(CustomOpenBitSet bitSet, int maxCount) {<br /> int count = 0;<br /> long start = Integer.MAX_VALUE;<br /> while (count < maxCount - 1) {<br /> long position = slowSeek(bitSet,start);<br /> count++;<br /> start = position - 1;<br /> }<br /> return count;<br /> }<br /><br /> private static long slowSeek(CustomOpenBitSet bitSet, long position) {<br /> while (!bitSet.get(position)) {<br /> position--;<br /> if (position < 0) {<br /> return -1;<br /> }<br /> }<br /> return position;<br /> }<br /><br /> private static void fillBitSet(CustomOpenBitSet bitSet, int numberOfBitsToSet) {<br /> Random random = new Random();<br /> int nextInt = -1;<br /> for (int i = 0; i < numberOfBitsToSet; i++) {<br /> do {<br /> nextInt = random.nextInt(Integer.MAX_VALUE);<br /> } while (bitSet.fastGet(nextInt));<br /> bitSet.set(nextInt);<br /> }<br /> }
Pass [0], the slow time took 7.867899136 seconds<br />Pass [0], the fast time took 0.059851008 seconds<br />Pass [1], the slow time took 7.84461184 seconds<br />Pass [1], the fast time took 0.051954944 seconds<br />Pass [2], the slow time took 7.820731904 seconds<br />Pass [2], the fast time took 0.07801088 seconds<br />Pass [3], the slow time took 7.81953408 seconds<br />Pass [3], the fast time took 0.074951168 seconds<br />Pass [4], the slow time took 7.798106112 seconds<br />Pass [4], the fast time took 0.07792384 seconds<br />Pass [5], the slow time took 7.742498048 seconds<br />Pass [5], the fast time took 0.067644928 seconds<br />Pass [6], the slow time took 7.664754944 seconds<br />Pass [6], the fast time took 0.07476992 seconds<br />Pass [7], the slow time took 7.841472768 seconds<br />Pass [7], the fast time took 0.073187072 seconds<br />Pass [8], the slow time took 7.927188992 seconds<br />Pass [8], the fast time took 0.07574912 seconds<br />Pass [9], the slow time took 7.85273088 seconds<br />Pass [9], the fast time took 0.076514048 seconds