Ring Buffer in Java

Creating an Atomic RingBuffer in Java

Multiple reader/multiple writer ring buffers are tricky.

Your way doesn't work, because you can't update that start/end position AND the array contents atomically. Consider adding to the buffer: If you update the end position first, then there is a moment before you update the array when the buffer contains an invalid item. If you update the array first, then there's nothing to stop simultaneous additions from stomping on the same array element.

There are lots of ways to deal with these problems, but the various ways have different trade-offs, and you have better options available if you can get rid of the multiple reader or multiple writer requirement.

If I had to guess at why we don't have a concurrent ring buffer in the standard library, I'd say it's because there is no one best way to implement it that is going to be good for most scenarios. The data structure used for ConcurrentLinkedQueue, in contrast, is simple and elegant and an obvious choice when a concurrent linked list is required.

flush() and isEmpty() methods for a ring buffer without using .size() in Java

You can read more about Full/Empty Buffer Distinction on Wikipedia
http://en.wikipedia.org/wiki/Circular_buffer#Full_.2F_Empty_Buffer_Distinction

There are multiple workarounds described. I would point out the one you mentioned and maybe the easiest one to understand.

Always keep one slot open

The buffer will never be full to the last item, but there will be always one slot empty. That means you can distinguish full from empty like this:

public boolean isEmpty() {
     return head == tail;
}

public boolean isFull() {
     // don't forget about the modulo here
     return head == ((tail - 1) % capacity);
}

When flushing (I would name it rather clear()) you don't have to overwrite the data in array or allocate a new one. You can just set pointers to the beginning of the array.

public void clear() {
     head = 0;
     tail = 0;
}

And that means the buffer will be considered empty. No matter what data are really written in memory they will be ignored and then overwritten.

If you liked this answer please mark it as accepted. Thank you.

Thread-safe circular buffer in Java

Buffer fifo = BufferUtils.synchronizedBuffer(new CircularFifoBuffer());

How would you code an efficient Circular Buffer in Java or C#?

I would use an array of T, a head and tail pointer, and add and get methods.

Like: (Bug hunting is left to the user)

// Hijack these for simplicity
import java.nio.BufferOverflowException;
import java.nio.BufferUnderflowException;

public class CircularBuffer<T> {

  private T[] buffer;

  private int tail;

  private int head;

  @SuppressWarnings("unchecked")
  public CircularBuffer(int n) {
    buffer = (T[]) new Object[n];
    tail = 0;
    head = 0;
  }

  public void add(T toAdd) {
    if (head != (tail - 1)) {
        buffer[head++] = toAdd;
    } else {
        throw new BufferOverflowException();
    }
    head = head % buffer.length;
  }

  public T get() {
    T t = null;
    int adjTail = tail > head ? tail - buffer.length : tail;
    if (adjTail < head) {
        t = (T) buffer[tail++];
        tail = tail % buffer.length;
    } else {
        throw new BufferUnderflowException();
    }
    return t;
  }

  public String toString() {
    return "CircularBuffer(size=" + buffer.length + ", head=" + head + ", tail=" + tail + ")";
  }

  public static void main(String[] args) {
    CircularBuffer<String> b = new CircularBuffer<String>(3);
    for (int i = 0; i < 10; i++) {
        System.out.println("Start: " + b);
        b.add("One");
        System.out.println("One: " + b);
        b.add("Two");
        System.out.println("Two: " + b);
        System.out.println("Got '" + b.get() + "', now " + b);

        b.add("Three");
        System.out.println("Three: " + b);
        // Test Overflow
        // b.add("Four");
        // System.out.println("Four: " + b);

        System.out.println("Got '" + b.get() + "', now " + b);
        System.out.println("Got '" + b.get() + "', now " + b);
        // Test Underflow
        // System.out.println("Got '" + b.get() + "', now " + b);

        // Back to start, let's shift on one
        b.add("Foo");
        b.get();
    }
  }
}

Understand Ring Buffer in async Logger

The number of slots in the ringbuffer needs to be a power of 2. This allows you to keep incrementing the counter and use a bitmask instead of modulo to get the array index from the counter.

For example, suppose we have a ringbuffer of size 4. Indexes 0 to 3 are valid indexes into the array. We want to avoid checking index++; if (index > 3) { index = 0; }. In a tight loop this if check can slow things down. Can we avoid it?

Yes we can. We can just increment without checking, and when we get a value from the array we ignore all multiples of 4 (the size of the array). Often people use the modulo operation for this: value = array[index % 4];

3 % 4 = 3
4 % 4 = 0
5 % 4 = 1
...

This works fine, but we can do better. The modulo operation works for any array size, but we chose the array size to be a power of two for a reason: bit masks! A bit mask can achieve the same thing, but much, much faster (about 25 times as fast).

How does this work? If the array is a power of two, we get its bit mask by subtracting one. We then use this mask when getting values from the array: value = array[index & mask];

For 4, the bit mask is 4-1=3. 3 in binary notation is 11. Let’s look at the same example as before:

0011 & 0011 = 0011 (3 & 3 = 3)
1000 & 0011 = 0000 (4 & 3 = 0)
1001 & 0011 = 0001 (5 & 3 = 1)
...

So this does the same as taking the modulo but faster. Again, key point is that the array needs to be a multiple of 2.

Back to the question: The actual number of slots in the ringbuffer is 262144. The documentation states 256 * 1024 to clarify that this is a power of 2.

Circular buffer implementation in Android

In Android development first preference is to use Java rather than C for implementing these things. Ofcourse you can do that in C (using JNI) but that requires certain overheads i.e. you need to implement your own garbage collection logic along with the code of circular buffer whereas in Java this can be achieved automatically. . See below class if it works for your case..

import java.nio.BufferOverflowException;
import java.nio.BufferUnderflowException;

public class CustomCircularBuffer<T> {

  private T[] buffer;

  private int tail;

  private int head;

  public CustomCircularBuffer(int n) {
    buffer = (T[]) new Object[n];
    tail = 0;
    head = 0;
  }

  public void add(T toAdd) {
    if (head != (tail - 1)) {
        buffer[head++] = toAdd;
    } else {
        throw new BufferOverflowException();
    }
    head = head % buffer.length;
  }

  public T get() {
    T t = null;
    int adjTail = tail > head ? tail - buffer.length : tail;
    if (adjTail < head) {
        t = (T) buffer[tail++];
        tail = tail % buffer.length;
    } else {
        throw new BufferUnderflowException();
    }
    return t;
  }

  public String toString() {
    return "CustomCircularBuffer(size=" + buffer.length + ", head=" + head + ", tail=" + tail + ")";
  }
}

Here are some other useful links which can give necessary explanations ..

Example

Another Example

In Depth Article