Set3

README

Set3

Set3 is a fast and pure set implmentation in and for Golang. I wrote it as an alternative to set implementations based on map[type]struct{}. Set3 is 15% faster and uses 40% less memory than map[type]struct{}. As hash function, Set3 uses the built-in hash function of Golang via dolthub/maphash.

The code is derived from SwissMap and it is implementing 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 (yes, the code is faster without SSE).

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.

Performance

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

go test -benchmem -benchtime=8s -timeout 115m -run="^$" -bench "^(BenchmarkSet3Fill|BenchmarkNativeMapFill|BenchmarkSet3Find|BenchmarkNativeMapFind)$" github.com/TomTonic/Set3

Please note the logarithmic scales for most axes.

Inserting Nodes in an Empty Set

Total time/additional memory/memory allocations for inserting different numbers of elements into empty sets with an initial capacity of 10 elements.

Searching Nodes in a Populated Set

Total time for searching 5000 elements in sets of different sizes, 30% hit ratio. Tests performed with commit id ceed986615c10f0b1493b855f703f880c1dedc9b, reduced maxAvgGroupLoad to 6.5, i.e. same as map[type]struct{}. Mean size ratio drops to 0.608.

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, lookups are 15% faster and the data structure uses 40% less memory than implementations based on `map[type]struct{}`.

Index

• type Set3
  • func AsSet3[T comparable](data []T) *Set3[T]
  • func NewSet3[T comparable]() *Set3[T]
  • func NewSet3WithSize[T comparable](size uint32) *Set3[T]
  • func (this *Set3[T]) Add(element T)
  • func (this *Set3[T]) AddAll(that *Set3[T])
  • func (this *Set3[T]) AddAllFrom(data []T)
  • func (Set3 *Set3[T]) Clear()
  • func (this *Set3[T]) Clone() *Set3[T]
  • func (this *Set3[T]) Contains(element T) bool
  • func (this *Set3[T]) ContainsAll(that *Set3[T]) bool
  • func (this *Set3[T]) ContainsAllFrom(data []T) bool
  • func (this *Set3[T]) Count() uint32
  • func (this *Set3[T]) Difference(that *Set3[T]) *Set3[T]
  • func (this *Set3[T]) Equals(that *Set3[T]) bool
  • func (this *Set3[T]) ImmutableRange() iter.Seq[T]
  • func (this *Set3[T]) Intersection(that *Set3[T]) *Set3[T]
  • func (this *Set3[T]) MutableRange() iter.Seq[T]
  • func (this *Set3[T]) Rehash()
  • func (this *Set3[T]) RehashTo(newSize uint32)
  • func (this *Set3[T]) Remove(element T) bool
  • func (this *Set3[T]) RemoveAll(that *Set3[T])
  • func (this *Set3[T]) RemoveAllFrom(data []T)
  • func (this Set3[T]) String() string
  • func (this *Set3[T]) Union(that *Set3[T]) *Set3[T]

Types

type Set3

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

Set3 is a set if type K

func AsSet3

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

AsSet3 is a convenience constructor to directly create a Set3 from given values. It creates a Set3 with the required capacity and adds all (unique) elements to this Set3. If the array contains duplicates, the duplicates will be omited. Use it like:

myset := AsSet3([]int{1, 2, 3, 4})

func NewSet3

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

NewSet3 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 wil 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.

func NewSet3WithSize

func NewSet3WithSize[T comparable](size uint32) *Set3[T]

NewSet3WithSize 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.

func (*Set3[T]) Add

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

Add attempts to insert |element|

func (*Set3[T]) AddAll

func (this *Set3[T]) AddAll(that *Set3[T])

Attempts to insert all elements from |that| into |this| Set3.

func (*Set3[T]) AddAllFrom

func (this *Set3[T]) AddAllFrom(data []T)

Attempts to insert all elements from |that| into |this| Set3.

func (*Set3[T]) Clear

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

Clear removes all elements from the Set3.

func (*Set3[T]) Clone

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

Clone creates an exact clone of this Set3. Cloning is rather cheap in comparison with creating a new set and adding all nodes from this set, as the backing data structures are just copied. You can manipulate both clones independently.

func (*Set3[T]) Contains

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

Contains returns true if the element is present in the Set3.

func (*Set3[T]) ContainsAll

func (this *Set3[T]) ContainsAll(that *Set3[T]) bool

func (*Set3[T]) ContainsAllFrom

func (this *Set3[T]) ContainsAllFrom(data []T) bool

func (*Set3[T]) Count

func (this *Set3[T]) Count() uint32

Count returns the number of elements in the Map.

func (*Set3[T]) Difference

func (this *Set3[T]) Difference(that *Set3[T]) *Set3[T]

Creates a new Set3 as a mathematical difference between |this| and |that|; i.e. the result contains nodes that are in |this| but not in |that|.

func (*Set3[T]) Equals

func (this *Set3[T]) Equals(that *Set3[T]) bool

func (*Set3[T]) ImmutableRange

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

Iterates over all elements in this |Set3|. Makes an internal copy of the stored elements first. To avoid this copy, choose MutableRange()

func (*Set3[T]) Intersection

func (this *Set3[T]) Intersection(that *Set3[T]) *Set3[T]

Creates a new Set3 as a mathematical intersection between |this| and |that|; i.e. the result contains nodes that are in |this| and in |that|.

func (*Set3[T]) MutableRange

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

Iterates over all elements in this |Set3|. Caution: If the |Set3| is changed during the iteration, the result may be arbitrary. If the |Set3| might get changed during the itration, you might prefer ImmutableRange()

func (*Set3[T]) Rehash

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

Rorganize Set3 for optimal space efficiency: This call rehashes the the Set3 to a size matching its current element count.

func (*Set3[T]) RehashTo

func (this *Set3[T]) RehashTo(newSize uint32)

Rorganize Set3 for better performance: You can assign the elements of this Set3 to a bigger hash structure in the backend to ensure fastest element access. If |newSize| is smaller than the current number of elements in the |Set3|, this function does nothing.

func (*Set3[T]) Remove

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

Remove attempts to remove |element|, returns true if the |element| was in the |Set3|

func (*Set3[T]) RemoveAll

func (this *Set3[T]) RemoveAll(that *Set3[T])

Attempts to insert all elements from |that| into |this| Set3.

func (*Set3[T]) RemoveAllFrom

func (this *Set3[T]) RemoveAllFrom(data []T)

Attempts to insert all elements from |that| into |this| Set3.

func (Set3[T]) String

func (this Set3[T]) String() string

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

func (*Set3[T]) Union

func (this *Set3[T]) Union(that *Set3[T]) *Set3[T]

Creates a new Set3 as a mathematical union of the elements from |this| and |that|.