В последнее время я работал над базой кода 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, которые упрощают жизнь разработчику. А пока желаю вам счастья и не стесняйтесь комментировать пост с предложениями и отзывами.

Отказ от ответственности

Все мнения мои собственные.