ПИШЕМ САМЫЙ БЫСТРЫЙ хеш для кэширования данных Роман Елизаров Devexperts

Преждевременная оптимизация!

Проблемы со скоростью? Вам точно надо их решать? Какие?Почему?Где?

Формулируем задачу Четко. Кратко. Измеримо.

Пример задачи 1. Работаем с заявками 2. Их много, они нужны часто 3. Хотим их кэшировать в памяти

Моделируем нагрузку

Пример нагрузки ~1М заявок в кэше 10М запросов getById Геометрическое распределение id

Что будем измерять? ВремяПамять

Избежим типичных ошибок Помним JIT компиляция и оптимизация кода Сборка мусора

Так что будем измерять? Среднее время одной итерации

Пишем код для замеров

Ищем готовые решения

Разные реализации хеш-таблиц

Не цифрами едиными! RTSL

Что мешает скорости? Функционал Гарантии real-time Thread-safety

Вечный конфликт Универсальность Скорость

Дизайн своего решения Производительность никогда не появляется случайно, только по замыслу авторов.

Из чего складывается скорость? Алгоритм и структуры данных РеализацияРезультат

Выбираем алгоритм Д. Кнут «Искусство программирования» Т. Кормен и др. «Алгоритмы: построение и анализ» С. Скиена «Алгоритмы. Руководство по разработке»

Хеш-таблицы Прямая адресация Открытая адресация Линейное исследование Двойное хеширование

Хеш-таблицы Прямая адресация Открытая адресация Линейной исследование Двойное хеширование И что работает быстрее? А это зависит от реализации и железа

Что используют другие?

Память – это новый диск

Меньше памяти занимает – быстрее работает* * При прочих равных

Проверим …

Меньше памяти использует – быстрее работает* * При прочих равных

Порядок оптимизации при дизайне Занимаемая памятьИспользуемая памятьДругие детали

Выберем структуру данных Открытая адресация – один массив

Оценим потребление памяти

Выберем алгоритм (1) Линейное исследование Проще Доступ к соседним ячейкам Более чувствительно к качеству хеш-функции High-scale-lib, HPPC Двойное хеширование Больше кода В случае промаха прыгает в новое место Требует две независимые хеш-функции Trove

Выберем алгоритм (2) Хеш-функция умножением Быстрая Работает с таблицами размером 2 K Требует выбора магического числа- множителя Хеш-функция делением Медленней – Но память еще медленней! Лучше всего работает с таблицами простого размера Trove High-scale-lib – не использует хеш-функцию HPPC – использует MurmurHash3

Как их комбинировать? Линейное исследование Проще всего Двойное хеширование Хеш-функция умножением Хеш-функция делением

Напишем же!

Магия золотого сечения Равномерно размазывает последовательные числа по таблице

Замерим скорость

Важно распределение вероятности доступа к разным элементам Наиболее часто используемые заявки (последние) имеют соседние id

Каждая деталь имеет значение

А если набор часто используемых id случаен?

Общий процесс Формулировка задачи Модель нагрузки Готовые решения Структура данных Алгоритм Проверка и замеры* * Повторить с начала по необходимости

Спасибо за внимание Роман Елизаров Специальная благодарность: Денису Кисловскому

Все подробности, код и обсуждение: Ваши комментарии важны для меня Хотите знать больше?