Що таке "стек викликів" у контексті пам'яті?

АлгоритмиJunior~3 хв читання

Коротка відповідь

Стек викликів - це область пам'яті процесу, де пошарово (за принципом LIFO) зберігаються кадри (frames) активних функцій: адреса повернення, аргументи, локальні змінні і збережені регістри. Він дуже швидкий, керується автоматично при вході/виході з функцій, має обмежений розмір і створюється окремо для кожного потоку. Переповнення стека відбувається при надто глибокій рекурсії чи надто великих локальних даних.

Детальний розбір

Що зберігається в стеку

Кадри викликів (stack frames) - один кадр на активну функцію.
Адреса повернення - куди продовжувати виконання після return.
Аргументи функції і її локальні змінні (що не «втікають» за межі функції).
Збережені регістри і вказівник кадру (FP) - для відновлення контексту.
Принцип LIFO: останній викликаний - перший завершений.
Автоматичний час життя: пам'ять виділяється/звільняється при вході/виході з функції.
Обмежений розмір (зазвичай мегабайти), висока швидкість доступу і немає явного GC для стека.
У кожного потоку - свій стек; використовуються SP (stack pointer) і часто FP (frame/base pointer).

Стек проти купи (heap)

Стек: швидкий, LIFO, автоматичний, обмежений, локальні дані і аргументи, кадри функцій, не потребує явного звільнення.
Купа: гнучка, довільний порядок життя об'єктів, більший розмір, виділення/звільнення дорожче; керується вручну (C/C++) або GC (JS, Java).

Як відбувається виклик і повернення

Передача аргументів функції, що викликається (через стек/регістри, залежить від ABI).
Збереження адреси повернення і потрібних регістрів, зсув вказівника стека (SP) - «виштовхування» кадру.
Виконання тіла функції, робота з локальними змінними.
При return: відновлення регістрів, згортання кадру (SP повертається), перехід за адресою повернення.

+----------------------------+  високі адреси
| frame: main                |
| locals, args               |
| return addr -> runtime     |
+----------------------------+
| frame: g()                 |
| saved FP, locals, args     |
| return addr -> main        |
+----------------------------+
| frame: f()                 |
| saved FP, locals, args     |
| return addr -> g           |
+----------------------------+  низькі адреси
            ^
            SP (stack pointer)  - вказує на вершину стека
            FP (frame pointer)  - вказує на базу поточного кадру

Приклади коду

C: локальні змінні, рекурсія і переповнення стека

#include <stdio.h>

int f(int n) {
    int local = n;                 // локальна змінна в стеку
    if (n == 0) return local;
    return f(n - 1) + 1;           // кожен виклик створює новий кадр
}

int main() {
    // Великий об'єкт на стеку - ризик переповнення (не робіть так)
    // int big[10 * 1024 * 1024];  // ~40 МБ на 64-біт - ймовірний crash

    // Глибока рекурсія теж може переповнити стек
    printf("%d\n", f(1000000));   // у якийсь момент впаде (stack overflow)
    return 0;
}

// ВАЖЛИВО: не можна повертати адресу локальної змінної
// int* bad() {
//     int x = 42;   // x живе лише поки кадр функції в стеку
//     return &x;    // НЕПРАВИЛЬНО: після return кадр знищено
// }

У C локальні змінні живуть до виходу з функції. Великі локальні масиви чи глибока рекурсія легко призводять до переповнення стека. Для великих буферів використовуйте купу (malloc/new).

JavaScript: стек викликів і асинхронність

// Синхронний стек і трасування
function a() { b(); }
function b() { c(); }
function c() {
  // У більшості JS-рушіїв Error().stack показує поточний стек
  console.log(String(new Error().stack));
}
a();

// Асинхронність: колбеки не продовжують поточний стек
console.log('start');
setTimeout(() => console.log('timeout callback (новий стек)'), 0);
Promise.resolve().then(() => console.log('microtask (після поточного стека)'));
console.log('end');

// Переповнення стека в JS
function recurse(i) { return recurse(i + 1); }
try {
  recurse(0);
} catch (e) {
  console.error(e.name + ': ' + e.message); // RangeError: Maximum call stack size exceeded
}

У JS стек керується рушієм: кожен синхронний виклик додає кадр, return знімає. Асинхронні колбеки виконуються пізніше, коли поточний стек порожній - це вже новий стек, тому «продовжень» стека у них немає. Помилка переповнення виникає при надто глибокій (часто нескінченній) рекурсії.

Винятки і «розгортання стека»

При викиданні винятку (наприклад, throw) виконані, але незавершені кадри послідовно знімаються до обробника (catch) - це називається розгортанням стека. На кожному кроці виконуються фіналізатори: блоки finally (JS), деструктори (C++/Rust drop). Якщо обробник не знайдено, програма завершується з помилкою і друкує трасування стека.

Багатопоточність і веб

Кожен потік ОС має власний стек із фіксованим початковим розміром (часто 1-8 МБ), який може зростати до ліміту.
У браузері основний потік UI і кожен Web Worker мають свій стек. Колбеки подій/таймерів виконуються на «порожньому» стеку, коли цикл подій готовий їх обробити.
Асинхронні межі (таймери, I/O, проміси) розривають безперервність стека: «далі» код виконується вже в новому кадрі і часто з новим трасуванням.

Оптимізації і нюанси

Tail-call optimization (TCO): теоретично дозволяє не нарощувати стек при хвостовій рекурсії, але в JS вона рідко реалізована на практиці.
Inlining і опускання вказівника кадру: компілятори/рушії можуть прибирати кадри чи об'єднувати їх, що впливає на трасування стека в дебазі.
Escape analysis: якщо об'єкт «не втікає» за межі функції, деякі мови/компілятори розміщують його в стеку (Go, в оптимізаціях JIT). У JS замикання зазвичай виводять дані в купу.
Безпека: захисні сторінки і canary-значення допомагають виявляти переповнення стека на рівні ОС/рантайму.

Практичні рекомендації

Уникайте глибокої/нескінченної рекурсії в JS: віддавайте перевагу ітерації чи переписуйте на хвостову рекурсію лише якщо TCO гарантована (зазвичай ні).
Не розміщуйте великі обсяги даних у стеку; використовуйте купу для масивів/буферів значного розміру.
Розумійте межі стека при асинхронності: помилки і трасування часто «обриваються» на межі await/then; додавайте контекст вручну за потреби.
Використовуйте трасування стека в логах для діагностики; у браузері і Node.js орієнтуйтеся на Error.stack і карти вихідного коду.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.