Програмування — це важкий процес для багатьох, поки вони не освоять його тонкощі. (Звісно, я маю на увазі епоху до ChatGPT). Є момент, коли програмісти вивчають синтаксис і базову логіку, набувають впевненості, але потім стикаються з проблемами складності часу та пам'яті. Хороший програміст оволодіває цими концепціями і починає писати швидкий код. Але чи достатньо цього?
Ми говоримо про швидкий код, але що це насправді означає? Програміст повинен розуміти, що ваш код буде перетворено в інструкції машини в кілька етапів. Код вважається швидким, якщо кількість інструкцій, які повинна виконати машина, мінімізована.
Уявіть, програміст працює над часо-чутливим кодом, що вимагає ініціалізації 2D масиву (50x50), заповненого нулями.
Ось як більшість людей пишуть цей код:
// створення масиву A тут
for (int i=0; i<50; i++)
{
for (int j=0; j<50; j++)
{
A[i][j] = 0
}
}
Але один розумний програміст подумав: "Чому б не зробити це цікавіше?" (Чи є це цікавим — питання на віки). Вона зробила невеликий зміни в коді:
// створення масиву A тут
for (int i=0; i<50; i++)
{
for (int j=0; j<50; j++)
{
A[j][i] = 0
}
}
Що змінилося? Було 2500 значень для ініціалізації. Всі вони ініціалізовані однаковим значенням. Єдина зміна — це порядок ініціалізації. І як вона очікувала, обидва коди виконуються за однакову кількість інструкцій і, очевидно, мають однаковий час виконання.
Програмістка мала інструмент, який точно розраховував час виконання їхнього коду. І вона запустила обидва варіанти через інструмент для розваги. (Легенда каже, що деякі люди все ще погоджуються, що це цікаво). Але, на її величезне здивування, один із кодів працював на порядок швидше за інший. (На цьому етапі багато хто погодився, що це дійсно цікаво).
Але чому так сталося? Це була помилка інструменту?
Виявляється, це насправді можливо через дещо, що відбувається всередині нашого комп'ютера. Який із цих кодів працює швидше, залежить від того, як масиви зберігаються в пам'яті комп'ютера, що в свою чергу залежить від багатьох факторів, таких як компілятор, ОС і так далі. Давайте подивимося на це.
Для роботи процесора вся необхідна інформація повинна бути в пам'яті (по суті, відомий усім RAM). Припустимо, що один елемент займає 2 байти, і тому 2500 цілих чисел займають 5 КБ пам'яті. Це нічого, якщо у вас є комп'ютер з 4–32 ГБ пам'яті (спойлер — це займає лише 0.00001% пам'яті).
Припустимо, що масив зберігається по рядках. Тоді перший код, ймовірно, буде працювати швидше. Тепер ви могли б подумати, що різниця в часі виникає через те, що час, необхідний для доступу до різних частин пам'яті, різний. (Спойлер — це неправда)
По-перше, ця різниця часу є дуже незначною. А по-друге, ви не можете знати, де в пам'яті кожен рядок зберігається. (Чи чули ви про сторінку?)
Яка ж справжня причина? Без зайвих слів (жарт у назві, коментуйте, якщо зрозуміли) ось до чого це призводить.
Ваш комп'ютер з 8 ГБ RAM повинен запускати багато програм одночасно, що в сумі займають значно більше ніж 8 ГБ. Тому всю інформацію не зберігають в RAM. Велика частина даних зберігається на жорсткому диску або SSD, і вони завантажуються в пам'ять, коли процесор запитує їх. Як було зазначено раніше, дані зберігаються у вигляді сторінок. Тепер давайте розглянемо один (очевидно, скриптований) випадок, коли код програмістки працював значно повільніше, ніж очікувалося.
Ось, що сталося, коли операційна система виділила одну сторінку пам'яті для масиву. Одна сторінка в цій системі займає 100 байт.
Перекладено з: Leetcode 242 — Valid Anagram in C++ | HashMap | Unordered Map | LC Easy | Cpp Interview Problem