README
¶
spack
spack is a minimal, high-performance string pack library for Go. It compresses a collection of strings into a single, contiguous byte slice using prefix and suffix overlap deduplication.
The resulting blob is flat, coherent and highly optimized for writing to a file and memory mapping (mmap).
Key Features
- Single Coherent Blob: Packing emits a single byte slice and an array of compact, 5-byte pointers. Perfect for direct disk serialization and zero-copy mmap.
- O(1) Lookups: Retrieving strings is a flat, simple offset lookup.
- Standalone Usability: GetString and GetStringUnsafe are decoupled from any struct. They operate directly on raw byte slices using the 5-byte Pointer, facilitating easy integration with mmap libraries.
- Zero Allocation Options: Unsafe retrieval returns views over the original block using Go string headers to avoid allocation.
Performance
Packing 81.8 million strings (which originally occupy 3.05 GB of heap space for slice/string headers and characters) takes about 30 seconds.
The process outputs a flat 1.18 GB byte blob, which is a 61.08% reduction in raw string data. Including the compact 5-byte pointers, the total in-memory size is 1.6 GB, yielding an overall 47.66% memory footprint reduction. The compression/packing stage runs with a net peak heap allocation of about 3.7 GB over the dataset baseline.
Usage
package main
import (
"fmt"
"github.com/coalaura/spack"
)
func main() {
// collect strings
sm := spack.NewStringMap(nil)
idx1, _ := sm.Add("hello world")
idx2, _ := sm.Add("world")
// pack strings into a flat blob
packed, err := sm.Pack()
if err != nil {
panic(err)
}
rawBytes := packed.Bytes()
pointers := packed.Pointers()
// independent, O(1) lookups on the raw bytes
str1, _ := spack.GetStringUnsafe(rawBytes, pointers[idx1])
str2, _ := spack.GetStringUnsafe(rawBytes, pointers[idx2])
fmt.Println(str1) // "hello world"
fmt.Println(str2) // "world"
}
Constraints
Individual strings cannot exceed 255 bytes (MaxStringLen is constrained by the 8-bit pointer length field).
Documentation
¶
Index ¶
- Constants
- Variables
- func GetString(packed []byte, pointer Pointer) (string, error)
- func GetStringUnsafe(packed []byte, pointer Pointer) (string, error)
- type PackedBlob
- type Pointer
- type StringMap
- func (s *StringMap) Add(str string) (int, error)
- func (s *StringMap) AddUnsafe(b []byte) (int, error)
- func (s *StringMap) GetString(index int) string
- func (s *StringMap) Length() int
- func (s *StringMap) Pack() (*PackedBlob, error)
- func (s *StringMap) Size() int
- func (s *StringMap) Strings() []string
Constants ¶
const ( // MaxStringLen is the maximum allowed length of a string to be packed. // This limit is constrained because the Pointer.Length field is a uint8. MaxStringLen = math.MaxUint8 )
Variables ¶
var ErrStringTooLong = fmt.Errorf("length exceeds max %d", MaxStringLen)
Functions ¶
func GetString ¶
Get returns a copied, independent string from the packed blob. It allocates a new underlying buffer to ensure the returned string can safely outlive the blob and remains isolated from any future mutations.
func GetStringUnsafe ¶
GetUnsafe returns a zero-copy string pointing directly into the blob's memory. It is fast but unsafe: the returned string's lifetime is tied to the blob, and it will reflect any future modifications made to the underlying slice.
Types ¶
type PackedBlob ¶
type PackedBlob struct {
// contains filtered or unexported fields
}
PackedBlob holds a single concatenated slice of bytes containing all the packed strings. Strings are retrieved using a Pointer.
func (*PackedBlob) Bytes ¶
func (s *PackedBlob) Bytes() []byte
Bytes returns the raw underlying byte slice of the PackedBlob. This slice should not be modified.
func (*PackedBlob) GetString ¶
func (s *PackedBlob) GetString(pointer Pointer) (string, error)
GetString returns a copied, independent string from the PackedBlob. It allocates a new underlying buffer to ensure the returned string can safely outlive the blob and remains isolated from any future mutations.
func (*PackedBlob) GetStringUnsafe ¶
func (s *PackedBlob) GetStringUnsafe(pointer Pointer) (string, error)
GetStringUnsafe returns a zero-copy string pointing directly into the blob's memory. It is fast but unsafe: the returned string's lifetime is tied to the blob, and it will reflect any future modifications made to the underlying slice.
func (*PackedBlob) Len ¶
func (s *PackedBlob) Len() int
Len returns the total length of the packed byte slice in the blob.
func (*PackedBlob) Pointers ¶
func (s *PackedBlob) Pointers() []Pointer
Pointers returns all pointers.
func (*PackedBlob) Size ¶
func (s *PackedBlob) Size() int
Size returns the total size of the packed bytes and pointers in memory.
type Pointer ¶
type Pointer struct {
// contains filtered or unexported fields
}
Pointer represents the location and length of a packed string within a PackedBlob. To maximize memory compression, it is packed as a 5-byte array to avoid struct alignment padding.
func NewPointer ¶
NewPointer initializes a new 5-byte packed Pointer.
func PointerFromBytes ¶
PointerFromBytes reconstructs a Pointer from a 5-byte array.
func PointerFromSlice ¶
PointerFromSlice reconstructs a Pointer from a slice. It returns an error if the slice contains fewer than 5 bytes.
type StringMap ¶
type StringMap struct {
// contains filtered or unexported fields
}
StringMap is a thread-safe collector for building a list of strings to be packed together into a PackedBlob.
func NewStringMap ¶
NewStringMap initializes a new StringMap with an optional pre-filled entries slice.
func (*StringMap) Add ¶
Add appends a string to the StringMap and returns its assigned index or ErrStringTooLong.
func (*StringMap) AddUnsafe ¶
AddUnsafe appends a string view of the provided byte slice to the StringMap and returns its assigned index or ErrStringTooLong. It avoids allocations by using unsafe-casting under the hood, but the caller must ensure the underlying byte slice is not mutated after this call.
func (*StringMap) GetString ¶
GetString returns the string at the specified index. It will panic if the index is out of bounds.
func (*StringMap) Length ¶
Length returns the number of strings currently collected in the StringMap.
func (*StringMap) Pack ¶
func (s *StringMap) Pack() (*PackedBlob, error)
Pack compresses all strings currently collected in the StringMap into a PackedBlob.
func (*StringMap) Size ¶
Size returns the total in-memory size of the entries slice and its strings.
Source Files