Name: krT82822 Date: 01/18/2000


java version "1.3beta"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.3beta-O)
Java(TM) HotSpot Client VM (build 1.3beta-O, mixed mode)

The following BitSet members should be changed from private to
protected: bits[], unitsInUse, ADDRESS_BITS_PER_UNIT,
BITS_PER_UNIT, BIT_INDEX_MASK

The BitSet class lacks several methods which are needed for
certain operations. It is extremely expensive to implement
these operations using the public methods that BitSet exposes.
In my tests, it was several orders of magnitude more costly
for some operations.

Since one of the main reasons for using a BitSet is efficiency,
inefficient implementation using the public methods is not a
viable option. Making these variables protected would allow
others to extend BitSet to add efficient implementations of
required operations.

If exposing these variables is not considered acceptable, the
alternative would be to implement a more complete set of BitSet
operations. Other RFEs (including one of mine) have suggested
this approach. If this approach is taken, then the methods
listed below should be included. Some, but not all of them
have been mentioned in other RFEs.

My application requires a number of BitSet operations which are
not supported. I initially implemented them using BitSet public
methods, but profiling indicated that they were consuming a
significant portion of the time. Adding new methods to BitSet
reduced the overall application execution time by 17.5%. This
required copying all of the source of BitSet and adding the new
methods.

The difference in the time for the actual operations is far more
dramatic. I wrote a number of timing tests using relatively
sparse BitSets of values ranging from 0 to 5000, and compared
the times required to implement these operations using the
standard BitSet methods with the time required for the newly
added methods. The following shows the results of those tests:

Test Descriptions:

    Empty test - Tests whether a BitSet is empty. The times
        reported are for 1,000,000 empty tests.

    Clear - Resets all of the set bits in the BitSet. Times
        reported are for cloning and clearing a BitSet 5000
times.

    Intersection - Determine if one BitSet intersects another.
        Times reported are for 50,000 tests.

    Cardinality - Determines the number of "set" bits in a
        BitSet. Times reported are for 1000 tests.

    Iteration - Iterate through all of the "set" bits in a
        Bitset. Times reported are for 1000 iterations.

Test times:
                         
    Test standard new ratio
    ------------------ -------- --- -------
    Empty test. 17.866 0.941 19 : 1
    Clear. 65.334 0.411 159 : 1
    Intersection test. 7.491 3.355 2.2 : 1
    Cardinality. 11.927 1.322 9 : 1
    Iteration. 12.408 0.100 124 : 1


The following methods were added to BitSet to provide an efficient
implementation of these operations. Note that *no* changes were
made to any of the existing BitSet methods, so adding these methods
will not affect the efficiency of existing code.

    /**
    ** Returns true if this BitSet contains no bits that are set to
    ** <code>true</code>.
    */
    public boolean isEmpty() {
        return ( unitsInUse == 0 );
    }

    /**
    ** Sets all of the bits in this BitSet to <code>false</code>.
    */
    public void clear() {
        while ( unitsInUse > 0 ) {
            -- unitsInUse;
            bits[ unitsInUse ] = 0;
        }
    }

    /**
    ** Returns true if the specified BitSet has any bits set <code>true</code>
    ** that are also set <code>true</code> in this BitSet.
    */
    public boolean intersects( BitSet set ) {
        for ( int i = Math.min(unitsInUse, set.unitsInUse) - 1;
                i >= 0; -- i )
        {
            if ( (bits[i] & set.bits[i]) != 0 ) {
                return true;
            }
        }
        return false;
    }

    /**
    ** Returns the number of bits that are set <code>true</code> in
    ** this BitSet.
    */
    public int cardinality() {
        int card = 0;

        for ( int i = unitsInUse-1; i >= 0; -- i ) {
            long unit = bits[i];
            while ( unit != 0 ) {
                if ( (unit & 1) != 0 ) {
                    ++ card;
                }
                unit >>>= 1;
            }
        }

        return card;
    }

    /**
    ** Returns the first bit greater than or equal to 'start' that is set
    ** to <code>true</code>.
    ** @param start the number of the lowest bit to check.
    ** @return the first bit greater than or equal to 'start' that is set
    ** to <code>true</code>, or -1 if there is no such bit.
    */
    public int firstSetBit( int start ) {
        int u = unitIndex( start );
        int i = (start & BIT_INDEX_MASK);
        long unit = (bits[ u ] >> i);
        while ( (unit == 0) && (u < unitsInUse-1) ) {
            unit = bits[ ++u ];
            i = 0;
        }
        if ( unit == 0 ) {
            return -1;
        }
        while ( (unit & 1) == 0 ) {
            ++ i;
            unit >>>= 1;
        }
        return ( (u * BITS_PER_UNIT) + i );
    }
(Review ID: 100063)
======================================================================