Розробка

Кротові нори в JavaScript

 

Комп’ютери — цікаві машини. У теорії вони представляються нам ідеальними механічними математиками працюють з цифрами і добре виконують операції додавання, множення і віднімання.

Однак, така абстракція досить оманлива. Вона відводить нас від розуміння того, що комп’ютер обробляє різні математичні операції з різною швидкістю. Якщо ви пишіть на JavaScript (чи на будь-якому іншому мовою) і дбаєте про продуктивності написаних вами алгоритмів, дуже важливо розуміти, як працюють комп’ютери під капотом.

Якщо ми знаємо на що здатний комп’ютер, ми можемо використовувати найкоротші шляхи або кротові нори, щоб зробити наші програми набагато швидше, ніж ми очікували.

 

Кротова нора в операції отримання залишку від ділення

 

Що конкретно це означає? Давайте подивимося на прикладі: уявімо, що ми хочемо реалізувати кільцевий список. Кільцевий список — це список з фіксованим розміром, у якому вставки більші, ніж розмір списку, переміщуються в початок списку і по колу. Кільцеві списки дуже зручні для багатьох речей — таких як збір статистики за певні інтервали часу, буферизація даних та багато іншого, але подивіться на цю реалізацію:

 

const list = new Array(15000)
function set (i, item) {
 // Оператор % - ділення по модулю, повертає залишок від ділення
 // числа зліва від нього на число праворуч
 // використання цього оператора тут, прив'язує цикл із змінною i до розміру списку
 list[i % list.length] = item
}

Як швидко виконується цей код? Давайте запустимо простий тест на швидкість

console.time()
for (var i = 0; i < 1e9; i++) {
 set(i, i)
}
console.timeEnd()

 

На моєму комп’ютері це зайняло ~4 сек на 1 млрд вставок. Непогано.

 

Однак, давайте застосуємо обчислювальну кротовую нору і змінимо розмір масиву на магічне число:

 

// Змінимо розмір списку із 15000 на 16384
const list = new Array(16384)

function set (i, item) {
 // Оператор % - ділення по модулю, повертає залишок від ділення
 // числа зліва від нього на число праворуч
 // використання цього оператора тут, прив'язує цикл із змінною i до розміру списку
 list[i % list.length] = item
}

Спробуємо запустити тест на продуктивність знову. На моєму комп’ютері тест виконався за ~1.5 сек. Більш ніж дворазове збільшення за рахунок простої зміни розміру. Для того щоб зрозуміти, чому так відбувається, ми повинні розуміти наступне, під капотом комп’ютер працює з числами з основою 2. Це важливо знати якщо ми отримуємо залишок від ділення (операція %). Таке обчислення можна зробити набагато простіше, якщо число кратно 2 (2 ^ n) b 16384 це 2 ^ 14. За фактом комп’ютер дивиться на число в двійковому вигляді і просто бере останні n біт.

Для прикладу: що буде відбуватися при виконанні такої операції 353 500 % 16 384? 353 500 у двійковому поданні буде виглядати як 1010110010011011100. Оскільки 16384 == 2 ^ 14 — нам необхідно взяти останні 14 біт — 10101 (10010011011100) або 9 346.

Ми можемо використовувати це знання стосовно іншої кротовій норі. Для комп’ютера дуже просто і швидко брати останні n біт. За фактом, необхідно всього лише провести бінарне і (операція &) з числом (2 ^ n) — 1

 

const list = new Array(16384)

function set (i, item) {
 // Використання швидкого оператора &(бінарне) замість % з довжиною списку 2 ^ n
 list[i & (list.length - 1)] = i
}

Запустивши знову тест продуктивності на моєму комп’ютері ми побачимо, що час виконання знизитися до ~1s або відбудеться 4-х кратне збільшення продуктивності в порівнянні з першим запуском. І все це за рахунок розуміння того, як комп’ютер працює.

 

Розумні компілятори або VМ здатні виробляти таку оптимізацію перетворюючи за лаштунками операцію отримання залишку в побитовую операцію і назад. За фактом остання V8 Javascript VM (не реалізовано в NodeJS) робить саме так.

Числові кротові нори

Іншої корисної кротової норою є розуміння того як працює читання і запис чисел. Пам’ятаєте як ми використали 32-бітні комп’ютери і як отримали 64 біта? А до 32-х біт у нас було 16 біт. Що конкретно це означає? Зазвичай ми думаємо про це так — як багато оперативної пам’яті у нас є на комп’ютері. 2 ^ 32 = 4294967296 або 4 Гб, що означає, що ми можемо отримати доступ тільки до 4 Гб пам’яті на 32-бітному комп’ютері. Коли ми пишемо JS програму зазвичай нам не потрібно думати про це, оскільки ми зазвичай не використовуємо стільки пам’яті.

Однак дуже важливо розуміти різницю між 32 – і 64-бітними комп’ютерами. З тих пір як процесори отримали 64-бітні регістри на 64 -розрядних комп’ютерах здійснення операцій стали в 2 рази швидше ніж на 32 бітних комп’ютерах, де ви мали тільки 32-бітні регістри.

Як же ми можемо використовувати інформацію про цю кротовій норі?
Давайте напишемо просту програму, яка копіює один Uint8Array в інший. Якщо ви не знайомі з Unit8Arrays — вони дуже схожі з Buffers в NodeJS, або просто “чистої” пам’яттю.

function copy (input, output) {
 // для простоти припустимо input.length <= output.length
 for (var i = 0; i < input.length; i++) {
 // копіюємо кожне 8-розрядне число (byte)
 output[i] = input[i]
}
}

 

Знову давайте виміряємо швидкість, запустивши тест продуктивності.

 

// давайте виділимо два 1MB Uint8Arrays для нашого тесту продуктивності
const input = new Uint8Array(1024 * 1024)
const output = new Uint8Array(1024 * 1024)

console.time()
for (var i = 0; i < 1e4; i++) {
 copy(input, output)
}
console.timeEnd()

 

На моєму комп’ютері програма виконалася за ~7.5 сек. Як ми можемо використовувати кротовую нору для прискорення? Використовуючи Uint8Array ми копіюємо тільки 8 біт за один раз, але маючи 64-бітний комп’ютер — ми можемо копіювати 64 біта інформації за той же час. Ми можемо зробити це в JavaScript, перетворивши наш Uint8Array в Float64Array перед копіюванням, що нам не буде нічого коштувати.

function copy (input, output) {
 // для простоти припустимо input.length <= output.length

 // на вхід і вихід 64-розрядних чисел
 // тут ми фактично використовуємо числа з плаваючою комою, 
 // тк кожне з них приймає 64-розрядне подання
 // коли BigInts оптимізований в JavaScript, ми можемо використовувати BigInt64Array.

 const input64 = new Float64Array(input.buffer, input.byteOffset, input.length / 8)
 const output64 = new Float64Array(output.buffer, output.byteOffset, output.length / 8)

 for (var i = 0; i < input64.length; i++) {
 // копіюємо кожне 64-розрядне число 
 output64[i] = input64[i]
}
}

Запустивши тести продуктивності знову ми отримаємо час виконання рівне 1 сек, що дає 8 кратний приріст швидкості.

Для копіювання прийнятним рішенням буде використання array.set(otherArray) методу для Uint8Array, що дає нам копіювання в нативному коді — що набагато швидше, ніж будь-які інші кротові нори. Для довідки це дасть результат в ~ 0.2 сек виконання в нашому тесті на моєму комп’ютері, що в 5 рази швидше ніж попереднє рішення.

 

Галактика JavaScript сповнена кротячих нір

 

Використання кротячих нір, наведених вище, допоможе Вам зробити тонни реальних алгоритмів набагато швидше. Існує ще багато подібних кротячих нір. Мій фаворит — Math.clz32 — метод, що повертає 32 бітному число з провідним 0. Ми можемо використовувати цей метод для безлічі цікавих алгоритмів. Я використовував його для прискорення реалізації бітових полів https://github.com/mafintosh/fast-bitfield) в 4 рази, що призвело до зниження витрати пам’яті також у 4 рази і дозволило мені в деяких ситуаціях сортувати числа набагато швидше (https://github.com/mafintosh/value-sort).

Розуміння основних принципів роботи комп’ютера дозволяє писати найбільш швидкі програми, які нам потрібні. Ці знання мають значення навіть тоді, коли ви пишіть на такій мові високого рівня як JavaScript.

 

Related Articles

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *

Close