StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here's an actual piece of code that I've pulled out of a larger project. (Sorry, it's the shortest one I can find that had a noticable speedup from prefetching.) This code performs a very large data transpose.</p> <p>This example uses the SSE prefetch instructions, which may be the same as the one that GCC emits.</p> <p>To run this example, you will need to compile this for x64 and have more than 4GB of memory. You can run it with a smaller datasize, but it will be too fast to time.</p> <pre><code>#include <iostream> using std::cout; using std::endl; #include <emmintrin.h> #include <malloc.h> #include <time.h> #include <string.h> #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"); } </code></pre> <p>When I run it with ENABLE_PREFETCH enabled, this is the output:</p> <pre><code>bytes = 4294967296 Starting Data Transpose... Done Time: 0.725 seconds Press any key to continue . . . </code></pre> <p>When I run it with ENABLE_PREFETCH disabled, this is the output:</p> <pre><code>bytes = 4294967296 Starting Data Transpose... Done Time: 0.822 seconds Press any key to continue . . . </code></pre> <p>So there's a 13% speedup from prefetching.</p> <p>EDIT:</p> <p>Here's some more results:</p> <pre><code>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 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload