title: speed of references in C++
body: <p>I have been working on a project and trying to find the source of a large slowdown in execution time and have narrowed it down to a single method which I have managed to optimise out of the logic. The problem is that my solution involves using a reference which makes another section of the code run quite slowly... The question I'd like answered is why the inner loop takes so much longer to evaluate when the map is a reference as opposed to a local variable?</p>
  
  <p>Here's the old way prior to optimisation:</p>
  
  <pre><code>// old method: create an empty map, populate it
  // and then assign it back to the path object later
  map&lt;int,float&gt; screenline_usage; 
  
  for (int i=0; i&lt;numCandidates; ++i)
  {
    // timing starts here. 
    map&lt;int, float&gt;&amp; my_screenline_usage =
      path-&gt;get_combined_screenline_usage(legnr, stop_id);
    map&lt;int, float&gt;::iterator it = my_screenline_usage.begin(); 
    for (; it != my_screenline_usage.end(); ++it) 
      screenline_usage[it-&gt;first] += usage * it-&gt;second; 
    // timing ends here, this block evaluated 4 million times for overall execution time of ~12 seconds
  }
  
  // This function call is evaluated 400k times for an overall execution time of ~126 seconds
  path-&gt;set_zone_screenline_usage(access_mode, zone_id, screenline_usage); 
  
  // TOTAL EXECUTION TIME: 138 seconds. 
  </code></pre>
  
  <p>New way after optimisation:</p>
  
  <pre><code>// new method: get a reference to internal path mapping and populate it
  map&lt;int, float&gt;&amp; screenline_usage =
    path-&gt;get_zone_screenline_usage(access_mode, zone_id);
  screenline_usage.clear();
  
  for (int i=0; i&lt;numCandidates; ++i)
  {
    // timing starts here
    map&lt;int, float&gt;&amp; my_screenline_usage =
      path-&gt;get_combined_screenline_usage(legnr, stop_id);
    map&lt;int, float&gt;::iterator it = my_screenline_usage.begin(); 
    for (; it != my_screenline_usage.end(); ++it) 
      screenline_usage[it-&gt;first] += usage * it-&gt;second; 
    // timing ends here, this block evaluated 4 million times for overall execution time of ~76 seconds
  }
  
  // New method... no need to assign back to path object (0 seconds execution :)
  // TOTAL EXECUTION TIME: 76 seconds (62 second time saving) ... but should be able to do it in just 12 seconds if the use of reference didn't add so much time :(
  </code></pre>
  
  <p>Here are the pertinent subroutines called from that code:</p>
  
  <pre><code>// This is the really slow routine, due to the copy assignment used. 
  void set_zone_screenline_usage(int access_mode, int zone_id,
    map&lt;int,float&gt;&amp; screenline_usage)
  {
    m_container[access_mode][zone_id] = screenline_usage; 
  }
  
  map&lt;int,float&gt;&amp; get_zone_screenline_usage(int access_mode, int zone_id)
  {
    return m_container[access_mode][zone_id]; 
  }
  </code></pre>
  
  <p>NOTES: Timing information is for a single run in which the above code is evaluated approximately 400k times. The timing is done using some classes that I built to access the RDTSC time stamp counter (yes i know TSC means time stamp counter), the average value of numCandidates is 10 and the average number of elements put into the screenline_usage map is 25.</p>
  
  <hr>
  
  <p>UPDATE: Firstly thanks to everyone who has gotten involved here. I think that in the end this had nothing to do c++ references at all and had more to do with cache consistency. I have replaced the optimised code above with a vector&amp; and a hash function implemented as a member variable map</p>
  
  <pre><code>// newest method: get a reference to internal path mapping (as vector) and populate it 
  // map&lt;int,int&gt; m_linkNum_to_SlNum declared in header and populated in constructor. 
  vector&lt;float&gt;&amp; screenline_usage = path-&gt;get_zone_screenline_usage(access_mode, zone_id);
  
  for (int i=0; i&lt;numCandidates; ++i)
  {
    // timing starts here
    map&lt;int, float&gt;&amp; my_screenline_usage =
      path-&gt;get_combined_screenline_usage(legnr, stop_id);
    map&lt;int, float&gt;::iterator it = my_screenline_usage.begin(); 
    for (; it != my_screenline_usage.end(); ++it) 
      screenline_usage[m_linkNum_to_SlNum[it-&gt;first]] += usage * it-&gt;second; 
    // timing ends here, this block evaluated 4 million times for overall execution time of ~9 seconds
  }
  
  // Newest method... again no need to assign back to path object (0 seconds execution :)
  // TOTAL EXECUTION TIME: just 9 seconds (129 second time saving) ... this is even better than using a locally constructed map which took 12 seconds in the inner loop :)
  </code></pre>
  
  <p>It seems to me here that, given that the vector isn't local but is a contiguous block of memory and that the hashing function (m_linkNum_to_SlNum) is a local member variable, this approach leads to code/data that is able to fit into cache without having to go out to main memory for data resulting in the significant speed up. Other conclusions given these findings are greatly appreciated. </p>