В предыдущих историях мы написали структуру данных хеш-таблицы полностью с нуля в Rust. Сегодня давайте напишем тестовую функцию, чтобы убедиться, что наша хеш-таблица ведет себя точно так же, как и стандартная библиотека. Затем мы напишем простые тесты для сравнения их производительности.
Что касается теста, я вызову пять методов `insert()`, `get()`, `get_mut()`, `remove()` и `len()` миллион раз в случайном порядке со случайным ключом и значениями. Для каждой итерации я сравниваю результат, с результатом полученным от объекта, созданного от стандартной библиотеки. Этот тест проверяет, что обе реализации имеют одинаковое поведение.
Я проводил тест несколько раз, и у тестов никогда не было сбоев. Далее необходимо измерить разницу в производительности между ними. Для этого я напишу `MapTrait`, который разделяет общий интерфейс между ними, чтобы я смог написать общую функцию эталонного теста.
Аналогично тестовой функции, будем повторять случайную операцию со случайным ключом, и значением в данной хэш-таблице. Ниже показан бенчмарк выполнения этой функции для нашей пользовательской реализации по сравнению со стандартной библиотекой, скомпилированной с флагом оптимизации.
Разница огромна! Разница во времени выполнения и `# instructions`, необходимые для выполнения теста, различаются в 20 раз. Что происходит?
При тестировании программы мы должны учитывать еще одну метрику: потребление памяти.
Мы знаем, что наша хеш-таблица работает так, как ожидалось с точки зрения поведения, но мы не знаем, эффективно ли она использует системную память. Самый простой способ измерения потребления памяти программой - это запуск с временем `gnu` и проверка размера резидентного набора (RSS). Это может быть немного сложно, потому что на bash, например, время является встроенной командой. Для явного запуска времени `gnu` необходимо ввести полный путь:
Хорошо, у нас есть идея. Наша реализация как-то очень неэффективно управляет памятью, что является основным узким местом производительности. Из за этого я чувствую, что мы должны посмотреть наш метод `resize()`, чтобы увидеть, что происходит. Действительно, виновником является то, что мы безоговорочно удваиваем размер массива, даже если занятые записи отсутствуют. Более подходящий подход заключается в изучении занятого места и принятии решения о сохранении размера массива или его удвоении.
С этим простым изменением наша реализация улучшилась более чем в 10 раз, и наша реализация вполне сравнима со стандартной библиотекой!
В следующей статье мы будем оптимизировать нашу реализацию еще дальше, так что будьте готовы!
Статья на rusty-code.ru