По какому алгоритму растет capacity у slice при использовании append?

Нет, slice не всегда увеличивает свою емкость (capacity) в два раза. Алгоритм роста является деталью реализации и может меняться между версиями Go. Его цель — найти баланс между скоростью (меньше переаллокаций) и использованием памяти (не выделять слишком много лишнего).

Когда вы используете append и текущей емкости не хватает, Go выделяет новый, больший массив и копирует в него старые данные. Правила выделения новой емкости в современных версиях Go (начиная с 1.18) примерно следующие:

1. 
   

   Для небольших слайсов (когда текущая capacity < 256 элементов): новая емкость будет в два раза больше старой (new_cap = old_cap * 2).

   
   
2. 
   

   Для больших слайсов (когда capacity >= 256): рост замедляется. Новая емкость увеличивается постепенно, примерно на 25% (но формула сложнее), пока не станет достаточной для новых элементов. Это предотвращает чрезмерное потребление памяти при работе с очень большими слайсами.

   
   

Ключевая идея: Разработчик не должен закладываться на конкретный коэффициент роста. Важно понимать, что:

• append может вызвать переаллокацию памяти и копирование данных, что является относительно дорогой операцией.
• Рост емкости обеспечивает амортизированную константную сложность O(1) для операции append.
• Если размер слайса заранее известен, лучше сразу создавать его с нужной емкостью с помощью make([]T, length, capacity), чтобы избежать лишних аллокаций.

Пример демонстрации:

s := make([]int, 0)
oldCap := cap(s)

for i := 0; i < 2000; i++ {
    s = append(s, i)
    if cap(s) != oldCap {
        fmt.Printf("len: %-4d -> cap: %-4d (рост ~x%.2f)n", len(s), cap(s), float64(cap(s))/float64(oldCap))
        oldCap = cap(s)
    }
}

Запустив этот код, вы увидите, что сначала capacity удваивается, а после достижения порога (256) коэффициент роста становится меньше.