github.com/lithdew/seq

seq

A fast implementation of sequence buffers described in this blog post by Glenn Fiedler in Go with 100% unit test coverage.

This was built for the purpose of creating reliable UDP networking protocols, where sequence buffers may be used as an efficient, resilient, fixed-sized rolling buffer for:

• tracking metadata over sent/received packets,
• ordering packets received from an unreliable stream, or
• tracking acknowledgement over the recipient of sent packets from peers.

The sequence numbers used to buffer entries are fixed to be unsigned 16-bit integers, as larger amounts of entries are redundant and would provide a negligible improvement to your packet acknowledgement system.

Notes

The size of the buffer must be divisible by the max value of an unsigned 16-bit integer (65536), otherwise data buffered by sequence numbers would not wrap around the entire buffer. This was encountered while writing tests for this library.

The method RemoveRange was benchmarked and optimized over the sequence buffer implementation in the reference C codebase reliable.io to use a few memcpy calls over for loops.

The actual sequences and buffered data are stored in two separate, contiguous slices so that entries that have popped from the rolling buffer will remain as stale memory that may optionally be garbage-collected later.

Setup

go get github.com/lithdew/seq

Benchmarks

$ go test -bench=. -benchtime=10s
goos: linux
goarch: amd64
pkg: github.com/lithdew/seq
BenchmarkTestBufferInsert-8                     327525945               35.6 ns/op             0 B/op          0 allocs/op
BenchmarkTestBufferRemoveRange-8                243091503               51.3 ns/op             0 B/op          0 allocs/op
BenchmarkTestBufferGenerateBitset32-8           84982886               137 ns/op               0 B/op          0 allocs/op