Skip to content

blues/safequeue

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

2 Commits
 
 
 
 
 
 
 
 

Repository files navigation

One of the amazing benefits of golang's "chan" structure is that it is a lock-free and highly-efficient for multiple goroutines to implement a queue. One of the downsides, however, is that these queues must be allocated as fixed-length data structures, and the enqueuer will bloc if/when enqueueing if the channel fills up. This typically results in developers just doing a wild-ass guess as to how many will be queueud, ignoring the overall system performance implications of what happens when the channel fills up and the enqueuer blocks.

In a situation where there are an extremely large number of concurrent queues, the developer is thus encouraged to minimize the channel size so as to be conservative about use of heap. On the other hand, we may need to deal with very high bursts of enqueueing on a statistically small number of channels, and so the reduced size of those channels will cause bad system behavior.

This package implements a super-efficient "infinite length channel". It preserves and stands on the shoulders of 'chan' semantics for timeout handling and for wait/signal, and yet (critically) it implements the queue using the careful head/tail manipulation mechanisms of Michael & Scott's classic concurrent lock-free queue algorithm, however it deviates from that algorithm (which would 'spin') by using a simple 1-entry golang chan for timeout and blocking. https://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf

Because of the recurring challenges in creating and 'winding down' queues, this code also supports the concept of synchronously deleting the queue by internally using the 'nil' object as a signal that the queue has been deleted and will no longer be used.

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages