Open-source project
Workiva/go-datastructures avatar
Workiva/go-datastructures

go-datastructures: a collection whose README admits several of its structures lose

A collection of useful, performant, and threadsafe Go datastructures.

7,969 stars851 forksGoApache-2.0

At a glance

What is it?
Workiva's go-datastructures holds 22 packages, from n-dimensional interval trees to X-Fast tries, in two dependencies and with a lot of self-criticism. Its priority queue is called somewhat slow, its skiplist is said to be often far worse than a balanced tree, its Fibonacci heap may lose to pairing heaps and is explicitly not thread-safe, and the stated Go floor is 1.3 while the manifest says 1.15.
Who is it for?
Use go-datastructures when you need a structure the standard library does not offer, most plausibly interval collision detection across n dimensions, a priority queue that never blocks on send, or a broadcast to many listeners, because those are the cases its own descriptions are written around.
Can I use it commercially?
Yes. Apache-2.0 is a permissive licence: you can use, modify and sell software built on it, as long as you keep its copyright and licence notices.
Is it still maintained?
Yes. The repository last received commits 45 days ago.
What is it written in?
Mainly Go, according to GitHub's language statistics.

Answers come from the project's GitHub data, last synced on November 15, 2026, and from our analysis. They are not legal advice.

From daily snapshots

Star history

  • Workiva/go-datastructures7,969 ★ · +10
Star history
Repository2026-09-222026-11-15
Workiva/go-datastructures8k8k

10 Stars in the last 54 days, measured from the daily GitHub snapshot. Compare with other projects

Editorial analysis

The README repeatedly says its own structures lose

The repository description calls the collection useful, performant and threadsafe. The per-package sections are considerably more cautious, and the honesty is the most useful thing in the file.

The priority queue is described as somewhat slow currently and targeted for an update to a Fibonacci heap.

The Fibonacci heap itself carries a warning that in practice the constant factors are large, so Fibonacci heaps could be slower than pairing heaps depending on usage.

The skiplist section is blunter: in testing, the performance of the skip list is often far worse than the guaranteed log n time of a BBST, because tall nodes cast shadows, particularly when large bitsizes are required.

And the fast integer hashmap draws a line rather than claiming victory. It is optimal up to a few million integers and faster than the native Golang implementation, and beyond that the native implementation is faster, with the author's guess that the native map uses a large-ary B-tree.

The consequence is that you cannot treat this as a performance library on the strength of the description. Read the section for the structure you actually want, because the useful information is the crossover point, and in four cases the README has already written it down for you.

Thread-safety is per package, and one package is excluded

The description says threadsafe in one word, and the packages do not agree.

The queue package includes an MPMC threadsafe ring buffer whose threadsafety is achieved using only CAS operations, making it quite fast, and the AVL tree is described as inherently threadsafe because any operation on a node makes a copy of that node's branch, though the writes will likely still need to be serialized. There is also a package literally named threadsafe, whose stated example is a threadsafe error, for setting an error in many threads at the same time, with the parenthetical that channels are slow.

Then there is the exception.

The Fibonacci heap section ends with a sentence that undoes the description: the heap has not been designed for thread-safety.

So the guarantee is per package, and one of the more prominent ones opts out.

There is a further wrinkle in the AVL tree, which is not thread-safety but mutability. It is an immutable branch-copy structure, described as an example and as a basis for a large number of functional data structures, good for many reads and infrequent writes because reads are highly available while writes are somewhat slow due to the copying.

The consequence is that you have to check the individual package rather than the repository. Nothing in the import path tells you which of these you are holding, and the one package where it matters most is the one that reads as safe by name.

Three Go versions across three files, and two dependencies

There is a support note at the very top of the README, and it is not a recent number.

Only tested with Go 1.3+.

Go 1.3 predates modules. The module manifest says something newer.

go
module github.com/Workiva/go-datastructures

go 1.15

And the container build pins a third version, on Alpine 3.13.

The consequence is that no two of the three agree, and the README's number is the one a reader meets first. In practice the manifest is what your toolchain reads, so 1.15 is the real floor and 1.3 is a historical artifact that has not been updated alongside the code.

The release record is current even so. The three most recent tags are v1.1.8 published on 2026-10-01, v1.1.7 on 2025-10-31 and v1.1.6 on 2025-09-02, and the last push to the repository was 2026-10-01, one second before that newest tag was published. So the latest release is the latest commit rather than a curated snapshot of it.

The manifest is also worth noting for its size. It requires two things: a test assertion library pinned at 1.7.0, and a MessagePack code generator. Nothing else, no hashing library, no ordered-map library and no external tree implementation, which fits a collection whose point is to show you the structure rather than wrap somebody else's. The generator is the unusual entry, because it implies at least one package emits serialisation code instead of asking you to hand-write it.

The Dockerfile stops at FROM scratch with nothing copied in

The container build is a GOPATH-era multi-stage file, and it does not finish.

dockerfile
FROM golang:1.16-alpine3.13 AS build-go

ARG GIT_SSH_KEY
ARG KNOWN_HOSTS_CONTENT
WORKDIR /go/src/github.com/Workiva/go-datastructures/
ADD . /go/src/github.com/Workiva/go-datastructures/

ARG GOPATH=/go/
ENV PATH $GOPATH/bin:$PATH
RUN echo "Starting the script section" && \
    go mod vendor && \
    echo "script section completed"

ARG BUILD_ARTIFACTS_DEPENDENCIES=/go/src/github.com/Workiva/go-datastructures/go.mod

FROM scratch

The final stage is `scratch`, which is an empty base image, and there is nothing after it. No `COPY --from`, no `ENTRYPOINT`, no compiled binary. Whatever this file was going to produce, as written it produces an image containing no files.

The rest of it also predates the module era it lives alongside. The working directory is a GOPATH-style path, the build step runs `go mod vendor`, and there are two build arguments for an SSH key and known-hosts content, which is the setup you need to fetch private dependencies over git rather than anything to do with this repository's own two dependencies.

The consequence is that this Dockerfile is not a supported way to build or test the library. Treat it as an abandoned artifact rather than as documentation, and use `go test` locally.

Twenty-two package directories, about fifteen README sections

The top level is one package directory per structure, plus a handful of files.

text
augmentedtree/
aviary.yaml
batcher/
bitarray/
btree/
cache/
common/
datastructures.go
documentation.md
fibheap/
futures/
go.mod
go.sum
graph/
hashmap/
list/
mock/
numerics/
queue/
rangetree/
rtree/
set/
slice/
sort/
threadsafe/
tree/
trie/

That is twenty-two directories. The visible README documents augmented trees, bitarrays, futures, queues, a Fibonacci heap, range trees, a set, a threadsafe package, an AVL tree, X-Fast and Y-Fast tries, a fast integer hashmap, a skiplist, a sort package and a numerics package.

So batcher, btree, cache, graph, list, mock, rtree, slice and tree do not correspond by name to any of those sections. Some of them are named in passing, since the Fast integer hashmap section mentions that a B-tree is the planned implementation for scale.

Two other files are worth noticing. `documentation.md` sits alongside the README as a second document, and `aviary.yaml` is a configuration file at the top level.

The consequence is that for packages without a matching README section, the package's own documentation is where you have to go.

Several packages are substitutes for textbook structures, and say so

Some of these are not the canonical implementation, and the README is upfront about which.

The range tree says it directly: not a typical range tree, as what is actually used is an n-dimensional sorted list of points, which proved simpler and faster than attempting a traditional range tree while saving space on any dimension greater than one. Its inserts are the usual balanced-tree times at O(log n^d) where d is the number of dimensions.

The AVL tree is labelled an example, built as a branch-copy immutable tree and presented as a basis for functional data structures.

The numerics package is described as early work on nonlinear optimization problems, allowing a simple use case with either linear or nonlinear constraints.

And the bitarray has a hard precondition worth knowing before you reach for it: entities must have a uint64 unique identifier. It offers a regular and a sparse implementation, where sparse saves a great deal of space but insertions are O(log n), plus fixed 32-bit and 64-bit bitmaps that give O(1) for everything by storing bits in unsigned integers rather than arrays.

The consequence is that the collection is better read as a set of solutions to specific problems than as a textbook. Several of these will not be what the name suggests, and the ones with preconditions, like the bitarray's identifier requirement, need checking before you design around them.

Set is the one section that points somewhere else

Most of the README describes what this repository offers. The Set section does the opposite, and it is the only place that happens.

The Set implementation is described as very simple, accepting items of type interface and including only a few methods. Then it tells you who to use instead: if your application requires a richer Set implementation over lists of type sort.Interface, see xtgo/set and goware/set.

Two named alternatives, both other people's repositories, and the condition for moving is specific: a richer interface over a sortable list.

The consequence is a useful signal about the rest of the collection. A maintainer who writes that sentence is telling you which packages are deliberate and which are minimal by choice, and it is the reason the plain Set is worth a paragraph at all.

It also tells you the shape of the trade in this repository generally. Almost everything here trades breadth for a specific property: a queue that never blocks on send and grows as necessary, a range query in n dimensions at the cost of not being a range tree, a skiplist without rotation complexity at the cost of the performance the README admits to. The Set section is the one where the trade is not worth taking, and it says so.

What this collection cannot do, and what it leaves you holding

Six limits, and most of them are stated in the README rather than discovered.

It cannot make the standard library faster. The integer hashmap says so past a few million entries, the skiplist section warns against its own performance, and the Fibonacci heap may lose to pairing heaps.

It cannot promise thread-safety as a collection-wide property. The Fibonacci heap has not been designed for it, and the AVL tree's thread-safety comes with writes that still need serialising.

It cannot be a drop-in for a general-purpose map or set. The integer hashmap is for integers within a known range, the bitarray requires a uint64 identifier, and the Set is minimal by design with two alternatives named.

It cannot tell you which Go version is right. Three files, three answers, and the first one a reader meets says 1.3.

It cannot be built with the container it ships. The Dockerfile ends at an empty scratch stage with no artefact copied into it.

And it does not document all of itself. Several of the twenty-two package directories, such as batcher, btree, cache and rtree, do not match any README section by name, which is a reason to read a package's own docs before depending on it.

Editorial conclusion

Use go-datastructures when you need a structure the standard library does not offer, most plausibly interval collision detection across n dimensions, a priority queue that never blocks on send, or a broadcast to many listeners, because those are the cases its own descriptions are written around. Do not reach for it expecting a drop-in speedup over the built-in maps and sorts, since its README repeatedly says the opposite for several of its structures and tells you where the crossover is. Before you pin a version, check three things. Thread-safety is a per-package property rather than a property of the collection, and the Fibonacci heap is explicitly excluded from it. The README claims testing only on Go 1.3 and later while go.mod declares 1.15 and the Dockerfile builds on 1.16. And several package directories, such as batcher, btree, cache and rtree, do not match any README section by name, so read the package before assuming it is documented.

Frequently asked questions

What data structures does go-datastructures provide?

Twenty-two packages, including augmented trees, bitarrays, futures, queues with a priority queue and an MPMC ring buffer, a Fibonacci heap, range trees, a set, a threadsafe package, an AVL tree, X-Fast and Y-Fast tries, a fast integer hashmap, a skiplist, a multithreaded bucket sort and a numerics package.

What is the purpose of Go, according to this collection?

The repository states a narrower purpose than the language: it is a collection of useful, performant and threadsafe Go datastructures, aimed at cases the standard library does not cover, such as interval collision detection in n dimensions, broadcast to many listeners, and a priority queue that never blocks on send.

Which of these structures is thread-safe?

It varies by package. The queue's MPMC ring buffer uses only CAS operations, the AVL tree is inherently threadsafe because operations copy branches, and there is a threadsafe package. The Fibonacci heap is the exception: the README says it has not been designed for thread-safety.

Does go-datastructures beat Go's built-in maps?

Not everywhere. The fast integer hashmap claims optimal performance up to a few million integers, faster than the native implementation, but says that beyond that the native implementation is faster. The README also says the skiplist is often far worse than a balanced tree's guaranteed log n, and that Fibonacci heaps could be slower than pairing heaps.

What Go version does go-datastructures need?

The README says only tested with Go 1.3 and later, go.mod declares go 1.15, and the Dockerfile builds on golang:1.16-alpine3.13. The newest release, v1.1.8, was published on 2026-10-01, one second after the last push to the repository.

Official sources

  1. Issues
  2. License: Apache-2.0
  3. README
  4. Releases
  5. Workiva/go-datastructures on GitHub
Add this badge to your README

If you maintain this project, the badge below links readers to this analysis and shows its maintenance status from the daily GitHub snapshot. Paste the markdown into your README; add ?metric=license or ?metric=stars to the image URL for a different field.

Add this badge to your README

markdown
[![Hysen Labs](https://hysenlabs.com/badge/workiva-go-datastructures.svg)](https://hysenlabs.com/projects/workiva-go-datastructures)

Star history chart for your README

markdown
[![Star history](https://hysenlabs.com/chart/workiva-go-datastructures.svg)](https://hysenlabs.com/projects/workiva-go-datastructures)

Was this useful?