В інформатиці локальність посилань (), також відома як принцип локальності,Не слід плутати з принципом локальності у фізиці. — це властивість процесора багаторазово звертатися до одного й того самого набору комірок пам'яті протягом короткого проміжку часу.
Типи локальності Розрізняють два основні типи локальності посилань: Часова локальність означає повторне використання певних даних та/або ресурсів протягом відносно короткого проміжку часу. Просторова локальність (також звана локальністю даних; )"NIST Big Data Interoperability Framework: Volume 1", [https://doi.org/10.6028/NIST.SP.1500-1r2 urn:doi:10.6028/NIST.SP.1500-1r2 означає використання елементів даних, розташованих у відносно близьких областях пам'яті. Послідовна локальність — окремий випадок просторової локальності — виникає тоді, коли елементи даних розміщені та опрацьовуються послідовно, наприклад під час проходження елементів одновимірного масиву.
Значення
Локальність є різновидом передбачуваної поведінки, що виникає в комп'ютерних системах. Системи, для яких характерна висока локальність посилань, добре піддаються оптимізації продуктивності за допомогою таких методів, як кешування, попереднє вибирання даних із пам'яті та використання вдосконалених предикторів переходів у ядрі процесора. Низька локальність посилань призводить до трешингу кешу та забруднення кешу, тому для уникнення цього елементи даних із низькою локальністю можуть не поміщатися до кешу.
Локальність часто виникає зі структури програми. Як правило, пов'язані дані зберігаються в близьких місцях пам'яті. Одним із поширених шаблонів програмування є обробка кількох елементів по одному. Це означає, що якщо над одним елементом виконується значний обсяг обчислень, до нього звертатимуться неодноразово, що призводить до часової локальності посилань. Крім того, перехід до наступного елемента означає, що буде прочитано сусідній елемент, що забезпечує просторову локальність посилань, оскільки пам'ять зазвичай читається блоками.
Локальність часто виникає тому, що код містить цикли, які звертаються до масивів або інших структур даних за індексами. Послідовна локальність, яка є окремим випадком просторової локальності, виникає тоді, коли відповідні елементи даних розташовані й опрацьовуються послідовно. Наприклад, простий обхід елементів одновимірного масиву від його базової адреси до останнього елемента використовує послідовну локальність масиву в пам'яті.Aho, Lam, Sethi, and Ullman. "Compilers: Principles, Techniques & Tools" 2nd ed. Pearson Education, Inc. 2007
Багатовимірні масиви Для локальності посилань при обході багатовимірного масиву, його потрібно розглядати як масив масивів меншої розмірності, які розміщені в пам'яті послідовно. І у внутрішньому циклі потрібно проходити елементи найбільш внутрішнього масиву (які є сусідніми фізично в пам'яті).
Див. також Фрагментація файлової системи
Примітки