roundrobin

package module
v1.3.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 24, 2025 License: MIT Imports: 8 Imported by: 0

README

Go Reference GitHub release (with filter) GitHub License

go-roundrobin

Ring (Circular or Round-Robin) queue-like container with fixed memory footprint.

This brings great memories of decades ago when I worked in a high-tech European company writing telecommunications firmware. Back then C was a luxury and we had to mix C with Assembly to meet memory space (RAM & ROM) and timing requirements. We used a Round-Robin buffer in some part. Later, for fun, I spiced up the round-robin code with some features similar to what we see in this module.

NOTE: Despite what it says above that it is N commits behind Serge's repo, I have already fixed that here but in a different way. I will have to disconnect the reference because our repositories are quite different.

What a Ring Queue is and Why use it

So, what is a Ring Queue and why it's useful:

  1. It uses a static / fixed array buffer (no costly allocations)
  2. It does not shift elements on element removal (no costly memcopy)
  3. It can start anywhere in the buffer and loop over the end

img

Using go-roundrobin

To add it on your module or GO application:

go get https://github.com/lordofscripts/go-roundrobin

Then in your source code:

	import "lordofscripts/go-roundrobin"
The programming interface

While it has three different implementations, you decide which one is more suitable for your requirements. All three implementations comply with:

	type IRingQueue[T any] interface {
		fmt.Stringer
		io.Closer

		SetPopDeadline(t time.Time) error
		SetWhenFull(a WhenFull) IRingQueue[T]
		SetOnClose(callback OnCloseCallback[T]) IRingQueue[T]

		Size() int
		Cap() int

		Push(element T) (newLen int, err error)
		Pop() (element T, newLen int, err error)
		Peek() (element T, len int, err error)

		Reset()
	}

If you plan to use it with Go Routines, or need to specify onClose actions and define behaviors for Full and Empty queues, or even set a deadline for a blocking Pop operation:

	const CAPACITY int = 100
	var intCallback roundrobin.OnCloseCallback[int] = somefunctionOrMethod
	intRingbuffer := roundrobin.NewSafeRingBuffer[int](CAPACITY, WhenFullError, WhenEmptyBlock, intCallback)
	intRingbuffer.SetPopDeadline(time.Now().Add(5 * time.Second))

	charRingbuffer := roundrobin.NewSafeRingBuffer[rune](CAPACITY, WhenFullOverwrite, WhenEmptyError, nil)

If you don't need any of the extra features (full/empty behavior, close callback, thread-safe, etc.):

	const CAPACITY int = 100
	intRingbuffer := roundrobin.NewRingBuffer[int](CAPACITY)
	charRingbuffer := roundrobin.NewRingBuffer[rune](CAPACITY)

And in the remote case you need something suitable for characters/runes whether single or multi-byte, not for concurrent use but with the ability to have a user-defined behavior when the buffer is full:

	const CAPACITY int = 100
	charRingbuffer := roundrobin.NewRuneRingBuffer(CAPACITY).
			SetWhenFull(WhenFullOverwrite)  // not required!
Improvements over original code

As you may have noticed, this is a forked repository from Serge. I was looking for something like that without the need to redesign the wheel, just improve it.

In this forked version, the original has been enhanced with a slightly different interface IRingQueue. So this repository is a hybrid between Serge's original, and Haddi's much improved version that introduced a change in the original signatures and the addition of a "safe" version that uses a synchronization mechanism.

Serge's wonderful implementation can be used with the NewRingQueue[T]() constructor. It has these features:

Muhammad's repository can be instantiated with the NewSafeRingQueue[T]() constructor. It brings in great new features:

  • Has a synchronization mechanism making it suitable for go-routines (multi-threaded).
  • The user can specify the behavior when Push() onto a full queue: WhenFullError or WhenFullOverwrite.
  • The user can specify the behavior when Pop() from an empty queue: WhenEmptyError or WhenEmptyBlock (block until data available).
  • The user can specify a callback to invoke when the Ring Queue is closed. Once closed all operations on it will fail. He added this to both his thread-safe version and the original thread-unsafe version. Additionally he backported the WhenFull feature into the original (thread-unsafe) version.
  • He introduced a generic interface implemented by both the single and multi-threaded versions.
  • Given that a Pop() on an empty queue may block (user-defined), he introduced a user-defined deadline.
  • Consolidated errors that are globally-defined
  • Has a bug in its Len() method though! which Serge already fixed after I filed an issue. Unfortunately, M. Hadi's repository has disabled issues.
  • I believe he also has a bug in his Push method that instead checks whenEmpty rather than whenFull, but again, there is no way to report problems with his code.

I needed a ring queue for runes only, and loved the benchmarking. I was curious about the performance differences between Serge's generics version, and a concrete rune version based entirely on his type, but without the generics. Then I discovered Muhammand's great enhancements and decided it would be nice to bring all together but adapted to my needs.

So, I, Lord of Scripts created this hybrid fork. My rune-specific type can be instantiated with the NewRuneRingQueue() constructor. While I didn't add great functionality other than adding a new (basic) type for curiosity, I also did this:

  • Added tests for different scenarios of WhenFull and WhenEmpty
  • Fixed several size issues from both Haddi's & Serge's code that returned the wrong size. I decided to use a thread-safe size counter instead of the unreliable size based on start/end comparisons (that bug remains in both their repos.)
  • I renamed the interface to IRingQueue[T any] and all three objects implement this interface.
  • RuneRingQueue is only suitable for single-threaded applications, like Serge's.
  • I simplified Muhammed's constructors without compromising functionality (see below).
  • I added the SetWhenFull(WhenFull) fluent API interface method.
  • I added the SetOnClose(func OnCloseCallback[T]) fluent API interface method.
  • Added Reset() which is handy when reusing a buffer of the same size
  • All sources use a standards template, sorry, it comes from my times working at Software Process Improvement and Standarization.
  • Refactored the tests so that they are split into several files depending on who implemented it.
  • Parallelized and modernized the Timing tests. Now they use a feature introduced in GO v1.24.

Performance

If you are interested, here are some benchmarks we ran on both the original code and the improved code.

RingQueue Performance

Do you like benchmarks? I love them, even though many cases they are non-exhaustive, relatively synthetic and might give a skewed view of reality :) So, let's see how our implementation performs against a simple Go array. Remember, what we're looking for is an array slow down due to excessive copying.

func BenchmarkRR(b *testing.B) {
	rr := NewRingQueue[int](100_000)

	for n := 0; n < b.N; n++ {
		if rr.IsFull() {
			rr.Pop()
		}
		rr.Push(n)
	}
}

func BenchmarkArray(b *testing.B) {
	var ar [100_000]int
	size := 0

	for n := 0; n < b.N; n++ {
		if size >= 100_000 {
			copy(ar[0:], ar[1:])
			size--
		}

		ar[size] = n
		size++
	}
}

Which one do you thing would be the fastest? 😉 Let's run it!

go test -bench=. -benchmem

Here's results on my Intel NUC Ubuntu Linux machine:

goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
BenchmarkRR-12          59798865                18.50 ns/op
BenchmarkArray-12        1000000             17321.00 ns/op
PASS

If I run the same test with just 10_000 queue size instead of 100_000:

goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
BenchmarkRR-12          57184480                18.65 ns/op
BenchmarkArray-12        1000000              1068 ns/op
PASS

Let's plot the relation of run times and queue lengths: img

On Lord of Script's old (2010) laptop

And old laptop from 2010 which works quite fine with Linux but it crawls to a halt with Windows 10 after they dumped zillions of bloatware and delayware to force people to buy new computers.

My system is an Intel i5-M430 with 4 cores at 2.27GHz instead of Serge's Intel i7 with 12 cores at 1.10GHz.

The benchmark on the specialized RuneRingQueue which spares you from the overhead of generics:

goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i5 CPU       M 430  @ 2.27GHz
BenchmarkRR-4          22,946,761                55.32 ns/op
BenchmarkArray-4        1,000,000              1,068 ns/op
PASS

Whereas the timing tests on a 100K Ring buffer using a plain array, the concrete Rune implementation (no generics) and the generics implementation respectively:

goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i5 CPU       M 430  @ 2.27GHz
TestSizes_Array        100K elements       116.96s
TestSizes_RuneConcrete 100K elements       0.055031723s
TestSizes_GenericRune  100K elements       0.060474519s
TestSizes_GenericInt   100K elements       0.055532279s
PASS

Documentation

Overview

----------------------------------------------------------------- * P u b l i c D o m a i n / F O S * Copyright (C)2025 Muhammad H. Hosseinpour, * Copyright (C)2025 Dídimo Grimaldo T. * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - * A generic interface to the RingQueue implementations (plain & safe) * offered by this GO module. *-----------------------------------------------------------------

----------------------------------------------------------------- * P u b l i c D o m a i n / F O S * Copyright (C)2023 Serge Toro, and * Copyright (C)2025 Muhammad H. Hosseinpour * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - * Serge Toro's original RingQueue with M. Hadi's enhancements. *-----------------------------------------------------------------

----------------------------------------------------------------- * P u b l i c D o m a i n / F O S * Copyright (C)2023 Serge Toro, and * Copyright (C)2025 Didimo Grimaldo * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - * A rune-specific version that does not have the overhead of generics. *-----------------------------------------------------------------

----------------------------------------------------------------- * P u b l i c D o m a i n / F O S * Copyright (C)2025 Muhammad H. Hosseinpour, * Copyright (C)2025 Dídimo Grimaldo T. * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - * M. Hadi's enhancements on the original RingQueue with my changes * to improve the constructor and implement new IRingQueue methods. *-----------------------------------------------------------------

----------------------------------------------------------------- * P u b l i c D o m a i n / F O S * Copyright (C)2023 Serge Toro, and * Copyright (C)2025 Muhammad H. Hosseinpour * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - * Serge Toro's original RingQueue with M. Hadi's enhancements. *-----------------------------------------------------------------

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrFullQueue   = fmt.Errorf("ring buffer is full")
	ErrEmptyQueue  = fmt.Errorf("ring buffer is empty")
	ErrClosed      = fmt.Errorf("ring buffer is closed")
	ErrBadDeadline = fmt.Errorf("deadline only possible for WhenEmptyBlock")
)

Functions

func NewSafeRingQueue 

func NewSafeRingQueue[T any](capacity int, whenFull WhenFull, whenEmpty WhenEmpty, onCloseFunc OnCloseCallback[T]) *safeRQ[T]

Types

type IRingQueue 

type IRingQueue[T any] interface {
	fmt.Stringer
	io.Closer

	SetPopDeadline(t time.Time) error
	SetWhenFull(a WhenFull) IRingQueue[T]
	SetOnClose(callback OnCloseCallback[T]) IRingQueue[T]

	Size() int
	Cap() int

	Push(element T) (newLen int, err error)
	Pop() (element T, newLen int, err error)
	Peek() (element T, len int, err error)

	Reset()
}

type OnCloseCallback 

type OnCloseCallback[T any] func(data T)

type RingQueue 

type RingQueue[T any] struct {
	// contains filtered or unexported fields
}

func NewRingQueue 

func NewRingQueue[T any](capacity int) *RingQueue[T]

func (*RingQueue[T]) Cap 

func (r *RingQueue[T]) Cap() int

func (*RingQueue[T]) Close 

func (r *RingQueue[T]) Close() error

@implement io.Closer

func (*RingQueue[T]) IsFull 

func (r *RingQueue[T]) IsFull() bool

func (*RingQueue[T]) Peek 

func (r *RingQueue[T]) Peek() (T, int, error)

func (*RingQueue[T]) Pop 

func (r *RingQueue[T]) Pop() (T, int, error)

func (*RingQueue[T]) Push 

func (r *RingQueue[T]) Push(elem T) (int, error)

func (*RingQueue[T]) Reset 

func (r *RingQueue[T]) Reset()

func (*RingQueue[T]) SetOnClose 

func (r *RingQueue[T]) SetOnClose(callback OnCloseCallback[T]) IRingQueue[T]

func (*RingQueue[T]) SetPopDeadline 

func (r *RingQueue[T]) SetPopDeadline(t time.Time) error

func (*RingQueue[T]) SetWhenFull 

func (r *RingQueue[T]) SetWhenFull(a WhenFull) IRingQueue[T]

func (*RingQueue[T]) Size 

func (r *RingQueue[T]) Size() int

func (*RingQueue[T]) String 

func (r *RingQueue[T]) String() string

@implements fmt.Stringer interface

type RuneRingQueue 

type RuneRingQueue struct {
	// contains filtered or unexported fields
}

*

  • A specialized version of the generics RingQueue[T]. First born out
  • of curiousity for the benchmark between this and the generic version,
  • and also because I was precisely looking for a rune ring buffer for
  • my pet project.

func NewRuneRingQueue 

func NewRuneRingQueue(capacity int) *RuneRingQueue

*

  • A specific (non-generic) Ring Queue to hold unicode runes.

func (*RuneRingQueue) Cap 

func (r *RuneRingQueue) Cap() int

func (*RuneRingQueue) Close 

func (r *RuneRingQueue) Close() error

*

  • Does nothing, simply complies with the interface.
  • @implement io.Closer

func (*RuneRingQueue) IsFull 

func (r *RuneRingQueue) IsFull() bool

func (*RuneRingQueue) Peek 

func (r *RuneRingQueue) Peek() (rune, int, error)

func (*RuneRingQueue) Pop 

func (r *RuneRingQueue) Pop() (rune, int, error)

func (*RuneRingQueue) Push 

func (r *RuneRingQueue) Push(elem rune) (int, error)

func (*RuneRingQueue) Reset 

func (r *RuneRingQueue) Reset()

func (*RuneRingQueue) SetOnClose 

func (r *RuneRingQueue) SetOnClose(callback OnCloseCallback[rune]) IRingQueue[rune]

*

  • Does nothing, simply complies with the interface.
  • @implement roundrobin.IRingQueue[rune]

func (*RuneRingQueue) SetPopDeadline 

func (r *RuneRingQueue) SetPopDeadline(t time.Time) error

*

  • Throws ErrUnsupported. Simply complies with the interface.
  • @implement roundrobin.IRingQueue[rune]

func (*RuneRingQueue) SetWhenFull 

func (r *RuneRingQueue) SetWhenFull(a WhenFull) IRingQueue[rune]

*

  • Sets the behaviour when pushing onto a full Ring Queue.
  • It can throw an error or overwrite old data.

func (*RuneRingQueue) Size 

func (r *RuneRingQueue) Size() int

func (*RuneRingQueue) String 

func (r *RuneRingQueue) String() string

@implements fmt.Stringer

type SafeCounter 

type SafeCounter struct {
	// contains filtered or unexported fields
}

func NewSafeCounter 

func NewSafeCounter() *SafeCounter

func (*SafeCounter) Clear 

func (c *SafeCounter) Clear()

func (*SafeCounter) Decrement 

func (c *SafeCounter) Decrement() int64

func (*SafeCounter) Increment 

func (c *SafeCounter) Increment() int64

func (*SafeCounter) IsZero 

func (c *SafeCounter) IsZero() bool

func (*SafeCounter) Value 

func (c *SafeCounter) Value() int64

type WhenEmpty 

type WhenEmpty int
const (
	WhenEmptyError WhenEmpty = iota
	WhenEmptyBlock
)

type WhenFull 

type WhenFull int
const (
	WhenFullError WhenFull = iota
	WhenFullOverwrite
)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.