Java Resizable Array

http://tutorials.jenkov.com/java-performance/resizable-array.html

Imagine you have a server receiving messages of varying sizes. Some messages are very small (e.g. less than 4KB), others as large as 1MB or even larger.

If the server is receiving messages from many (100K +) connections at the same time, we need to limit how much memory we pre-allocate for each message. We cannot just allocate the maximal message size (e.g. 1MB or 16MB etc.) for each buffer. That would deplete the server memory fast when the number of connections and messages go up! 100.000 x 1MB = 100GB (approximately - not precisely - but you get the picture).

Instead we want to assume that most messages are small, so we start with a small buffer. If a message grows beyond the small buffer size, we allocate a new, larger array and copy the data to the new, larger array. If the message outgrows the larger array, an even larger array is allocated, and the message is copied to that.

Keeping Track of Free Blocks

The large array inside the ResizableArrayBuffer is split up into three sections. Each section is split up into smaller blocks. Each block in each section has the same size. Blocks in the small message section has the same small block size. Blocks in the medium message section has the same medium block size. And blocks in the large message section has the same large block size.

When all blocks within a section has the same size, it is easier to keep track of used and unused blocks. You can simply use a queue containing the start indexes of each block. One queue is needed for each section of the shared array. Thus, one queue is needed to keep track of free small blocks, one queue for free medium blocks and one queue for free large blocks.

Allocating a block from any of the sections can be accomplished simply by taking the next free block start index from the queue associated with the desired section. Freeing a block is done by putting the start index back into the corresponding queue.

Expand on Write

The Resizable array will expand itself when you write data to it. If you attempt to write more data to it than it has space for in its currently allocated block, it will allocate a new, larger block and copy all its data to that new block. The previous smaller block is then freed.

Freeing Arrays

Once you are done with a resizable array you should free it again, so that it can be used for other messages.

 * A shared buffer which can contain many messages inside. A message gets a section of the buffer to use. If the
 * message outgrows the section in size, the message requests a larger section and the message is copied to that
 * larger section. The smaller section is then freed again.
 *
 *
 * Created by jjenkov on 18-10-2015.
 */
public class ResizableArrayBuffer {

    public static int KB = 1024;
    public static int MB = 1024 * KB;


    //package scope (default) - so they can be accessed from unit tests.
    byte[] sharedArray = null;

    private int capacity = 0;

    private int smallBlockSize  = 0;
    private int mediumBlockSize = 0;
    private int largeBlockSize  = 0;

    private int smallBlockCount  = 0;
    private int mediumBlockCount = 0;
    private int largeBlockCount  = 0;


    QueueIntFlip smallFreeBlocks  = null;
    QueueIntFlip mediumFreeBlocks = null;
    QueueIntFlip largeFreeBlocks  = null;

    public ResizableArrayBuffer(int smallBlockSize, int smallBlockCount, int mediumBlockSize, int mediumBlockCount, int largeBlockSize, int largeBlockCount) {
        this.capacity = smallBlockSize * smallBlockCount + mediumBlockSize * mediumBlockCount + largeBlockSize * largeBlockCount;
        this.sharedArray = new byte[this.capacity];

        this.smallBlockSize   = smallBlockSize;
        this.smallBlockCount  = smallBlockCount;
        this.mediumBlockSize  = mediumBlockSize;
        this.mediumBlockCount = mediumBlockCount;
        this.largeBlockSize   = largeBlockSize;
        this.largeBlockCount  = largeBlockCount;

        this.smallFreeBlocks  = new QueueIntFlip(smallBlockCount);
        this.mediumFreeBlocks = new QueueIntFlip(mediumBlockCount);
        this.largeFreeBlocks  = new QueueIntFlip(largeBlockCount);

        //add all free sections to all free section queues.
        int smallBlocksEndIndex   = smallBlockSize * smallBlockCount;
        for(int i=0; i<smallBlocksEndIndex; i+= smallBlockSize){
            this.smallFreeBlocks.put(i);
        }
        int mediumBlocksStartIndex = smallBlockCount * smallBlockSize;
        int mediumBlocksEndIndex   = mediumBlocksStartIndex + mediumBlockSize * mediumBlockCount;
        for(int i=mediumBlocksStartIndex; i<mediumBlocksEndIndex; i+= mediumBlockSize){
            this.mediumFreeBlocks.put(i);
        }
        int largeBlocksStartIndex = mediumBlocksEndIndex;
        int largeBlocksEndIndex   = largeBlocksStartIndex + largeBlockSize * largeBlockCount;
        for(int i=largeBlocksStartIndex; i<largeBlocksEndIndex; i+= largeBlockSize){
            this.largeFreeBlocks.put(i);
        }
    }

    public ResizableArray getArray() {
        int nextFreeSmallBlock = this.smallFreeBlocks.take();

        if(nextFreeSmallBlock == -1) return null;

        ResizableArray resizableArray = new ResizableArray(this);       //todo get from Message pool - caps memory usage.

        resizableArray.sharedArray = this.sharedArray;
        resizableArray.capacity    = smallBlockSize;
        resizableArray.offset      = nextFreeSmallBlock;
        resizableArray.length      = 0;

        return resizableArray;
    }

    public boolean expandArray(ResizableArray resizableArray){
        if(resizableArray.capacity == smallBlockSize){
            return moveArray(resizableArray, this.smallFreeBlocks, this.mediumFreeBlocks, mediumBlockSize);
        } else if(resizableArray.capacity == mediumBlockSize){
            return moveArray(resizableArray, this.mediumFreeBlocks, this.largeFreeBlocks, largeBlockSize);
        } else {
            return false;
        }
    }

    private boolean moveArray(ResizableArray resizableArray, QueueIntFlip srcBlockQueue, QueueIntFlip destBlockQueue, int newCapacity) {
        int nextFreeBlock = destBlockQueue.take();
        if(nextFreeBlock == -1) return false;

        System.arraycopy(this.sharedArray, resizableArray.offset, this.sharedArray, nextFreeBlock, resizableArray.length);

        srcBlockQueue.put(resizableArray.offset); //free smaller block after copy

        resizableArray.sharedArray = this.sharedArray;
        resizableArray.offset      = nextFreeBlock;
        resizableArray.capacity    = newCapacity;
        return true;
    }


    public void free(ResizableArray resizableArray){
        if(resizableArray.capacity == smallBlockSize){
            this.smallFreeBlocks.put(resizableArray.offset);
        } else if(resizableArray.capacity == mediumBlockSize){
            this.mediumFreeBlocks.put(resizableArray.offset);
        } else {
            this.largeFreeBlocks.put(resizableArray.offset);
        }
    }
}

public class ResizableArray {

    private ResizableArrayBuffer resizableArrayBuffer = null;

    public byte[] sharedArray = null;
    public int    offset      = 0; //offset into sharedArray where this message data starts.
    public int    capacity    = 0; //the size of the section in the sharedArray allocated to this message.
    public int    length      = 0; //the number of bytes used of the allocated section.

    public ResizableArray(ResizableArrayBuffer resizableArrayBuffer) {
        this.resizableArrayBuffer = resizableArrayBuffer;
    }

    /**
     * Writes data from the ByteBuffer into this message - meaning into the buffer backing this message.
     *
     * @param byteBuffer The ByteBuffer containing the message data to write.
     * @return
     */
    public int writeToMessage(ByteBuffer byteBuffer){
        int remaining = byteBuffer.remaining();

        while(length + remaining > capacity){
            //expand message.
            if(!this.resizableArrayBuffer.expandArray(this)) {
                return -1;
            }
        }

        int bytesToCopy = Math.min(remaining, this.capacity - this.length);
        byteBuffer.get(this.sharedArray, this.offset + this.length, bytesToCopy);
        this.length += bytesToCopy;

        return bytesToCopy;
    }

    public void free() {
        this.resizableArrayBuffer.free(this);
    }
}

https://github.com/jjenkov/java-resizable-array/blob/master/src/main/java/com/jenkov/resizablearray/QueueIntFlip.java