Измерение циклов процессора кода C++

Question

Моя цель - измерить эффект (кеширование) различных типов с помощью простого кода. Я следую этой статье, особенно страница 20 и 21: https://people.freebsd.org/~lstewart/articles/cpumemory.pdf

Я работаю над 64-разрядным Linux. Кэш L1d имеет значение 32K, L2 - 256K, а L3 - 25M.

Это мой код (я скомпилировать этот код с г ++, без флагов):

#include <iostream> 

// *********************************** 
// This is for measuring CPU clocks 
#if defined(__i386__) 
static __inline__ unsigned long long rdtsc(void) 
{ 
    unsigned long long int x; 
    __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x)); 
    return x; 
} 
#elif defined(__x86_64__) 
static __inline__ unsigned long long rdtsc(void) 
{ 
    unsigned hi, lo; 
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi)); 
    return ((unsigned long long)lo)|(((unsigned long long)hi)<<32); 
} 
#endif 
// *********************************** 


static const int ARRAY_SIZE = 100; 

struct MyStruct { 
    struct MyStruct *n; 
}; 

int main() { 
    MyStruct myS[ARRAY_SIZE]; 
    unsigned long long cpu_checkpoint_start, cpu_checkpoint_finish; 

    // Initializing the array of structs, each element pointing to the next 
    for (int i=0; i < ARRAY_SIZE - 1; i++){ 
     myS[i].n = &myS[i + 1]; 
     for (int j = 0; j < NPAD; j++) 
      myS[i].pad[j] = (long int) i; 
    } 
    myS[ARRAY_SIZE - 1].n = NULL; // the last one 
    for (int j = 0; j < NPAD; j++) 
     myS[ARRAY_SIZE - 1].pad[j] = (long int) (ARRAY_SIZE - 1); 

    // Filling the cache 
    MyStruct *current = &myS[0]; 
    while ((current = current->n) != NULL) 
     ; 

    // Sequential access 
    current = &myS[0]; 

    // For CPU usage in terms of clocks (ticks) 
    cpu_start = rdtsc(); 

    while ((current = current->n) != NULL) 
     ; 

    cpu_finish = rdtsc(); 

    unsigned long long avg_cpu_clocks = (cpu_finish - cpu_start)/ARRAY_SIZE; 

    std::cout << "Avg CPU Clocks: " << avg_cpu_clocks << std::endl; 
    return 0; 
} 

У меня есть две проблемы:

1- я изменял ARRAY_SIZE от 1 до 1000000 (поэтому размер мой массив находится в диапазоне от 2 до 2 Мбайт), но средняя частота процессора всегда равна 10.

Согласно этому PDF (рис. 3-10 на стр. 21), я ожидал получить 3-5 часов, когда массив может полностью вписывается в L1 и получает более высокие цифры (9 циклов), когда он превышает размер L1.

2- Если я увеличу ARRAY_SIZE за 1 000 000, я получу ошибку сегментации (сброс ядра), из-за переполнения стека. Мой вопрос заключается в том, не использует ли динамическое распределение (MyStruct *myS = new MyStruct[ARRAY_SIZE]) любое ограничение производительности.

Answer 1

Хотя метод, который вы использовали для измерения исполнения, не является надежным, результат, который вы получили (4 цикла), имеет смысл, и вот почему. Измеряемый цикл содержит три команды (mov, test, branch). Из-за предсказания ветвей мы можем притвориться, что у нас есть только последовательность команд mov/test. Из-за суперскалярного выполнения выполнение команды mov может быть перекрыто выполнением тестовой команды некоторой предыдущей итерации. Следовательно, mov определяет время выполнения. Задержка получения данных из кэша L1 в большинстве современных процессоров Intel составляет 4 цикла. Поэтому для каждого элемента должно занимать около 4 циклов, предполагая, что он существует в кеше L1. Однако, просто угадывая, но это зависит от микроархитектуры, причина, по которой количество элементов в массиве, по-видимому, не влияет на время, заключается в том, что аппаратные предварительные считыватели L1 и L2 скрывают большую часть затрат на получение данных с более низких уровней памяти система эффективно делает размер кеша L1 бесконечным.

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

Intel recommends using the rdtscp instruction to measure execution time. При правильном использовании он может давать измерения более точными, чем clock_gettime или любые другие функции.

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