Fast ring-buffer deque (double-ended queue)

deque

Build Status Go Report Card codecov License

Fast ring-buffer deque (double-ended queue) implementation.

GoDoc

For a pictorial description, see the Deque diagram

Installation

$ go get github.com/gammazero/deque

Deque data structure

Deque generalizes a queue and a stack, to efficiently add and remove items at either end with O(1) performance. Queue (FIFO) operations are supported using PushBack() and PopFront(). Stack (LIFO) operations are supported using PushBack() and PopBack().

Ring-buffer Performance

This deque implementation is optimized for CPU and GC performance. The circular buffer automatically re-sizes by powers of two, growing when additional capacity is needed and shrinking when only a quarter of the capacity is used, and uses bitwise arithmetic for all calculations. Since growth is by powers of two, adding elements will only cause O(log n) allocations.

The ring-buffer implementation improves memory and time performance with fewer GC pauses, compared to implementations based on slices and linked lists. By wrapping around the buffer, previously used space is reused, making allocation unnecessary until all buffer capacity is used. This is particularly efficient when data going into the dequeue is relatively balanced against data coming out. However, if size changes are very large and only fill and then empty then deque, the ring structure offers little benefit for memory reuse. For that usage pattern a different implementation may be preferable.

For maximum speed, this deque implementation leaves concurrency safety up to the application to provide, however the application chooses, if needed at all.

Reading Empty Deque

Since it is OK for the deque to contain a nil value, it is necessary to either panic or return a second boolean value to indicate the deque is empty, when reading or removing an element. This deque panics when reading from an empty deque. This is a run-time check to help catch programming errors, which may be missed if a second return value is ignored. Simply check Deque.Len() before reading from the deque.

Example

package main

import (
    "fmt"
    "github.com/gammazero/deque"
)

func main() {
    var q deque.Deque
    q.PushBack("foo")
    q.PushBack("bar")
    q.PushBack("baz")

    fmt.Println(q.Len())   // Prints: 3
    fmt.Println(q.Front()) // Prints: foo
    fmt.Println(q.Back())  // Prints: baz

    q.PopFront() // remove "foo"
    q.PopBack()  // remove "baz"

    q.PushFront("hello")
    q.PushBack("world")

    // Consume deque and print elements.
    for q.Len() != 0 {
        fmt.Println(q.PopFront())
    }
}

Uses

Deque can be used as both a:

  • Queue using PushBack and PopFront
  • Stack using PushBack and PopBack
Comments
  • Feature request: Add search, delete,

    Feature request: Add search, delete, "insert after" functionality

    In my use case I PushBack 99% of the time, but sometimes I wish to insert an element after a specific other one. O(n) performance would be fine. Search for and deleting an element would also be a fine addition. May I ask for these functions, pretty please? :)

  • Add Set and Copy methods

    Add Set and Copy methods

    This is adding the Set() and Copy() methods with the same intent as At(): to be able to use deque as a more general purpose circular buffer (similar to deque in C++). Please comment and/or merge.

  • Returns zero and loses messages

    Returns zero and loses messages

    Hey Andrew,

    Can you tell me what I'm doing wrong? From time to time the PopFront method returns nil, and some messages get lost?

    Thank you!

    package somepackage
    
    import (
    	"sync"
    	"testing"
    	"time"
    
    	"github.com/gammazero/deque"
    	"github.com/google/uuid"
    	"github.com/jpillora/backoff"
    )
    
    func Test(t *testing.T) {
    	dq := deque.New[*string]()
    
    	count := 15000
    
    	m := make([]*string, 0, count)
    
    	wg := sync.WaitGroup{}
    	wg.Add(2)
    
    	go func() {
    		for i := 0; i < count; i++ {
    			if i%3000 == 0 {
    				b := &backoff.Backoff{
    					Factor: 2,
    					Min:    time.Second * 2,
    					Max:    time.Second * 10,
    				}
    
    				time.Sleep(b.Duration())
    			}
    
    			s := uuid.New().String()
    			dq.PushBack(&s)
    		}
    
    		wg.Done()
    	}()
    
    	go func() {
    		for {
    			if len(m) == count {
    				break
    			}
    
    			if dq.Len() == 0 {
    				continue
    			}
    
    			s := dq.PopFront()
    			if s == nil {
    			} // sometime it's true
    
    			m = append(m, s)
    		}
    		wg.Done()
    	}()
    
    	wg.Wait()
    }
    
  • Add a method to Test whether container is empty

    Add a method to Test whether container is empty

    Feature Request

    This function returns whether the deque container is empty (i.e. whether its size is 0) or not.

    This function does not modify the container in any way.

    • Parameters none

    • Return Value true if the container size is 0, false otherwise.

    Ref

    https://www.cplusplus.com/reference/deque/deque/empty/

  • Fix Clear not zeroing items when buffer full

    Fix Clear not zeroing items when buffer full

    When the deque buffer is full Clear was not zeroing the items in it. This fixes that problem.

    Additional changes:

    • New out of range panic messages
    • Minor document spelling and formatting fixes
  • Use generics to define Deque instance for a type

    Use generics to define Deque instance for a type

    Deque uses generics to create a Deque that contains items of the type specified. To create a Deque that holds a specific type, provide a type argument to New or with the variable declaration.

    This is a breaking change.

  • Add Index, Insert, and Remove functions

    Add Index, Insert, and Remove functions

    This allows items to be searched, inserted, and removed from the middle of the deque. These operations are O(n), unlike the O(1) operations on the ends of the deque.

    Addresses Issue #19

  • Allow Len and Cap to work with nil Deque

    Allow Len and Cap to work with nil Deque

    This is similar to calling these on a nil slice or map. This allows a nil Deque to work like an empty Deque for operations that work with an empty Deque.

  • codecov in .travis.yml - security issue

    codecov in .travis.yml - security issue

    Good day, https://codecov.io/bash recently outputted a security issue. Details can be found at https://about.codecov.io/security-update/

    The following file and code are impacted. Please follow the recommended actions in the link above to secure your env and code integrity. file: .travis.yml Code: after_success:

    bash <(curl -s https://codecov.io/bash)

  • Add Set method

    Add Set method

    This is adding the Set() method with the same intent as At(): to be able to use deque as a more general purpose circular buffer (similar to deque in C++). Please comment and/or merge.

    The request removed the Copy method from #8 .

  • New func to specify minimum capacity

    New func to specify minimum capacity

    A larger minimum capacity can be specified to avoid buffer resizing in cases where the size frequently grows and shrinks across a wide range.

    Add module support

  • Benefits of this library?

    Benefits of this library?

    What's the advantage, if any, of using this in place of standard slice?

    Taken from Marwan Burelle's example on SO:

    queue := make([]int, 0)
    // Push to the queue
    queue = append(queue, 1)
    // Top (just get next element, don't remove it)
    x = queue[0]
    // Discard top element
    queue = queue[1:]
    // Is empty ?
    if len(queue) == 0 {
        fmt.Println("Queue is empty !")
    }
    

    Does deque offer any benchmarks comparing it to standard slice implementations?

Fast golang queue using ring-buffer

Queue A fast Golang queue using a ring-buffer, based on the version suggested by Dariusz Górecki. Using this instead of other, simpler, queue implemen

Jan 3, 2023
Double-ARray Trie System for golang

Darts This is a GO implementation of Double-ARray Trie System. It's a clone of the C++ version Darts can be used as simple hash dictionary. You can al

Nov 17, 2022
Hairetsu: a TRIE implementation by double array

hairetsu hairetsu is a TRIE implementation by double array. alpha quality : thin

Mar 20, 2022
Package ring provides a high performance and thread safe Go implementation of a bloom filter.

ring - high performance bloom filter Package ring provides a high performance and thread safe Go implementation of a bloom filter. Usage Please see th

Nov 20, 2022
Protocol Buffer compiler written in Go

gotoc This is gotoc, a protocol buffer compiler written in Go. This is only the parser side; you will need a plugin to generate code. Quick Start go g

Nov 29, 2022
Go concurrent-safe, goroutine-safe, thread-safe queue
Go concurrent-safe, goroutine-safe, thread-safe queue

goconcurrentqueue - Concurrent safe queues The package goconcurrentqueue offers a public interface Queue with methods for a queue. It comes with multi

Dec 31, 2022
go.fifo provides a simple fifo thread-safe queue for the Go programming language

go.fifo Description go.fifo provides a simple FIFO thread-safe queue. *fifo.Queue supports pushing an item at the end with Add(), and popping an item

Aug 29, 2022
Simple priority queue in Go

Priority Queue in Go ==================== This package provides a priority queue implementation and scaffold interfaces. Installation ------------ U

Apr 5, 2022
High-performance minimalist queue implemented using a stripped-down lock-free ringbuffer, written in Go (golang.org)

This project is no longer maintained - feel free to fork the project! gringo A high-performance minimalist queue implemented using a stripped-down loc

Oct 24, 2022
A Go queue manager on top of Redis

Queue A Go library for managing queues on top of Redis. It is based on a hiring exercise but later I found it useful for myself in a custom task proce

Aug 12, 2022
Cross-platform beanstalkd queue server admin console.
Cross-platform beanstalkd queue server admin console.

Overview aurora is a web-based Beanstalkd queue server console written in Go and works on macOS, Linux, and Windows machines. The main idea behind usi

Dec 30, 2022
Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time.

vEB Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time. Supports the following

Mar 7, 2022
Go native library for fast point tracking and K-Nearest queries

Geo Index Geo Index library Overview Splits the earth surface in a grid. At each cell we can store data, such as list of points, count of points, etc.

Dec 3, 2022
Fast in-memory key:value store/cache with TTL

MCache library go-mcache - this is a fast key:value storage. Its major advantage is that, being essentially a thread-safe . map[string]interface{} wit

Nov 11, 2022
Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.

Trie Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching. Usage Create a Trie with: t := trie.New() Add Keys with:

Dec 27, 2022
Fast and easy-to-use skip list for Go.

Skip List in Golang Skip list is an ordered map. See wikipedia page skip list to learn algorithm details about this data structure. Highlights in this

Dec 4, 2022
A fast little LRU cache for Go

tinylru A fast little LRU cache. Getting Started Installing To start using tinylru, install Go and run go get: $ go get -u github.com/tidwall/tinylru

Dec 24, 2022
Fast Raft framework using the Redis protocol for Go
Fast Raft framework using the Redis protocol for Go

This project has been archived. Please check out Uhaha for a fitter, happier, more productive Raft framework. Finn is a fast and simple framework for

Oct 10, 2022
Go implementation of SipHash-2-4, a fast short-input PRF created by Jean-Philippe Aumasson and Daniel J. Bernstein.

SipHash (Go) Go implementation of SipHash-2-4, a fast short-input PRF created by Jean-Philippe Aumasson and Daniel J. Bernstein (http://131002.net/sip

Dec 25, 2022