Я многому научился из превосходных ответов, предоставленных @JamesScriven и @Mystical. Однако их примеры дают лишь скромный импульс - цель этого ответа - представить (я должен признаться, несколько искусственный) пример, где предварительная выборка оказывает большее влияние (примерно на коэффициент 4 на моей машине).
Существует три возможных узких места для современных архитектур: скорость процессора, ширина полосы памяти и задержка памяти. Предварительная выборка сводится к уменьшению задержки доступа к памяти.
В идеальном сценарии, когда задержка соответствует X этапам вычисления, у нас был бы оракул, который сообщал бы нам, к какой памяти мы будем обращаться в X этапах вычисления, будет запущена предварительная выборка этих данных, и она получит только вовремя X шагов вычисления позже.
Для многих алгоритмов мы (почти) в этом идеальном мире. Для простого цикла for легко предсказать, какие данные понадобятся через X шагов. Выполнение не по порядку и другие аппаратные уловки делают здесь очень хорошую работу, почти полностью скрывая задержку.
Вот причина такого незначительного улучшения для примера @ Mystical: предварительный сборщик уже довольно хорош - просто не так много возможностей для улучшения. Задача также связана с памятью, поэтому, вероятно, осталось немного ширины полосы - это может стать ограничивающим фактором. В лучшем случае я видел улучшение на моей машине примерно на 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
}
}
Некоторые замечания:
- данные подготовлены таким образом, что оракул всегда прав.
- может быть, что удивительно, чем меньше нагрузка на процессор, тем больше ускорение: мы можем почти полностью скрыть задержку, таким образом ускорение составляет
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";
}
}