Databases
StackOverflow2013
Postsdbo
POWhat is the Cost of an L1 Cache Miss?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhat is the Cost of an L1 Cache Miss?
    primarykey
    data
    text
    <p><strong>Edit</strong>: For reference purposes (if anyone stumbles across this question), Igor Ostrovsky wrote a <a href="http://igoro.com/archive/gallery-of-processor-cache-effects/" rel="noreferrer">great post</a> about cache misses. It discusses several different issues and shows example numbers. <strong>End Edit</strong></p> <p>I did some testing <code>&lt;long story goes here&gt;</code> and am wondering if a performance difference is due to memory cache misses. The following code demonstrates the issue and boils it down to the critical timing portion. The following code has a couple of loops that visit memory in random order and then in ascending address order. </p> <p>I ran it on an XP machine (compiled with VS2005: cl /O2) and on a Linux box (gcc –Os). Both produced similar times. These times are in milliseconds. I believe all loops are running and are not optimized out (otherwise it would run “instantly”). </p> <pre> *** Testing 20000 nodes Total Ordered Time: 888.822899 Total Random Time: 2155.846268 </pre> <p>Do these numbers make sense? Is the difference primarily due to L1 cache misses or is something else going on as well? There are 20,000^2 memory accesses and if every one were a cache miss, that is about 3.2 nanoseconds per miss. The XP (P4) machine I tested on is 3.2GHz and I suspect (but don’t know) has a 32KB L1 cache and 512KB L2. With 20,000 entries (80KB), I assume there is not a significant number of L2 misses. So this would be <code>(3.2*10^9 cycles/second) * 3.2*10^-9 seconds/miss) = 10.1 cycles/miss</code>. That seems high to me. Maybe it’s not, or maybe my math is bad. I tried measuring cache misses with VTune, but I got a BSOD. And now I can’t get it to connect to the license server (grrrr). </p> <pre><code>typedef struct stItem { long lData; //char acPad[20]; } LIST_NODE; #if defined( WIN32 ) void StartTimer( LONGLONG *pt1 ) { QueryPerformanceCounter( (LARGE_INTEGER*)pt1 ); } void StopTimer( LONGLONG t1, double *pdMS ) { LONGLONG t2, llFreq; QueryPerformanceCounter( (LARGE_INTEGER*)&amp;t2 ); QueryPerformanceFrequency( (LARGE_INTEGER*)&amp;llFreq ); *pdMS = ((double)( t2 - t1 ) / (double)llFreq) * 1000.0; } #else // doesn't need 64-bit integer in this case void StartTimer( LONGLONG *pt1 ) { // Just use clock(), this test doesn't need higher resolution *pt1 = clock(); } void StopTimer( LONGLONG t1, double *pdMS ) { LONGLONG t2 = clock(); *pdMS = (double)( t2 - t1 ) / ( CLOCKS_PER_SEC / 1000 ); } #endif long longrand() { #if defined( WIN32 ) // Stupid cheesy way to make sure it is not just a 16-bit rand value return ( rand() &lt;&lt; 16 ) | rand(); #else return rand(); #endif } // get random value in the given range int randint( int m, int n ) { int ret = longrand() % ( n - m + 1 ); return ret + m; } // I think I got this out of Programming Pearls (Bentley). void ShuffleArray ( long *plShuffle, // (O) return array of "randomly" ordered integers long lNumItems // (I) length of array ) { long i; long j; long t; for ( i = 0; i &lt; lNumItems; i++ ) plShuffle[i] = i; for ( i = 0; i &lt; lNumItems; i++ ) { j = randint( i, lNumItems - 1 ); t = plShuffle[i]; plShuffle[i] = plShuffle[j]; plShuffle[j] = t; } } int main( int argc, char* argv[] ) { long *plDataValues; LIST_NODE *pstNodes; long lNumItems = 20000; long i, j; LONGLONG t1; // for timing double dms; if ( argc &gt; 1 &amp;&amp; atoi(argv[1]) &gt; 0 ) lNumItems = atoi( argv[1] ); printf( "\n\n*** Testing %u nodes\n", lNumItems ); srand( (unsigned int)time( 0 )); // allocate the nodes as one single chunk of memory pstNodes = (LIST_NODE*)malloc( lNumItems * sizeof( LIST_NODE )); assert( pstNodes != NULL ); // Create an array that gives the access order for the nodes plDataValues = (long*)malloc( lNumItems * sizeof( long )); assert( plDataValues != NULL ); // Access the data in order for ( i = 0; i &lt; lNumItems; i++ ) plDataValues[i] = i; StartTimer( &amp;t1 ); // Loop through and access the memory a bunch of times for ( j = 0; j &lt; lNumItems; j++ ) { for ( i = 0; i &lt; lNumItems; i++ ) { pstNodes[plDataValues[i]].lData = i * j; } } StopTimer( t1, &amp;dms ); printf( "Total Ordered Time: %f\n", dms ); // now access the array positions in a "random" order ShuffleArray( plDataValues, lNumItems ); StartTimer( &amp;t1 ); for ( j = 0; j &lt; lNumItems; j++ ) { for ( i = 0; i &lt; lNumItems; i++ ) { pstNodes[plDataValues[i]].lData = i * j; } } StopTimer( t1, &amp;dms ); printf( "Total Random Time: %f\n", dms ); } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMark Wilkins
    1. USMark Wilkins
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWhat is the Cost of an L1 Cache Miss?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POWhat is the Cost of an L1 Cache Miss?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POWhat is the Cost of an L1 Cache Miss?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COand your question is.... ?
      singulars
      1. POWhat is the Cost of an L1 Cache Miss?
      1. USJavier
    2. COHis question is: "Do these numbers make sense?"
      singulars
      1. POWhat is the Cost of an L1 Cache Miss?
      1. USTim Sylvester
    3. COSorry - I kind of buried the question in too much text. But yes, the question is if the numbers make sense. Are 10 cycles for an L1 cache miss about right?
      singulars
      1. POWhat is the Cost of an L1 Cache Miss?
      1. USMark Wilkins
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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