Implementing Fixed-Size Ring Buffer Data Structures in Go

Ring Buffer Queue is a fixed size memory FIFO (first in, first out) data structure that is used to handle data exchange before different processes. It works by using two pins (head/tail) to determine where to put the data now in a continuous fixed size interval of memory. This article will take you through a quick implementation of the Ring Buffer data structure in Go.

Usage Timing

Since Queue is a fixed size, it is very useful in the embedded system field. Especially when the memory is very small, it is very careful to use it, so developers usually declare a fixed size to store data instead of using dynamic allocation to avoid running out of system memory.

It is important to know that this data structure also has a limit, a fixed size Queue, eventually will encounter data full when what to do, there are two ways, the first is to discard the latest data, the other is to continue to write the latest data into the old memory segment.

Principle of practical work

From the Wiki, we see this animation below.

Circular_buffer

As you can see from the above diagram, the following members are required in the data structure

buf: Content storage format
capacity: fixed size (length)
head: refers to the data taken out from the Buffer (start)
tail: points to save data from Buffer (end)

The API implementation details require the following four functions

Enqueue: Putting data into Queue
Dequeue: Read data from Queue
IsEmpty: Determine if there is data in the Queue
IsFull: Determines if the Queue is full.

How to implement

Based on the above data structure, you can declare the following in Go language.

type T interface{}

type CircularBuffer struct {
  sync.Mutex
  taskQueue []T
  capacity  int
  head      int
  tail      int
}

IsEmpty, if head and tail have the same value, then it is empty. After the data structure is initialized, both head and tail will be zero.

1
2
3

func (s *CircularBuffer) IsEmpty() bool {
  return s.head == s.tail
}

The implementation determines whether IsFull is full and cannot write data. When new data is written, the tail will be +1, while the head will remain unchanged. When Queue writes to the last space, tail + 1 will be equal to the head value, and since it is a Ring structure, you need to divide by capacity to get the remainder. Please note here that since we need to calculate whether it is full or not, we need to waste a position to confirm.

1
2
3

func (s *CircularBuffer) IsFull() bool {
  return s.head == (s.tail+1)%s.capacity
}

Let’s assume that the buffer size is 4.

# Initialization
head: 0, tail: 0
# Write data
head: 0, tail: 1
# Write data
head: 0, tail: 2
# Write data
head: 0, tail: 3
# Queue has only three more
# IsFull() is already true

Next, see how to implement Enqueue and Dequeue.

func (s *CircularBuffer) Enqueue(task T) error {
  if s.IsFull() {
    return errMaxCapacity
  }

  s.Lock()
  s.taskQueue[s.tail] = task
  s.tail = (s.tail + 1) % s.capacity
  s.Unlock()

  return nil
}

func (s *CircularBuffer) Dequeue() (T, error) {
  if s.IsEmpty() {
    return nil, queue.ErrNoTaskInQueue
  }

  s.Lock()
  data := s.taskQueue[s.head]
  s.head = (s.head + 1) % s.capacity
  s.Unlock()

  return data, nil
}

You can see that the above code works the same way, Enqueue is tail+1 and Dequeue is head+1. Finally, the New function is added.

func NewCircularBuffer(size int) *CircularBuffer {
  w := &CircularBuffer{
    taskQueue: make([]T, size),
    capacity:  size,
  }

  return w
}

Verify the above code, below is the test code.

func TestQueue(t *testing.T) {
  size := 100
  q := NewCircularBuffer(size)

  for i := 0; i < (size - 1); i++ {
    assert.NoError(t, q.Enqueue(i+1))
  }
  // can't insert new data.
  assert.Error(t, q.Enqueue(0))
  assert.Equal(t, errFull, q.Enqueue(0))

  for i := 0; i < (size - 1); i++ {
    v, err := q.Dequeue()
    assert.Equal(t, i+1, v.(int))
    assert.NoError(t, err)
  }

  _, err := q.Dequeue()
  // no task
  assert.Error(t, err)
  assert.Equal(t, errNoTask, err)
}

Above you can see that the 100 size Slice is declared first, but only 99 size can be used, the 100th one will be stuffed with an error. Please refer to here for the code, and here for the test code.

Solve the waste of a single space

The above mentioned Ring buffer needs to waste a space to calculate Empty or Full. let’s see how to solve this problem, in fact it is very simple, add a full variable in the data structure to confirm whether the Queue is full.

type CircularBuffer struct {
  capacity  int
  head      int
  tail      int
+ full      bool
}

func (s *CircularBuffer) IsEmpty() bool {
- return s.head == s.tail
+ return s.head == s.tail && !s.full
}

func (s *CircularBuffer) IsFull() bool {
- return s.head == (s.tail+1)%s.capacity
+ return s.full
}

func (s *CircularBuffer) Enqueue(task T) error {
  s.Lock()
  s.taskQueue[s.tail] = task
  s.tail = (s.tail + 1) % s.capacity
+ s.full = s.head == s.tail
  s.Unlock()

  return nil
}

func (s *CircularBuffer) Dequeue() (T, error) {

  s.Lock()
  data := s.taskQueue[s.head]
+ s.full = false
  s.head = (s.head + 1) % s.capacity
  s.Unlock()

Performance Test

The test code is as follows.


func BenchmarkCircularBufferEnqueueDequeue(b *testing.B) {
  q := NewCircularBuffer(b.N)

  b.ReportAllocs()
  b.ResetTimer()
  for i := 0; i < b.N; i++ {
    _ = q.Enqueue(i)
    _, _ = q.Dequeue()
  }
}

func BenchmarkCircularBufferEnqueue(b *testing.B) {
  q := NewCircularBuffer(b.N)

  b.ReportAllocs()
  b.ResetTimer()
  for i := 0; i < b.N; i++ {
    _ = q.Enqueue(i)
  }
}

func BenchmarkCircularBufferDequeue(b *testing.B) {
  q := NewCircularBuffer(b.N)

  for i := 0; i < b.N; i++ {
    _ = q.Enqueue(i)
  }

  b.ReportAllocs()
  b.ResetTimer()
  for i := 0; i < b.N; i++ {
    _, _ = q.Dequeue()
  }
}

The results of the GitHub Action test are as follows.

goos: linux
goarch: amd64
pkg: github.com/go-training/training/example52-ring-buffer-queue
cpu: Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz
BenchmarkCircularBufferEnqueueDequeue
BenchmarkCircularBufferEnqueueDequeue-2     21792045          57.14 ns/op         7 B/op         0 allocs/op
BenchmarkCircularBufferEnqueue
BenchmarkCircularBufferEnqueue-2            34254517          37.20 ns/op         7 B/op         0 allocs/op
BenchmarkCircularBufferDequeue
BenchmarkCircularBufferDequeue-2            54213112          22.14 ns/op         0 B/op         0 allocs/op

Please refer here for the final code, and here for the test code

Ref

https://blog.wu-boy.com/2023/01/ring-buffer-queue-with-fixed-size-in-golang/

Table of Contents

Usage Timing

Principle of practical work

How to implement

Solve the waste of a single space

Performance Test

Ref