Golang manages memory via GC and it's good for almost every use case but sometimes it can be a bottleneck. and this is where mm-go comes in to play.
go get -u github.com/joetifa2003/mm-go
type MyStruct struct {
a int
b float32
}
func Example_datastructures() {
alloc := allocator.NewC()
defer alloc.Destroy()
p := allocator.Alloc[MyStruct](alloc)
defer allocator.Free(alloc, p)
p.a = 100
p.b = 200
fmt.Println(*p)
v := vector.New[int](alloc)
defer v.Free()
v.Push(15)
v.Push(70)
for _, i := range v.Iter() {
fmt.Println(i)
}
l := linkedlist.New[*mmstring.MMString](alloc)
defer l.Free()
l.PushBack(mmstring.From(alloc, "hello"))
l.PushBack(mmstring.From(alloc, "world"))
for _, i := range l.Iter() {
fmt.Println(i.GetGoString())
}
// Output:
// {100 200}
// 15
// 70
// hello
// world
}
mm-go
is built around the concept of Allocators, which is an interface that can be implemented and passed around to the library.
You use these allocators to allocate memory, and also allocate datastructures like vectors, linkedlists, hashmaps, etc.
Check the test files and github actions for the benchmarks (linux, macos, windows). mm-go can sometimes be 5-10 times faster.
Run go test ./... -bench=. -count 5 > out.txt && benchstat out.txt
goos: linux
goarch: amd64
pkg: github.com/joetifa2003/mm-go
cpu: AMD Ryzen 7 5800H with Radeon Graphics
│ out.txt │
│ sec/op │
LinkedListManaged-16 605.7µ ± ∞ ¹
LinkedListCAlloc-16 933.1µ ± ∞ ¹
LinkedListBatchAllocator/bucket_size_100-16 513.3µ ± ∞ ¹
LinkedListBatchAllocator/bucket_size_200-16 405.8µ ± ∞ ¹
LinkedListBatchAllocator/bucket_size_500-16 425.4µ ± ∞ ¹
LinkedListBatchAllocator/bucket_size_10000-16 200.7µ ± ∞ ¹
LinkedListTypedArena/chunk_size_100-16 105.3µ ± ∞ ¹
LinkedListTypedArena/chunk_size_200-16 95.50µ ± ∞ ¹
LinkedListTypedArena/chunk_size_500-16 83.02µ ± ∞ ¹
LinkedListTypedArena/chunk_size_10000-16 75.96µ ± ∞ ¹
geomean 240.1µ
¹ need >= 6 samples for confidence interval at level 0.95
pkg: github.com/joetifa2003/mm-go/hashmap
│ out.txt │
│ sec/op │
HashmapGo-16 210.7µ ± ∞ ¹
HashmapCAlloc-16 189.1µ ± ∞ ¹
HashmapBatchAlloc-16 118.2µ ± ∞ ¹
geomean 167.6µ
¹ need >= 6 samples for confidence interval at level 0.95
import "github.com/joetifa2003/mm-go"
func SizeOf[T any]() int
SizeOf returns the size of T in bytes
fmt.Println(mm.SizeOf[int32]())
fmt.Println(mm.SizeOf[int64]())
// Output:
// 4
// 8
4
8
func Zero[T any]() T
Zero returns a zero value of T
import "github.com/joetifa2003/mm-go/allocator"
package main
import (
"fmt"
"github.com/joetifa2003/mm-go/allocator"
)
func main() {
alloc := allocator.NewC()
defer alloc.Destroy()
ptr := allocator.Alloc[int](alloc)
defer allocator.Free(alloc, ptr)
*ptr = 15
fmt.Println(*ptr)
}
15
package main
import (
"fmt"
"github.com/joetifa2003/mm-go/allocator"
"github.com/joetifa2003/mm-go/linkedlist"
"github.com/joetifa2003/mm-go/mmstring"
"github.com/joetifa2003/mm-go/vector"
)
type MyStruct struct {
a int
b float32
}
func main() {
alloc := allocator.NewC()
defer alloc.Destroy() // all the memory allocated bellow will be freed, no need to free it manually.
p := allocator.Alloc[MyStruct](alloc)
defer allocator.Free(alloc, p)
p.a = 100
p.b = 200
fmt.Println(*p)
v := vector.New[int](alloc)
defer v.Free()
v.Push(15)
v.Push(70)
for _, i := range v.Iter() {
fmt.Println(i)
}
l := linkedlist.New[*mmstring.MMString](alloc)
defer l.Free()
l.PushBack(mmstring.From(alloc, "hello"))
l.PushBack(mmstring.From(alloc, "world"))
for _, i := range l.Iter() {
fmt.Println(i.GetGoString())
}
}
{100 200}
15
70
hello
world
func Alloc[T any](a Allocator) *T
Alloc allocates T and returns a pointer to it.
alloc := allocator.NewC()
defer alloc.Destroy()
// So you can do this:
ptr := allocator.Alloc[int](alloc) // allocates a single int and returns a ptr to it
defer allocator.Free(alloc, ptr) // frees the int (defer recommended to prevent leaks)
*ptr = 15
fmt.Println(*ptr)
// instead of doing this:
ptr2 := (*int)(alloc.Alloc(mm.SizeOf[int]()))
defer alloc.Free(unsafe.Pointer(ptr2))
*ptr2 = 15
fmt.Println(*ptr2)
// Output:
// 15
// 15
15
15
func AllocMany[T any](a Allocator, n int) []T
AllocMany allocates n of T and returns a slice representing the heap. CAUTION: don't append to the slice, the purpose of it is to replace pointer arithmetic with slice indexing
package main
import (
"fmt"
"github.com/joetifa2003/mm-go/allocator"
)
func main() {
alloc := allocator.NewC()
defer alloc.Destroy()
heap := allocator.AllocMany[int](alloc, 2) // allocates 2 ints and returns it as a slice of ints with length 2
defer allocator.FreeMany(alloc, heap) // it's recommended to make sure the data gets deallocated (defer recommended to prevent leaks)
heap[0] = 15 // changes the data in the slice (aka the heap)
ptr := &heap[0] // takes a pointer to the first int in the heap
// Be careful if you do ptr := heap[0] this will take a copy from the data on the heap
*ptr = 45 // changes the value from 15 to 45
heap[1] = 70
fmt.Println(heap[0])
fmt.Println(heap[1])
}
45
70
func Free[T any](a Allocator, ptr *T)
FreeMany frees memory allocated by Alloc takes a ptr CAUTION: be careful not to double free, and prefer using defer to deallocate
func FreeMany[T any](a Allocator, slice []T)
FreeMany frees memory allocated by AllocMany takes in the slice (aka the heap) CAUTION: be careful not to double free, and prefer using defer to deallocate
func Realloc[T any](a Allocator, slice []T, newN int) []T
Realloc reallocates memory allocated with AllocMany and doesn't change underling data
package main
import (
"fmt"
"github.com/joetifa2003/mm-go/allocator"
)
func main() {
alloc := allocator.NewC()
defer alloc.Destroy()
heap := allocator.AllocMany[int](alloc, 2) // allocates 2 int and returns it as a slice of ints with length 2
heap[0] = 15
heap[1] = 70
heap = allocator.Realloc(alloc, heap, 3)
heap[2] = 100
fmt.Println(heap[0])
fmt.Println(heap[1])
fmt.Println(heap[2])
allocator.FreeMany(alloc, heap)
}
15
70
100
Allocator is an interface that defines some methods needed for most allocators. It's not a golang interface, so it's safe to use in manually managed structs (will not get garbage collected).
type Allocator struct {
// contains filtered or unexported fields
}
func NewAllocator(allocator unsafe.Pointer, alloc func(allocator unsafe.Pointer, size int) unsafe.Pointer, free func(allocator unsafe.Pointer, ptr unsafe.Pointer), realloc func(allocator unsafe.Pointer, ptr unsafe.Pointer, size int) unsafe.Pointer, destroy func(allocator unsafe.Pointer)) Allocator
NewAllocator creates a new Allocator
package main
import (
"unsafe"
"github.com/joetifa2003/mm-go/allocator"
)
func main() {
// Create a custom allocator
alloc := allocator.NewAllocator(
nil,
myallocator_alloc,
myallocator_free,
myallocator_realloc,
myallocator_destroy,
)
// Check how C allocator is implemented
// or batchallocator source for a reference
_ = alloc
}
func myallocator_alloc(allocator unsafe.Pointer, size int) unsafe.Pointer {
return nil
}
func myallocator_free(allocator unsafe.Pointer, ptr unsafe.Pointer) {
}
func myallocator_realloc(allocator unsafe.Pointer, ptr unsafe.Pointer, size int) unsafe.Pointer {
return nil
}
func myallocator_destroy(allocator unsafe.Pointer) {
}
func NewC() Allocator
NewC returns an allocator that uses C calloc, realloc and free.
func (a Allocator) Alloc(size int) unsafe.Pointer
Alloc allocates size bytes and returns an unsafe pointer to it.
func (a Allocator) Destroy()
Destroy destroys the allocator. After calling this, the allocator is no longer usable. This is useful for cleanup, freeing allocator internal resources, etc.
func (a Allocator) Free(ptr unsafe.Pointer)
Free frees the memory pointed by ptr
func (a Allocator) Realloc(ptr unsafe.Pointer, size int) unsafe.Pointer
Realloc reallocates the memory pointed by ptr with a new size and returns a new pointer to it.
import "github.com/joetifa2003/mm-go/batchallocator"
This allocator purpose is to reduce the overhead of calling CGO on every allocation/free, it also acts as an arena since it frees all the memory when `Destroy` is called. It allocats large chunks of memory at once and then divides them when you allocate, making it much faster. This allocator has to take another allocator for it to work, usually with the C allocator. You can optionally call `Free` on the pointers allocated by batchallocator manually, and it will free the memory as soon as it can. `Destroy` must be called to free internal resources and free all the memory allocated by the allocator.
package main
import (
"github.com/joetifa2003/mm-go/allocator"
"github.com/joetifa2003/mm-go/batchallocator"
)
func main() {
alloc := batchallocator.New(allocator.NewC()) // by default it allocates page, which is usually 4kb
defer alloc.Destroy() // this frees all memory allocated by the allocator automatically
ptr := allocator.Alloc[int](alloc)
// but you can still free the pointers manually if you want (will free buckets of memory if all pointers depending on it is freed)
defer allocator.Free(alloc, ptr) // this can removed and the memory will be freed.
}
package main
import (
"fmt"
"github.com/joetifa2003/mm-go/allocator"
"github.com/joetifa2003/mm-go/batchallocator"
"github.com/joetifa2003/mm-go/linkedlist"
"github.com/joetifa2003/mm-go/mmstring"
"github.com/joetifa2003/mm-go/vector"
)
func main() {
alloc := batchallocator.New(allocator.NewC())
defer alloc.Destroy() // all the memory allocated bellow will be freed, no need to free it manually.
v := vector.New[int](alloc)
v.Push(15)
v.Push(70)
for _, i := range v.Iter() {
fmt.Println(i)
}
l := linkedlist.New[*mmstring.MMString](alloc)
l.PushBack(mmstring.From(alloc, "hello"))
l.PushBack(mmstring.From(alloc, "world"))
for _, i := range l.Iter() {
fmt.Println(i.GetGoString())
}
}
15
70
hello
world
func New(a allocator.Allocator, options ...BatchAllocatorOption) allocator.Allocator
New creates a new BatchAllocator and applies optional configuration using BatchAllocatorOption
BatchAllocator manages a collection of memory buckets to optimize small allocations
type BatchAllocator struct {
// contains filtered or unexported fields
}
type BatchAllocatorOption func(alloc *BatchAllocator)
func WithBucketSize(size int) BatchAllocatorOption
WithBucketSize Option to specify bucket size when creating BatchAllocator You can allocate more memory than the bucketsize in one allocation, it will allocate a new bucket and put the data in it.
alloc := batchallocator.New(
allocator.NewC(),
batchallocator.WithBucketSize(mm.SizeOf[int]()*15), // configure the allocator to allocate size of 15 ints per bucket.
)
defer alloc.Destroy()
ptr := allocator.Alloc[int](alloc)
defer allocator.Free(alloc, ptr) // this can be removed and the memory will still be freed on Destroy.
ptr2 := allocator.Alloc[int](alloc) // will not call CGO because there is still enough memory in the Bucket.
defer allocator.Free(alloc, ptr2) // this can be removed and the memory will still be freed on Destroy.
import "github.com/joetifa2003/mm-go/hashmap"
alloc := batchallocator.New(allocator.NewC())
defer alloc.Destroy()
hm := New[int, int](alloc)
defer hm.Free() // can be removed
hm.Set(1, 10)
hm.Set(2, 20)
hm.Set(3, 30)
sumKeys := 0
sumValues := 0
for k, v := range hm.Iter() {
sumKeys += k
sumValues += v
}
fmt.Println(sumKeys)
fmt.Println(sumValues)
// Output:
// 6
// 60
6
60
Hashmap Manually managed hashmap,
type Hashmap[K comparable, V any] struct {
// contains filtered or unexported fields
}
func New[K comparable, V any](alloc allocator.Allocator) *Hashmap[K, V]
New creates a new Hashmap with key of type K and value of type V
func (hm *Hashmap[K, V]) Delete(key K)
Delete delete value with key K
func (hm *Hashmap[K, V]) Free()
Free frees the Hashmap
func (hm *Hashmap[K, V]) Get(key K) (value V, exists bool)
Get takes key K and return value V
func (hm *Hashmap[K, V]) GetPtr(key K) (value *V, exists bool)
GetPtr takes key K and return a pointer to value V
func (hm *Hashmap[K, V]) Iter() iter.Seq2[K, V]
Iter returns an iterator over all key/value pairs
func (hm *Hashmap[K, V]) Keys() []K
Keys returns all keys as a slice
func (hm *Hashmap[K, V]) Set(key K, value V)
Set inserts a new value V if key K doesn't exist, Otherwise update the key K with value V
func (hm *Hashmap[K, V]) Values() []V
Values returns all values as a slice
import "github.com/joetifa2003/mm-go/linkedlist"
alloc := allocator.NewC()
defer alloc.Destroy()
ll := New[int](alloc)
defer ll.Free()
ll.PushBack(1)
ll.PushBack(2)
ll.PushBack(3)
ll.PushBack(4)
fmt.Println("PopBack:", ll.PopBack())
fmt.Println("PopFront:", ll.PopFront())
for _, i := range ll.Iter() {
fmt.Println(i)
}
// Output:
// PopBack: 4
// PopFront: 1
// 2
// 3
PopBack: 4
PopFront: 1
2
3
LinkedList a doubly-linked list. Note: can be a lot slower than Vector but sometimes faster in specific use cases
type LinkedList[T any] struct {
// contains filtered or unexported fields
}
func New[T any](alloc allocator.Allocator) *LinkedList[T]
New creates a new linked list.
func (ll *LinkedList[T]) At(idx int) T
At gets value T at idx.
func (ll *LinkedList[T]) AtPtr(idx int) *T
AtPtr gets a pointer to value T at idx.
func (ll *LinkedList[T]) FindIndex(f func(value T) bool) (idx int, ok bool)
FindIndex returns the first index of value T that pass the test implemented by the provided function.
func (ll *LinkedList[T]) FindIndexes(f func(value T) bool) []int
FindIndex returns all indexes of value T that pass the test implemented by the provided function.
func (ll *LinkedList[T]) ForEach(f func(idx int, value T))
ForEach iterates through the linked list.
func (ll *LinkedList[T]) Free()
Free frees the linked list.
func (ll *LinkedList[T]) Iter() iter.Seq2[int, T]
Iter returns an iterator over the linked list values.
func (ll *LinkedList[T]) Len() int
Len gets linked list length.
func (ll *LinkedList[T]) PopBack() T
PopBack pops and returns value T from the back of the linked list.
func (ll *LinkedList[T]) PopFront() T
PopFront pops and returns value T from the front of the linked list.
func (ll *LinkedList[T]) PushBack(value T)
PushBack pushes value T to the back of the linked list.
func (ll *LinkedList[T]) PushFront(value T)
PushFront pushes value T to the back of the linked list.
func (ll *LinkedList[T]) Remove(f func(idx int, value T) bool) (value T, ok bool)
Remove removes the first value T that pass the test implemented by the provided function. if the test succeeded it will return the value and true
func (ll *LinkedList[T]) RemoveAll(f func(idx int, value T) bool) []T
RemoveAll removes all values of T that pass the test implemented by the provided function.
func (ll *LinkedList[T]) RemoveAt(idx int) T
RemoveAt removes value T at specified index and returns it.
import "github.com/joetifa2003/mm-go/minheap"
package main
import (
"fmt"
"github.com/joetifa2003/mm-go/allocator"
"github.com/joetifa2003/mm-go/minheap"
)
func int_less(a, b int) bool { return a < b }
func main() {
alloc := allocator.NewC()
defer alloc.Destroy()
h := minheap.New[int](alloc, int_less)
// Push some values onto the heap
h.Push(2)
h.Push(1)
h.Push(4)
h.Push(3)
h.Push(5)
// Pop the minimum value from the heap
fmt.Println(h.Pop())
fmt.Println(h.Pop())
}
1
2
package main
import (
"fmt"
"github.com/joetifa2003/mm-go/allocator"
"github.com/joetifa2003/mm-go/minheap"
)
func int_greater(a, b int) bool { return a > b }
func main() {
alloc := allocator.NewC()
defer alloc.Destroy()
h := minheap.New[int](alloc, int_greater)
// Push some values onto the heap
h.Push(2)
h.Push(1)
h.Push(4)
h.Push(3)
h.Push(5)
// Pop the max value from the heap
fmt.Println(h.Pop())
fmt.Println(h.Pop())
}
5
4
type MinHeap[T any] struct {
// contains filtered or unexported fields
}
func New[T any](alloc allocator.Allocator, less func(a, b T) bool) *MinHeap[T]
New creates a new MinHeap.
func (h *MinHeap[T]) Free()
Free frees the heap.
func (h *MinHeap[T]) Iter() iter.Seq2[int, T]
Iter returns an iterator over the elements of the heap.
func (h *MinHeap[T]) Len() int
Len returns the number of elements in the heap.
func (h *MinHeap[T]) Peek() T
Peek returns the minimum value from the heap without removing it.
func (h *MinHeap[T]) Pop() T
Pop removes and returns the minimum value from the heap.
func (h *MinHeap[T]) Push(value T)
Push adds a value to the heap.
func (h *MinHeap[T]) Remove(f func(T) bool)
Remove the first element that makes f return true
import "github.com/joetifa2003/mm-go/mmstring"
package main
import (
"fmt"
"github.com/joetifa2003/mm-go/allocator"
"github.com/joetifa2003/mm-go/mmstring"
)
func main() {
alloc := allocator.NewC()
defer alloc.Destroy()
s := mmstring.New(alloc)
defer s.Free()
s.AppendGoString("Hello ")
s.AppendGoString("World")
s2 := mmstring.From(alloc, "Foo Bar")
defer s2.Free()
fmt.Println(s.GetGoString())
fmt.Println(s2.GetGoString())
}
Hello World
Foo Bar
package main
import (
"fmt"
"github.com/joetifa2003/mm-go/allocator"
"github.com/joetifa2003/mm-go/batchallocator"
"github.com/joetifa2003/mm-go/mmstring"
"github.com/joetifa2003/mm-go/vector"
)
func main() {
alloc := batchallocator.New(allocator.NewC())
defer alloc.Destroy() // all the memory allocated bellow will be freed, no need to free it manually.
m := vector.New[*mmstring.MMString](alloc)
m.Push(mmstring.From(alloc, "hello"))
m.Push(mmstring.From(alloc, "world"))
for k, v := range m.Iter() {
fmt.Println(k, v.GetGoString())
}
}
0 hello
1 world
MMString is a manually manged string that is basically a *Vector[rune] and contains all the methods of a vector plus additional helper functions
type MMString struct {
// contains filtered or unexported fields
}
func From(alloc allocator.Allocator, input string) *MMString
From creates a new manually managed string, And initialize it with a go string
func New(alloc allocator.Allocator) *MMString
New create a new manually managed string
func (s *MMString) AppendGoString(input string)
AppendGoString appends go string to manually managed string
func (s *MMString) Free()
Free frees MMString
func (s *MMString) GetGoString() string
GetGoString returns go string from manually managed string. CAUTION: You also have to free the MMString
import "github.com/joetifa2003/mm-go/typedarena"
typedarena is a growable typed arena that allocates memory in fixed chunks , it's faster that batchallocator but more limited, you can use batchallocator if you want to allocate multiple different types, and you want to use an arena like behavior spanning multiple datastructures (like vector, linkedlist, hashmap etc..), typedarena is much faster when you are only allocating one type.
package main
import (
"fmt"
"github.com/joetifa2003/mm-go/allocator"
"github.com/joetifa2003/mm-go/typedarena"
)
type Entity struct {
VelocityX float32
VelocityY float32
PositionX float32
PositionY float32
}
func main() {
alloc := allocator.NewC()
defer alloc.Destroy()
arena := typedarena.New[Entity](
alloc,
10,
)
defer arena.Free() // frees all memory
for i := 0; i < 10; i++ {
e := arena.Alloc() // *Entity
e.VelocityX = float32(i)
e.VelocityY = float32(i)
e.PositionX = float32(i)
e.PositionY = float32(i)
fmt.Println(e.VelocityX, e.VelocityY, e.PositionX, e.PositionY)
}
entities := arena.AllocMany(10) // allocate slice of 10 entities (cannot exceed 10 here because chunk size is 10 above, this limitation doesn't exist in batchallocator)
_ = entities
}
0 0 0 0
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
5 5 5 5
6 6 6 6
7 7 7 7
8 8 8 8
9 9 9 9
TypedArena is a growable typed arena
type TypedArena[T any] struct {
// contains filtered or unexported fields
}
func New[T any](alloc allocator.Allocator, chunkSize int) *TypedArena[T]
New creates a typed arena with the specified chunk size. a chunk is the the unit of the arena, if T is int for example and the chunk size is 5, then each chunk is going to hold 5 ints. And if the chunk is filled it will allocate another chunk that can hold 5 ints. then you can call FreeArena and it will deallocate all chunks together
func (ta *TypedArena[T]) Alloc() *T
Alloc allocates T from the arena
func (ta *TypedArena[T]) AllocMany(n int) []T
AllocMany allocates n of T and returns a slice representing the heap. CAUTION: don't append to the slice, the purpose of it is to replace pointer arithmetic with slice indexing CAUTION: n cannot exceed chunk size
func (ta *TypedArena[T]) Free()
Free frees all allocated memory
import "github.com/joetifa2003/mm-go/vector"
package main
import (
"fmt"
"github.com/joetifa2003/mm-go/allocator"
"github.com/joetifa2003/mm-go/vector"
)
func main() {
alloc := allocator.NewC()
v := vector.New[int](alloc)
v.Push(1)
v.Push(2)
v.Push(3)
fmt.Println("Length:", v.Len())
for i := 0; i < v.Len(); i++ {
fmt.Println(v.At(i))
}
for _, k := range v.Iter() {
fmt.Println(k)
}
}
Length: 3
1
2
3
1
2
3
Vector a contiguous growable array type
type Vector[T any] struct {
// contains filtered or unexported fields
}
func Init[T any](alloc allocator.Allocator, values ...T) *Vector[T]
Init initializes a new vector with the T elements provided and sets it's len and cap to len(values)
func New[T any](aloc allocator.Allocator, args ...int) *Vector[T]
New creates a new empty vector, if args not provided it will create an empty vector, if only one arg is provided it will init a vector with len and cap equal to the provided arg, if two args are provided it will init a vector with len = args[0] cap = args[1]
func (v *Vector[T]) At(idx int) T
At gets element T at specified index
func (v *Vector[T]) AtPtr(idx int) *T
AtPtr gets element a pointer of T at specified index
func (v *Vector[T]) Cap() int
Cap gets vector capacity (underling memory length).
func (v *Vector[T]) Free()
Free deallocats the vector
func (v *Vector[T]) Iter() iter.Seq2[int, T]
Iter iterates over the vector
func (v *Vector[T]) Last() T
Last gets the last element from a vector
func (v *Vector[T]) Len() int
Len gets vector length
func (v *Vector[T]) Pop() T
Pop pops value T from the vector and returns it
func (v *Vector[T]) Push(value T)
Push pushes value T to the vector, grows if needed.
func (v *Vector[T]) RemoveAt(idx int) T
func (v *Vector[T]) Set(idx int, value T)
Set sets element T at specified index
func (v *Vector[T]) Slice() []T
Slice gets a slice representing the vector CAUTION: don't append to this slice, this is only used if you want to loop on the vec elements
func (v *Vector[T]) UnsafeAt(idx int) T
UnsafeAT gets element T at specified index without bounds checking
Generated by gomarkdoc