Програмування часто здається головоломкою для багатьох, поки не розберешся в цьому мистецтві. (Звісно, я маю на увазі епоху до ChatGPT). І ось наступає момент, коли програмісти опановують синтаксис і базову логіку, здобуваючи впевненість, і раптом стикаються з проблемами складності часу та простору. Хороший програміст освоює ці концепції та, зрештою, створює швидко працюючі коди. Але чи цього достатньо?
Коли ми говоримо про швидкодіючий код, що саме маємо на увазі? Програміст має розуміти, що його код буде перекладений у кілька етапів в інструкції для машини. Код вважається швидким, якщо в кінці кількість інструкцій, які потрібно виконати, мінімізована.
Програміст працює над дуже чутливим до часу кодом, де йому потрібно ініціалізувати 2D масив (50*50), що має значення 0 в усіх своїх елементах.
Ось як це часто пишуть більшість людей:
// створення масиву 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;
}
}
Вона просто поміняла місцями i та j. Що змінилося? Було 2500 значень для ініціалізації, усі вони ініціалізовані однаковим значенням. Єдина зміна — це порядок, у якому їх ініціалізовано. І як вона й очікувала, обидва коди виконують однакову кількість інструкцій і повинні витрачати той самий час на виконання.
Програмістка мала інструмент, який точно вимірює час виконання коду. І вона прогнала обидва варіанти через цей інструмент просто для розваги. (Легенда каже, що деякі погоджуються, що це все-таки цікаво). Але на її велике здивування один з варіантів працював значно швидше за інший. (На цьому етапі багато хто згодився, що це справді цікаво)
Але чому так сталося? Чи це збій в інструменті?
Це дійсно могло статися через особливість, що трапляється всередині комп'ютерів. Який з цих кодів працюватиме швидше, залежить від того, як масиви зберігаються всередині комп'ютера, що, у свою чергу, залежить від багатьох факторів, таких як компілятор, операційна система тощо. Ну що ж, час для історії!
Для того, щоб процесор міг виконати щось, всі відповідні дані повинні бути збережені в пам'яті (відомій нам як RAM). Якщо взяти 2 байти на одне ціле значення, то 2500 цілих чисел займатимуть 5 КБ пам'яті в RAM. Це нічого, якщо у вас є комп'ютер з 4–32 ГБ RAM (спойлер: це займає близько 0.00001% пам'яті).
Припустимо, що масив зберігається по рядках. Тоді перший код, ймовірно, працюватиме швидше. Тепер ви можете подумати, що різниця у часі виникає через те, що час досягнення різних частин RAM різний. (Спойлер: це неправда)
По-перше, різниця у часі незначна. По-друге, ви не можете точно знати, де зберігається кожен рядок в RAM. (Чи чули ви про сторінки?)
Отже, в чому насправді причина? Без зайвих слів давайте розглянемо це.
Ваш комп'ютер з 8 ГБ RAM повинен працювати з багатьма програмами одночасно, які в сумі займають значно більше ніж 8 ГБ. Тому вони не зберігають усе в RAM. Велика частина даних зберігається в сховищі (жорсткому диску або SSD), і їх витягують і переносять в пам'ять, коли це потрібно процесору. Як зазначено раніше, дані зберігаються в сторінках. Тепер подивимося на випадок, коли код програміста виконався значно повільніше, ніж очікувалося.
Бачачи дуже малий код, операційна система виділяє одну сторінку пам'яті в RAM. Одна сторінка в цій системі займає 100 байт.
Перекладено з: Should programmers know what happens inside a computer?