Почему увеличение slice происходит не всегда в два раза?

Оптимизация выделения памяти в Go слайсах

В Go слайсы действительно увеличиваются не всегда ровно в два раза, хотя удвоение емкости является базовым механизмом роста. Однако на практике реализация в стандартной библиотеке Go (пакет runtime) содержит несколько важных оптимизаций, которые делают рост более эффективным.

Базовый механизм роста

При вызове append() когда cap < len, происходит аллокация нового массива большего размера. Наивный подход - всегда удваивать емкость:

func naiveGrow(oldCap int) int {
    if oldCap == 0 {
        return 1
    }
    return oldCap * 2
}

Но в реальной реализации Go (runtime/slice.go) используется более сложная логика.

Фактическая реализация роста

В исходном коде Go (версия 1.19+) функция роста выглядит примерно так:

func growslice(et *_type, old slice, cap int) slice {
    newcap := old.cap
    doublecap := newcap + newcap
    
    if cap > doublecap {
        newcap = cap
    } else {
        const threshold = 256
        if old.cap < threshold {
            newcap = doublecap
        } else {
            // Проверка переполнения и рост на 25%
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
    // Дальнейшие вычисления с учетом выравнивания памяти
}

Ключевые особенности алгоритма роста

1. Порог в 256 элементов:

   • Для маленьких слайсов (<256 элементов) действительно происходит удвоение
   • Для больших слайсов рост замедляется

2. Учет требуемой емкости:

   s := make([]int, 0, 10)
   s = append(s, 1, 2, 3)
   // Если append требует больше элементов чем 2*cap,
   // то емкость устанавливается ровно под требуемое количество
   

3. Оптимизация под большие слайсы:

   • После 256 элементов рост происходит на 25% от текущей емкости
   • Это уменьшает фрагментацию памяти и избыточное выделение
   • Особенно важно для long-lived слайсов

Практический пример

package main

import "fmt"

func main() {
    var s []int
    
    for i := 0; i < 1000; i++ {
        oldCap := cap(s)
        s = append(s, i)
        newCap := cap(s)
        
        if oldCap != newCap {
            fmt.Printf("Рост: %d -> %d (коэффициент: %.2f)\n", 
                oldCap, newCap, float64(newCap)/float64(oldCap))
        }
    }
}

Вывод покажет:

Рост: 0 -> 1 (коэффициент: +Inf)
Рост: 1 -> 2 (коэффициент: 2.00)
Рост: 2 -> 4 (коэффициент: 2.00)
Рост: 4 -> 8 (коэффициент: 2.00)
... до 256 ...
Рост: 256 -> 512 (коэффициент: 2.00)
Рост: 512 -> 848 (коэффициент: 1.66)  // Уже не 2 раза!
Рост: 848 -> 1280 (коэффициент: 1.51)

Причины такого подхода

1. Эффективность использования памяти:

   • Постоянное удвоение приводит к exponential memory growth
   • Для больших слайсов это создает excessive memory overhead
   • После 256 элементов 25% рост более предсказуем

2. Снижение нагрузки на GC:

   • Меньше неиспользуемой зарезервированной памяти
   • Более плавное увеличение pressure на garbage collector

3. Выравнивание памяти:

   • Фактический размер вычисляется с учетом alignment требований
   • Окончательная емкость может немного отличаться от расчетной

4. Предотвращение overflow:

   • Проверки переполнения при вычислении новой емкости
   • Особенно важно для very large slices

Рекомендации для разработчиков

// Если известен ожидаемый размер - указывайте capacity заранее
func efficientExample() {
    // Плохо: multiple reallocations
    var s []int
    for i := 0; i < 10000; i++ {
        s = append(s, i) // Многократные реаллокации
    }
    
    // Хорошо: предварительное выделение
    s2 := make([]int, 0, 10000)
    for i := 0; i < 10000; i++ {
        s2 = append(s2, i) // Без реаллокаций
    }
}

Заключение

Алгоритм роста слайсов в Go - это компромисс между производительностью и эффективностью использования памяти. Изначальное быстрое удвоение для маленьких слайсов минимизирует количество дорогих операций переаллокации, а постепенное замедление роста для больших слайсов предотвращает excessive memory waste. Этот подход отражает философию Go: предоставлять разумные умолчания, оптимизированные для реальных сценариев использования, сохраняя при этом предсказуемость и эффективность.