set3

package module
v0.4.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 11, 2025 License: Apache-2.0 Imports: 5 Imported by: 1

README

Set3

Go Report Card Go Reference Tests coverage OpenSSF Best Practices OpenSSF Scorecard

Set3 is a high-performance, native Golang set implementation. It offers a significant improvement in speed and memory efficiency, being 10%-30% faster and utilizing 25% less memory compared to map[type]struct{}. Additionally, Set3 provides the flexibility to optimize for either space consumption or speed through the RehashToCapacity(newCapacity) function. This level of performance and adaptability is unattainable with implementations based on map[type]struct{}, which is the standard foundation for most set implementations in Go.

The code is derived from SwissMap and it implements the "Fast, Efficient, Cache-friendly Hash Table" found in Abseil. For details on the algorithm see the CppCon 2017 talk by Matt Kulukundis. The dependency on x86 assembler for SSE2/SSE3 instructions has been removed for portability and speed; the code runs faster without SSE and the necessary additional stack frame. As hash function, Set3 uses the original hash function from map[type]struct{} via dolthub/maphash.

The name "Set3" comes from the fact that this was the 3rd attempt for an optimized datastructure/code-layout to get the best runtime performance.

Installation

To use the Set3 package in your Go project, follow these steps:

  1. Initialize a Go module (if you haven't already):

    go mod init your-module-name

  2. Add the package: Simply import the package in your Go code, and Go modules will handle the rest:

    import "github.com/TomTonic/Set3"

  3. Download dependencies: Run the following command to download the dependencies:

    go mod tidy

    This will automatically download and install the Set3 package along with any other dependencies.

Using Set3

The following test case creates two sets and demonstrates some operations. For a full list of operations on the Set3 type, see API doc.

func TestExample(t *testing.T) {
    // create a new Set3
    set1 := Empty[int]()
    // add some elements
    set1.Add(1)
    set1.Add(2)
    set1.Add(3)
    // add some more elements
    set1.AddAllOf(4, 5, 6)
    // create a second set directly from an array
    set2 := FromArray([]int{2, 3, 4, 5})
    // check if set2 is a subset of set1. must be true in this case
    isSubset := set1.ContainsAll(set2)
    assert.True(t, isSubset, "%v is not a subset of %v", set2, set1)
    // mathematical operations like Unite, Subtract and Intersect
    // do not manipulate a Set3 but return a new set
    intersect := set1.Intersect(set2)
    // compare sets. as set2 is a subset of set1, intersect must be equal to set2
    equal := intersect.Equals(set2)
    assert.True(t, equal, "%v is not equal to %v", intersect, set2)
}

Performance

The following benchmarks have been performed with v0.4.0 to compare Set3[uint64] with map[uint64]struct{} with the command:

go test -v -count=1 -run "^(TestSet3Fill|TestNativeMapFill|TestSet3Find|TestNativeMapFind)$" github.com/TomTonic/Set3 -timeout=120m > benchresult.txt

(Raw benchmark results are available in plain text. Go version 1.23.1, no PGO. Please note that you have to comment out the instructions to skip the tests first (t.Skip("...")). The whole benchmark runs about 45 minutes.)

Inserting Nodes into an Empty Set

The following chart illustrates the time required to insert random uint64 values into newly allocated sets. The displayed times encompass the set allocation process. All sets were allocated with an initial capacity of 21 elements, which is the current default in Set3. As a result, rehashing occurs—sometimes multiple times—for larger sets. This effect is clearly visible in the two charts below.

n = 1 ... 300 (step size +1, linear scale)

Please note that the memory chart displays the total memory consumption divided by the number of elements in the set. This effectively represents the memory usage for storing a single element, i.e., 8 bytes. Additionally, be aware of the lower bound of 10 bytes and the logarithmic scale of the y-axis.

n = 1 ... 300 (step size +1, linear scale)

Searching Nodes in a Populated Set

The following chart illustrates the time required to determine whether a random value is present in the set. The test driver maintains a 30% hit ratio, ensuring that 30% of the queried values are contained within the set, while the remaining 70% are not. The x-axis represents sets of varying sizes, and the y-axis indicates the average time taken to look up a random value in a set of the corresponding size.

n = 1 ... 300 (step size +1, linear scale)

Documentation

Overview

Set3 is an efficient set implementation in plain Go. Unlike many other set implementations, Set3 does not rely on Go's internal map data structure. Instead, it implements a hash set based on the "Fast, Efficient, Cache-friendly Hash Table" found in Abseil, Google's C++ libraries. As a result, Set3 is 10%-20% faster and the data structure uses 40% less memory than implementations based on `map[type]struct{}`.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Set3 

type Set3[T comparable] struct {
	// contains filtered or unexported fields
}

Set3 is a hash set of type K.

func Empty added in v0.4.0 

func Empty[T comparable]() *Set3[T]

Empty creates a new and empty Set3 with a reasonable default initial capacity. Choose this constructor if you have no idea on how big your set will be. You can add as many elements to this set as you like, the backing data structure will automatically be reorganized to fit your needs.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)

func EmptyWithCapacity added in v0.4.0 

func EmptyWithCapacity[T comparable](initialCapacity uint32) *Set3[T]

EmptyWithCapacity creates a new and empty Set3 with a given initial capacity. Choose this constructor if you have a pretty good idea on how big your set will be. Nonetheless, you can add as many elements to this set as you like, the backing data structure will automatically be reorganized to fit your needs.

Example: 

set1 := Empty[int]() // you can put 1 mio. ints in set1. set1 will rehash itself several times while adding them
set2 := EmptyWithCapacity[int](2_000_000) // you can put 1 mio. ints in set2. set2 does not need to rehash itself while adding them

func From added in v0.4.0 

func From[T comparable](args ...T) *Set3[T]

From is a convenience constructor to directly create a Set3 from given arguments. It creates a new Set3 and adds all (unique) elements to this set.

If the arguments contain duplicates, the duplicates are omitted. If no arguments are provided, an empty Set3 is returned.

Example: 

set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := From(1, 2, 3) // set1 and set2 are equal

func FromArray added in v0.4.0 

func FromArray[T comparable](data []T) *Set3[T]

FromArray is a convenience constructor to directly create a Set3 from given values. It creates a new Set3 and adds all (unique) elements to this set.

If the array contains duplicates, the duplicates are omitted. If data is nil, an empty Set3 is returned.

Example: 

set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := FromArray([]int{1, 2, 3}) // set1 and set2 are equal

func (*Set3[T]) Add 

func (thisSet *Set3[T]) Add(element T)

Inserts the element into thisSet if it is not yet in thisSet.

Example: 

set := Empty[int]()
set.Add(7)

func (*Set3[T]) AddAll added in v0.2.0 

func (thisSet *Set3[T]) AddAll(thatSet *Set3[T])

Inserts all elements from thatSet that are not yet in thisSet into thisSet.

If thatSet is nil, nothing is added to thisSet.

Example: 

set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set2 := Empty[int]()
set2.Add(2)
set2.Add(3)
set1.AddAll(set2) // set1 will now contain 1, 2, 3

func (*Set3[T]) AddAllFromArray added in v0.4.0 

func (thisSet *Set3[T]) AddAllFromArray(data []T)

Inserts all elements from the given data array that are not yet in thisSet into thisSet.

If data is nil, nothing is added to thisSet.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.AddAllFromArray([]int{2,3}]) // set will now contain 1, 2, 3

func (*Set3[T]) AddAllOf added in v0.4.0 

func (thisSet *Set3[T]) AddAllOf(args ...T)

Inserts all parameter values that are not yet in thisSet into thisSet.

If the number of parameters is zero, nothing is added to thisSet.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.AddAllOf(2,3) // set will now contain 1, 2, 3

func (*Set3[T]) Clear 

func (thisSet *Set3[T]) Clear()

Clear removes all elements from thisSet.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.Clear()  // set will be empty, Count() will return 0

func (*Set3[T]) Clone added in v0.2.0 

func (thisSet *Set3[T]) Clone() *Set3[T]

Clone creates an exact clone of thisSet. You can manipulate both clones independently.

Cloning is 'cheap' in comparison with creating a new set and adding all elements from this set, as only the backing data structures are copied (no rehashing is applied).

Example: 

set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := set1.Clone() // set2 will be an exact but independent clone of set1

func (*Set3[T]) Contains 

func (thisSet *Set3[T]) Contains(element T) bool

Contains returns true if the element is contained in thisSet.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
b1 := set.Contains(2) // b1 will be true
b2 := set.Contains(4) // b2 will be false

func (*Set3[T]) ContainsAll added in v0.2.0 

func (thisSet *Set3[T]) ContainsAll(thatSet *Set3[T]) bool

Returns true if thisSet contains all elements from thatSet.

If thatSet is empty, ContainsAll returns true. If thatSet is nil, ContainsAll returns true.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
Empty := Empty[int]()
b := set.ContainsAll(Empty) // b will be true

func (*Set3[T]) ContainsAllFromArray added in v0.4.0 

func (thisSet *Set3[T]) ContainsAllFromArray(data []T) bool

Returns true if thisSet contains all elements from the given data array.

If the length of data is zero, ContainsAllFromArray returns true. If data is nil, ContainsAllFromArray returns true.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
b := set.ContainsAllFromArray([]int{2,3,4}) // b will be false

func (*Set3[T]) ContainsAllOf added in v0.4.0 

func (thisSet *Set3[T]) ContainsAllOf(args ...T) bool

Returns true if thisSet contains all of the given argument values.

If the number of arguments is zero, ContainsAllOf returns true.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
b := set.ContainsAllOf(2,3,4) // b will be false

func (*Set3[T]) ContainsAny added in v0.3.2 

func (thisSet *Set3[T]) ContainsAny(thatSet *Set3[T]) bool

Checks if thisSet contains any element that is also present in thatSet. This function also provides a quick way to check if two Set3 are disjoint (i.e. !ContainsAny).

Returns false if thatSet is nil.

Example: 

set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := Empty[int]()
set2.Add(0)
set2.Add(1)
b := set1.ContainsAny(set2) // b will be true

func (*Set3[T]) ContainsAnyFromArray added in v0.4.0 

func (thisSet *Set3[T]) ContainsAnyFromArray(data []T) bool

Checks if thisSet contains any element fromthe given data array.

Returns false if data is nil.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
b := set1.ContainsAnyFromArray([]int{4, 5, 6}) // b will be false

func (*Set3[T]) ContainsAnyOf added in v0.4.0 

func (thisSet *Set3[T]) ContainsAnyOf(args ...T) bool

Checks if thisSet contains any of the given argument values.

Returns false if the number of arguments is zero.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
b := set1.ContainsAnyOf(4, 5, 6) // b will be false

func (*Set3[T]) Equals added in v0.2.0 

func (thisSet *Set3[T]) Equals(thatSet *Set3[T]) bool

Returns true if thisSet and thatSet have the same size and contain the same elements.

If thatSet is nil, Equals returns true if and only if thisSet is empty.

Example: 

set1 := Empty[int]()
set2 := Empty[int]()
b1 := set1.Equals(set2) // b1 will be true
set1.Add(7)
set2.Add(31)
b2 := set1.Equals(set2) // b2 will be false

func (*Set3[T]) ImmutableRange added in v0.2.0 

func (thisSet *Set3[T]) ImmutableRange() iter.Seq[T]

Iterates over all elements in thisSet.

Makes an internal copy of the stored elements first, so you can add or remove elements to or from thisSet during the itration, for example. To avoid this extra copy, e.g., for performance reasons, choose [MutableRange].

Example: 

for elem := range set.ImmutableRange() {
	// do something with elem...
}

func (*Set3[T]) Intersect added in v0.4.0 

func (thisSet *Set3[T]) Intersect(thatSet *Set3[T]) *Set3[T]

Creates a new Set3 as a mathematical intersection between this and that. The result is a new Set3 that contains elements that are in both sets.

If thatSet is nil, Intersect returns an empty Set3.

Example: 

set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := Empty[int]()
set2.Add(3)
set2.Add(4)
intersect := set1.Intersect(set2) // set1 and set2 are not altered, intersect will contain 3

func (*Set3[T]) IntersectWithArray added in v0.4.0 

func (thisSet *Set3[T]) IntersectWithArray(data []T) *Set3[T]

Creates a new Set3 as a mathematical intersection between thisSet and the elements of the data array. The result is a new Set3.

If data is nil, IntersectWithArray returns an empty Set3.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
intersect := set.IntersectWithArray([]int{3,4}]) // set1 and set2 are not altered, intersect will contain 3

func (*Set3[T]) MutableRange added in v0.2.0 

func (thisSet *Set3[T]) MutableRange() iter.Seq[T]

Iterates over all elements in thisSet.

Caution: If thisSet is changed during the iteration, the result is unpredictable. So if you want to add or remove elements to or from thisSet during the itration, choose [ImmutableRange].

Example: 

for elem := range set.MutableRange() {
	// do something with elem...
}

func (*Set3[T]) Rehash added in v0.2.0 

func (thisSet *Set3[T]) Rehash()

Rorganizes the backend of thisSet for optimal space efficiency: This call rehashes thisSet to a size matching its current element count.

Example: 

set := Empty[int](1_000_000) // allocates a big hashset
set.Add(1)
set.Add(2)
set.Add(3)
set.Rehash() // saves memory consumed by set

func (*Set3[T]) RehashToCapacity added in v0.4.0 

func (thisSet *Set3[T]) RehashToCapacity(newCapacity uint32)

Rorganizes the backend of thisSet: RehashToCapacity redistributs the elements of thisSet onto a new hashset in its backend, e.g., to ensure faster element access.

If newSize is smaller than the current number of elements in thisSet, this function does nothing. If newSize is equal to the current number of elements in thisSet, this function does the same as [Rehash].

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
set.RehashToCapacity(1000) // ensures that you can add at least 997 more elements to set without rehashing

func (*Set3[T]) Remove 

func (thisSet *Set3[T]) Remove(element T) bool

Removes the given element from thisSet if it is in thisSet, returns whether or not the element was in thisSet.

Example: 

set := Empty[int]()
set.Add(1)
set.Remove(2)	// nothing happens to set
set.Remove(1)	// set will be empty
set.Remove(0)	// set will still be empty

func (*Set3[T]) RemoveAll added in v0.2.0 

func (thisSet *Set3[T]) RemoveAll(thatSet *Set3[T])

Removes all elements from thisSet that are in thatSet.

If thatSet is nil, nothing happens.

Example: 

set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := Empty[int]()
set2.Add(3)
set2.Add(4)
set1.RemoveAll(set2) // set1 will now contain 1, 2

func (*Set3[T]) RemoveAllFromArray added in v0.4.0 

func (thisSet *Set3[T]) RemoveAllFromArray(data []T)

Removes all elements from thisSet that are in the data array.

If data is nil, nothing happens.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
set.RemoveAllFromArray([]int{3,4}]) // set will now contain 1, 2

func (*Set3[T]) RemoveAllOf added in v0.4.0 

func (thisSet *Set3[T]) RemoveAllOf(args ...T)

Removes all elements from thisSet that are passed as arguments.

If no arguments are passed, nothing happens.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
set.RemoveAllOf(3,4) // set will now contain 1, 2

func (*Set3[T]) Size added in v0.4.0 

func (thisSet *Set3[T]) Size() uint32

Size returns the number of elements in thisSet.

Example: 

set := Empty[int]()
set.Add(7)
set.Add(8)
set.Add(9)
c := set.Size()   // c will be 3

func (*Set3[T]) String added in v0.2.0 

func (thisSet *Set3[T]) String() string

Returns a string representation of the elements of thisSet in Roster notation (https://en.wikipedia.org/wiki/Set_(mathematics)#Roster_notation). The order of the elements in the result is arbitrarily.

Example: 

set := Empty[int]()
set.Add(1)
set.Add(2)
set.Add(3)
fmt.Println(set) // will print "{2,3,1}" with the numbers in arbitrary order

func (*Set3[T]) Subtract added in v0.4.0 

func (thisSet *Set3[T]) Subtract(thatSet *Set3[T]) *Set3[T]

Creates a new Set3 as a mathematical difference between thisSet and thatSet. The result is a new Set3 that contains elements that are in thisSet but not in thatSet.

If thatSet is nil, Subtract returns a clone of thisSet.

Example: 

set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set1.Add(3)
set2 := Empty[int]()
set2.Add(3)
set2.Add(4)
d := set1.Subtract(set2) // set1 and set2 are not altered, d will contain 1, 2

func (*Set3[T]) ToArray added in v0.3.0 

func (thisSet *Set3[T]) ToArray() []T

ToArray allocates an array of type T and adds all elements of thisSet to it. The order of the elements in the resulting array is arbitrary.

Example: 

set := Empty[int]()
set.Add(7)
set.Add(31)
intArray := set.ToArray() // will be an []int of length 2 containing 7 and 31 in arbitrary order

func (*Set3[T]) Unite added in v0.4.0 

func (thisSet *Set3[T]) Unite(thatSet *Set3[T]) *Set3[T]

Creates a new Set3 as a mathematical union of the elements from thisSet and thatSet.

If thatSet is nil, Unite returns a clone of thisSet.

Example: 

set1 := Empty[int]()
set1.Add(1)
set1.Add(2)
set2 := Empty[int]()
set2.Add(2)
set2.Add(3)

u := set1.Unite(set2) // set1 and set2 remain unchanged, u will contain 1, 2, 3

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.