Repository files navigation

Go-datastructures is a collection of useful, performant, and threadsafe Godatastructures.

Interval tree for collision in n-dimensional ranges. Implemented via ared-black augmented tree. Extra dimensions are handled in simultaneousinserts/queries to save space although this may result in suboptimal timecomplexity. Intersection determined using bit arrays. In a single dimension,inserts, deletes, and queries should be in O(log n) time.

Bitarray used to detect existence without having to resort to hashing withhashmaps. Requires entities have a uint64 unique identifier. Twoimplementations exist, regular and sparse. Sparse saves a great deal of spacebut insertions are O(log n). There are some useful functions on the BitArrayinterface to detect intersection between two bitarrays.

A helpful tool to send a "broadcast" message to listeners. Channels have theissue that once one listener takes a message from a channel the other listenersaren't notified. There were many cases when I wanted to notify many listenersof a single event and this package helps.

Package contains both a normal and priority queue. Both implementations neverblock on send and grow as much as necessary. Both also only return errors ifyou attempt to push to a disposed queue and will not panic like sending amessage on a closed channel. The priority queue also allows you to place itemsin priority order inside the queue. If you give a useful hint to the regularqueue, it is actually faster than a channel. The priority queue is somewhatslow currently and targeted for an update to a Fibonacci heap.

Also included in the queue package is a MPMC threadsafe ring buffer. This is ablock full/empty queue, but will return a blocked thread if the queue isdisposed while a thread is blocked. This can be used to synchronize goroutinesand ensure goroutines quit so objects can be GC'd. Threadsafety is acheivedusing only CAS operations making this queue quite fast. Benchmarks can be foundin that package.

Useful to determine if n-dimensional points fall within an n-dimensional range.Not a typical range tree however, as we are actually using an n-dimensionalsorted list of points as this proved to be simpler and faster than attempting atraditional range tree while saving space on any dimension greater than one.Inserts are typical BBST times at O(log n^d) where d is the number ofdimensions.

Self explanatory. Could be further optimized by getting the uintptr of thegeneric interface{} used and using that as the key as Golang maps handle thatmuch better than the generic struct type.

A package that is meant to contain some commonly used items but in a threadsafeway. Example: there's a threadsafe error in there as I commonly found myselfwanting to set an error in many threads at the same time (yes, I know, butchannels are slow).

This is an example of a branch copy immutable AVL BBST. Any operation on a nodemakes a copy of that node's branch. Because of this, this tree is inherentlythreadsafe although the writes will likely still need to be serialized. Thisstructure is good if your use case is a large number of reads and infrequentwrites as reads will be highly available but writes somewhat slow due to thecopying. This structure serves as a basis for a large number of functional datastructures.

An interesting design that treats integers as words and uses a trie structure toreduce time complexities by matching prefixes. This structure is really fastfor finding values or making predecessor/successor types of queries, but alsoresults in greater than linear space consumption. The exact time complexitiescan be found in that package.

An extension of the X-Fast trie in which an X-Fast trie is combined with someother ordered data structure to reduce space consumption and improve CRUD typesof operations. These secondary structures are often BSTs, but our implementionuses a simple ordered list as I believe this improves cache locality. We alsouse fixed size buckets to aid in parallelization of operations. Exact timecomplexities are in that package.

A datastructure used for checking existence but without knowing the bounds ofyour data. If you have a limited small bounds, the bitarray package might be abetter choice. This implementation uses a fairly simple hashing alogrithmcombined with linear probing and a flat datastructure to provide optimalperformance up to a few million integers (faster than the native Golangimplementation). Beyond that, the native implementation is faster (I believethey are using a large -ary B-tree). In the future, this will be implementedwith a B-tree for scale.

An ordered structure that provides amoritized logarithmic operations but withoutthe complication of rotations that are required by BSTs. In testing, however,the performance of the skip list is often far worse than the guaranteed log ntime of a BBST. Tall nodes tend to "cast shadows", especially when largebitsizes are required as the optimum maximum height for a node is often based onthis. More detailed performance characteristics are provided in that package.

The sort package implements a multithreaded bucket sort that can be up to 3xfaster than the native Golang sort package. These buckets are then merged usinga symmetrical merge, similar to the stable sort in the Golang package. However,our algorithm is modified so that two sorted lists can be merged by usingsymmetrical decomposition.

Early work on some nonlinear optimization problems. The initial implementationallows a simple use case with either linear or nonlinear constraints. You canfind min/max or target an optimal value. The package currently employs aprobablistic global restart system in an attempt to avoid local critical points.More details can be found in that package.

Initial implementation of a B+ tree. Delete method still needs added as well assome performance optimization. Specific performance characteristics can befound in that package. Despite the theoretical superiority of BSTs, the B-treeoften has better all around performance due to cache locality. The currentimplementation is mutable, but the immutable AVL tree can be used to build animmutable version. Unfortunately, to make the B-tree generic we require aninterface and the most expensive operation in CPU profiling is the interfacemethod which in turn calls into runtime.assertI2T. We need generics.

1. Install Go 1.3 or higher.
2. Rungo get github.com/Workiva/go-datastructures/...

When new code is merged to master, you can use

go get -u github.com/Workiva/go-datastructures/...

To retrieve the latest version of go-datastructures.

To run all the unit tests use these commands:

cd $GOPATH/src/github.com/Workiva/go-datastructuresgo get -t -u ./...go test ./...

Once you've done this once, you can simply use this command to run all unit tests:

go test ./...

Requirements to commit here:

• Branch off master, PR back to master.
• gofmt'd code.
• Compliance withthese guidelines
• Unit test coverage
• Good commit messages

• Dustin Hiatt <dustin.hiatt@workiva.com>
• Alexander Campbell <alexander.campbell@workiva.com>