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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25 Проверим …

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

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

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

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

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

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

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

33 Напишем же!

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

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

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

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

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

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

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

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