Fast golang queue using ring-buffer

Overview

Queue

Build Status GoDoc Code of Conduct

A fast Golang queue using a ring-buffer, based on the version suggested by Dariusz Górecki. Using this instead of other, simpler, queue implementations (slice+append or linked list) provides substantial memory and time benefits, and fewer GC pauses.

The queue implemented here is as fast as it is in part because it is not thread-safe.

Follows semantic versioning using https://gopkg.in/ - import from gopkg.in/eapache/queue.v1 for guaranteed API stability.

Comments
  • Suggest Pop() function

    Suggest Pop() function

    This is useful to clear the queue in such a way that does not cause GC, particularly when the queue will be refilled by a similar number of items than it was previously.

    opened by gammazero 6
  • Threadsafe Queue Implementation

    Threadsafe Queue Implementation

    Now for what I originally came here for ;)

    Added a very basic threadsafe implementation of the queue, which surprisingly doesn't have too huge a performance overhead. This is dependent on my previous two PRs (prevent merge conflicts, if they're accepted), but if you want to merge this but not those two, I'll resubmit a version without those changes.

    ➜  queue git:(pop) ✗ go test -bench=.
    PASS
    BenchmarkQueueSerial     10000000          334 ns/op
    BenchmarkQueueGet        50000000         29.7 ns/op
    BenchmarkQueueTickTock   30000000         56.3 ns/op
    BenchmarkTsQueueSerial   2000000           651 ns/op
    BenchmarkTsQueueGet      10000000          204 ns/op
    BenchmarkTsQueueTickTock 3000000           585 ns/op
    ok      github.com/connor4312/queue 36.370s
    
    opened by connor4312 6
  • Add a mean to get an index, allowing iterations of the queue.

    Add a mean to get an index, allowing iterations of the queue.

    With this change, one can iterate over the queue:

    for i := 0; i < q.Length(); i++ {
        if q.Get(i).(int) != i {
            t.Errorf("index %d doesn't contain %d", i, i)
        }
    }
    

    Tests output:

    $ go test -v 
    === RUN TestQueueLength
    --- PASS: TestQueueLength (0.00 seconds)
    === RUN TestQueueGet
    --- PASS: TestQueueGet (0.01 seconds)
    === RUN TestQueueGetOORPanic
    --- PASS: TestQueueGetOORPanic (0.00 seconds)
        queue_test.go:51: got panic as expected: index out of range
        queue_test.go:65: got panic as expected: index out of range
    PASS
    ok      github.com/eapache/queue    0.022s
    
    opened by aybabtme 4
  • Use errors instead of panic?

    Use errors instead of panic?

    Putting this up for discussion: public package api in go should rather use errors than panics. Would it make sense to have a 2.0 release implementing this approach?

    opened by andig 3
  • Get() allows negative index.  Use modular math for speed.  Add Pop() …

    Get() allows negative index. Use modular math for speed. Add Pop() …

    …and Clear() methods and unit tests.

    Please consider the changes proposed in this PR, as I have found them to be useful extensions of queue, and would like offer them for inclusion in your code base if you find any or all of them useful/acceptable.

    • Negative indexing for Get() is very useful in some cases.
    • Benchmarking shows that modular math makes implementation slightly faster.
    • Pop() is sometimes useful instead of separate Peek() and Remove(), and when a preceeding check for empty queue is not wanted.
    • Clear() is useful for emptying the queue without provoking GC due to capacity resizing.
    opened by gammazero 3
  • Pop

    Pop

    Probably the most common means to consume a queue is popping off the first element -- removing and returning the head -- so I added a helper method called Pop() which does just that.

    Depends on my previous #6, and is partly build for #8 so that we only need to acquire a single lock for common use cases.

    opened by connor4312 3
  • Return an error rather than panicking on a bad request.

    Return an error rather than panicking on a bad request.

    It's considered much more idiomatic to return errors rather than panicking if something goes wrong. It might actually be dangerous to panic here... the expectation is that if there's a possiblity for an error, an error will be returned. If consumers don't see that an error is returned, they may simply assume nil is returned on an invalid request, and applications will burn...

    Unfortunately this is not a backwards-compatible change.

    opened by connor4312 3
  • new release?

    new release?

    Some useful things have landed since last tag, time for a new release so that dep and similar will grab them? AFAICS should be tagged v1.1.0 since Remove changed api (in backwards compatible way).

    opened by mmlb 2
  • Adding code to run on Powersystem

    Adding code to run on Powersystem

    Hi Here is my contribution to your code, its working good on powersystems. Tested with latest version of GO .

    Thanks for the code, its working good.

    What do these changes do?

    Added Architecture "ppc64le"

    Are there changes in behavior for the user?

    No

    opened by genisysram 1
  • Remove() returns item removed.

    Remove() returns item removed.

    The reason I am suggesting this change is because for many of my uses of queue, I remove an item in each iteration of a loop:

    for q.Length() > 0 {
        x := q.Remove()
        ...
    

    Only in some cases (e.g. your channels) do I find a need to do a Peek() and remove separately.

    opened by gammazero 1
  • Get() accepts negative index.

    Get() accepts negative index.

    Allow caller to retrieve items from the queue by specifying the number of places from the tail. Using Get(0) and Get(-1) is equivalent to Head() and Tail() often found in other queue implementations.

    opened by gammazero 1
Releases(v1.1.0)
  • v1.1.0(Nov 21, 2017)

    • Get() now accepts negative indices to index from the back of the queue
    • Remove() now returns the element removed so you don't have to call Peek() first
    • minor performance improvements via some bitwise math
    Source code(tar.gz)
    Source code(zip)
Owner
Evan Huus
Amateur musician and actor. Trying to end up with the right regrets.
Evan Huus
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

Tanner Ryan 130 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

David Symonds 119 Nov 29, 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

Darren Elwood 129 Oct 24, 2022
A highly optimized double-ended queue

Overview Deque is a highly optimized double-ended queue. Benchmark Benchmark_PushBack/Deque<harden> 100000000 10.3 ns/op 9 B/op

Edwin 91 Dec 1, 2022
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

Enrique Bris 225 Nov 26, 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

Foize 42 Aug 29, 2022
Simple priority queue in Go

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

Kris Kovalik 14 Apr 5, 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

Kaveh Mousavi Zamani 74 Aug 12, 2022
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

null 569 Nov 24, 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

null 4 Mar 7, 2022
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

Josh Baker 543 Oct 10, 2022
A fast (5x) string keyed read-only map for Go - particularly good for keys using a small set of nearby runes.

faststringmap faststringmap is a fast read-only string keyed map for Go (golang). For our use case it is approximately 5 times faster than using Go's

The Sensible Code Company 29 Nov 11, 2022
go/golang: fast bit set Bloom filter

package implements a fast bloom filter with real 'bitset' and JSONMarshal/JSONUnmarshal to store/reload the Bloom filter.

Andreas Briese 125 Nov 3, 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.

Hailo Network IP Ltd 344 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

O.J 86 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:

Derek Parker 616 Dec 2, 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

Huan Du 304 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

Josh Baker 129 Nov 29, 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

Dmitry Chestnykh 245 Dec 3, 2022