AtomicBitSet implementation for java

Question

The standard api does not include an AtomicBitSet implementation. I could roll my own on top of AtomicIntegerArray, but would prefer not too.

Is anyone aware of an existing implementation released under a licence compatible with Apache 2? I require only basic operations to set and check bits.

Edit:

The code is both performance and memory critical so I'd like to avoid synchronization or an integer per flag if possible.

I assume a synchronized BitSet is not an option? If you want concurrency you could have an array of say 16 of them which would allow up to 16 threads to access them at once. — Peter Lawrey, Sep 14 '12 at 12:36
IMHO using AtomicIntegerArray would make sense for most (?) cases. Why not use that? — Lefteris Laskaridis, Sep 14 '12 at 12:37
Of course, it wouldn't be extendable like `BitSet`. You'd need to use a read/write lock or similar. — Tom Hawtin - tackline, Sep 14 '12 at 12:41
The code has fairly critical performance and memory requirements so I'd like to avoid using locks or an integer per flag if possible. — henry, Sep 14 '12 at 12:43

Peter Lawrey · Accepted Answer · 2017-04-22T07:21:20.833

22

I would use an AtomicIntegerArray and I would use 32 flags per integer which would give you the same density as BitSet but without needing locks for thread safety.

public class AtomicBitSet {
    private final AtomicIntegerArray array;

    public AtomicBitSet(int length) {
        int intLength = (length + 31) >>> 5; // unsigned / 32
        array = new AtomicIntegerArray(intLength);
    }

    public void set(long n) {
        int bit = 1 << n;
        int idx = (int) (n >>> 5);
        while (true) {
            int num = array.get(idx);
            int num2 = num | bit;
            if (num == num2 || array.compareAndSet(idx, num, num2))
                return;
        }
    }

    public boolean get(long n) {
        int bit = 1 << n;
        int idx = (int) (n >>> 5);
        int num = array.get(idx);
        return (num & bit) != 0;
    }
}

edited Apr 22 '17 at 07:21

answered Sep 14 '12 at 12:53

Peter Lawrey

525,659
79
751
1,130

If its performance critical you may want to avoid to *divide* and replace it by bit-shifting (>>). The JIT as of now is not able to guess that the values can be only positive and will not automagically optimize that. – Durandal Sep 14 '12 at 14:50
@Durandal Good idea. Changed it so you can have 64 billion bits. – Peter Lawrey Sep 14 '12 at 15:07
Thanks - this is the roll my own option that I was hoping to avoid, but I will accept this answer if no-one can point me at an off the shelf solution. I take it there are no objections to releasing this under apache 2 with appropriate attribution? – henry Sep 14 '12 at 15:54
@henry I would be pleased if you did. Go ahead. – Peter Lawrey Sep 14 '12 at 15:55
2

@PeterLawrey Shouldn't `int bit = 1 << n;` be `int bit = 1 << ( n % 32 );` in both `get` and `set`? – tim_yates Feb 13 '13 at 11:23
2

@tim_yates In Java, doing such a modulus has no effect as the shift is `& 31` for `int` and `& 63` for long. – Peter Lawrey Feb 14 '13 at 18:15
1

I had to develop a ThreadSafeBitSet for a project, and added few atomic methods like compareAndSet, and clearAndGetNextSetBit methods. Code is here https://gist.github.com/gomathi/322b8f3a3af54243383d. – vinayag Jul 29 '14 at 23:37
Java 8 made this somewhat more elegant with getAndAccumulate/accumulateAndGet, because now you don't have to have a while loop just to set one bit. – Hakanai Jun 29 '15 at 03:07
@Trejkaz except you can't be sure to set a specific bit with an add operation. If two threads try to "set" `0b01` with an add operation, you will get `0b10` – Peter Lawrey Jun 29 '15 at 10:20
@PeterLawrey Is that true? From their documentation, it makes it sound like you just call `array.getAndAccumulate(index, 0b01, (a,b) -> a|b)` and they take care of the details. – Hakanai Jun 30 '15 at 05:26
@Trejkaz good point though there is still a loop involved but you don't need to know this except for performance. – Peter Lawrey Jul 01 '15 at 05:26
Might want to change the constructor to do something like this (or equivalent) to avoid the unnecessary exception when passing in Integer.MAX_VALUE: `int intLength = length == 0 ? 0 : (length - 1) / 32 + 1;` – Tyler Hoppe Apr 20 '17 at 22:47
@TylerHoppe good point. I have changed it to use `>>> 5` for an unsigned / 32 – Peter Lawrey Apr 22 '17 at 07:21
can we add a method to get bitset object from this AtomicBitSet class? the use case is that while filling up i want to use atomicbitset for concurrent modification, but the clients are expecting old bitset for readonly use case. – best wishes Jul 11 '22 at 14:55

score 0 · Answer 2 · answered Sep 14 '12 at 12:35

0

Look at http://www.javamex.com/tutorials/synchronization_concurrency_7_atomic_integer_long.shtml

Not exactly using BitSet, but AtomicInteger.

answered Sep 14 '12 at 12:35

kovica

2,443
3
21
25

AtomicBitSet implementation for java

2 Answers2

Linked