priorityq/README.md

# 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