Язык Go поставляется со встроенными хорошими инструментами для профилирования процессора и памяти. Но как насчет локальности памяти? Одна из вещей, которая может замедлить работу программы, — это переполнение кеша ЦП; но это трудно сказать при проверке кода или просмотре профиля ЦП.
Существующий инструмент для ответа на этот вопрос — Cachegrind, который имитирует производительность кэшей ЦП. Я решил попробовать заставить его работать с простой программой Go. Вот канонический пример функции с хорошей локализацией кеша, и та же функция, реализованная таким образом, что создает плохую локальность кеша:
func sumRowOrder(a [][]int) int { total := 0 for _, row := range a { for _, x := range row { total += x } } return total } func sumColumnOrder(a [][]int) int { total := 0 size := len(a) for x := 0; x < size; x++ { for y := 0; y < size; y++ { total += a[y][x] } } return total }
Полный пример программы можно найти здесь: https://gist.github.com/mgritter/dc3678b3c988e25eaf1629a416a8c0e9
Ошибки профайлера
Первоначальная попытка была не очень обнадеживающей. Да, программа работает (Cachegrind может работать с любым бинарным файлом), но отсутствует вся информация о функциях и строках:
mark@ubuntu:~/profiling$ /usr/bin/valgrind --tool=cachegrind ./profiling ==38974== Cachegrind, a cache and branch-prediction profiler ==38974== Copyright (C) 2002-2017, and GNU GPL'd, by Nicholas Nethercote et al. ==38974== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info ==38974== Command: ./profiling ==38974== --38974-- warning: L3 cache found, using its data for the LL simulation. sum = 5000661 sum = 5000411 ==38974== ==38974== I refs: 375,202,059 ==38974== I1 misses: 11,302 ==38974== LLi misses: 4,518 ==38974== I1 miss rate: 0.00% ==38974== LLi miss rate: 0.00% ==38974== ==38974== D refs: 198,565,777 (132,841,529 rd + 65,724,248 wr) ==38974== D1 misses: 1,455,976 ( 1,180,036 rd + 275,940 wr) ==38974== LLd misses: 1,404,071 ( 1,136,702 rd + 267,369 wr) ==38974== D1 miss rate: 0.7% ( 0.9% + 0.4% ) ==38974== LLd miss rate: 0.7% ( 0.9% + 0.4% ) ==38974== ==38974== LL refs: 1,467,278 ( 1,191,338 rd + 275,940 wr) ==38974== LL misses: 1,408,589 ( 1,141,220 rd + 267,369 wr) ==38974== LL miss rate: 0.2% ( 0.2% + 0.4% )
Cachegrind может работать с любым настраиваемым размером кэша, но по умолчанию он использует то, что может узнать о ЦП в системе, в которой он работает. Он сообщает количество загрузок инструкций (I), загрузок данных (D) и количество промахов в кэшах уровня 1 (I1, D1) и в кэше более низкого уровня (LL, кэш уровня 3 в моей системе). Взглянув на файл cachegrind.out, вы увидите сведения о размере кеша и общее количество, но не более того:
desc: I1 cache: 32768 B, 64 B, 8-way associative desc: D1 cache: 32768 B, 64 B, 8-way associative desc: LL cache: 6291456 B, 64 B, 12-way associative cmd: ./profiling events: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw fl=??? fn=??? 0 375202059 11302 4518 132841529 1180036 1136702 65724248 275940 267369 summary: 375202059 11302 4518 132841529 1180036 1136702 65724248 275940 267369
Чтобы сообщить о промахах на уровне функций и строк, Cachegrind считывает отладочную информацию (в формате DWARF) из двоичного файла. Это тот же формат, который использует Go, но я подозреваю, что могут возникнуть проблемы с его синтаксическим анализом.
Это был valgrind 3.13 (по умолчанию в версии Ubuntu LTS, которую я использую), и доступна более новая версия. Поэтому я проверил новейший исходный код из их репозитория Git и попробовал еще раз; результаты на этот раз были намного лучше:
... fl=.//home/mark/profiling/main.go fn=main.main 37 7 1 1 2 0 0 1 0 0 39 9 3 3 3 0 0 6 1 1 40 15 0 0 4 2 1 5 1 1 41 16 2 2 6 0 0 10 1 1 42 15 1 1 4 2 2 5 1 1 43 19 4 3 9 0 0 10 1 1 44 15 0 0 4 2 2 5 1 1 45 16 1 1 6 0 0 10 1 1 46 15 1 1 4 2 2 5 1 1 47 15 3 3 8 0 0 7 0 0 48 14 1 1 4 2 2 5 1 1 ...
Теперь мы можем видеть информацию на уровне строки в необработанном выводе. Cachegrind поставляется с инструментом под названием cg_annotate, который печатает эту информацию вместе со строками из оригинального исходного кода. К сожалению, имя файла «.//home/mark/profiling/main.go» имеет неверный формат, и cg_annotate не смог его найти (даже когда я пытался указать ему правильный каталог).
Одним из способов заставить инструмент работать должным образом является редактирование вывода (вручную или с помощью скрипта). Просто удалите лишние ./ из имен файлов, и cg_annotate начнет работать. Или я нашел ошибку в cachegrind и отправил отчет об ошибке и исправление здесь: https://bugs.kde.org/show_bug.cgi?id=419087
Вероятно, основная причина в том, что Go включает в себя как «.», имя каталога и абсолютный путь к файлу в отладочной информации, в то время как другие компиляторы либо не включают имя каталога, либо используют абсолютное имя каталога. Но это только мое предположение; Я не исследовал дальше.
Результаты
Как только инструмент заработает, вот один из способов показать результаты:
mark@ubuntu:~/profiling$ cg_annotate --show-percs=no cachegrind.out.38925 --auto=no --show=Dr,D1mr /home/mark/profiling/main.go
Это говорит о том, что не следует автоматически выбирать, какие файлы показывать; обычно включаются все те, кто превышает пороговое значение. Но в моей игрушечной программе, которая включает в себя кучу ненужных вещей в среде выполнения Go. Я отключил процентное представление и запросил только чтение данных и отсутствие соответствующего кеша L1.
-------------------------------------------------------------------------------- -- User-annotated source: /home/mark/profiling/main.go -------------------------------------------------------------------------------- Dr D1mr . . func sumRowOrder(a [][]int) int { . . total := 0 2,002 375 for _, row := range a { 1,000,000 125,000 for _, x := range row { 0 0 total += x . . } . . } 1 0 return total . . } . . 0 0 func sumColumnOrder(a [][]int) int { . . total := 0 . . size := len(a) 2 0 for x := 0; x < size; x++ { 0 0 for y := 0; y < size; y++ { 3,000,000 1,006,976 total += a[y][x] . . } . . } 2 0 return total . . } . .
Эффективная версия обращается к целым числам в том порядке, в котором они расположены в памяти, и допускает только 125 000 промахов в двумерном массиве из 1 000 000 элементов. Кэш L1, моделируемый в этом примере, имеет размер 64 байта, поэтому он содержит восемь 8-байтовых целых чисел. Таким образом, одного промаха в кэше достаточно для следующих семи значений, что объясняет соотношение чтений и промахов.
Неэффективная версия требует больше промахов кеша, чем элементов массива! И, что удивительно, читает в 3 раза больше памяти.
Постскриптум
Другой подход заключается в измерении фактического количества промахов кэша с помощью счетчиков производительности процессора. Тестируемая программа может быть сэмплирована каждые N раз, когда происходит определенное событие ЦП, например промах кеша. Эту статистическую выборку использует инструмент Linux perf. Я пытался использовать Intel VTune, который может выполнять такой анализ и утверждает, что поддерживает Go, но мне не удалось заставить его работать. VTune говорит, что его микроархитектурная поддержка в любом случае не работает на виртуальной машине.