README
¶
freelist
Pure Go generic implementation of freelist allocator.
It allows faster allocation and reuse of small objects, making some implementations of datastructures (linked lists, trees, ...) significantly more efficient.
Key features:
- Unlike many other implementations, it doesn't ruin garbage collection for pointers inside allocated objects and plays nicely with garbage collector.
- Unlike many other implementations, it doesn't depend on CGO and doesn't encumber builds.
Usage
See godoc examples.
Benchmarks
Here is benchmarks of original container/list.List (BenchmarkContainerList.*) versus the same List, but augmented by this freelist package (BenchmarkFreelistList.*).
goos: linux
goarch: amd64
pkg: github.com/Snawoot/freelist
cpu: Intel(R) N100
BenchmarkContainerList/PushFront-4 10445557 119.1 ns/op 55 B/op 1 allocs/op
BenchmarkContainerList/PushPopFront-4 6943459 167.8 ns/op 55 B/op 1 allocs/op
BenchmarkContainerList/PushPopFrontImmediate-4 13197672 90.06 ns/op 56 B/op 1 allocs/op
BenchmarkFreelistList/PushFront-4 16623741 77.49 ns/op 62 B/op 0 allocs/op
BenchmarkFreelistList/PushPopFront-4 18434035 70.82 ns/op 56 B/op 0 allocs/op
BenchmarkFreelistList/PushPopFrontImmediate-4 41839992 29.08 ns/op 8 B/op 0 allocs/op
BenchmarkFreelistList/WarmedUpPushFront-4 50492380 23.67 ns/op 7 B/op 0 allocs/op
BenchmarkFreelistList/WarmedUpPushPopFront-4 41505009 29.39 ns/op 7 B/op 0 allocs/op
BenchmarkBuiltinNew-4 63081798 19.17 ns/op 8 B/op 1 allocs/op
BenchmarkFreelistAlloc-4 72595954 16.48 ns/op 19 B/op 0 allocs/op
BenchmarkWarmedUpFreelistAlloc-4 294823388 4.159 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/Snawoot/freelist 30.642s
As you can see it performs about twice faster than original container/list.List in worst case and performs 3-5 times faster once freelist reaches right size.
Documentation
¶
Overview ¶
Package freelist provides generic implementation of freelist allocator in pure Go.
It is useful for implementation of algorithms and data structures using a lot of small objects. To some extent it is similar to sync.Pool. But unlike sync.Pool, this package provides more predictable retention, type safety and control over lifecycle of allocated objects. On the other hand, this package requires allocated objects to be explicitly freed to avoid memory leaks.
Example ¶
package main
import (
"encoding/json"
"fmt"
"io"
"log"
"strings"
"github.com/Snawoot/freelist"
)
func main() {
const jsonStream = `
{"Name": "Ed", "Text": "Knock knock."}
{"Name": "Sam", "Text": "Who's there?"}
{"Name": "Ed", "Text": "Go fmt."}
{"Name": "Sam", "Text": "Go fmt who?"}
{"Name": "Ed", "Text": "Go fmt yourself!"}
`
type Message struct {
Name, Text string
}
dec := json.NewDecoder(strings.NewReader(jsonStream))
var messages []*Message
var allocator freelist.Freelist[Message]
for {
m := allocator.Alloc()
if err := dec.Decode(m); err == io.EOF {
break
} else if err != nil {
log.Fatal(err)
}
messages = append(messages, m)
}
for _, m := range messages {
fmt.Printf("%s: %s\n", m.Name, m.Text)
allocator.Free(m)
}
messages = nil // make sure pointers released
}
Output:
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Freelist ¶
type Freelist[T any] struct { // If NextCapFn is not nil, it is called to query next capacity value // on freelist auto-grow. The currentCap argument of that function // is the number of objects freelist can hold at this moment and // the returned value is the new capacity. Returned value must be larger // than the current capacity, otherwise panic will occur. // // If NextCapFn is nil, default function is used, which doubles capacity // if it is smaller than 1024 (but adds no less than 64 elements) and // adds 25% of current capacity if current capacity is greater or equal 1024. // // Note that Freelist can be also expanded explicitly by [Freelist.Grow], // which means currentCap passed to NextCapFn may be not one of the // values returned by NextCapFn previously. NextCapFn func(currentCap int) int // contains filtered or unexported fields }
A Freelist is an instance of freelist allocator of objects of type T. The zero value for Freelist is an empty freelist ready to use.
A Freelist should not be copied after first use.
Methods of Freelist are not safe for concurrent use by multiple goroutines.
func (*Freelist[T]) Alloc ¶
func (fl *Freelist[T]) Alloc() *T
Alloc allocates new object. Allocated pointers should be eventually disposed with either:
- Passing pointer to Freelist.Free.
- Clearing entire freelist with Freelist.Clear.
- Dropping reference to entire Freelist and all objects allocated from it.
func (*Freelist[T]) Clear ¶
func (fl *Freelist[T]) Clear()
Clear resets freelist to initial empty state.
func (*Freelist[T]) Free ¶
func (fl *Freelist[T]) Free(x *T)
Free deallocates object previously allocated by Freelist.Alloc. Free immediately overwrites freed memory with zero value of corresponding type T and marks memory as available for reuse.
Pointer to deallocated object should not be used after call to Free.
Source Files