title: Thrust: sort_by_key with zip_iterator performance
body: <p><strong>Problem</strong></p>
  
  <p>I am using <code>sort_by_key</code> with the values being passed using a <code>zip_iterator</code>. This <code>sort_by_key</code> is called many times, and after a certain iteration it becomes 10x <strong>slower</strong>! What is the cause of this <strong>drop in performance</strong>?</p>
  
  <p><strong>Symptom</strong></p>
  
  <p>I am sorting 3 vectors using <code>sort_by_key</code>, one of them acts as the key vector:</p>
  
  <pre><code>struct Segment
  {
    int v[2];
  };
  
  thrust::device_vector&lt;int&gt; keyVec;
  thrust::device_vector&lt;int&gt; valVec;
  thrust::device_vector&lt;Segment&gt; segVec;
  
  // ... code which fills these vectors ...
  
  thrust::sort_by_key( keyVec.begin(), keyVec.end(),
                       make_zip_iterator( make_tuple( valVec.begin(), segVec.begin() ) ) );
  </code></pre>
  
  <p>The size of the vector is usually about 4 million. In the initial 2 times it is called, the <code>sort_by_key</code> takes 0.04s, in loop 3 it takes 0.1s and then degrades further to 0.3s for the rest of the loops. Thus, we see a 10x degradation in performance.</p>
  
  <p><strong>Extra Information</strong></p>
  
  <p>To ensure that the only factor of degradation was <code>sort_by_key</code>, I replaced the above with manual sorting using a handwritten kernel:</p>
  
  <pre><code>thrust::device_vector&lt;int&gt; indexVec( keyVec.size() );
  thrust::sequence( indexVec.begin(), indexVec.end() );
  
  // Sort the keys and indexes
  thrust::sort_by_key( keyVec.begin(), keyVec.end(), indexVec.begin() );
  
  thrust::device_vector&lt;int&gt; valVec2( keyVec.size() );
  thrust::device_vector&lt;Segment&gt; segVec2( keyVec.size() );
  
  // Use index array and move vectors to destination
  moveKernel&lt;&lt;&lt; x, y &gt;&gt;&gt;(
    toRawPtr( indexVec ),
    indexVec.size(),
    toRawPtr( valVec ),
    toRawPtr( segVec ),
    toRawPtr( valVec2 ),
    toRawPtr( segVec2 ) );
  
  // Swap back into original vectors
  valVec.swap( valVec2 );
  segVec.swap( segVec2 );
  </code></pre>
  
  <p>This handwritten sort takes 0.03s and this performance is consistent across all iterations, unlike the performance drop seen with sort_by_key and zip_iterator.</p>