go-queue/README.md

Queue data structure for Go

I was hacking a breadth-first search in Go and needed a queue but all I could find in the standard library was container/list.

Now in principle there's nothing wrong with container/list, but I had just admonished my students to always carefully think about the number of memory allocations their programs make. In other words, it felt a bit wrong for me to use a data structure that will allocate memory for every single vertex we visit during a breadth-first search.

So I quickly hacked a simple queue on top of a slice and finished my project. Now I am trying to clean up the code I wrote to give everybody else what I really wanted the standard library to have: A queue abstraction that doesn't allocate memory on every single insertion.

I am trying to stick close to the conventions container/list seems to follow even though I disagree with several of them.

Latest Performance Comparison

The benchmarks are not very sophisticated yet but it seems that we rather clearly beat container/list on the most common operations.

$ go test -bench . -benchmem -cover
PASS
BenchmarkPushFrontQueue	20000000	       191 ns/op	      53 B/op	       0 allocs/op
BenchmarkPushFrontList	10000000	       290 ns/op	      49 B/op	       1 allocs/op
BenchmarkPushBackQueue	10000000	       171 ns/op	      53 B/op	       0 allocs/op
BenchmarkPushBackList	 5000000	       305 ns/op	      49 B/op	       1 allocs/op
BenchmarkRandomQueue	 5000000	       418 ns/op	      26 B/op	       0 allocs/op
BenchmarkRandomList	 2000000	       799 ns/op	      78 B/op	       1 allocs/op
coverage: 84.1% of statements
ok  	github.com/phf/go-queue	17.092s