lenshood / go-lock-free-ring-buffer Goto Github PK

This repo is an implementation of lock-free ring buffer built on Golang.

You can find more information about this implementation at my blog post.

Please note that v0.2.0 involved generics feature, which requires go version >= 1.18. Lower go version please choose v0.1.0.

Below is the API and how to use it:

type RingBuffer[T any] interface {
  Offer(T) (success bool)
  Poll() (value T, success bool)
}

We can simply call Offer() and Poll() to use it like a normal queue.

The GCShape introduced by generics feature can ensure that no heap memory allocation during Offer() and Poll(). Here is an article to explain the performance changes before and after involve generic.

When create an instance, say we want to use it to store string:

import (
  "github.com/LENSHOOD/go-lock-free-ring-buffer"
)

buffer := lfring.New[string](lfring.NodeBased, 16)

The first argument of New() is the type of ring buffer, I currently provide two implementations, they both have same behavior, but benchmark test shows that the "NodeBased" one has better performance.

The second argument capacity defines how big the ring buffer is, in consideration of different concrete type, the size of buffer maybe different. For instance, string has two underlying elements str unsafe.Pointer and len int, so if we build a buffer has capacity=16, the size of buffer array will be 16*(8+8)=256 bytes(64bit platform).

1. Two types of lock-free ring buffer compare with go channel in different capacities

2. Two types of lock-free ring buffer compare with go channel in different producers / consumers ratio

3. Two types of lock-free ring buffer compare with go channel in different threads

From above performance curve, we can see that ring buffer get better performance under some specific conditions. Below image clarifies the proper use scenario of ring buffer.

As the result, ring buffer fits better in the case of producers/consumers not balance, and capacity not too big.

Above images are screenshots, check full charts here.

• Try to optimize the performance of single producer/consumer performance

  • Based on the previous result, the ratio of production/consumption speed plays a partial key role to influence ordinary channel's performance. We can move one step forward, to do some optimization at such a special case of single producer/consumer.

  • Single means no contention, so the costly CAS operation may be replaced with normal operation, and single load/store may be replaced with vectorized load/store. Furthermore, once we say vectorization, we think introduce SIMD to accelerate load/store operations.