Custom Data Structures: Designing Custom Data Structures that Minimize Memory Usage

When standard data structures don't fit the needs of your application, designing custom data structures can help optimize memory usage and performance. Here, we'll explore the principles and techniques for creating custom data structures in Go that are memory-efficient.

Principles of Memory-Efficient Data Structures

1. Minimize Overhead: Reduce the overhead associated with pointers, metadata, and unused fields.
2. Compact Representation: Use compact representations of data, such as bit fields or packed arrays.
3. Efficient Memory Allocation: Optimize memory allocation patterns to minimize fragmentation and overhead.
4. Lazy Initialization: Only initialize fields and structures when they are needed.
5. Memory Pooling: Reuse memory blocks to reduce the frequency and overhead of allocations.

Techniques for Designing Custom Data Structures

1. Compact Data Structures

Bit Fields: Use bit fields to pack multiple boolean flags or small integers into a single word, reducing the memory footprint.

go
type Permissions struct {
    Read  bool
    Write bool
    Exec  bool
}

// Packed representation using bit fields
type PackedPermissions struct {
    flags uint8
}

const (
    ReadFlag  = 1 << iota
    WriteFlag
    ExecFlag
)

func (p *PackedPermissions) SetRead(enabled bool) {
    if enabled {
        p.flags |= ReadFlag
    } else {
        p.flags &^= ReadFlag
    }
}

func (p *PackedPermissions) IsRead() bool {
    return p.flags&ReadFlag != 0
}

Struct Packing: Carefully order fields in structs to minimize padding due to alignment requirements.

go
type PackedStruct struct {
    ID    int32  // 4 bytes
    Flags uint8  // 1 byte
    Value uint32 // 4 bytes
    Name  string // 16 bytes (pointer and length)
}

2. Custom Memory Pools

Memory Pools: Use memory pools to manage a fixed-size block of memory, reducing allocation and deallocation overhead.

go
var bufferPool = sync.Pool{
    New: func() interface{} {
        return make([]byte, 1024) // Allocate 1KB buffers
    },
}

func getBuffer() []byte {
    return bufferPool.Get().([]byte)
}

func putBuffer(buf []byte) {
    bufferPool.Put(buf[:0]) // Reset buffer before putting it back
}

3. Efficient Container Structures

Custom Linked Lists: Design linked lists with minimal memory overhead, avoiding extra pointers or metadata.

go
type Node struct {
    Value int
    Next  *Node
}

type LinkedList struct {
    Head *Node
}

func (l *LinkedList) Insert(value int) {
    newNode := &Node{Value: value}
    newNode.Next = l.Head
    l.Head = newNode
}

Dynamic Arrays: Implement dynamic arrays with efficient resizing strategies to balance between memory overhead and allocation cost.

go
type DynamicArray struct {
    data []int
    size int
}

func NewDynamicArray() *DynamicArray {
    return &DynamicArray{data: make([]int, 0, 4)}
}

func (a *DynamicArray) Append(value int) {
    if len(a.data) == cap(a.data) {
        newCap := cap(a.data) * 2
        newData := make([]int, len(a.data), newCap)
        copy(newData, a.data)
        a.data = newData
    }
    a.data = append(a.data, value)
}

4. Sparse Data Structures

Sparse Arrays: Use hash maps or other techniques to implement sparse arrays, which are more memory-efficient for datasets with many zero or default values.

go
type SparseArray struct {
    data map[int]int
}

func NewSparseArray() *SparseArray {
    return &SparseArray{data: make(map[int]int)}
}

func (a *SparseArray) Set(index int, value int) {
    if value == 0 {
        delete(a.data, index)
    } else {
        a.data[index] = value
    }
}

func (a *SparseArray) Get(index int) int {
    return a.data[index]
}

5. Custom Hash Maps

Optimized Hash Maps: Implement hash maps with memory-efficient collision resolution and load factor strategies.

go
type HashMap struct {
    buckets [][]entry
    size    int
}

type entry struct {
    key   string
    value int
}

func NewHashMap() *HashMap {
    return &HashMap{buckets: make([][]entry, 8)}
}

func (m *HashMap) put(key string, value int) {
    index := hash(key) % len(m.buckets)
    bucket := &m.buckets[index]
    for i, e := range *bucket {
        if e.key == key {
            (*bucket)[i].value = value
            return
        }
    }
    *bucket = append(*bucket, entry{key, value})
    m.size++
    if float64(m.size)/float64(len(m.buckets)) > 0.75 {
        m.resize()
    }
}

func (m *HashMap) resize() {
    newBuckets := make([][]entry, len(m.buckets)*2)
    for _, bucket := range m.buckets {
        for _, e := range bucket {
            index := hash(e.key) % len(newBuckets)
            newBuckets[index] = append(newBuckets[index], e)
        }
    }
    m.buckets = newBuckets
}

func hash(key string) int {
    h := 0
    for _, c := range key {
        h = h*31 + int(c)
    }
    return h
}

Conclusion

Designing custom data structures in Go requires a careful balance between functionality and memory efficiency. By leveraging techniques such as bit fields, custom memory pools, sparse representations, and efficient container structures, you can create data structures that minimize memory usage while maintaining performance. Consider the specific needs of your application and the characteristics of your data when designing these structures.