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

Вот фактический fragment кода, который я вытащил из более крупного проекта. (Извините, это самый короткий, который я могу найти, который имел заметное ускорение от предварительной выборки.) Этот код выполняет очень большую передачу данных.

В этом примере используются инструкции предварительной выборки SSE, которые могут быть такими же, как и GCC.

Для запуска этого примера вам нужно будет скомпилировать это для x64 и иметь более 4 ГБ памяти. Вы можете запустить его с меньшим размером данных, но со временем это будет слишком быстро.

 #include  using std::cout; using std::endl; #include  #include  #include  #include  #define ENABLE_PREFETCH #define f_vector __m128d #define i_ptr size_t inline void swap_block(f_vector *A,f_vector *B,i_ptr L){ // To be super-optimized later. f_vector *stop = A + L; do{ f_vector tmpA = *A; f_vector tmpB = *B; *A++ = tmpB; *B++ = tmpA; }while (A < stop); } void transpose_even(f_vector *T,i_ptr block,i_ptr x){ // Transposes T. // T contains x columns and x rows. // Each unit is of size (block * sizeof(f_vector)) bytes. //Conditions: // - 0 < block // - 1 < x i_ptr row_size = block * x; i_ptr iter_size = row_size + block; // End of entire matrix. f_vector *stop_T = T + row_size * x; f_vector *end = stop_T - row_size; // Iterate each row. f_vector *y_iter = T; do{ // Iterate each column. f_vector *ptr_x = y_iter + block; f_vector *ptr_y = y_iter + row_size; do{ #ifdef ENABLE_PREFETCH _mm_prefetch((char*)(ptr_y + row_size),_MM_HINT_T0); #endif swap_block(ptr_x,ptr_y,block); ptr_x += block; ptr_y += row_size; }while (ptr_y < stop_T); y_iter += iter_size; }while (y_iter < end); } int main(){ i_ptr dimension = 4096; i_ptr block = 16; i_ptr words = block * dimension * dimension; i_ptr bytes = words * sizeof(f_vector); cout << "bytes = " << bytes << endl; // system("pause"); f_vector *T = (f_vector*)_mm_malloc(bytes,16); if (T == NULL){ cout << "Memory Allocation Failure" << endl; system("pause"); exit(1); } memset(T,0,bytes); // Perform in-place data transpose cout << "Starting Data Transpose... "; clock_t start = clock(); transpose_even(T,block,dimension); clock_t end = clock(); cout << "Done" << endl; cout << "Time: " << (double)(end - start) / CLOCKS_PER_SEC << " seconds" << endl; _mm_free(T); system("pause"); } 

Когда я запускаю его с включенным ENABLE_PREFETCH, это вывод:

 bytes = 4294967296 Starting Data Transpose... Done Time: 0.725 seconds Press any key to continue . . . 

Когда я запускаю его с отключенным ENABLE_PREFETCH, это вывод:

 bytes = 4294967296 Starting Data Transpose... Done Time: 0.822 seconds Press any key to continue . . . 

Таким образом, 13% ускоряется от предварительной выборки.

РЕДАКТИРОВАТЬ:

Вот еще несколько результатов:

 Operating System: Windows 7 Professional/Ultimate Compiler: Visual Studio 2010 SP1 Compile Mode: x64 Release Intel Core i7 860 @ 2.8 GHz, 8 GB DDR3 @ 1333 MHz Prefetch : 0.868 No Prefetch: 0.960 Intel Core i7 920 @ 3.5 GHz, 12 GB DDR3 @ 1333 MHz Prefetch : 0.725 No Prefetch: 0.822 Intel Core i7 2600K @ 4.6 GHz, 16 GB DDR3 @ 1333 MHz Prefetch : 0.718 No Prefetch: 0.796 2 x Intel Xeon X5482 @ 3.2 GHz, 64 GB DDR2 @ 800 MHz Prefetch : 2.273 No Prefetch: 2.666 

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

В этом примере я предварительно выбираю два возможных «средних» местоположения следующей итерации цикла в текущей итерации. Один из предварительных примеров, вероятно, никогда не будет использоваться, но другой будет (если это не будет окончательная итерация).

  #include  #include  #include  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 

  $ 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