89 lines
3.6 KiB
Markdown
89 lines
3.6 KiB
Markdown
# priorityq - generic prioritized queues in Go
|
|
|
|
In Go, the builtin buffered channels provide a concurrent FIFO queue for
|
|
passing messages between goroutines. Sometimes, however, it's convenient to be
|
|
able to assign priority levels to messages, so that they get delivered to
|
|
consumers more promptly.
|
|
|
|
The `mq` package in this module implements a concurrent, dual-priority message
|
|
queue that guarantees receipt of a high-priority items before low-priority
|
|
ones. There is a pattern using two channels and select statements to achieve
|
|
similar functionality, but it's not exactly equivalent. (See the
|
|
[Background](#background) section for more details.)
|
|
|
|
Additionally, the `pq` package implements a concurrent, traditional priority
|
|
queue, using a binary max-heap. This is more general than `mq`, because it
|
|
allows multiple levels of priority. This, of course, also makes operations
|
|
slower.
|
|
|
|
Lastly, the `npq` package implements a concurrent, n-priority message queue.
|
|
It's similar to `mq`, except that it an arbitrary fixed number of priority
|
|
levels. It can have better performance than `pq` for several hundred levels.
|
|
|
|
## Benchmarks
|
|
|
|
Here are some benchmark results from running on a Mac Studio/M1 Ultra.
|
|
|
|
pkg: gogs.humancabbage.net/sam/priorityq/mq
|
|
Send-20 13.93n ± 0%
|
|
SendChan-20 13.19n ± 0%
|
|
Recv-20 13.64n ± 1%
|
|
RecvChan-20 13.29n ± 1%
|
|
ConcSendRecv-20 97.60n ± 1%
|
|
ConcSendRecvChan-20 171.8n ± 5%
|
|
HighContention-20 128.2n ± 0%
|
|
HighContentionChan-20 47.27n ± 0%
|
|
|
|
pkg: gogs.humancabbage.net/sam/priorityq/npq
|
|
Send-20 13.56n ± 0%
|
|
Recv-20 13.51n ± 0%
|
|
ConcSendRecv-20 176.3n ± 8%
|
|
HighContention-20 121.0n ± 0%
|
|
|
|
pkg: gogs.humancabbage.net/sam/priorityq/pq
|
|
Send-20 18.79n ± 1%
|
|
Recv-20 268.1n ± 3%
|
|
ConcSendRecv-20 199.2n ± 2%
|
|
HighContention-20 440.0n ± 1%
|
|
|
|
pkg: gogs.humancabbage.net/sam/priorityq/binheap
|
|
Insert-20 11.92n ± 0%
|
|
Extract-20 261.6n ± 2%
|
|
RepeatedInsertExtract-20 25.68n ± 1%
|
|
|
|
pkg: gogs.humancabbage.net/sam/priorityq/circ
|
|
Push-20 2.196n ± 1%
|
|
Pop-20 2.187n ± 0%
|
|
|
|
## Background
|
|
|
|
This module was inspired by [a reddit post][reddit] wherein /u/zandery23 asked
|
|
how to implement a prioritized message queue in Go. A fantastic solution was
|
|
[provided by /u/Ploobers][sol]. That's probably right for 99 out of 100 use
|
|
cases, but it's not completely precise.
|
|
|
|
Particularly, the second select block does not guarantee that an item from the
|
|
prioritized queue will be taken if there is also an item in the regular queue.
|
|
|
|
```go
|
|
select {
|
|
case job := <-mq.priorityQueue:
|
|
// ...
|
|
case job := <-mq.regularQueue:
|
|
// ...
|
|
// ...
|
|
}
|
|
```
|
|
|
|
From the [Go Language Specification][go_select]:
|
|
|
|
> If one or more of the communications can proceed, a single one that can
|
|
> proceed is chosen via a uniform pseudo-random selection.
|
|
|
|
Thus, it is possible for the second case to be chosen even if the first case is
|
|
also ready.
|
|
|
|
[reddit]: https://www.reddit.com/r/golang/comments/11drc17/worker_pool_reading_from_two_channels_one_chan/
|
|
[sol]: https://www.reddit.com/r/golang/comments/11drc17/worker_pool_reading_from_two_channels_one_chan/jabfvkh/
|
|
[go_select]: https://go.dev/ref/spec#Select_statements
|