Час проти пам'яті на прикладі хеш-таблиць на Java

    Ця стаття ілюструє т. н. компроміс швидкості і пам'яті — правило, яке виконується в багатьох областях CS, — на прикладі різних реалізацій хеш-таблиць на Java. Чим більше пам'яті займає хеш-таблиця, тим швидше виконуються операції над нею (наприклад, взяття значення по ключу).
 
 
 
 Як міряються
Тестувалися хеш-мапи з інтовимі ключами і значеннями.
 
Міра використання пам'яті — відносно кількість додатково займаної пам'яті понад теоретичного мінімуму для мапи заданого розміру. Наприклад, 1000 інтових пар ключ-значення займають (4 (розмір инта) + 4) * 1000 = 8000 байт. Якщо мапа такого розміру займає 20 000 байт, її міра використання пам'яті буде дорівнювати (20 000 — 8000) / 8000 = 1,5.
 
Кожна реалізація була протестована на 9 рівнях завантаженості (load factors). Кожна реалізація на кожному рівні виключалася на 10 розмірах, логарифмічно рівномірно розподілених між 1000 і 10 000 000. Потім показники використання пам'яті і середні часи виконання операцій незалежно усереднювалися: за трьома найменшим розмірами («small sizes» на графіках), трьом найбільшим (large sizes ) і всім десяти від 1000 до 10 000 000 (all sizes).
 
Реалізації:
  
 Взяття значення по ключу (успішний пошук)
Тільки дивлячись на картинку, можна припустити, що HFTC, Trove і Mahout з одного боку, fastutil, HPPC і GS з іншого використовують один алгоритм хешування. (Насправді це не зовсім так.) Більш розріджені хещ-таблиці в середньому перевіряють менше слотів, перш ніж знайти шуканий ключ, тому відбувається менше читань з пам'яті, тому операція виконується швидше. Можна помітити, що на маленьких розмірах самі розвантажені мапи — вони ж і самі бистриее, для всіх шести реалізацій, але на великих розмірах і при усередненні по всіх розмірами починаючи з показника перевикористання пам'яті ~ 4 прискорення не видно. Це відбувається тому, що якщо загальний розмір мапи перевищує місткість кеша якогось рівня, кеш-промахи частішають у міру подальшого зростання розміру мапи. Цей ефект компенсує теоретичний виграш від меншої кількості перевірок слотів.
 
 
 
 
 Оновлення (інкремент) значення по ключу
Оновлення досить схоже на взяття по ключу. Реалізація fastutil не тестували, бо в ній немає спеціального оптимізованого методу для цієї операції (з цієї ж причини деякі реалізації відсутні при тестуванні інших операцій).
 
 
 
 
 Запис пари ключ-значення (ключ був відсутній в мапе)
Для замірів цієї операції, мапи заповнювалися з нуля дл цільового розміру (1000 — 10 000 000). Перестроювання хеш-таблиць не повинні були траплятися, тому що мапи були ініціалізовані цільовим розміром в конструкторах.
 
Для маленьких розмірів, графіки і раніше схожі на гіперболи, але у мене немає чіткого пояснення такої різкої зміни картинки при переході до великих розмірах і різниці між HFTC та іншими примітивними реалізаціями.
 
 
 
 
 Внутрішня ітерація (forEach)
Ітерація ставав повільніше із зростанням використання пам'яті, на відміну від операцій за окремими ключам. Ще цікаво, що для всіх реалізацій з відкритим хешуванням швидкість залежить тільки від пам'яті, а не теоретичного показника завантаженості таблиці, тому що він розрізняється для різних реалізацій на одному рівні перевикористання пам'яті. Також, на відміну від інших операцій, швидкість forEach практично не залежить від розміру таблиці.
 
 
 
 
 Зовнішня ітерація (через ітератор або курсор)
Швидкість зовнішньої ітерації танцює куди більше, ніж внутрішньої, тому що тут більше простору для оптимізацій (точніше сказати, більше можливостей зробити щось неоптимально). HFTC і Trove використовують власні інтерфейси, інші реалізації — звичайний
java.util.Iterator
.
 
 
 
 
 

 Сирі результати вимірів , по яких були побудовані картинки в цьому пості. Там же, в описі, є посилання на код бенчмарков та інформація про середовище виконання.
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.