Я проверяю поведение кэша двух алгоритмов поиска, которые работают с отсортированным диапазоном элементов с помощью Cachegrind.У меня есть n элементов в векторе и еще один вектор, который содержит все допустимые индексы.Я использую std :: random_shuffle для второго вектора, а затем выполняю n успешных поисков элементов в первом векторе.Функция, которую я тестирую, выглядит примерно так:
template <typename Iterator>
void lookup_in_random_order(Iterator begin, Iterator end)
{
const std::size_t N = std::distance(begin, end);
std::vector<std::size_t> idx(N);
std::iota(idx.begin(), idx.end(), 0);
std::srand(std::time(0));
std::random_shuffle(idx.begin(), idx.end());
// Warm the cache -- I don't care about measuring this loop.
for(std::size_t i = 0; i < N; ++i)
my_search(begin, end, idx[i]);
std::random_shuffle(idx.begin(), idx.end());
// This one I would care about!
for(std::size_t i = 0; i < N; ++i)
{
int s = idx[i];
// Especially this line, of course.
my_search(begin, end, s);
}
}
Я компилирую свой код с помощью g ++ (с -g и -O2).Я запускаю Cachegrind и затем cg_annotate.Я получаю что-то вроде следующего:
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
. . . . . . . . . template <typename Iterator>
17 2 2 0 0 0 6 0 0 void lookup_in_random_order(Iterator begin, Iterator end)
. . . . . . . . . {
. . . . . . . . . const std::size_t N = std::distance(begin, end);
. . . . . . . . . std::vector<std::size_t> idx(N);
. . . . . . . . . std::iota(idx.begin(), idx.end(), 0);
. . . . . . . . .
4 0 0 0 0 0 2 1 1 std::srand(std::time(0));
. . . . . . . . . std::random_shuffle(idx.begin(), idx.end());
. . . . . . . . .
3,145,729 0 0 0 0 0 0 0 0 for(std::size_t i = 0; i < N; ++i)
. . . . . . . . . my_search(begin, end, idx[i]);
. . . . . . . . .
. . . . . . . . . std::random_shuffle(idx.begin(), idx.end());
. . . . . . . . .
3,145,729 1 1 0 0 0 0 0 0 for(std::size_t i = 0; i < N; ++i)
. . . . . . . . . {
1,048,575 0 0 1,048,575 132,865 131,065 0 0 0 int s = idx[i];
. . . . . . . . . my_search(begin, end, s);
. . . . . . . . . }
7 0 0 6 1 1 0 0 0 }
По некоторым причинам, некоторые строки (особенно самые интересные!) Состоят из точек.Теперь в руководстве Cachegrind говорится: «События, не применимые к линии, представлены точкой. Это полезно для различения события, которое не может произойти, и события, которое может, но не произошло».
Как это следует интерпретировать?Моя первая идея состояла в том, что, возможно, компилятор оптимизирует мой поиск.Я думал, что это не может быть, потому что программа потратила довольно много времени на запуск.Тем не менее, я попытался скомпилировать без флага -O2, и, похоже, это работало в том смысле, что теперь в каждой строке с вызовом my_search записывается несколько чисел (больше нет точек!).Тем не менее, это не похоже на правильный путь по очевидным причинам.
В общем, есть ли способ, которым я могу сказать Cachegrind: «Посмотрите на эту строку особенно, мне очень интересно, сколько кеш пропускаетэто вызывает "?