Speed of BitSet operations

[Momo]

Why are the BitSet manipulations so slow on large BitSets when I try
to modify the same bit twice in a row? I've been running tests on
x=new BitSet(size=1000000). If I first turn all the bits on, and then
turn all the bits off, as follows,

for (loop=0; loop<size; loop++)
x.set(loop);
for (loop=0; loop<size; loop++)
x.clear(loop);

it goes very quickly (around 150 ms). (I know that x.clear() is much
faster for clearing the BitSet; this is just to compare with below.)

However, if I turn each bit on, and then immediately off, it goes
much slower. That is,

for (loop=0; loop<size; loop++) {
x.set(loop);
x.clear(loop);
}

takes about 25000 ms, or about 150 times longer.

If I stagger things a little, so that I wait a little before
reflipping a bit, it gets fast again. That is,

for (loop=1; loop<size; loop++) {
x.set(loop);
x.clear(loop-1);
}

is again around 150 ms. The slowdown for immediately reflipping a bit
becomes more pronounced for larger BitSets.

Second (or instead), is it possible to see how to Sun implements
BitSet, which would (presumably) let me figure out what's going on? A
number of old posts imply that the implementation is publicly
available, but I couldn't find it at Sun's website.

Momo

 

[Patricia Shanahan]

Momo wrote:
....

Second (or instead), is it possible to see how to Sun implements
BitSet, which would (presumably) let me figure out what's going on? A
number of old posts imply that the implementation is publicly
available, but I couldn't find it at Sun's website.

....

Look for "src.zip" in your jdk install directory.

Patricia

 

[Tom Hawtin]

Why are the BitSet manipulations so slow on large BitSets when I try
to modify the same bit twice in a row? I've been running tests on

BitSet keeps track of the number of 'word in use' (for some reason). If
you clear the top set bit and it happens to be the only set bit, then it
checks through all lower bits. So repeatedly setting and clearing the
top (and only) bit is O(n^2).

Tom Hawtin

 

[Momo]

Momo wrote:

...> Second (or instead), is it possible to see how to Sun implements

...

Look for "src.zip" in your jdk install directory.

Patricia

Oh, it's already on my computer. OK, now I feel like a jackass.

As it turns out, Tom Hawtin has already saved me the trouble of
inspecting the BitSet implementation, but thanks, this is quite useful
for next time.

Momo

 

[Momo]

BitSet keeps track of the number of 'word in use' (for some reason). If
you clear the top set bit and it happens to be the only set bit, then it
checks through all lower bits. So repeatedly setting and clearing the
top (and only) bit is O(n^2).

Tom Hawtin

Thank you very much! This was causing a mysterious slowdown by a
factor of 10-100 in my simulations, for certain inputs. So it's great
to have this fixed.

Momo

 

[Roedy Green]

However, if I turn each bit on, and then immediately off, it goes
much slower. That is,

You can view the source in source.zip. It has arrays of longs. To set
a bit, it fetches the long, ors a bit mask and stores it back. If you
do it bit by bit that happens 64 times to clear one item.

to clear all bits it just has to store a 0.