Примеры Предварительной Выборки?

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

 #include <time.h>
 #include <stdio.h>
 #include <stdlib.h>

 int binarySearch(int *array, int number_of_elements, int key) {
         int low = 0, high = number_of_elements-1, mid;
         while(low <= high) {
                 mid = (low + high)/2;
            #ifdef DO_PREFETCH
            // low path
            __builtin_prefetch (&array[(mid + 1 + high)/2], 0, 1);
            // high path
            __builtin_prefetch (&array[(low + mid - 1)/2], 0, 1);
            #endif

                 if(array[mid] < key)
                         low = mid + 1; 
                 else if(array[mid] == key)
                         return mid;
                 else if(array[mid] > key)
                         high = mid-1;
         }
         return -1;
 }
 int main() {
     int SIZE = 1024*1024*512;
     int *array =  malloc(SIZE*sizeof(int));
     for (int i=0;i<SIZE;i++){
       array[i] = i;
     }
     int NUM_LOOKUPS = 1024*1024*8;
     srand(time(NULL));
     int *lookups = malloc(NUM_LOOKUPS * sizeof(int));
     for (int i=0;i<NUM_LOOKUPS;i++){
       lookups[i] = rand() % SIZE;
     }
     for (int i=0;i<NUM_LOOKUPS;i++){
       int result = binarySearch(array, SIZE, lookups[i]);
     }
     free(array);
     free(lookups);
 }

когда я компилирую и запускаю этот пример с включенным DO_PREFETCH, я вижу сокращение времени выполнения на 20%:

 $ gcc c-binarysearch.c -DDO_PREFETCH -o with-prefetch -std=c11 -O3
 $ gcc c-binarysearch.c -o no-prefetch -std=c11 -O3

 $ perf stat -e L1-dcache-load-misses,L1-dcache-loads ./with-prefetch 

  Performance counter stats for './with-prefetch':

    356,675,702      L1-dcache-load-misses     #   41.39% of all L1-dcache hits  
   861,807,382      L1-dcache-loads                                             

   8.787467487 seconds time elapsed

 $ perf stat -e L1-dcache-load-misses,L1-dcache-loads ./no-prefetch 

 Performance counter stats for './no-prefetch':

   382,423,177      L1-dcache-load-misses     #   97.36% of all L1-dcache hits  
   392,799,791      L1-dcache-loads                                             

  11.376439030 seconds time elapsed

обратите внимание, что мы делаем в два раза больше загрузок кэша L1 в версии предварительной выборки. На самом деле мы делаем намного больше работы, но шаблон доступа к памяти более дружелюбен к конвейеру. Это также показывает компромисс. Хотя этот блок кода работает быстрее в изоляции, мы загрузили много мусора в кэши, и это может оказать большее давление о других частях приложения.

Я многому научился из отличных ответов, предоставленных @JamesScriven и @Mystical. Однако их примеры дают только скромный импульс - цель этого ответа-представить (я должен признаться, несколько искусственный) пример, где предварительная выборка имеет большее влияние (около фактора 4 на моей машине).

есть три возможных бутылочных горлышка для современных архитектур: CPU-speed, memory-band-width и задержка памяти. Предварительная выборка - это все о снижении задержки доступ к памяти.

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

для многих алгоритмов мы (почти) в этом идеальном мире. Для простого цикла for легко предсказать, какие данные понадобятся X шагов позже. Из-за исполнения Заказа и другие аппаратные трюки делают очень хорошую работу здесь, скрывая задержку почти полностью.

вот почему есть такое скромное улучшение для примера @Mystical: prefetcher уже довольно хорош - просто нет места для улучшения. Задача также связана с памятью, поэтому, вероятно, не так много ширины полосы осталось-это может стать ограничивающим фактором. Я мог видеть в лучшем случае около 8% улучшение на моей машине.

критическую проницательность из примера @JamesScriven: ни мы, ни процессор не знаем следующего адреса доступа до того, как текущие данные будут извлечены из памяти-эта зависимость довольно важна, иначе выполнение вне порядка приведет к ожиданию, и оборудование сможет предварительно выбрать данные. Однако, поскольку мы можем рассуждать только об одном шаге, потенциал не так уж велик. Я не смог получить более 40% на моей машине.

Итак, давайте установим конкуренцию и подготовим данные в таким образом, мы знаем, к какому адресу обращаются в X шагах, но не можем узнать его аппаратно из-за зависимостей от еще не доступных данных (см. Всю программу в конце ответа):

//making random accesses to memory:
unsigned int next(unsigned int current){
   return (current*10001+328)%SIZE;
}

//the actual work is happening here
void operator()(){

    //set up the oracle - let see it in the future oracle_offset steps
    unsigned int prefetch_index=0;
    for(int i=0;i<oracle_offset;i++)
        prefetch_index=next(prefetch_index);

    unsigned int index=0;
    for(int i=0;i<STEP_CNT;i++){
        //use oracle and prefetch memory block used in a future iteration
        if(prefetch){
            __builtin_prefetch(mem.data()+prefetch_index,0,1);    
        }

        //actual work, the less the better
        result+=mem[index];

        //prepare next iteration
        prefetch_index=next(prefetch_index);  #update oracle
        index=next(mem[index]);               #dependency on `mem[index]` is VERY important to prevent hardware from predicting future
    }
}

некоторые замечания:

1. данные подготовлены таким образом, что оракул всегда прав.
2. возможно, удивительно, что чем меньше задача с привязкой к процессору, тем больше скорость: мы можем скрыть задержку почти полностью, таким образом, ускорение это CPU-time+original-latency-time/CPU-time.

компиляция и выполнение приводит:

>>> g++ -std=c++11 prefetch_demo.cpp -O3 -o prefetch_demo
>>> ./prefetch_demo
#preloops   time no prefetch    time prefetch   factor
...
7   1.0711102260000001  0.230566831 4.6455521002498408
8   1.0511602149999999  0.22651144600000001 4.6406494398521474
9   1.049024333 0.22841439299999999 4.5926367389641687
....

для ускорения между 4 и 5.

---

список prefetch_demp.cpp:

//prefetch_demo.cpp

#include <vector>
#include <iostream>
#include <iomanip>
#include <chrono>

const int SIZE=1024*1024*1;
const int STEP_CNT=1024*1024*10;

unsigned int next(unsigned int current){
   return (current*10001+328)%SIZE;
}


template<bool prefetch>
struct Worker{
   std::vector<int> mem;

   double result;
   int oracle_offset;

   void operator()(){
        unsigned int prefetch_index=0;
        for(int i=0;i<oracle_offset;i++)
            prefetch_index=next(prefetch_index);

        unsigned int index=0;
        for(int i=0;i<STEP_CNT;i++){
            //prefetch memory block used in a future iteration
            if(prefetch){
                __builtin_prefetch(mem.data()+prefetch_index,0,1);    
            }
            //actual work:
            result+=mem[index];

            //prepare next iteration
            prefetch_index=next(prefetch_index);
            index=next(mem[index]);
        }
   }

   Worker(std::vector<int> &mem_):
       mem(mem_), result(0.0), oracle_offset(0)
   {}
};

template <typename Worker>
    double timeit(Worker &worker){
    auto begin = std::chrono::high_resolution_clock::now();
    worker();
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count()/1e9;
}


 int main() {
     //set up the data in special way!
     std::vector<int> keys(SIZE);
     for (int i=0;i<SIZE;i++){
       keys[i] = i;
     }

     Worker<false> without_prefetch(keys);
     Worker<true> with_prefetch(keys);

     std::cout<<"#preloops\ttime no prefetch\ttime prefetch\tfactor\n";
     std::cout<<std::setprecision(17);

     for(int i=0;i<20;i++){
         //let oracle see i steps in the future:
         without_prefetch.oracle_offset=i;
         with_prefetch.oracle_offset=i;

         //calculate:
         double time_with_prefetch=timeit(with_prefetch);
         double time_no_prefetch=timeit(without_prefetch);

         std::cout<<i<<"\t"
                  <<time_no_prefetch<<"\t"
                  <<time_with_prefetch<<"\t"
                  <<(time_no_prefetch/time_with_prefetch)<<"\n";
     }

 }

С документация:

      for (i = 0; i < n; i++)
        {
          a[i] = a[i] + b[i];
          __builtin_prefetch (&a[i+j], 1, 1);
          __builtin_prefetch (&b[i+j], 0, 1);
          /* ... */
        }

предварительная выборка данных может быть оптимизирована до размера строки кэша, который для большинства современных 64-разрядных процессоров составляет 64 байта, например, для предварительной загрузки uint32_t[16] С одной инструкцией.

например, на ArmV8 я обнаружил, что в результате экспериментов указатель памяти на вектор матрицы uint32_t 4x4 (размер которого составляет 64 байта) вдвое сократил требуемые инструкции, как и раньше, мне пришлось увеличить на 8, поскольку он загружал только половину данных, хотя я понимал, что это было извлекает полную строку кэша.

предварительная выборка исходного кода uint32_t[32]...

int addrindex = &B[0];
    __builtin_prefetch(&V[addrindex]);
    __builtin_prefetch(&V[addrindex + 8]);
    __builtin_prefetch(&V[addrindex + 16]);
    __builtin_prefetch(&V[addrindex + 24]);

после...

int addrindex = &B[0];
__builtin_prefetch((uint32x4x4_t *) &V[addrindex]);
__builtin_prefetch((uint32x4x4_t *) &V[addrindex + 16]);

по какой-то причине int datatype для индекса адреса/смещения дал лучшую производительность. Испытано с GCC 8 на Cortex-a53. Использование эквивалентного 64-байтового вектора на других архитектурах может дать такое же повышение производительности, если вы обнаружите, что он не предварительно извлекает все данные, как в моем случае. В моем приложении с циклом один миллион итераций, это улучшило производительность на 5%, просто сделав это. Были и другие требования к улучшению.

выделение памяти 128 мегабайт "V" должно было быть выровнено до 64 байт.

uint32_t *V __attribute__((__aligned__(64))) = (uint32_t *)(((uintptr_t)(__builtin_assume_aligned((unsigned char*)aligned_alloc(64,size), 64)) + 63) & ~ (uintptr_t)(63));

кроме того, мне пришлось использовать операторы C вместо встроенных неоновых, поскольку они требуют регулярных указателей типа данных (в моем случае это было uint32_t *) в противном случае новый встроенный метод выборки было снижения производительности.

мой реальный пример можно найти по адресу https://github.com/rollmeister/veriumMiner/blob/main/algo/scrypt.c в scrypt_core () и его внутренней функции, которые все легко читать. Тяжелая работа выполняется GCC8. Общее улучшение производительности составило 25%.