Давайте возьмем стандартную библиотечную реализацию `HashMap`, измеренную на нашем синтетическом тесте. Для этого мы запустим профилировщик и изучим, где главное узкое место, и попытаемся улучшить это.
Для моей системы Linux я буду использовать утилиту perf. Не забудьте построить исполняемый файл с использованием символов отладки. Кроме того, рекомендуется профилировать релизную сборку.
Согласно отчету профилировщика, наибольшие накладные расходы (30%) приходятся на метод `get_index()`. Для интереса, вот как реализуется метод:
Возможно, это - функция хеширования, которая занимает слишком много времени? Ну, давайте исследуем её далее, войдя в инструкции уровня ассемблера:
Обратите внимание, что наше узкое место появляется после метода `hasher::finish()` непосредственно перед возвратом `get_index()`. Наиболее важной операцией, по мнению профилировщика, является `mov`. Имеет ли это смысл? `mov`-операция, вероятно, является всего лишь одним циклом, поскольку она перемещает между регистрами.
Ну, на самом деле профилировщик не может указать на точную инструкцию. Скорее, это указывает на то что рядом. Обратите внимание на предыдущую инструкцию, которая является `div`. Это фактический виновник узкого места, что имеет смысл. Оператор деления будет использовать несколько циклов. Вопрос в том, откуда это взялось? Посмотрите на последнюю строку метода `get_index()`:
Вот и все. Существует оператор деление по модулю `%`, который по существу является операцией деления и получает остаток. Это наше главное узкое место. Для каждого вызова `get()`, `get_mut()`, `insert()` или `remove()` необходимо искать индекс в массиве, поэтому имеет смысл вызывать этот метод миллионы раз. Операция `div` сама по себе составляет всего несколько циклов, но когда она выполняется неоднократно в течение миллиона раз, накладные расходы суммируются.
Мы можем что-нибудь с этим сделать? Мы не можем оптимизировать `div` в целом, но мы можем для некоторых особых случаев, например, когда делитель является степень 2. Напомним, что наш метод `resize()` удваивает массив, начиная с 64. Из этого мы знаем, что размер массива всегда будет равен 2. При этом операция по модулю идентична побитовому `AND` с `array.len() - 1`. Поразрядная операция и операция вычитания должны состоять из одного цикла. Давайте поищем все `%` операции и заменим нашей оптимизированной битовой операцией. Для этого я создам метод `index()`. Готов поспорить, что компилятор встроит метод, так что не беспокойтесь о затратах на вызов функции.
С этим изменением, давайте снова запустим профилировщик, чтобы увидеть, изменились показания или нет:
Действительно, накладные расходы `get_index()` сократились с 30% до 24%. Не резкое улучшение, но и неплохое для всего нескольких строк изменений кода. Давайте измерим время выполнения:
После оптимизации по модулю наша реализация работает наравне со стандартной библиотекой!
Статья на rusty-code.ru