В последнее время я работал над базой кода Go lang разумного размера, где принято думать, что
- Если введение этого нового алгоритма ухудшит производительность существующего программного обеспечения?
- Лучше кэшировать определенные данные вместо того, чтобы вычислять их снова?
- Лучше выбрать хэш-карту вместо списка? и Т. Д.
Хотя производительность системы сложнее оценить количественно только из-за ее более широкого использования в области информатики, я буду говорить о времени выполнения как о метрике для повышения производительности. Go поставляется с множеством встроенных инструментов анализа производительности, которые помогут нам раньше выявить узкие места. В этом посте я расскажу о некоторых из них на примере задачи.
Сценарий
Часто плохой выбор структур данных может укусить нас, когда дело касается производительности.
Для простоты давайте рассмотрим задачу реализации хранилища KV (Key-Value) в памяти с операциями Get и Put, где ключи являются строками, а значения - некоторыми числами. Я не понимаю, как использовать срезы и карты. Итак, я прибегу к подходу, основанному на данных, чтобы найти, какая структура данных является наименее затратной в вычислительном отношении, и буду использовать ее.
В первой итерации я собираюсь реализовать хранилище, используя срез, а затем сгенерировать граф вызовов, а во второй итерации реализовать то же самое с помощью карты.
Тестовый файл содержит несколько тестов для операций Get и Put. Функции эталонного тестирования запускают целевой код N раз, так что они выполняются достаточно долго для надежного хронометража. Для простоты я ограничил количество записей в KVStore 50 КБ. Подробнее о тестах в Go можно найти здесь (https://golang.org/pkg/testing/).
Теперь создание профиля ЦП для определения того, на что тратится большая часть времени ЦП, очень просто в Go и может быть выполнено с помощью следующей команды.
$ go test -run=^$ -bench=. -cpuprofile=cpu.out
Это создаст исполняемый файл с расширением .test (в данном случае KVStore.test) и cpu.out, который содержит информацию о профиле.
График вызовов с указанием времени, затраченного на каждую функцию, был бы идеальным способом копнуть глубже. Мы можем легко сгенерировать граф вызовов в Go, используя следующую команду.
$ go tool pprof KVStore.test cpu.out Entering interactive mode (type “help” for commands) (pprof) web
Мы видим, что время выполнения для KVStore.Store.Put составляет 38,72 секунды, а для KVStore.Store.Get - 1,97 секунды.
- В Put при дальнейшем углублении мы можем заметить, что большую часть времени (36,64 секунды), затрачиваемого на runtime.growSlice, когда мы добавляем новые элементы в срез. Обычно функция добавления в Go увеличивает размер фрагмента на 1,25–2 (в зависимости от размера фрагмента), чтобы он все еще мог увеличиваться, и мы копируем дважды. (Для получения дополнительной информации см. Https://blog.golang.org/slices ). 1.98 сек в функции checkIfItemExistsInStore.
- В Get мы замечаем, что тратим около 1,97 секунды на функцию checkIfItemExistsInStore.
Именно тогда я понял, что выполнение линейного сканирования среза для определения того, существует ли элемент, обходится дорого, а добавление к самому срезу - дорогое удовольствие из-за memmove и mallogc.
Итак, теперь я изменил код, чтобы использовать карту со строками в качестве ключей и значениями в виде int. Результирующий код выглядит так:
Я снова запустил тот же тест, и теперь код выполняется за миллисекунды.
Чтобы понять, что происходит, я снова сгенерировал график вызовов, и теперь функция Put занимает 30 мс, а Get - 40 мс для тех же 50 тыс. Записей. Технически функция Get просто ищет запись на карте и возвращает ее значение, так что это самый быстрый из возможных вариантов с теоретическим O (1). Функция Put также становится операцией вставки в карту с O (1).
Вывод
С приведенными выше данными ясно, что в этом сценарии можно использовать карту, а не фрагмент. Хотя этот сценарий довольно прост и интуитивно понятен для использования карты, в этом посте представлены инструменты анализа производительности и механизмы сравнительного тестирования Go. В следующих статьях я расскажу о других инструментах и профилях производительности, доступных в репертуаре Go, которые упрощают жизнь разработчику. А пока желаю вам счастья и не стесняйтесь комментировать пост с предложениями и отзывами.
Отказ от ответственности
Все мнения мои собственные.