Cachegrind - модуль Valgrind

Cachegrind - модуль Valgrind

27.05.2018 07:56:52 Просмотров 28 Источник

Посыл каждого модуля Валгринд понятен, за исключением Кэшгринд. Как я понял из мауналов

Модуль используется

  1. Для сбора информации о статистике попадания в кэши процессора данных и инструкций программы.
  2. Для сбора статистики работы модуля предсказания ветвления в программах.

Возникли вопросы

  1. Я понимаю что кэши проца нужны для того чтобы он как то автоматически оптимизировался и делал некоторые вещи быстрее за счет сохранения некоторой инфы в кэше. Но! Разве мы как то можем повлиять на это? Судя по тому что Кэшгринд это профайлер, то по идее это как то можно сделать, получив инфу, но как? И как вообще понять что у нас есть потенциал увеличить нагрузку на кэши проца нашей программой (т.е. сказать процу использовать кеши активнее при работе с нашей прогой что ли)

  2. Если есть инфа по работе модуля ветвлений, которая каким то образом говорит нам что этот модуль отработал плохо, то как мы можем изменить ситуацию?

У вопроса есть решение - Посмотреть?

Ответы - Cachegrind - модуль Valgrind / Cachegrind - модуль Valgrind

Является ответом!
Fat-Zer

29.05.2018 06:58:51

Как в случае с кешированием, так и в случае с блоком предсказания ветвлений, надо понимать типовые алгоритмы и устройство этих модулей. За подробностями от себя порекомендую обратиться к классике, Таненбаум — «Архитектура компьютера». Но вопрос не про их устройство, так что здесь я ограничусь простыми примерами, где можно увидеть их действие.

Про кеширование

Есть несколько эффектов, которое кеширование оказывает на реальное время выполнение. Оптимизация программы в этом плане почти всегда сводится к тому, чтобы использовать те алгоритмы, которые хорошо сочетаются с оным. Самый значительный параметр при этом — локальность данных, но есть и целый шлейф других эффектов связанных с устройством кешей, которые дают схожие проблемы.

Простой пример алгоритма, который плохо сочетается с кешированием — обход матрицы по столбцам:

#define SZ 2048

// размер матрицы 16MB ≥L3 на большинстве процессоров.
int matr[SZ][SZ];

// ...

for (int j=0; j<SZ; j++) {
  for (int i=0; i<SZ; i++) {
    matr[i][j]++;
  }
}

Если просто поменять местами внешний и внутренний цикл, то время выполнения значительно уменьшится. (Иногда, компилятор может сделать это сам.)

Вообще с кешированием плохо сочетается весь класс задач, где нужен произвольный доступ к большим объёмам данных: сюда входят многие алгоритмы связанные с использованием деревьев, графов, хеш-таблиц и т.д.; зачастую для исправления ситуации можно выбрать другой алгоритм или изменить текущий, иногда можно улучшить ситуацию перераспределив данные в памяти, например, создав специальный аллокатор; обычно и то и другое требует дополнительного исследования. На практике до этого мало у кого доходят руки.

Про блок предсказаний ветвления.

Здесь свободы намного меньше, а выигрыш зависит от архитектуры.

При статическом предсказании может помочь правильная подготовка кода на этапе компиляции. В частности (на примере gcc):

  • Эвристики и встроенные оптимизации компилятора.
  • Профилирование с помощью встроенного в gcc профилировщика (см. ключи -fprofile-arcs и -fbranch-probabilities). AFAIK данные от valgrind'а пока нельзя напрямую скормить gcc.
  • Ручная расстановка макросов __builtin_expect
  • Форматирование кода: например в операторе if-then-else блок then обычно считается наиболее вероятным.

Но на архитектурах с динамическими предсказаниями (например i686+ [да поправят меня, может и на i586]) эффект от этих приёмов минимален и ими имеет смысл пользоваться только в относительно редко вызываемом, но крайне критичном по времени коде, например, в обработчиках прерываний. Для кода общего назначения обычно ничего сделать нельзя/бессмысленно, за исключением разве что предподготовки данных. Например, следующий код будет работать заметно быстрее на [почти]отсортированном массиве, чем на случайном именно за счёт блока предсказаний:

int arr[SZ];
// ...
int threshold = 42;
size_t cnt = 0;

for (size_t i; i<SZ; ++i) {
  if (arr[i]>threshold) {
    cnt++;
  }
}

Замечание о valgrind

Стоит заметить, что valgrind не опирается на запрос какой-либо статистике у процессора, а просто симулирует работу кеша и блока предсказаний, так что результаты его работы могут отличаться от исполнения на реальном ЦП, но с определённой долей достоверности их вполне можно использовать для оценки и оптимизации.

Закрыть X