generic_collections

module

v0.1.1 Latest Latest Go to latest Published: Jan 20, 2024 License: MIT

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/fireflycons/generic_collections

Links

Open Source Insights

README ¶

Generic Collections

build

Package generic_collections provides generic versions of common collection types. You will find each collection in its own sub-package. The code is based on ideas from other go packages and .NET generic collections.

Collections are optionally thread-safe (see Thread Safety), and optionally use concurrency in some methods (see Concurrency).

Elements of any type may be stored in these collections. Most basic types are supported out the box, whilst custom types will require the developer to provide functions to support the implementation.

Supported Types

The following types are supported directly by this library without a requirement to provide custom functions for hashing (required for HashSet) and comparer (required for all collections).

Numeric types - all classes of integer and float.
Pointers - Out of the box, the pointers themselves (i.e. the memory address) are compared by value. If you want to compare/hash on what is being pointed to, then you must provide implementations for these operations.
string
bool
time.Time
Any type directly castable to one of the above, e.g. time.Duration which is in effect int64.

Anything else e.g. structs require implementation of these functions, or the collection will panic.

Collection Hierarchy

Collection
- Lists
  - SList - A singly linked list
  - DList - A doubly linked list.
- Stacks
  - Stack - A slice-backed LIFO stack.
- Queues
  - Queue - A slice-backed FIFO queue.
  - RingBuffer - A slice-backed circular buffer
- Sets
  - HashSet - An unordered collection of unique items. Implemented as a hash table.
  - OrderedSet - An ordered collection of unique items. Implemented as a red-black tree.

Thread Safety

You have the option of whether or not a collection supports thread safety by way of a constructor option. Thread safety is not enabled by default. Enabling thread safety engages a sync.RWMutex taking the appropriate lock for the type of operation. Some overhead is incurred if thread safety is enabled. . Use the WithThreadSafe() constructor option to enable. See Benchmarks.

stk := stack.New[int](WithThreadSafe[int]())

Concurrency

In a few places within the sub-packages, concurrency may be enabled to improve performance of some operations. Concurrency is not enabled by default. This is currently limited in scope and may be expanded in future versions. Use the WithConcurrent() constructor option to enable. See benchmarks to see where this applies.

Concurrency features only kick in on large collections (currently > 64K elements). For small collections, using concurrency would slow things down due to the overhead involved in managing goroutines.

stk := stack.New[int](WithConcurrent[int]())

Error Handling

Contrary to the more common pattern of returning an error interface as a second argument, I took the decision to panic in case of errors. Common errors include reading from an empty collection, and modifying an underlying collection while an iteration is in progress. If user code is well behaved, then you should be able to avoid these. All collections can be tested for being empty, and many have "Try" versions of methods that return an additional bool on some operations that would panic.

Iteration

All collections are iterable via a common Iterator interface that yields Element[T] interface permitting interaction with the values stored in the collections. Collections may be iterated forwards (start to end), reverse (end to start), or forwards with a filter (TakeWhile()) It has the following interface:

type Iterator[T any] interface {
	Start() Element[T]
	Next() Element[T]
}

An iteration can be performed as follows

ll := slist.New[int]()
// add values, then...
iter := ll.Iterator()

for e := iter.Start() ; e != nil; e = iter.Next() {
    // do something with e.Value() or e.ValuePtr()
}

Collections must not be modified during iteration. Modification of the collection will cause iterators to panic on the next call to Start() or Next().

Element

Iteration yields Element[T] permitting access to the value stored in the collection at that point. It has the following methods:

type Element[T any] interface {
	Value() T
	ValuePtr() *T
}

Note that attempting to modify an item in a collection that implements Set[T] via ValuePtr() will panic as changing a value breaks the implementation of a set.

Functions

Some function signatures are provided for you to create your own logic to support various collection operations

ComparerFunc

This function allows the developer to supply a custom compare function to a collection for a type that is not one of the supported types.

A compare function should return < 0 if a < b, 0 if a == b else > 0 and looks like this, e.g. for a collection typed on int

func myComparer(int a, int b) int {
    return a - b
}

PredicateFunc

For many of the Enumerable methods, a predicate function must be given as an argument. A value is selected when the predicate function returns true. For instance, to filter all even numbers from a collection of int it might look like this

func filterEvens(int value) bool {
    return value % 2 == 0
}

HashFunc

For collections that use a hash table to store values (currently only HashSet), a function to compute a hash value for types not supported by default (as per ComparerFunc) must be provided.

The hash algorithms for the supported types are exported as function variables by the hashset sub-package so can be used to construct hashes for struct types.

DeepCopyFunc

The default action if an instance of this function is not passed to the collection constructor is that when making copies of collection elements, they will be copied by value. If the element type is a pointer, or a struct containing pointers this may not be what you want.

Should you need to deep-copy elements, supply an implementation of this function to the collection's constructor.

The function should return a new instance of the type which is a deep copy of the instance passed as an argument.

Enumerable

Enumerable defines a set of methods for enumerating a collection in various ways. All collections are enumerable.

type Enumerable[T any] interface {
	Any(predicate PredicateFunc[T]) bool
	All(predicate PredicateFunc[T]) bool
    Find(predicate functions.PredicateFunc[T]) Element[T]
    FindAll(predicate functions.PredicateFunc[T]) []Element[T]
	ForEach(func(Element[T]))
    Min() T
    Max() T
	Map(func(T) T) Collection[T]
	Select(PredicateFunc[T]) Collection[T]
    SelectDeep(functions.PredicateFunc[T]) Collection[T]
}

Benchmarks

In the following tables, the data in the columns have the following meanings

Elements - Number of elements stored in collection.
Operation
- Add/Push/Enqueue - Starting with an empty collection, add the given number of elements one at a time to what is logically the end of the collection. ns/op is the time to add all the elements.
- Remove/Pop/Dequeue - Starting with a full collection, items are all removed one at a time. ns/op is the time to remove all the elements.
- Sort - For collections that support sorting, take a collection collection containing the given number of elements. ns/op is the time to sort the collection.
- Contains - Collection is filled with given number of elements. Source element slice is shuffled and the values it contains are looked up in the collection ns/op is the average time to lookup any single element in the collection.
- Min, Max - Collection is filled with given number of elements. Min and Max are then taken b.N times.
TS (ThreadSafe)
- ✔ - Thread safety enabled. Lock is acquired/released on entry/exit of collection method under test.
- ❌ - Thread safety not enabled.
- Empty - Locking is negligible compared to total run time of the method so not benchmarked.
PS (Pre-sized)
- ✔ - Backing store initialized to given number of elements
- ❌ - Backing store not pre-initialized meaning that it has to grow periodically.
- Empty - Collection does not support a backing store that can be pre-sized.
CC (Concurrent)
- ✔ - Concurrent algorithm enabled.
- ❌ - Concurrent algorithm not enabled.
- Empty - No concurrency option on this algorithm.

Benchmarks are run on collections of int

Intel(R) Core(TM) i7-7800X

CPU Specification

Lists

Expand

Collection	Operation	Elements	TS	ns/op	B/op	allocs/op
DList	Add	100	❌	`5,162`	3,200	100
DList	Add	1,000	❌	`40,489`	32,000	1,000
DList	Add	10,000	❌	`377,561`	320,000	10,000
DList	Add	100,000	❌	`5,236,563`	3,200,022	100,000
DList	Add	100	✔	`6,947`	3,200	100
DList	Add	1,000	✔	`72,904`	32,000	1,000
DList	Add	10,000	✔	`613,653`	320,000	10,000
DList	Add	100,000	✔	`7,706,782`	3,200,038	100,000
DList	Remove	100	❌	`1,456`	0	0
DList	Remove	1,000	❌	`12,370`	0	0
DList	Remove	10,000	❌	`127,025`	0	0
DList	Remove	100,000	❌	`1,736,280`	1	0
DList	Remove	100	✔	`4,059`	0	0
DList	Remove	1,000	✔	`37,468`	0	0
DList	Remove	10,000	✔	`363,614`	0	0
DList	Remove	100,000	✔	`3,959,233`	1	0
DList	Sort	100		`5,612`	0	0
DList	Sort	1,000		`101,728`	0	0
DList	Sort	10,000		`1,612,152`	0	0
DList	Sort	100,000		`30,913,500`	0	0
DList	Min	100		`354.1`	0	0
DList	Min	1,000		`3,336`	0	0
DList	Min	10,000		`32,851`	0	0
DList	Min	100,000		`330,851`	0	0
DList	Max	100		`353.1`	0	0
DList	Max	1,000		`3,395`	0	0
DList	Max	10,000		`33,297`	0	0
DList	Max	100,000		`332,389`	0	0
DList	Contains	100		`160.3`	0	0
DList	Contains	1,000		`1,421`	0	0
DList	Contains	10,000		`14,289`	0	0
DList	Contains	100,000		`142,327`	0	0
SList	Add	100	❌	`4,252`	2,400	100
SList	Add	1,000	❌	`39,132`	24,000	1,000
SList	Add	10,000	❌	`314,291`	240,000	10,000
SList	Add	100,000	❌	`3,662,899`	2,400,011	100,000
SList	Add	100	✔	`8,217`	2,400	100
SList	Add	1,000	✔	`54,659`	24,000	1,000
SList	Add	10,000	✔	`552,099`	240,000	10,000
SList	Add	100,000	✔	`5,989,855`	2,400,000	100,000
SList	Remove	100	❌	`1,185`	0	0
SList	Remove	1,000	❌	`12,092`	0	0
SList	Remove	10,000	❌	`104,223`	0	0
SList	Remove	100,000	❌	`1,033,820`	0	0
SList	Remove	100	✔	`3,688`	0	0
SList	Remove	1,000	✔	`34,738`	0	0
SList	Remove	10,000	✔	`350,273`	0	0
SList	Remove	100,000	✔	`3,309,956`	0	0
SList	Sort	100		`5,121`	0	0
SList	Sort	1,000		`93,342`	0	0
SList	Sort	10,000		`1,461,912`	0	0
SList	Sort	100,000		`25,846,042`	0	0
SList	Min	100		`346.0`	0	0
SList	Min	1,000		`3,280`	0	0
SList	Min	10,000		`32,769`	0	0
SList	Min	100,000		`328,320`	0	0
SList	Max	100		`348.2`	0	0
SList	Max	1,000		`3,341`	0	0
SList	Max	10,000		`33,216`	0	0
SList	Max	100,000		`331,937`	0	0
SList	Contains	100		`168.1`	0	0
SList	Contains	1,000		`1,525`	0	0
SList	Contains	10,000		`15,196`	0	0
SList	Contains	100,000		`154,434`	0	0

Queues

Expand

Collection	Operation	Elements	TS	PS	CC	ns/op	B/op	allocs/op
Queue	Enqueue	100	❌	❌		`2,227`	1,792	3
Queue	Enqueue	1,000	❌	❌		`15,661`	16,128	6
Queue	Enqueue	10,000	❌	❌		`168,893`	261,888	10
Queue	Enqueue	100,000	❌	❌		`1,630,451`	2,096,901	13
Queue	Enqueue	100	❌	✔		`661.9`	0	0
Queue	Enqueue	1,000	❌	✔		`8,476`	0	0
Queue	Enqueue	10,000	❌	✔		`121,440`	0	0
Queue	Enqueue	100,000	❌	✔		`1,248,483`	2	0
Queue	Enqueue	100	✔	❌		`4,003`	1,792	3
Queue	Enqueue	1,000	✔	❌		`45,827`	16,128	6
Queue	Enqueue	10,000	✔	❌		`367,966`	261,888	10
Queue	Enqueue	100,000	✔	❌		`3,742,788`	2,096,899	13
Queue	Enqueue	100	✔	✔		`2,564`	0	0
Queue	Enqueue	1,000	✔	✔		`36,120`	0	0
Queue	Enqueue	10,000	✔	✔		`321,078`	0	0
Queue	Enqueue	100,000	✔	✔		`3,303,376`	0	0
Queue	Dequeue	100	❌			`638.3`	0	0
Queue	Dequeue	1,000	❌			`13,667`	0	0
Queue	Dequeue	10,000	❌			`129,131`	0	0
Queue	Dequeue	100,000	❌			`1,258,166`	1	0
Queue	Dequeue	100	✔			`2,435`	0	0
Queue	Dequeue	1,000	✔			`33,463`	0	0
Queue	Dequeue	10,000	✔			`324,595`	0	0
Queue	Dequeue	100,000	✔			`3,283,561`	0	0
Queue	Sort	100				`4,867`	928	2
Queue	Sort	1,000				`88,174`	8,224	2
Queue	Sort	10,000				`1,333,856`	81,952	2
Queue	Sort	100,000				`16,674,301`	802,849	2
Queue	Min	100			❌	`960.2`	0	0
Queue	Min	1,000			❌	`3,300`	0	0
Queue	Min	10,000			❌	`33,681`	0	0
Queue	Min	100,000			❌	`337,106`	0	0
Queue	Min	100,000			✔	`107,563`	1,893	35
Queue	Max	100			❌	`954.1`	0	0
Queue	Max	1,000			❌	`3,376`	0	0
Queue	Max	10,000			❌	`32,882`	0	0
Queue	Max	100,000			❌	`329,761`	0	0
Queue	Max	100,000			✔	`107,083`	1,881	35
Queue	Contains	100				`595.5`	0	0
Queue	Contains	1,000				`5,750`	0	0
Queue	Contains	10,000				`58,685`	0	0
Queue	Contains	100,000				`585,437`	0	0
RingBuffer	Enqueue	100	❌			`790.1`	0	0
RingBuffer	Enqueue	1,000	❌			`18,859`	0	0
RingBuffer	Enqueue	10,000	❌			`138,050`	0	0
RingBuffer	Enqueue	100,000	❌			`1,368,396`	0	0
RingBuffer	Enqueue	100	✔			`3,292`	0	0
RingBuffer	Enqueue	1,000	✔			`36,771`	0	0
RingBuffer	Enqueue	10,000	✔			`341,061`	0	0
RingBuffer	Enqueue	100,000	✔			`3,539,813`	2	0
RingBuffer	Dequeue	100	❌			`609.1`	0	0
RingBuffer	Dequeue	1,000	❌			`3,954`	0	0
RingBuffer	Dequeue	10,000	❌			`36,054`	0	0
RingBuffer	Dequeue	100,000	❌			`366,657`	1	0
RingBuffer	Dequeue	100	✔			`2,786`	0	0
RingBuffer	Dequeue	1,000	✔			`28,678`	0	0
RingBuffer	Dequeue	10,000	✔			`290,307`	0	0
RingBuffer	Dequeue	100,000	✔			`2,791,561`	1	0
RingBuffer	Sort	100				`10,418`	928	2
RingBuffer	Sort	1,000				`113,191`	8,224	2
RingBuffer	Sort	10,000				`1,444,259`	81,952	2
RingBuffer	Sort	100,000				`17,667,739`	802,849	2
RingBuffer	Min	100				`943.2`	0	0
RingBuffer	Min	1,000				`9,339`	0	0
RingBuffer	Min	10,000				`95,596`	0	0
RingBuffer	Min	100,000				`953,840`	0	0
RingBuffer	Max	100				`938.7`	0	0
RingBuffer	Max	1,000				`9,404`	0	0
RingBuffer	Max	10,000				`94,722`	0	0
RingBuffer	Max	100,000				`945,439`	0	0
RingBuffer	Contains	100				`598.5`	0	0
RingBuffer	Contains	1,000				`5,884`	0	0
RingBuffer	Contains	10,000				`58,109`	0	0
RingBuffer	Contains	100,000				`589,616`	0	0

Sets

Expand

Collection	Operation	Elements	TS	PS	ns/op	B/op	allocs/op
HashSet	Add	100	❌	❌	`8,841`	9,964	107
HashSet	Add	1,000	❌	❌	`153,902`	180,734	1,028
HashSet	Add	10,000	❌	❌	`1,518,866`	1,432,842	10,209
HashSet	Add	100,000	❌	❌	`17,702,102`	12,233,593	103,929
HashSet	Add	100	❌	✔	`6,414`	2,113	101
HashSet	Add	1,000	❌	✔	`80,157`	16,000	1,000
HashSet	Add	10,000	❌	✔	`842,747`	160,004	10,000
HashSet	Add	100,000	❌	✔	`11,545,505`	2,076,248	101,653
HashSet	Add	100	✔	❌	`19,281`	9,965	107
HashSet	Add	1,000	✔	❌	`175,249`	180,701	1,028
HashSet	Add	10,000	✔	❌	`1,678,002`	1,432,757	10,209
HashSet	Add	100,000	✔	❌	`19,997,582`	12,236,830	103,940
HashSet	Add	100	✔	✔	`12,774`	2,113	101
HashSet	Add	1,000	✔	✔	`98,353`	16,000	1,000
HashSet	Add	10,000	✔	✔	`1,100,168`	160,000	10,000
HashSet	Add	100,000	✔	✔	`13,549,729`	2,077,883	101,659
HashSet	Remove	100	❌		`6,100`	0	0
HashSet	Remove	1,000	❌		`52,680`	0	0
HashSet	Remove	10,000	❌		`525,006`	0	0
HashSet	Remove	100,000	❌		`7,590,020`	0	0
HashSet	Remove	100	✔		`7,676`	0	0
HashSet	Remove	1,000	✔		`77,053`	0	0
HashSet	Remove	10,000	✔		`832,967`	0	0
HashSet	Remove	100,000	✔		`9,916,081`	0	0
HashSet	Min	100			`1,378`	0	0
HashSet	Min	1,000			`14,594`	0	0
HashSet	Min	10,000			`136,113`	0	0
HashSet	Min	100,000			`1,925,612`	0	0
HashSet	Max	100			`1,392`	0	0
HashSet	Max	1,000			`14,448`	0	0
HashSet	Max	10,000			`135,533`	0	0
HashSet	Max	100,000			`1,915,966`	0	0
HashSet	Contains	100			`27.39`	0	0
HashSet	Contains	1,000			`37.85`	0	0
HashSet	Contains	10,000			`44.72`	0	0
HashSet	Contains	100,000			`78.73`	0	0
OrderedSet	Add	100	❌		`5,782`	4,800	100
OrderedSet	Add	1,000	❌		`139,177`	48,000	1,000
OrderedSet	Add	10,000	❌		`1,777,309`	480,001	10,000
OrderedSet	Add	100,000	❌		`27,412,678`	4,800,011	100,000
OrderedSet	Add	100	✔		`17,031`	4,800	100
OrderedSet	Add	1,000	✔		`132,474`	48,000	1,000
OrderedSet	Add	10,000	✔		`1,897,430`	480,001	10,000
OrderedSet	Add	100,000	✔		`29,175,012`	4,800,014	100,000
OrderedSet	Remove	100	❌		`6,572`	0	0
OrderedSet	Remove	1,000	❌		`98,252`	0	0
OrderedSet	Remove	10,000	❌		`1,371,899`	0	0
OrderedSet	Remove	100,000	❌		`22,635,769`	0	0
OrderedSet	Remove	100	✔		`5,266`	0	0
OrderedSet	Remove	1,000	✔		`101,616`	0	0
OrderedSet	Remove	10,000	✔		`1,364,635`	0	0
OrderedSet	Remove	100,000	✔		`23,862,490`	0	0
OrderedSet	Min	100			`6.216`	0	0
OrderedSet	Min	1,000			`6.660`	0	0
OrderedSet	Min	10,000			`9.111`	0	0
OrderedSet	Min	100,000			`11.13`	0	0
OrderedSet	Max	100			`4.560`	0	0
OrderedSet	Max	1,000			`5.843`	0	0
OrderedSet	Max	10,000			`6.875`	0	0
OrderedSet	Max	100,000			`8.876`	0	0
OrderedSet	Contains	100			`33.14`	0	0
OrderedSet	Contains	1,000			`75.97`	0	0
OrderedSet	Contains	10,000			`111.6`	0	0
OrderedSet	Contains	100,000			`197.8`	0	0

Stacks

Expand

Collection	Operation	Elements	TS	PS	CC	ns/op	B/op	allocs/op
Stack	Push	100	❌	❌		`1,122`	2,016	3
Stack	Push	1,000	❌	❌		`6,525`	18,656	6
Stack	Push	10,000	❌	❌		`50,456`	299,239	10
Stack	Push	100,000	❌	❌		`751,467`	2,363,622	13
Stack	Push	100	❌	✔		`586.5`	0	0
Stack	Push	1,000	❌	✔		`3,763`	0	0
Stack	Push	10,000	❌	✔		`43,139`	0	0
Stack	Push	100,000	❌	✔		`388,153`	3	0
Stack	Push	100	✔	❌		`3,068`	2,016	3
Stack	Push	1,000	✔	❌		`19,165`	18,656	6
Stack	Push	10,000	✔	❌		`323,252`	299,233	10
Stack	Push	100,000	✔	❌		`3,271,576`	2,363,618	13
Stack	Push	100	✔	✔		`3,276`	0	0
Stack	Push	1,000	✔	✔		`34,538`	0	0
Stack	Push	10,000	✔	✔		`274,057`	0	0
Stack	Push	100,000	✔	✔		`2,857,594`	0	0
Stack	Pop	100	❌			`720.5`	0	0
Stack	Pop	1,000	❌			`3,349`	0	0
Stack	Pop	10,000	❌			`36,320`	1	0
Stack	Pop	100,000	❌			`342,374`	2	0
Stack	Pop	100	✔			`3,014`	0	0
Stack	Pop	1,000	✔			`22,547`	0	0
Stack	Pop	10,000	✔			`276,337`	0	0
Stack	Pop	100,000	✔			`2,669,541`	1	0
Stack	Sort	100				`4,634`	32	1
Stack	Sort	1,000				`107,059`	32	1
Stack	Sort	10,000				`1,295,618`	32	1
Stack	Sort	100,000				`16,371,947`	33	1
Stack	Min	100			❌	`371.1`	0	0
Stack	Min	1,000			❌	`3,618`	0	0
Stack	Min	10,000			❌	`36,231`	0	0
Stack	Min	100,000			❌	`357,545`	0	0
Stack	Min	100,000			✔	`108,811`	1,882	35
Stack	Max	100			❌	`379.1`	0	0
Stack	Max	1,000			❌	`3,639`	0	0
Stack	Max	10,000			❌	`35,200`	0	0
Stack	Max	100,000			❌	`354,018`	0	0
Stack	Max	100,000			✔	`109,385`	1,882	35
Stack	Contains	100			❌	`156.6`	0	0
Stack	Contains	1,000			❌	`1,363`	0	0
Stack	Contains	10,000			❌	`14,037`	0	0
Stack	Contains	100,000			❌	`139,171`	0	0
Stack	Contains	100,000			✔	`100,202`	1,600	29

Intel(R) Core(TM) i7-12700H

CPU Specification

Lists

Expand

Collection	Operation	Elements	TS	ns/op	B/op	allocs/op
DList	Add	100	❌	`2,988`	3,200	100
DList	Add	1,000	❌	`26,507`	32,000	1,000
DList	Add	10,000	❌	`243,373`	320,000	10,000
DList	Add	100,000	❌	`3,558,804`	3,200,034	100,000
DList	Add	100	✔	`6,702`	3,200	100
DList	Add	1,000	✔	`51,964`	32,000	1,000
DList	Add	10,000	✔	`540,395`	320,000	10,000
DList	Add	100,000	✔	`6,676,934`	3,200,027	100,000
DList	Remove	100	❌	`866.4`	0	0
DList	Remove	1,000	❌	`11,226`	0	0
DList	Remove	10,000	❌	`107,712`	0	0
DList	Remove	100,000	❌	`988,447`	1	0
DList	Remove	100	✔	`3,527`	0	0
DList	Remove	1,000	✔	`30,529`	0	0
DList	Remove	10,000	✔	`322,074`	1	0
DList	Remove	100,000	✔	`2,764,714`	0	0
DList	Sort	100		`4,165`	0	0
DList	Sort	1,000		`71,783`	0	0
DList	Sort	10,000		`1,325,536`	0	0
DList	Sort	100,000		`21,481,198`	0	0
DList	Min	100		`142.2`	0	0
DList	Min	1,000		`1,224`	0	0
DList	Min	10,000		`14,411`	0	0
DList	Min	100,000		`128,253`	0	0
DList	Max	100		`141.4`	0	0
DList	Max	1,000		`1,288`	0	0
DList	Max	10,000		`13,221`	0	0
DList	Max	100,000		`130,500`	0	0
DList	Contains	100		`74.73`	0	0
DList	Contains	1,000		`682.6`	0	0
DList	Contains	10,000		`7,257`	0	0
DList	Contains	100,000		`75,901`	0	0
SList	Add	100	❌	`3,204`	2,400	100
SList	Add	1,000	❌	`29,243`	24,000	1,000
SList	Add	10,000	❌	`245,878`	240,000	10,000
SList	Add	100,000	❌	`2,632,169`	2,400,007	100,000
SList	Add	100	✔	`6,467`	2,400	100
SList	Add	1,000	✔	`42,146`	24,000	1,000
SList	Add	10,000	✔	`410,458`	240,000	10,000
SList	Add	100,000	✔	`4,451,332`	2,400,007	100,000
SList	Remove	100	❌	`1,003`	0	0
SList	Remove	1,000	❌	`9,262`	0	0
SList	Remove	10,000	❌	`82,960`	0	0
SList	Remove	100,000	❌	`444,766`	0	0
SList	Remove	100	✔	`3,390`	0	0
SList	Remove	1,000	✔	`29,534`	0	0
SList	Remove	10,000	✔	`258,203`	0	0
SList	Remove	100,000	✔	`2,518,566`	0	0
SList	Sort	100		`3,844`	0	0
SList	Sort	1,000		`60,946`	0	0
SList	Sort	10,000		`1,115,609`	0	0
SList	Sort	100,000		`19,240,269`	0	0
SList	Min	100		`145.1`	0	0
SList	Min	1,000		`1,359`	0	0
SList	Min	10,000		`13,594`	0	0
SList	Min	100,000		`134,319`	0	0
SList	Max	100		`151.6`	0	0
SList	Max	1,000		`1,394`	0	0
SList	Max	10,000		`13,703`	0	0
SList	Max	100,000		`131,296`	0	0
SList	Contains	100		`75.89`	0	0
SList	Contains	1,000		`676.4`	0	0
SList	Contains	10,000		`6,859`	0	0
SList	Contains	100,000		`69,234`	0	0

Queues

Expand

Collection	Operation	Elements	TS	PS	CC	ns/op	B/op	allocs/op
Queue	Enqueue	100	❌	❌		`1,447`	1,792	3
Queue	Enqueue	1,000	❌	❌		`9,382`	16,128	6
Queue	Enqueue	10,000	❌	❌		`86,595`	261,889	10
Queue	Enqueue	100,000	❌	❌		`805,183`	2,096,904	13
Queue	Enqueue	100	❌	✔		`687.1`	0	0
Queue	Enqueue	1,000	❌	✔		`5,328`	0	0
Queue	Enqueue	10,000	❌	✔		`56,027`	0	0
Queue	Enqueue	100,000	❌	✔		`556,338`	1	0
Queue	Enqueue	100	✔	❌		`3,599`	1,792	3
Queue	Enqueue	1,000	✔	❌		`31,312`	16,128	6
Queue	Enqueue	10,000	✔	❌		`283,523`	261,888	10
Queue	Enqueue	100,000	✔	❌		`2,672,735`	2,096,897	13
Queue	Enqueue	100	✔	✔		`2,985`	0	0
Queue	Enqueue	1,000	✔	✔		`28,162`	0	0
Queue	Enqueue	10,000	✔	✔		`233,762`	0	0
Queue	Enqueue	100,000	✔	✔		`2,338,408`	0	0
Queue	Dequeue	100	❌			`688.3`	0	0
Queue	Dequeue	1,000	❌			`5,216`	0	0
Queue	Dequeue	10,000	❌			`57,024`	0	0
Queue	Dequeue	100,000	❌			`472,703`	0	0
Queue	Dequeue	100	✔			`2,709`	0	0
Queue	Dequeue	1,000	✔			`26,728`	0	0
Queue	Dequeue	10,000	✔			`237,120`	0	0
Queue	Dequeue	100,000	✔			`2,201,107`	0	0
Queue	Sort	100				`5,050`	928	2
Queue	Sort	1,000				`73,676`	8,224	2
Queue	Sort	10,000				`948,724`	81,952	2
Queue	Sort	100,000				`11,564,077`	802,848	2
Queue	Min	100			❌	`222.1`	0	0
Queue	Min	1,000			❌	`1,160`	0	0
Queue	Min	10,000			❌	`12,438`	0	0
Queue	Min	100,000			❌	`128,021`	0	0
Queue	Min	100,000			✔	`64,953`	3,036	52
Queue	Max	100			❌	`223.1`	0	0
Queue	Max	1,000			❌	`1,250`	0	0
Queue	Max	10,000			❌	`11,444`	0	0
Queue	Max	100,000			❌	`113,885`	0	0
Queue	Max	100,000			✔	`60,476`	3,034	52
Queue	Contains	100				`238.6`	0	0
Queue	Contains	1,000				`2,336`	0	0
Queue	Contains	10,000				`23,404`	0	0
Queue	Contains	100,000				`236,049`	0	0
RingBuffer	Enqueue	100	❌			`800.2`	0	0
RingBuffer	Enqueue	1,000	❌			`6,197`	0	0
RingBuffer	Enqueue	10,000	❌			`57,253`	0	0
RingBuffer	Enqueue	100,000	❌			`554,793`	1	0
RingBuffer	Enqueue	100	✔			`3,140`	0	0
RingBuffer	Enqueue	1,000	✔			`25,130`	0	0
RingBuffer	Enqueue	10,000	✔			`239,471`	0	0
RingBuffer	Enqueue	100,000	✔			`2,340,666`	0	0
RingBuffer	Dequeue	100	❌			`472.7`	0	0
RingBuffer	Dequeue	1,000	❌			`3,147`	0	0
RingBuffer	Dequeue	10,000	❌			`32,156`	0	0
RingBuffer	Dequeue	100,000	❌			`276,973`	3	0
RingBuffer	Dequeue	100	✔			`2,860`	0	0
RingBuffer	Dequeue	1,000	✔			`25,374`	0	0
RingBuffer	Dequeue	10,000	✔			`221,808`	0	0
RingBuffer	Dequeue	100,000	✔			`2,314,409`	1	0
RingBuffer	Sort	100				`5,245`	928	2
RingBuffer	Sort	1,000				`67,790`	8,224	2
RingBuffer	Sort	10,000				`921,211`	81,952	2
RingBuffer	Sort	100,000				`12,147,900`	802,848	2
RingBuffer	Min	100				`227.5`	0	0
RingBuffer	Min	1,000				`2,249`	0	0
RingBuffer	Min	10,000				`22,563`	0	0
RingBuffer	Min	100,000				`224,869`	0	0
RingBuffer	Max	100				`229.2`	0	0
RingBuffer	Max	1,000				`2,262`	0	0
RingBuffer	Max	10,000				`22,853`	0	0
RingBuffer	Max	100,000				`226,723`	0	0
RingBuffer	Contains	100				`249.9`	0	0
RingBuffer	Contains	1,000				`2,392`	0	0
RingBuffer	Contains	10,000				`23,815`	0	0
RingBuffer	Contains	100,000				`243,623`	0	0

Sets

Expand

Collection	Operation	Elements	TS	PS	ns/op	B/op	allocs/op
HashSet	Add	100	❌	❌	`10,294`	9,963	107
HashSet	Add	1,000	❌	❌	`107,654`	180,694	1,028
HashSet	Add	10,000	❌	❌	`1,170,594`	1,432,765	10,209
HashSet	Add	100,000	❌	❌	`11,240,331`	12,234,374	103,932
HashSet	Add	100	❌	✔	`9,209`	2,113	101
HashSet	Add	1,000	❌	✔	`66,145`	16,000	1,000
HashSet	Add	10,000	❌	✔	`688,392`	160,003	10,000
HashSet	Add	100,000	❌	✔	`7,238,287`	2,078,747	101,662
HashSet	Add	100	✔	❌	`14,157`	9,965	107
HashSet	Add	1,000	✔	❌	`133,932`	180,693	1,028
HashSet	Add	10,000	✔	❌	`1,225,502`	1,433,053	10,210
HashSet	Add	100,000	✔	❌	`11,446,165`	12,236,271	103,938
HashSet	Add	100	✔	✔	`11,180`	2,114	101
HashSet	Add	1,000	✔	✔	`71,554`	16,000	1,000
HashSet	Add	10,000	✔	✔	`755,077`	160,001	10,000
HashSet	Add	100,000	✔	✔	`8,826,382`	2,078,576	101,661
HashSet	Remove	100	❌		`6,245`	0	0
HashSet	Remove	1,000	❌		`47,646`	0	0
HashSet	Remove	10,000	❌		`410,425`	0	0
HashSet	Remove	100,000	❌		`4,901,910`	0	0
HashSet	Remove	100	✔		`7,600`	0	0
HashSet	Remove	1,000	✔		`58,179`	0	0
HashSet	Remove	10,000	✔		`468,389`	0	0
HashSet	Remove	100,000	✔		`6,180,152`	0	0
HashSet	Min	100			`738.1`	0	0
HashSet	Min	1,000			`9,053`	0	0
HashSet	Min	10,000			`85,572`	0	0
HashSet	Min	100,000			`821,231`	0	0
HashSet	Max	100			`741.4`	0	0
HashSet	Max	1,000			`9,181`	0	0
HashSet	Max	10,000			`86,746`	0	0
HashSet	Max	100,000			`830,899`	0	0
HashSet	Contains	100			`9.696`	0	0
HashSet	Contains	1,000			`15.71`	0	0
HashSet	Contains	10,000			`31.41`	0	0
HashSet	Contains	100,000			`37.66`	0	0
OrderedSet	Add	100	❌		`7,095`	4,800	100
OrderedSet	Add	1,000	❌		`104,035`	48,000	1,000
OrderedSet	Add	10,000	❌		`1,293,838`	480,004	10,000
OrderedSet	Add	100,000	❌		`19,638,457`	4,800,034	100,000
OrderedSet	Add	100	✔		`10,053`	4,800	100
OrderedSet	Add	1,000	✔		`108,203`	48,000	1,000
OrderedSet	Add	10,000	✔		`1,414,259`	480,003	10,000
OrderedSet	Add	100,000	✔		`21,027,762`	4,800,031	100,000
OrderedSet	Remove	100	❌		`3,186`	0	0
OrderedSet	Remove	1,000	❌		`71,386`	0	0
OrderedSet	Remove	10,000	❌		`1,015,825`	4	0
OrderedSet	Remove	100,000	❌		`16,077,759`	0	0
OrderedSet	Remove	100	✔		`5,102`	0	0
OrderedSet	Remove	1,000	✔		`81,914`	0	0
OrderedSet	Remove	10,000	✔		`1,126,826`	8	0
OrderedSet	Remove	100,000	✔		`17,350,911`	0	0
OrderedSet	Min	100			`2.071`	0	0
OrderedSet	Min	1,000			`2.428`	0	0
OrderedSet	Min	10,000			`3.484`	0	0
OrderedSet	Min	100,000			`4.856`	0	0
OrderedSet	Max	100			`2.239`	0	0
OrderedSet	Max	1,000			`3.639`	0	0
OrderedSet	Max	10,000			`5.302`	0	0
OrderedSet	Max	100,000			`4.986`	0	0
OrderedSet	Contains	100			`11.33`	0	0
OrderedSet	Contains	1,000			`46.42`	0	0
OrderedSet	Contains	10,000			`81.52`	0	0
OrderedSet	Contains	100,000			`180.9`	0	0

Stacks

Expand

Collection	Operation	Elements	TS	PS	CC	ns/op	B/op	allocs/op
Stack	Push	100	❌	❌		`1,281`	2,016	3
Stack	Push	1,000	❌	❌		`6,305`	18,656	6
Stack	Push	10,000	❌	❌		`76,407`	299,232	10
Stack	Push	100,000	❌	❌		`582,318`	2,363,629	13
Stack	Push	100	❌	✔		`494.4`	0	0
Stack	Push	1,000	❌	✔		`3,266`	0	0
Stack	Push	10,000	❌	✔		`29,567`	0	0
Stack	Push	100,000	❌	✔		`277,348`	2	0
Stack	Push	100	✔	❌		`3,637`	2,016	3
Stack	Push	1,000	✔	❌		`26,152`	18,656	6
Stack	Push	10,000	✔	❌		`264,761`	299,232	10
Stack	Push	100,000	✔	❌		`2,559,970`	2,363,617	13
Stack	Push	100	✔	✔		`2,672`	0	0
Stack	Push	1,000	✔	✔		`25,598`	0	0
Stack	Push	10,000	✔	✔		`230,666`	0	0
Stack	Push	100,000	✔	✔		`2,219,721`	0	0
Stack	Pop	100	❌			`408.0`	0	0
Stack	Pop	1,000	❌			`2,888`	0	0
Stack	Pop	10,000	❌			`29,767`	0	0
Stack	Pop	100,000	❌			`265,711`	6	0
Stack	Pop	100	✔			`2,639`	0	0
Stack	Pop	1,000	✔			`24,835`	0	0
Stack	Pop	10,000	✔			`224,791`	0	0
Stack	Pop	100,000	✔			`2,188,625`	3	0
Stack	Sort	100				`4,914`	32	1
Stack	Sort	1,000				`66,146`	32	1
Stack	Sort	10,000				`910,777`	32	1
Stack	Sort	100,000				`11,592,799`	32	1
Stack	Min	100			❌	`145.6`	0	0
Stack	Min	1,000			❌	`1,273`	0	0
Stack	Min	10,000			❌	`11,584`	0	0
Stack	Min	100,000			❌	`114,872`	0	0
Stack	Min	100,000			✔	`61,672`	3,036	52
Stack	Max	100			❌	`149.2`	0	0
Stack	Max	1,000			❌	`1,269`	0	0
Stack	Max	10,000			❌	`11,410`	0	0
Stack	Max	100,000			❌	`114,919`	0	0
Stack	Max	100,000			✔	`59,504`	3,034	52
Stack	Contains	100			❌	`57.69`	0	0
Stack	Contains	1,000			❌	`468.5`	0	0
Stack	Contains	10,000			❌	`4,514`	0	0
Stack	Contains	100,000			❌	`45,569`	0	0
Stack	Contains	100,000			✔	`55,627`	2,496	45

Directories ¶

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL

Path	Synopsis
collections Package collections provides the interfaces that define the collections in this module.	Package collections provides the interfaces that define the collections in this module.
functions This package contains signatures for functions used by collections and their methods.	This package contains signatures for functions used by collections and their methods.
internal
local
messages
util
lists Package lists defines the interface for list collections.	Package lists defines the interface for list collections.
dlist Package dlist implements a doubly linked list.	Package dlist implements a doubly linked list.
slist Package slist implements a singly linked list.	Package slist implements a singly linked list.
queues Package lists defines the interface for FIFO queue collections.	Package lists defines the interface for FIFO queue collections.
queue Package queue provides a slice-backed FIFO queue.	Package queue provides a slice-backed FIFO queue.
ringbuffer Package ringbuffer provides a fixed length FIFO circular buffer.	Package ringbuffer provides a fixed length FIFO circular buffer.
sets Package set defines the interface for set collections.	Package set defines the interface for set collections.
hashset Package hashset provides a hash bucket backed collection that contains an unordered collection of unique values.	Package hashset provides a hash bucket backed collection that contains an unordered collection of unique values.
orderedset Package orderedset provides a red-black tree backed ordered collection of unique items.	Package orderedset provides a red-black tree backed ordered collection of unique items.
stacks Package stacks defines the interface for LIFO stack collections.	Package stacks defines the interface for LIFO stack collections.
stack Package stack implements a slice-backed LIFO stack.	Package stack implements a slice-backed LIFO stack.