A Memory Efficient and Fast Byte Array Builder Implementation

In many applications we come across scenarios where we need a builder for byte array, similar to say like a StringBuilder. We seek for an option where we can go appending bytes (array), and finally get the constructed array.

Since Java does not provide any such library, most create a simple utility with at least the following behaviour.

byte[] toBytes();
ByteArrayBuilder append(byte[] bytes);

In its simplest form (Java 1.6+), an implementation can be as follows:

ByteArrayBuilder append(byte[] _bytes)
{
int offset = values.length;
values = Arrays.copyOf(values, offset+_bytes.length);
System.arraycopy(_bytes, 0, values, offset, _bytes.length);
return this;
}

byte[] toBytes() {
return values;
}

The full class is not provided, for brevity purpose.

This method is one of the various ways this can be implemented. However, in any such solutions, there will be multiple intermediate array instantiations (line 4, above). This can turn ugly with a high heap memory usage (although that should be in eden space), where big byte arrays are being created from within a loop, and result into an OOM exception.

I was specifically facing "GC overhead limit exceeded" and "Java heap space" errors, while running a test with fixed max heap size.

Can we eliminate this intermediate array instantiation? The solution I am providing here does exactly that. PLEASE NOTE: To avoid intermediate instantions, we would be utilising off-heap allocations using the (in)famous sun.misc.Unsafe.

Compared to the previous solution this produced around 3.5 times less heap usage, as tested in my laptop (Ubuntu 12.04, 8gb ram) using Java1.7u79 with no additional JVM parameters. Also the performance was slightly better as well (execution timing), though I would really consider the memory efficiency more.

package com.vortex.files.util;

import java.lang.reflect.Field;

import sun.misc.Unsafe;

public class ByteArrayBuilder implements ArrayBuilder<byte[]> 
{
private static Unsafe UNSAFE;
static
{
try {
Field f = Unsafe.class.getDeclaredField("theUnsafe");
f.setAccessible(true);
UNSAFE = (Unsafe) f.get(null);
} catch (Exception e) {
throw new ExceptionInInitializerError("sun.misc.Unsafe not instantiated ["+e.toString()+"]");
}

}

private long _address = -1;
private int byteSize = 0;

/* (non-Javadoc)
 * @see com.vortex.files.util.ArrayBuilder#toArray()
 */
@Override
public byte[] toArray() {
byte[] values = new byte[byteSize];

        UNSAFE.copyMemory(null, _address,
                          values, Unsafe.ARRAY_BYTE_BASE_OFFSET,
                          byteSize);

        return values;
}

public ByteArrayBuilder()
{
appendFirst(new byte[0]);
}
public ByteArrayBuilder(byte[] bytes)
{
appendFirst(bytes);
}
/* (non-Javadoc)
 * @see com.vortex.files.util.ArrayBuilder#append(byte[])
 */
@Override
public ByteArrayBuilder append(byte[] _bytes)
{
return appendNext(_bytes);
}
private ByteArrayBuilder appendFirst(byte[] _bytes)
{
long _address2 = UNSAFE.allocateMemory(byteSize + _bytes.length);
UNSAFE.copyMemory(_bytes, Unsafe.ARRAY_BYTE_BASE_OFFSET, null, _address2, _bytes.length);
_address = _address2;
byteSize += _bytes.length;
return this;
}
private ByteArrayBuilder appendNext(byte[] _bytes)
{
long _address2 = UNSAFE.allocateMemory(byteSize + _bytes.length);
UNSAFE.copyMemory(_address, _address2, byteSize);
UNSAFE.copyMemory(_bytes, Unsafe.ARRAY_BYTE_BASE_OFFSET+byteSize, null, _address2, _bytes.length);
UNSAFE.freeMemory(_address);
_address = _address2;
byteSize += _bytes.length;
return this;
}
/* (non-Javadoc)
 * @see com.vortex.files.util.ArrayBuilder#free()
 */
@Override
public void free() {
UNSAFE.freeMemory(_address);

}
}