Какие знаешь ограничения у Stack?

Какие знаешь ограничения у Stack?

Этот вопрос про ограничения Call Stack (стека вызовов) и Stack Memory (памяти стека). Расскажу про оба.

1. Call Stack (стек вызовов)

Это место, где хранятся информация о вызванных функциях.

Структура:

┌──────────────────┐
│ main()           │  ← bottom (нижний конец)
│  printAge()      │
│   getString()    │  ← top (верхний конец)
└──────────────────┘

2. StackOverflowError (бесконечная рекурсия)

Проблема: слишком глубокая рекурсия

// ПЛОХО: бесконечная рекурсия
fun fibonacci(n: Int): Int {
    return if (n <= 1) n else fibonacci(n - 1) + fibonacci(n - 2)
}

fibonacci(10000)  // StackOverflowError!

Почему: каждый вызов fibonacci добавляет frame на стек. При n=10000 будет 10000 frame'ов, и стек переполнится.

Решение 1: итеративный подход

fun fibonacci(n: Int): Int {
    if (n <= 1) return n
    var a = 0
    var b = 1
    for (i in 2..n) {
        val temp = a + b
        a = b
        b = temp
    }
    return b
}

fibonacci(10000)  // OK, нет рекурсии

Решение 2: Tail Recursion (оптимизация компилятором)

// Компилятор преобразует в цикл (если хвостовая рекурсия)
tailrec fun fibonacci(n: Int, a: Int = 0, b: Int = 1): Int {
    return if (n == 0) a else fibonacci(n - 1, b, a + b)
}

fibonacci(10000)  // OK, компилятор оптимизирует

Важно: @tailrec должна быть последняя операция функции!

3. Stack Memory Limits

Лимиты памяти стека (зависят от платформы):

4. Локальные переменные на Stack

fun example() {
    val x = 10              // Stack (примитив)
    val str = "Hello"       // Heap (String объект)
    val list = listOf(1, 2) // Heap (List объект)
    
    // Но ссылки x, str, list хранятся на Stack!
    // х (int 10) → Stack
    // str (reference) → Stack, объект → Heap
    // list (reference) → Stack, объект → Heap
}

Stack заканчивается → StackOverflowError Heap заканчивается → OutOfMemoryError

5. Локальные переменные в loops

// ПЛОХО: каждая итерация создаёт новый frame
for (i in 1..1000000) {
    val user = User(i, "User $i")  // Stack память
    process(user)
}

// ХОРОШО: переиспользуем переменную
var user: User
for (i in 1..1000000) {
    user = User(i, "User $i")
    process(user)
}

6. Вложенные вызовы функций

Глубина Call Stack:

fun level1() = level2()
fun level2() = level3()
fun level3() = level4()
fun level4() = level5()
// ...
fun level1000000() = "done"

level1()  // StackOverflowError при ~100000 уровне

Stack trace:

java.lang.StackOverflowError
  at Level2.level3()
  at Level2.level2()
  at Level2.level1()
  at Level2.level3()
  ... (repeat 1000000 раз)

7. Thread Stack vs Application Heap

Приложение:
┌─────────────────────┐
│ Heap (shared)       │  ← Общая память для всех потоков
│ ┌─────────────────┐ │
│ │ Objects         │ │
│ │ Arrays          │ │
│ │ Strings         │ │
│ └─────────────────┘ │
└─────────────────────┘

┌─────────────────────┐
│ Thread 1 Stack (1MB)│  ← Своя для каждого потока
└─────────────────────┘

┌─────────────────────┐
│ Thread 2 Stack (1MB)│  ← Своя для каждого потока
└─────────────────────┘

8. Много потоков = много Stack памяти

// ПРОБЛЕМА: каждый поток требует 1MB Stack
repeat(10000) {
    thread {
        Thread.sleep(Long.MAX_VALUE)  // Бесконечно спит
    }
}

// 10000 потоков × 1MB = 10GB памяти только на Stack!
// OutOfMemoryError!

Решение: использовать Coroutines

repeat(10000) {
    launch {  // Не создаёт поток!
        delay(Long.MAX_VALUE)
    }
}

// Все 10000 корутин на 1-2 потоках, памяти в 1000x меньше

9. Stack vs Heap в контексте GC

Stack:

• Автоматически очищается когда функция заканчивается
• LIFO (Last In First Out)
• Очень быстро
• Ограничено размером (1MB)
• Нет GC (сборка мусора)

Heap:

• Очищается только GC
• Может быть медленнее
• Большего размера (сотни MB)
• Требует GC (сборка мусора)

10. Практический пример: рекурсивный обход дерева

data class TreeNode(val value: Int, val children: List<TreeNode>)

// ПЛОХО: может вызвать StackOverflowError на глубоких деревьях
fun sumRec(node: TreeNode): Int {
    return node.value + node.children.sumOf { sumRec(it) }
}

// ХОРОШО: итеративный обход
fun sumIter(root: TreeNode): Int {
    var sum = 0
    val stack = mutableListOf(root)
    
    while (stack.isNotEmpty()) {
        val node = stack.removeAt(stack.lastIndex)
        sum += node.value
        stack.addAll(node.children)
    }
    
    return sum
}

11. Компилятор оптимизирует хвостовую рекурсию

// Компилятор видит, что fibonacci вызывается в конце
// и может оптимизировать в цикл
tailrec fun fibonacci(n: Int, a: Int = 0, b: Int = 1): Int {
    return if (n == 0) a else fibonacci(n - 1, b, a + b)
    //     ↑
    //     Последний вызов = хвостовой вызов!
}

// Скомпилированный код (примерно):
fun fibonacci(n: Int, a: Int = 0, b: Int = 1): Int {
    var n = n
    var a = a
    var b = b
    while (true) {
        if (n == 0) return a
        val temp = b
        b = a + b
        a = temp
        n--
    }
}

12. Как выявить StackOverflow

fun findMaxStackDepth() {
    var depth = 0
    fun go() {
        depth++
        go()
    }
    
    try {
        go()
    } catch (e: StackOverflowError) {
        println("Max stack depth: $depth")  // ~10000-50000 зависит от JVM
    }
}

13. Ограничения Summary

Call Stack:

• Лимит: ~10000 уровней вложенности
• StackOverflowError если переполнить
• Автоматически очищается
• Быстро

Stack Memory (per thread):

• Лимит: 1MB per thread на Android
• Хранит локальные переменные, ссылки
• Быстро
• Если мало потоков — не проблема

Избегай:

• Глубокой рекурсии без хвостовой оптимизации
• Слишком много потоков
• Локальные переменные в циклах (если возможно)

Используй:

• Tail recursion (@tailrec)
• Итеративные решения
• Coroutines вместо Thread'ов
• Stack trace для отладки

Итог

• Stack — это место вызовов функций и локальных переменных
• Лимит ~10000 вложенных вызовов → StackOverflowError
• Каждый thread требует 1MB stack памяти
• Корутины экономят stack (тысячи корутин на одном потоке)
• Хвостовая рекурсия оптимизируется компилятором в цикл
• Лучше использовать итеративные подходы для безопасности