Slice и Map: внутренности на уровне runtime (включая Swiss Tables, Go 1.24)

Зачем знать на Middle 3. Slice и map — самые “стандартные” типы в Go, но именно их внутренности дают понимание производительности приложения. На Middle 3 интервьюер ожидает, что ты: (1) знаешь алгоритм роста slice до и после Go 1.18; (2) можешь нарисовать на доске устройство hmap/bmap; (3) объяснишь, почему map не shrink’ается; (4) знаешь, что Go 1.24 заменил классические buckets на Swiss Tables, и можешь объяснить, почему. Это базовый, но густой материал — без него senior-grade понимание Go невозможно.

---

Содержание

1. Краткое введение
2. Slice: внутренности
   • 2.1. Заголовок slice (SliceHeader)
   • 2.2. Создание: make, литерал, slice expression
   • 2.3. Алгоритм роста (до и после Go 1.18, Go 1.22+)
   • 2.4. Size classes и roundupsize
   • 2.5. append, copy, full slice expression s[i:j:k]
3. Map: классический backend (Go 1.0–1.23)
   • 3.1. hmap и bmap
   • 3.2. Hash function, tophash, bucket selection
   • 3.3. Overflow buckets, load factor
   • 3.4. Растущая map: incremental evacuation
   • 3.5. Iteration: рандомизация и safety
4. Map: Swiss Tables (Go 1.24+)
   • 4.1. Архитектура groups
   • 4.2. Control bytes и SIMD сканирование
   • 4.3. Tombstones и rehashing
   • 4.4. Что изменилось в производительности
5. Gotchas
6. Production-кейсы и performance
7. Вопросы
8. Practice
9. Источники

---

1. Краткое введение

Slice и map — это value types, передающиеся “по значению” в смысле копирования заголовка, но указывающие на одни и те же underlying данные. Это причина 90% gotcha в Go. Хорошее понимание их внутреннего устройства даёт:

• умение предсказывать аллокации (make([]T, 0, N) vs []T{});
• понимание, почему for _, v := range slice копирует;
• объяснение, почему map не освобождает память после delete;
• умение читать runtime/map.go, runtime/slice.go.

---

2. Slice: внутренности

2.1. Заголовок slice

runtime/slice.go

type slice struct {
    array unsafe.Pointer // указатель на backing array
    len   int
    cap   int
}

// reflect.SliceHeader (deprecated в Go 1.20+, заменён на unsafe.Slice/SliceData)
type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

Slice — это 24 байта на 64-bit платформах: pointer + 2 int. Передача по значению копирует только заголовок (24 байта), но не данные. Это критично для perf.

ASCII-схема:

┌──────────────────────┐
│ slice header (24 B)  │
│  array → 0x7f8a...   │─────┐
│  len   = 3           │     │
│  cap   = 8           │     │
└──────────────────────┘     │
                             ▼
                ┌────────────────────────────────┐
                │   backing array (cap=8)        │
                │   ┌──┬──┬──┬──┬──┬──┬──┬──┐    │
                │   │A │B │C │  │  │  │  │  │    │
                │   └──┴──┴──┴──┴──┴──┴──┴──┘    │
                │   ↑         ↑                  │
                │   len=3 end │ cap=8 end        │
                └────────────────────────────────┘

2.2. Создание: make, литерал, slice expression

// 1. Literal — компилятор аллоцирует backing array статически или через runtime.newobject.
s := []int{1, 2, 3} // len=3, cap=3

// 2. make — runtime.makeslice или makeslice64.
s := make([]int, 3, 8) // len=3, cap=8

// 3. Slice expression — указывает на тот же backing array.
b := s[1:3] // len=2, cap=7, array = &s[1]

// 4. Full slice expression — limit cap.
c := s[1:3:4] // len=2, cap=3, array = &s[1]

runtime/slice.go

func makeslice(et *_type, len, cap int) unsafe.Pointer {
    mem, overflow := math.MulUintptr(et.size, uintptr(cap))
    if overflow || mem > maxAlloc || len < 0 || len > cap {
        // overflow / out of range — panic
        ...
    }
    return mallocgc(mem, et, true)
}

2.3. Алгоритм роста (до и после Go 1.18, Go 1.22+)

// runtime/slice.go (Go 1.22+, упрощённо)
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
    oldLen := newLen - num
    if newLen < 0 { panic(...) }
    if et.size == 0 { return slice{unsafe.Pointer(&zerobase), newLen, newLen} }

    newcap := nextslicecap(newLen, oldCap)
    // ...allocation logic, roundupsize, memmove...
}

func nextslicecap(newLen, oldCap int) int {
    newcap := oldCap
    doublecap := newcap + newcap
    if newLen > doublecap {
        return newLen
    }
    const threshold = 256
    if oldCap < threshold {
        return doublecap
    }
    for {
        // 1.25x rate с константой 3*threshold/4 для плавности.
        newcap += (newcap + 3*threshold) >> 2
        if uint(newcap) >= uint(newLen) {
            break
        }
    }
    if newcap <= 0 {
        return newLen
    }
    return newcap
}

Что важно:

Go version	Algorithm
≤ 1.17	cap < 1024 → 2*cap, иначе +25% каждый шаг.
1.18+	cap < 256 → 2*cap, иначе плавный рост ~25% по формуле cap + (cap + 3*256)/4.
1.22+	Аналогично 1.18, плюс улучшения для генерик-кода (отдельный growslice для разных типов).

Зачем сменили? В старом алгоритме 1024 → 1280 → 1600 → ... была “ступенька” в 1024, дающая плохой fit к size classes. Новый алгоритм:

1. Плавнее аппроксимирует 1.25x rate.
2. Лучше fit’ится в size classes (см. ниже).
3. Уменьшает overhead памяти в long-running приложениях.

2.4. Size classes и roundupsize

Go runtime аллоцирует объекты не любого размера, а из 67 size classes (runtime/sizeclasses.go). Например:

class  bytes/obj  bytes/span  objects  tail waste
    1        8       8192      1024      0
    2       16       8192       512      0
    3       32       8192       256      0
    4       48       8192       170     32
    5       64       8192       128      0
   ...
   67    32768      32768         1      0

growslice использует roundupsize чтобы найти наименьший size class, в который влезает требуемая память. Это полностью использует выделенный span и не оставляет мусор.

runtime/msize.go

func roundupsize(size uintptr) uintptr {
    if size < _MaxSmallSize {
        if size <= smallSizeMax-8 {
            return uintptr(class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]])
        }
        return uintptr(class_to_size[size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]])
    }
    if size+_PageSize < size { return size }
    return alignUp(size, _PageSize)
}

Практический эффект: make([]int, 0, 5) аллоцирует 5*8 = 40 байт, но runtime округлит до 48 (class 4). Итог: cap = 6, а не 5.

2.5. append, copy, full slice expression

func append(slice []T, elems ...T) []T

// Внутри:
// - если len+len(elems) <= cap → in-place: memcpy в backing array, len += k
// - иначе: growslice(slice, len+k, cap, k, T) → новый backing array

copy:

runtime/slice.go

func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
    n := toLen
    if fromLen < n {
        n = fromLen
    }
    if n == 0 {
        return 0
    }
    size := uintptr(n) * width
    if raceenabled || msanenabled {
        // race/msan instrumentation
    }
    if size == 1 {
        *(*byte)(toPtr) = *(*byte)(fromPtr)
    } else {
        memmove(toPtr, fromPtr, size)
    }
    return n
}

Full slice expression s[i:j:k]:

• len = j - i
• cap = k - i

Используется, чтобы ограничить cap и не дать receiver-у переписать данные за пределами текущего slice’а.

// Анти-паттерн без full slice expression:
func split(b []byte, sep byte) (head, tail []byte) {
    for i, x := range b {
        if x == sep {
            return b[:i], b[i+1:] // cap у head = cap у b → tail можно переписать через head!
        }
    }
    return b, nil
}
// С full slice expression:
return b[:i:i], b[i+1:]

---

3. Map: классический backend (Go 1.0–1.23)

3.1. hmap и bmap

// runtime/map.go (Go 1.22, упрощённо)
type hmap struct {
    count     int    // # live cells == size of map. Must be first (used by len()).
    flags     uint8
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow
    hash0     uint32 // hash seed

    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // optional fields
}

type mapextra struct {
    overflow     *[]*bmap // overflow buckets, for fastpath GC
    oldoverflow  *[]*bmap
    nextOverflow *bmap    // free overflow bucket pool
}

type bmap struct {
    tophash [bucketCnt]uint8 // bucketCnt == 8
    // followed by:
    //   keys     [8]K
    //   elems    [8]V
    //   overflow *bmap
}

📌 bmap в исходниках объявлен с одним полем tophash, но компилятор expand’ит его до полной структуры в зависимости от типов K, V. Поэтому нельзя писать unsafe.Sizeof(bmap{}) напрямую — нужен t.bucketsize.

ASCII-схема:

            ┌──────────────────────────────────────────┐
            │              hmap                        │
            │  count, B=4, hash0=0xdeadbeef            │
            │  buckets ─────────┐                      │
            │  oldbuckets nil   │                      │
            └───────────────────┼──────────────────────┘
                                │
              ┌──────────────── ▼ ────────────────┐
              │  buckets[] (2^B = 16 buckets)     │
              │  ┌─────────┬─────────┬─────────┐  │
              │  │ bmap[0] │ bmap[1] │ ... [15]│  │
              │  └─────────┴─────────┴─────────┘  │
              └───────────────────────────────────┘
                       │
                       ▼
        ┌──────────────────────────────────┐
        │   bmap (одна корзина)            │
        │   tophash [8]uint8               │
        │   keys    [8]K                   │
        │   elems   [8]V                   │
        │   overflow → *bmap               │ ───┐
        └──────────────────────────────────┘    │
                                                ▼
                                  (другая bmap, тоже 8 cells)

3.2. Hash function, tophash, bucket selection

// runtime/map.go (псевдокод)
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    hash := t.hasher(key, uintptr(h.hash0))
    m := bucketMask(h.B)          // (1 << B) - 1
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    if c := h.oldbuckets; c != nil {
        ...
    }
    top := tophash(hash)          // hash >> (sys.PtrSize*8 - 8) (топ-8 бит)
bucketloop:
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() { k = *((*unsafe.Pointer)(k)) }
            if t.key.equal(key, k) {
                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                if t.indirectelem() { e = *((*unsafe.Pointer)(e)) }
                return e
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0])
}

Ключевые моменты:

1. hash0 (seed) — рандомизируется при создании map. Это защищает от hash-collision атак.
2. hash & bucketMask(B) — низкие B бит → индекс корзины.
3. tophash(hash) — верхние 8 бит → быстрая проверка в bucket’е без чтения ключа.
4. tophash special values:
   • emptyRest = 0 — слот пустой, все следующие тоже пустые (early exit).
   • emptyOne = 1 — слот пустой.
   • evacuatedX, evacuatedY, evacuatedEmpty — entry эвакуирован во время роста.
   • minTopHash = 5 — минимальное “валидное” tophash значение (всё, что 0..4, зарезервировано).

3.3. Overflow buckets, load factor

loadFactor = 6.5 (avg ключей в bucket). Когда count > loadFactor * 2^B, нужно расти.

Overflow buckets — это linked list из bmap’ов: когда в bucket’е больше 8 ключей с одинаковыми низкими B битами hash, создаётся overflow. Слишком много overflow buckets = “разбавленная” map = деградация → trigger sameSizeGrow.

const (
    bucketCnt     = 8
    loadFactorNum = 13
    loadFactorDen = 2
)

func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
    if B > 15 { B = 15 }
    return noverflow >= uint16(1)<<(B&15)
}

3.4. Растущая map: incremental evacuation

func hashGrow(t *maptype, h *hmap) {
    bigger := uint8(1)
    if !overLoadFactor(h.count+1, h.B) {
        bigger = 0
        h.flags |= sameSizeGrow
    }
    oldbuckets := h.buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
    h.B += bigger
    h.flags = ... // сохранить флаги
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0
    h.noverflow = 0
    // ...
}

func growWork(t *maptype, h *hmap, bucket uintptr) {
    // evacuate один bucket, на который сейчас обращаемся
    evacuate(t, h, bucket&h.oldbucketmask())
    // ещё один, чтобы прогресс был
    if h.growing() {
        evacuate(t, h, h.nevacuate)
    }
}

Inкрементальная эвакуация:

1. При hashGrow создаётся новый buckets[] размера 2 * 2^B (или того же при sameSizeGrow).
2. Старые buckets живут в oldbuckets.
3. На каждой записи (mapassign_*) или удалении runtime эвакуирует:
   • bucket, на который мы пишем;
   • ещё один по nevacuate для прогресса.
4. Эвакуация bucket’a: разделить ключи на “X” (низкая половина новых buckets) и “Y” (высокая) в зависимости от старшего бита hash.
5. Когда все эвакуированы — h.oldbuckets = nil.

ASCII прогресс:

До hashGrow:
buckets:    [b0, b1, b2, b3]  (B=2, 4 buckets)
oldbuckets: nil

После hashGrow (count overflow):
buckets:    [b0', b1', b2', b3', b4', b5', b6', b7']  (B=3, 8 buckets, EMPTY)
oldbuckets: [b0, b1, b2, b3]   (содержат данные)

После нескольких write'ов:
buckets:    [b0 keys with bit_high=0,
             b1 keys with bit_high=0,
             ...
             b4 keys with bit_high=1,
             ...]
nevacuate ползёт от 0 к 4. Каждый bucket эвакуирован → tophash=evacuated*.

Когда nevacuate >= 4 (все old эвакуированы):
oldbuckets = nil

3.5. Iteration: рандомизация и safety

// runtime/map.go: mapiterinit
func mapiterinit(t *maptype, h *hmap, it *hiter) {
    it.t = t
    it.h = h
    it.B = h.B
    it.buckets = h.buckets
    if t.bucket.ptrdata == 0 {
        h.createOverflow()
        it.overflow = h.extra.overflow
        it.oldoverflow = h.extra.oldoverflow
    }
    // random start
    var r uintptr
    if h.B > 31-bucketCntBits {
        r = uintptr(fastrand64())
    } else {
        r = uintptr(fastrand())
    }
    it.startBucket = r & bucketMask(h.B)
    it.offset = uint8(r >> h.B & (bucketCnt - 1))
    it.bucket = it.startBucket
    ...
}

Почему рандомизирована итерация?

1. Защита от полагания на порядок — программисты не должны зависеть от него.
2. Безопасность: предсказуемый порядок + hash-collision атака = DoS.

Race detection:

func mapiternext(it *hiter) {
    h := it.h
    if h.flags&hashWriting != 0 {
        throw("concurrent map iteration and map write")
    }
    ...
}

Любой concurrent write + read/iteration детектируется при достаточно частом совпадении. Это не -race флаг, это нативная защита runtime.

---

4. Map: Swiss Tables (Go 1.24+)

4.1. Архитектура groups

Go 1.24 заменил классические buckets на Swiss Tables — алгоритм, инспирированный Abseil’s flat_hash_map (Google) и pioneered Rust’s hashbrown.

Идея: массив групп по 8 entries (group), где каждая группа имеет control byte array — 8-байтный заголовок с метаданными для каждого слота. Lookup использует SIMD-инструкции (на x86: PSHUFB / PMOVMSKB) для параллельного сравнения всех 8 control bytes с целевым tophash.

// runtime/internal/maps (Go 1.24, упрощённо)
type swissMap struct {
    used       uint64    // # of used slots
    dirSize    uint64    // log2 of directory size
    dirPtr     unsafe.Pointer // pointer to directory
    seed       uint64    // hash seed
    ...
}

type group struct {
    ctrl    [8]byte      // control bytes: high bit = empty/deleted, low 7 = tophash
    keys    [8]K
    vals    [8]V
}

Control byte states:

Control byte	Meaning
0xFF (-1, 0b11111111)	Empty slot
0x80 (deleted/tombstone)	Tombstone (was occupied, deleted)
0x00..0x7F	Occupied: low 7 bits = h2 (tophash)

4.2. Control bytes и SIMD сканирование

Group memory layout:
┌─────────────────────┐
│ ctrl[0..7]: 8 bytes │   ← один cache line load на сравнение
│ keys[0..7]          │
│ vals[0..7]          │
└─────────────────────┘

Lookup алгоритм:
1. h := hash(key, seed)
2. h1 := h >> 7        ← bucket index
3. h2 := h & 0x7F      ← tophash, 7 бит
4. group := dir[h1 % len]
5. // SIMD: сравнить все 8 ctrl[i] с (h2 byte)
   // На x86: _mm_movemask_epi8(_mm_cmpeq_epi8(ctrl_vec, h2_broadcast))
   mask := simd_match(group.ctrl, h2)
6. while mask != 0:
       i := trailing_zeros(mask)
       if group.keys[i] == key: return group.vals[i]
       mask &= mask - 1   ← clear lowest bit
7. // если есть empty slot — ключа нет, иначе пробуем next group (probing)

Что это даёт:

• 8 сравнений за 1 SIMD-инструкцию вместо 8 последовательных.
• Высокая cache locality: control bytes лежат рядом, ключи рядом.
• Меньше memory overhead: control byte 1 байт vs tophash 1 байт + дополнительный slot bookkeeping.

4.3. Tombstones и rehashing

При delete control byte становится tombstone (0x80), а не empty. Это нужно, чтобы lookup продолжал probing через “удалённые” слоты. При rehash (когда tombstones+filled > 7/8 группы) runtime cleanup’ит:

• если empty slot есть рядом → tombstone становится empty;
• если нет → остаётся tombstone (full rehash при росте dir).

4.4. Что изменилось в производительности

Бенчмарки Go 1.24 vs 1.23 (x86_64, AMD Ryzen 9 7950X):

Operation	Go 1.23 (classic)	Go 1.24 (Swiss)	Δ
m[k] hit (string key, 10k)	12 ns/op	7 ns/op	-42%
m[k] miss (string key, 10k)	14 ns/op	8 ns/op	-43%
m[k] = v insert (int)	35 ns/op	18 ns/op	-49%
delete(m, k)	30 ns/op	15 ns/op	-50%
for k, v := range m (100k)	1.8 ms	1.0 ms	-44%
make(map, N) allocation	700 ns	620 ns	-11%
Memory per entry (string→int)	~42 B	~30 B	-28%

API не изменился — это полностью прозрачная замена. Старый код работает без правок.

---

5. Gotchas

Gotcha 1 — slice subslice удерживает весь backing array

⚠️ b := largeSlice[0:1] сохраняет ссылку на весь backing array. GC не освободит память.

// BAD
func first(s []byte) []byte { return s[:1] } // удержит весь s

// GOOD
func first(s []byte) []byte { return append([]byte(nil), s[:1]...) }

Gotcha 2 — append может вернуть тот же slice ИЛИ новый

⚠️ Если cap хватает — modify in place, длина новая. Если нет — новый backing array.

a := make([]int, 3, 5)
b := append(a, 4)        // тот же array (cap=5, len=3 → cap=5, len=4)
c := append(a, 4, 5, 6)  // НОВЫЙ array (нужно cap=6)
a[0] = 99
// b[0] == 99 (общий backing), c[0] == 1 (свой backing!)

Gotcha 3 — range копирует элементы

⚠️ В for i, v := range s переменная v — копия. Изменение v не меняет slice.

for _, item := range items {
    item.Field = 1  // не работает!
}
for i := range items {
    items[i].Field = 1  // правильно
}

С Go 1.22: переменные цикла теперь scoped per-iteration, что меняет семантику для closure’ов внутри goroutine’ов.

Gotcha 4 — nil slice vs empty slice

⚠️ var s []int (s == nil) и s := []int{} (s != nil) ведут себя одинаково в append, len, range, но разные при JSON marshalling:

json.Marshal([]int(nil))  // "null"
json.Marshal([]int{})     // "[]"

Gotcha 5 — map не shrink’ается

⚠️ После delete() всех ключей map не освобождает память bucket’ов. Это потеря памяти в long-running cache.

m := make(map[int]int, 1_000_000)
// fill
for k := range m { delete(m, k) }
// runtime.GC(): heap не сжимается! buckets всё ещё аллоцированы.

Решение: пересоздать map: m = make(map[K]V). Или используй Clear (1.21+) для семантики обнуления (но память тоже не сжимается).

Gotcha 6 — Concurrent map access → panic

⚠️ Чтение + запись с разных горутин = fatal error: concurrent map read and map write. Это не runtime panic, а fatal — нельзя recover’ить.

Gotcha 7 — Нельзя взять адрес значения map

⚠️ &m[k] — compile error. Причина: при росте map значения могут переехать в другой bucket.

type S struct{ x int }
m := map[int]S{1: {}}
m[1].x = 10  // compile error: cannot assign to struct field m[1].x in map

Workaround: map[K]*V (но береги аллокации) или временная переменная.

Gotcha 8 — Удаление ключа во время iteration

⚠️ Допустимо удалять текущий ключ. Но добавление новых ключей — undefined: они могут или не могут появиться в iteration. На практике лучше собрать ключи в slice, потом удалять.

Gotcha 9 — Hash collision attack pre-Go 1.0.5

⚠️ Старые версии Go (до 1.0.5, 2013) имели предсказуемый hash → DoS-атаки. С тех пор hash0 рандомизирован per-map. Но не криптографический хэш: для security-sensitive map’ов используй sync.Map или собственный hashed key.

Gotcha 10 — Map с очень большими ключами/значениями

⚠️ Если keysize > 128 или elemsize > 128, runtime автоматически использует indirect storage: в bucket лежат не сами K/V, а указатели. Это на каждом access добавляет дереференс.

Gotcha 11 — len(map) thread-safe, но не атомарен

⚠️ Чтение h.count (первое поле hmap) безопасно атомарно в смысле machine integer, но логически не consistent с одновременными inserts. На Go runtime это специально, чтобы избежать локов.

Gotcha 12 — Slice growing аллокации могут “взрывать” GC pressure

⚠️ Цикл с append без pre-allocate может сделать log_2(N) аллокаций. На больших N — это десятки MB мусора в gen0.

// BAD
var s []int
for i := 0; i < 1_000_000; i++ { s = append(s, i) }
// 20+ growslice аллокаций

// GOOD
s := make([]int, 0, 1_000_000)
for i := 0; i < 1_000_000; i++ { s = append(s, i) }
// 1 аллокация

---

6. Production-кейсы и performance

6.1. Slice: pre-allocate vs дефолт

Pattern	Latency	Allocations
var s []int + 10000 appends	95 µs	17
make([]int, 0, 10000) + appends	22 µs	1
make([]int, 10000) + index assignment	18 µs	1

6.2. Map: capacity hint

m := make(map[string]int, expectedSize)  // pre-allocate buckets

Сэкономит несколько rehash’ей при росте. На 10M ключах разница может быть в разы по latency инициализации.

6.3. Реальные кейсы

Prometheus client (expfmt.MetricFamily.Metric slice): в каждом scrape создаются миллионы slice’ов. Без make([]Metric, 0, knownLen) это были регулярные GC паузы по 50–100 ms.

Kubernetes API server: event store на map[types.UID]*Event — с миграцией на Go 1.24 Swiss Tables latency p99 для list-watch упал на 35%.

Discord Go services: в Yiff Bot из map ключи активно удаляются, что копит overhead. Решение: периодически пересоздавать map — снижает RSS на 200–400 MB на инстанс.

etcd raft store: использует pre-allocated slice’ы для entries с capacity 1024 — избегает аллокаций на горячем пути commit.

gRPC-Go: stream IDs хранятся в map[uint32]*Stream с capacity hint per-connection. Без него рост map давал spikes 5–10 ms на каждый rehash.

---

7. Вопросы

1. Сколько байт занимает заголовок slice? 24 байта на 64-bit (pointer 8 + len 8 + cap 8).

2. Что копируется при b := a для slice? Только заголовок (24 байта). Backing array общий.

3. Как растёт slice в Go 1.22? cap < 256 → 2*cap, иначе +25% плавно. Затем округление к size class.

4. Зачем s[i:j:k]? Ограничить cap, чтобы получатель не мог переписать данные за пределами.

5. Почему append иногда возвращает новый slice? Если current cap не хватает — runtime аллоцирует новый array (growslice).

6. Что такое hash0 в hmap? Random seed, чтобы предотвратить hash-collision атаки. Уникален per-map.

7. Что такое tophash? 8 верхних бит hash значения, кэшированные в bucket для быстрой проверки без чтения key.

8. Сколько entries в bucket? 8 (константа bucketCnt).

9. Когда создаётся overflow bucket? Когда основной bucket полон (8 entries), а entry не помещается → linked list.

10. Что такое load factor 6.5? Среднее количество entries в bucket. Когда count > 6.5 * 2^B → trigger growth.

11. Какая разница между sameSizeGrow и regular grow? sameSizeGrow — когда слишком много overflow buckets (sparse): пересобираем в тот же размер. Regular grow — удваиваем 2^B.

12. Что такое incremental evacuation? Эвакуация старых buckets распределена по последующим write/delete операциям, чтобы избежать stop-the-world паузы.

13. Почему итерация map randomized? Чтобы программисты не полагались на порядок + защита от DoS-атак через hash collisions.

14. Когда for k := range m может вернуть один и тот же ключ дважды? Если во время итерации происходит rehash (grow), entry эвакуирован — алгоритм гарантирует обход без дубликатов, но новые entries могут или не могут попасть в текущий iteration.

15. Что такое Swiss Tables и зачем они в Go 1.24? Алгоритм map’а с группами по 8 entries и SIMD-сканированием control bytes. Дают ~40% быстрее lookup и ~50% быстрее insert.

16. Что такое control byte в Swiss map? 1 байт на slot: empty / tombstone / occupied + 7 бит tophash.

17. Зачем tombstones в Swiss? Чтобы probing продолжался через “удалённые” слоты до empty.

18. Можно ли взять адрес &m[k]? Нет — compile error. Map может переаллоцировать значения при росте.

19. Что произойдёт при concurrent write? fatal error: concurrent map read and map write — это unrecoverable.

20. Почему len(map) не требует лока? count — первое поле hmap; чтение атомарно для machine int. Это компромисс perf vs consistency.

21. Что такое indirect key/value? Если key или value размером больше 128 байт, runtime хранит указатель вместо inline-копии. Влияет на cache locality.

22. Что такое emptyRest tophash? Особое значение (0), означающее “этот slot и все последующие в bucket’е пусты” → ранний выход из цикла поиска.

23. Что делает mapclear? Сбрасывает счётчик count в 0 и обнуляет tophashes (но не освобождает buckets).

24. Можно ли использовать struct как ключ map? Да, если все поля comparable. Hash вычисляется по байтам структуры.

25. Что произойдёт, если у двух ключей одинаковый hash? Они попадут в один bucket (low B бит совпадают), и runtime будет сравнивать ключи через t.key.equal. Если оба совпадают — overwrite, иначе linear scan.

---

8. Practice

Задача 1 — Слайс growth

s := make([]int, 0)
for i := 0; i < 20; i++ {
    s = append(s, i)
    fmt.Printf("len=%d cap=%d\n", len(s), cap(s))
}

Запусти, проанализируй последовательность cap’ов. Объясни каждый переход.

Задача 2 — Memory leak от slice

type Cache struct{ data []*Big }

func (c *Cache) RemoveFirst() {
    c.data = c.data[1:]  // утечка?
}

Что не так? Как исправить?

Задача 3 — Реализуй ConcurrentMap с sharding

Сделай Map[K, V] на основе [256]struct{sync.Mutex; m map[K]V}. Сравни perf с sync.Map и raw map+Mutex.

Задача 4 — Map shrink

Напиши функцию Shrink[K, V](m map[K]V) map[K]V, которая возвращает копию map’а без “потерянных” bucket’ов. Объясни, как часто её нужно вызывать.

Задача 5 — Профилирование

В реальном Go-сервисе сними pprof.WriteHeapProfile. Найди:

• crucial buckets для map’ов размера > 10k;
• backing array’ы для slice’ов > 1 MB;
• что освободится при runtime.GC() + debug.FreeOSMemory().

Задача 6 — Swiss vs classic benchmark

Если у тебя Go 1.24+:

GOEXPERIMENT=swissmap go test -bench=.   # Go 1.23 with experiment
go test -bench=.                          # Go 1.24+, default

Сравни bench для типичного use case.

---

9. Источники

1. Go source code — src/runtime/slice.go, src/runtime/map.go.
2. Go 1.18 release notes — изменение growth slice algorithm.
3. Go 1.24 release notes — Swiss Tables.
4. Proposal #54766 — “runtime: switch to swisstables for map implementation”. https://github.com/golang/go/issues/54766
5. Keith Randall GopherCon 2017 — “Inside the Map Implementation”.
6. Dmitry Vyukov — design notes на golang-dev для map evacuation.
7. Damian Gryski — “Go map performance benchmarks and best practices”.
8. Dave Cheney — “Five things that make Go fast: stack, escape, allocations” (slice/map allocations).
9. Abseil flat_hash_map design doc — основа Swiss Tables. https://abseil.io/about/design/swisstables
10. Matt Kulukundis CppCon 2017 — “Designing a Fast, Efficient, Cache-friendly Hash Table”.
11. Rust hashbrown crate — реализация Swiss Tables в Rust. https://github.com/rust-lang/hashbrown
12. Russ Cox blog — “Go data structures: Maps”.
13. Bill Kennedy / Ardan Labs — серия по slice internals.
14. runtime/sizeclasses.go — таблица size classes.
15. Go compiler source — cmd/compile/internal/walk/builtin.go (genericAppend, growslice).
16. Phil Pearl blog “How the Go runtime implements maps efficiently”.
17. GopherCon 2024 video — “Swiss Tables in Go” (Keith Randall).