Data Structures Deep Dive

Slice, map и string — структуры, которые Go-разработчик использует сотни раз в день. Но сколько из них могут объяснить, почему append иногда мутирует оригинал, а иногда нет? Почему нельзя взять &m[key]? Или почему len("Привет") возвращает 12, а не 6?

Профайлер регулярно показывает неожиданные аллокации на безобидном append, slice aliasing bugs проскальзывают в production, а разница между подходами к конкатенации строк может составлять 10x по производительности. Эти "базовые" структуры — одна из главных слепых зон Senior разработчиков.

Обзор структур данных

🗺️

Data Structures Overview

Интерактивная карта структур данных Go

Открыть

TL;DR: Memory Layout

Структура	Header	Backing Storage	Pass-by	Mutable	Copy Trigger
slice	24 bytes	Heap (backing array)	Value (header)	Elements: Yes	append beyond cap
string	16 bytes	Heap or rodata	Value	No (immutable)	Any modification
map	8 bytes	Heap (hmap+buckets)	Pointer	Yes	Never (reference)
array	N × sizeof(T)	Stack or Heap	Value (full copy)	Yes	Always on assign

Ключевой инсайт

Slice и string — value types с pointer внутри: при передаче в функцию header копируется, но backing storage остаётся общим. Map — это pointer type: переменная m уже содержит указатель на runtime.hmap.

Memory Layout Overview

┌─────────────────────────────────────────────────────────────────────────────────┐
│                         Data Structures Memory Layout                           │
├─────────────────────────────────────────────────────────────────────────────────┤
│                                                                                 │
│   SLICE (24 bytes header)              STRING (16 bytes header)                 │
│   ═══════════════════════              ════════════════════════                 │
│                                                                                 │
│   ┌─────────────────┐                  ┌─────────────────┐                      │
│   │ ptr ─────────┐  │                  │ ptr ─────────┐  │                      │
│   │ len = 3      │  │                  │ len = 12     │  │  (bytes, not runes)  │
│   │ cap = 8      │  │                  └──────────────┼──┘                      │
│   └──────────────┼──┘                                 │                         │
│                  │                                    ▼                         │
│                  ▼                     ┌─────────────────────┐                  │
│   ┌──────────────────────┐             │ "Привет" (UTF-8)    │ (immutable)      │
│   │ [0] [1] [2] ... [7]  │ (mutable)   └─────────────────────┘                  │
│   └──────────────────────┘                                                      │
│              Heap                                 Heap / rodata                 │
│                                                                                 │
├─────────────────────────────────────────────────────────────────────────────────┤
│                                                                                 │
│   MAP (8 bytes pointer)                                                         │
│   ═════════════════════                                                         │
│                                                                                 │
│   ┌─────────┐      ┌─────────────────────────────────────────────────────┐      │
│   │ *hmap ──┼─────▶│ hmap                                                │      │
│   └─────────┘      │ ┌────────────────────────────────────────────────┐  │      │
│                    │ │ count, B, hash0, buckets, oldbuckets, nevacuate│  │      │
│                    │ └────────────────────────────────────────────────┘  │      │
│                    │           │                                         │      │
│                    │           ▼                                         │      │
│                    │ ┌─────────────────────────────────────────────────┐ │      │
│                    │ │ buckets: [bucket0][bucket1]...[bucket_2^B]     │ │      │
│                    │ │          ├─tophash[8]─┤                         │ │      │
│                    │ │          ├─keys[8]────┤                         │ │      │
│                    │ │          ├─values[8]──┤                         │ │      │
│                    │ │          └─overflow───┘                         │ │      │
│                    │ └─────────────────────────────────────────────────┘ │      │
│                    └─────────────────────────────────────────────────────┘      │
│                                          Heap                                   │
│                                                                                 │
└─────────────────────────────────────────────────────────────────────────────────┘

Ключевые файлы runtime/

Файл	Назначение
runtime/slice.go	Slice operations, growslice
runtime/map.go	Map operations, hmap structure
runtime/map_fast*.go	Optimized ops для int32, int64, string
runtime/string.go	String operations, concatenation
runtime/utf8.go	UTF-8 encoding/decoding

Ключевые константы Go 1.25

Параметр	Значение	Описание
Slice header size	24 bytes	ptr + len + cap
String header size	16 bytes	ptr + len
Map pointer size	8 bytes	Pointer to hmap
Bucket size	8 k-v pairs	bucketCnt в runtime/map.go
Growth threshold	256	Порог смены стратегии роста slice
Map load factor	6.5	loadFactorNum/loadFactorDen

Структура раздела

Slice Internals

24-байтовый header (ptr, len, cap), backing array на heap, growth strategy (изменённая в Go 1.18). Escape analysis для размещения: когда slice целиком на stack. Внутренности runtime.growslice, расчёт новой capacity.

Slice Append

Семантика append: когда создаётся новый backing array, а когда мутируется существующий. Главная ловушка — shared array при cap > len. Решения: slices.Clone(), three-index slice s[low:high:max], явное копирование.

Map Internals

Структура hmap, bmap (bucket), overflow chains, evacuation при load factor ~6.5. Почему нельзя взять &m[key] — нет стабильных адресов. Iteration randomization как защита от hash-DoS. Специализированные map_fast*.go для частых типов ключей.

String & Rune

Immutable UTF-8 bytes под капотом. Индексация s[i] возвращает byte, не rune. range автоматически декодирует UTF-8. strings.Builder для эффективной конкатенации. Конвертации []byte ↔ string и когда они zero-copy.

Go 1.21+ пакеты slices и maps

// Безопасное копирование без shared backing array
dst := slices.Clone(src)

// Pre-allocation для известного размера
s := slices.Grow(s, additionalCapacity)

// Deep copy map
m2 := maps.Clone(m1)

// Утилиты
keys := maps.Keys(m)
values := maps.Values(m)

Performance Guidelines

Slice pre-allocation

// ❌ Avoid: repeated allocations
var result []Item
for _, x := range data {
    result = append(result, process(x))  // до 20+ аллокаций
}

// ✅ Better: single allocation
result := make([]Item, 0, len(data))
for _, x := range data {
    result = append(result, process(x))  // 0 аллокаций
}

Map initialization

// ❌ Avoid: multiple evacuations
m := make(map[string]int)  // начальный размер
for i := 0; i < 10000; i++ {
    m[keys[i]] = values[i]  // несколько evacuations
}

// ✅ Better: hint для начального размера
m := make(map[string]int, len(keys))
for i := 0; i < 10000; i++ {
    m[keys[i]] = values[i]  // 0 evacuations
}

String concatenation

// ❌ Avoid: O(n²) allocations
s := ""
for _, part := range parts {
    s += part  // новая аллокация на каждой итерации
}

// ✅ Better: O(n) с strings.Builder
var b strings.Builder
b.Grow(totalLen)  // optional pre-allocation
for _, part := range parts {
    b.WriteString(part)
}
s := b.String()

Map iteration with delete

// ✅ Safe: прямое удаление во время итерации
for k, v := range m {
    if shouldDelete(v) {
        delete(m, k)  // безопасно в Go
    }
}

// ✅ Alternative: collect-then-delete (clearer intent)
var toDelete []string
for k, v := range m {
    if shouldDelete(v) {
        toDelete = append(toDelete, k)
    }
}
for _, k := range toDelete {
    delete(m, k)
}

Debugging & Tools

# Escape analysis — что уходит на heap
go build -gcflags="-m -m" ./...

# Memory allocations в бенчмарках
go test -bench=. -benchmem ./...

# Heap profile — где аллоцируется память
go tool pprof -alloc_objects http://localhost:6060/debug/pprof/heap

# Bounds check elimination
go build -gcflags="-d=ssa/check_bce/debug=1" ./...

# Assembly output — что генерирует компилятор
go build -gcflags="-S" ./...

Частые ошибки

1. Slice aliasing

s1 := make([]int, 3, 5)
s2 := append(s1, 4)  // ⚠️ при cap > len оба смотрят на тот же массив
s1[0] = 999          // s2[0] тоже станет 999!

2. Map nil check

var m map[string]int
_ = m["key"]         // ✅ OK — вернёт zero value
m["key"] = 1         // ❌ panic: assignment to entry in nil map

3. String iteration

for i, c := range "Привет" {
    // i — byte offset (0, 2, 4, 6, 8, 10), не rune index
    // c — rune (П, р, и, в, е, т)
}

4. Map pointer stability

m := map[string]Data{"key": {}}
ptr := &m["key"]  // ❌ не компилируется — нет стабильных адресов
m["key"].Field = 1  // ❌ не компилируется — нельзя модифицировать напрямую

// ✅ Решение: извлечь, модифицировать, записать обратно
d := m["key"]
d.Field = 1
m["key"] = d

Связь с Runtime

Операции над структурами данных тесно связаны с memory allocator:

• make([]T, n) → runtime.makeslice → mallocgc
• make(map[K]V, hint) → runtime.makemap → bucket allocation
• String literals → rodata section (не heap)

См. Stack vs Heap для понимания escape analysis и когда backing array размещается на stack.

Дальнейшее чтение

• Go Slices: usage and internals — официальный блог
• Go maps in action — официальный блог
• Strings, bytes, runes and characters — официальный блог
• Исходники: $GOROOT/src/runtime/slice.go, map.go, string.go
• slices package — Go 1.21+
• maps package — Go 1.21+