Efficient concatenation of Bit Arrays Java

Question

I am currently writing a piece of code where I have identified that the concatenation of my two bit arrays is the bottleneck, and debating on how to make it more efficient.

My Bit array is modelled as follows

public BitArray(int size) { 
    int sizeBytes = size / 8 ;
    if (size % 8 !=0) sizeBytes++;
    this.array = new byte[sizeBytes];
    this.size = size ; 
}

where size is the size in bits.

The challenge when concatenating two bit arrays efficiently is the straddling that needs to occur when concatenating a bit array of size 7 with one of size 6 for example. As such, it is not possible to simply do two array copies.

The solutions I am investigating, on top of what i currently have implemented is the following: compute the "straddle region" (the last 3 bits of a 5 bitarray for example). copy the first array with system.array.copy manually set the 3 "straddling bits" from the second array using my setBit function. shift the second array by 3 to the left do a System.arraycopy()

Currently, I manually set each individual bit of the second array, as shown below.

The issue is that with bit shifting,the operation is actually quite expensive given it has to be done for each byte, then the straddling has to occur again.

Thoughts on how to improve the techniques outlined above?

Here is the current code which performs poorly:

public static BitArray concatenate(BitArray x1_, BitArray x2_) {
    if (x1_ == null) {
        System.out.println("x1 is null");
        int b = x2_.getArray().length;
        byte[] array = new byte[b];
        System.arraycopy(x2_.getArray(), 0, array, 0, b);
        BitArray res = new BitArray(array);
        res.setSize(x2_.getSize());
        return res;
    } else if (x2_ == null) { 
        System.out.println("x2 is null");
        int b = x1_.getArray().length;
        byte[] array = new byte[b];
        System.arraycopy(x1_.getArray(), 0, array, 0, b);
        BitArray res = new BitArray(array);
        res.setSize(x1_.getSize());
        return res;
    }

    int size1 = x1_.getSize();
    int size2 = x2_.getSize();
    int size = (x1_.getSize() + x2_.getSize()) / 8 ;
    if ((size1 + size2)%8!=0) size++;
    byte[] result = new byte[size];
    System.arraycopy(x1, 0, result, 0, x1.length);
    BitArray res = new BitArray(result);
    res.setSize(size1 + size2);
    for (int i = 0 ; i<size2 ; i++) {
        res.setBit(size1 + i, x2_.getBit(i) );
    }
    return res; 
}

Answer 1

Your code is very convoluted and difficult to read. However, a few things that can take time:

• Using the % operator
• calling getSize() multiple times in the method - why don't you use the size property of your bit arrays?

I think using a linked list of bytes/longs to represent your BitArray would make concatenating much, much faster, as you can avoid copying anything at all, just updating a pointer.

Is concatenate an operation you will be performing a lot on the arrays? If so, I think I would have used a linked list of longs to represent the bit array. How big are your bit arrays?