Speed of BitSet operations

Discussion in 'Java' started by Momo, Jun 6, 2007.

  1. Momo

    Momo Guest

    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
     
    Momo, Jun 6, 2007
    #1
    1. Advertising

  2. 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
     
    Patricia Shanahan, Jun 6, 2007
    #2
    1. Advertising

  3. Momo

    Tom Hawtin Guest

    Momo wrote:
    > 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
     
    Tom Hawtin, Jun 6, 2007
    #3
  4. Momo

    Momo Guest

    On Jun 6, 4:27 pm, Patricia Shanahan <> wrote:
    > 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



    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, Jun 6, 2007
    #4
  5. Momo

    Momo Guest

    On Jun 6, 4:53 pm, Tom Hawtin <> wrote:
    > Momo wrote:
    > > 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


    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
     
    Momo, Jun 6, 2007
    #5
  6. Momo

    Roedy Green Guest

    On Wed, 06 Jun 2007 12:58:45 -0700, Momo <>
    wrote, quoted or indirectly quoted someone who said :

    >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.
    --
    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
     
    Roedy Green, Jun 15, 2007
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ham

    I need speed Mr .Net....speed

    Ham, Oct 28, 2004, in forum: ASP .Net
    Replies:
    6
    Views:
    2,372
    Antony Baula
    Oct 29, 2004
  2. efiedler
    Replies:
    1
    Views:
    2,131
    Tim Ward
    Oct 9, 2003
  3. Jesus M. Salvo Jr.
    Replies:
    2
    Views:
    4,324
    robert
    Feb 11, 2006
  4. Chris Lervag

    Need for speed - array operations

    Chris Lervag, Apr 29, 2011, in forum: Ruby
    Replies:
    6
    Views:
    132
    Joel VanderWerf
    May 17, 2011
  5. Ninds
    Replies:
    14
    Views:
    862
    W Karas
    Dec 3, 2012
Loading...

Share This Page